C. Nastya and a Wardrobe

Nastya 在新年收到了一份礼物——一个魔法衣橱。它的神奇之处在于，每个月末，衣橱中的连衣裙数量会翻倍（即变为月初数量的两倍）。 不幸的是，每次翻倍后，衣橱会以 #cf_span[50%] 的概率吃掉一件连衣裙（如果有的话）。这一过程发生在一年中的每个月，除了最后一个月。 Nastya 目前拥有 #cf_span[x] 件连衣裙，她想知道一年后她拥有的连衣裙的期望数量。Nastya 居住在 Byteland，那里的一年持续 #cf_span[k + 1] 个月。 Nastya 非常忙碌，所以她希望你来解决这个问题。你可是程序员啊。此外，你应该对答案取模 #cf_span[109 + 7]，因为可以很容易看出答案始终是整数。 输入仅一行包含两个整数 #cf_span[x] 和 #cf_span[k]（#cf_span[0 ≤ x, k ≤ 1018]），其中 #cf_span[x] 是初始的连衣裙数量，#cf_span[k + 1] 是 Byteland 一年的月份数。 请在一行中输出一个整数——Nastya 一年后拥有的连衣裙的期望数量，对 #cf_span[109 + 7] 取模。 在第一个例子中，一年只有一个月，因此衣橱不会吃掉任何连衣裙。 在第二个例子中，第一个月结束后，有 #cf_span[50%] 的概率剩下 #cf_span[3] 件连衣裙，有 #cf_span[50%] 的概率剩下 #cf_span[4] 件连衣裙。因此，年末时有 #cf_span[50%] 的概率有 #cf_span[6] 件连衣裙，有 #cf_span[50%] 的概率有 #cf_span[8] 件连衣裙。因此该测试用例的答案为 #cf_span[(6 + 8) / 2 = 7]。 ## Input 仅一行包含两个整数 #cf_span[x] 和 #cf_span[k]（#cf_span[0 ≤ x, k ≤ 1018]），其中 #cf_span[x] 是初始的连衣裙数量，#cf_span[k + 1] 是 Byteland 一年的月份数。 ## Output 仅一行输出一个整数——Nastya 一年后拥有的连衣裙的期望数量，对 #cf_span[109 + 7] 取模。 [samples] ## Note 在第一个例子中，一年只有一个月，因此衣橱不会吃掉任何连衣裙。 在第二个例子中，第一个月结束后，有 #cf_span[50%] 的概率剩下 #cf_span[3] 件连衣裙，有 #cf_span[50%] 的概率剩下 #cf_span[4] 件连衣裙。因此，年末时有 #cf_span[50%] 的概率有 #cf_span[6] 件连衣裙，有 #cf_span[50%] 的概率有 #cf_span[8] 件连衣裙。因此该测试用例的答案为 #cf_span[(6 + 8) / 2 = 7]。

Let $ x $ be the initial number of dresses, and $ k+1 $ be the number of months in the year. Define $ E_n $ as the expected number of dresses at the end of month $ n $, with $ E_0 = x $. For each month $ i = 1, 2, \dots, k $ (i.e., all months except the last), the process is: - Double the dresses: $ 2E_{i-1} $ - Then, with probability $ \frac{1}{2} $, one dress is eaten (if any), so: $$ E_i = \frac{1}{2} \cdot (2E_{i-1}) + \frac{1}{2} \cdot (2E_{i-1} - 1) = 2E_{i-1} - \frac{1}{2} $$ For the final month (month $ k+1 $), there is no eating: $$ E_{k+1} = 2E_k $$ Thus, we have the recurrence: - For $ 1 \leq i \leq k $: $ E_i = 2E_{i-1} - \frac{1}{2} $ - $ E_{k+1} = 2E_k $ We solve the recurrence for $ E_k $, then compute $ E_{k+1} $. --- ### Solving the recurrence: Let $ E_0 = x $ For $ i \geq 1 $, define: $$ E_i = 2E_{i-1} - \frac{1}{2} $$ This is a linear nonhomogeneous recurrence. Solve it: Homogeneous solution: $ E_i^{(h)} = A \cdot 2^i $ Particular solution: Try constant $ C $. Plug in: $$ C = 2C - \frac{1}{2} \Rightarrow C = \frac{1}{2} $$ General solution: $$ E_i = A \cdot 2^i + \frac{1}{2} $$ Use initial condition $ E_0 = x $: $$ x = A \cdot 2^0 + \frac{1}{2} \Rightarrow A = x - \frac{1}{2} $$ Thus: $$ E_i = \left(x - \frac{1}{2}\right) \cdot 2^i + \frac{1}{2} $$ So for $ i = k $: $$ E_k = \left(x - \frac{1}{2}\right) \cdot 2^k + \frac{1}{2} $$ Then: $$ E_{k+1} = 2E_k = 2\left[\left(x - \frac{1}{2}\right) \cdot 2^k + \frac{1}{2}\right] = \left(x - \frac{1}{2}\right) \cdot 2^{k+1} + 1 $$ Simplify: $$ E_{k+1} = x \cdot 2^{k+1} - 2^k + 1 $$ --- ### Final Answer: $$ \boxed{E_{k+1} = x \cdot 2^{k+1} - 2^k + 1} $$ Compute this modulo $ 10^9 + 7 $, with $ x, k \leq 10^{18} $. Note: All operations must be done modulo $ 10^9 + 7 $, using modular exponentiation and modular arithmetic. Thus, the answer is: $$ \left( x \cdot 2^{k+1} - 2^k + 1 \right) \mod (10^9 + 7) $$