Arcane Behemoths题解

网络赛第二场D题，Arcane Behemoths

题意

一个子序列删除一个数之后， 剩下的所有数字都要增加刚刚删除的数字的值， 计算所有子序列只剩下最后一个数字的时候的值的和

失误

赛时计算这道题的时候犯了些计算上的失误， 作为第k个数会贡献多少次， 每次我算的时候都只是简单模拟枚举两三个数字， 因此得到错误的计算结果， 还有就是组合数学不行

题解

1. 考虑$a_k$为第k个数的贡献为$2^{k-2}$, 特别当k=1, 贡献为1, 可以简单模拟得到, 设为$f_k$
2. 接下来考虑$a_k$一共会贡献多少次, 我们来模拟一下, $a_k$作为第i小的数会贡献多少次:

• $i = 1, \binom{0}{k-1}f_1$
• $i = 2, \binom{1}{k-1}f_2$
• $i = 3, \binom{2}{k-1}f_3$
• $i = k, \binom{k-1}{k-1}f_k$
  所以一共贡献$\sum_{i=1}{k} \binom{i-1}{k-1} f_{i}$

3. 接下来化简
   $$
   \sum_{i=1}^{k}\binom{i-1}{k-1}f_{i}
   =1 + \sum_{i=2}{^k}\binom{i-1}{k-1}2^{i-2} : (因为f_{1}是特值)
   $$

用$j=i-1$
$$
=1 + \frac{1}{2} \sum_{j}{k-1}\binom{j}{k-1}2^{j}
$$

由二项式定理$(1+x)^{n} = \sum_{i=1}^{n}x^{i}$
$$
=1+ \frac{1}{2} \sum_{j}{k-1}\binom{j}{k-1}2^{j}
=1 + (1 + 2)^{k-1}
$$