幂和 题解
System_Error_
·
·
个人记录
免责申明，以下的 k 有多种含义，请读者仔细分辨。
先起手推柿子，把 (i + x)^k 暴力展开，得：
\sum_{i = 0}^n (-1)^{popcnt(i)} \sum_{j = 0}^k i^{k - j} x^j \binom{k}{j} \\
= \sum_{j = 0}^k x_j \binom{k}{j} \sum_{i = 0}^n (-1)^{popcnt(i)} i^{k - j}
我们设 \sum_{i = 0}^n (-1)^{popcnt(i)} i^k 为 ans_{n,k}，那么答案等于 \sum_{j = 0}^k x_j \binom{k}{j} ans_{n,k - j}，我们考虑求出 ans_n 序列。
首先考虑 ans_{n,0} 怎么求，相当于我们要求一个 (-1)^{popcnt(i)} 的前缀和，设为 pre_i，打表容易发现：当 i 为奇数时 pre_i = 0，否则 pre_i = (-1)^{popcnt(i)}。证明如下：
- 首先 pre_{2k - 1} = pre_{2k + 1}，设 (-1)^{popcnt(2k)} = x，则 (-1)^{popcnt(2k+1)} = -x，所以 pre_{2k + 1} = pre_{2k - 1} + x - x = pre_{2k - 1}。由于 pre_1 = 0，所以当 i 为奇数时 pre_i = 0。
- 其次 pre_{2k} = pre_{2k - 1} + (-1)^{popcnt(2k)}，又因为 pre_{2k - 1} = 0，所以 pre_{2k} = (-1)^{popcnt(2k)}。
这样你就会 \Theta(1) 求 pre 了，开始推柿子。
ans_{n,k} = \sum_{i = 0}^n (-1)^{popcnt(i)} i^k \\
= n^k \sum_{i = 0}^n (-1)^{popcnt(i)} - \sum_{i = 0}^n (-1)^{popcnt(i)} (n^k - i^k) \\
= n^k pre_n - \sum_{i = 0}^n (-1)^{popcnt(i)} (n^k - i^k)
考虑计算后面的柿子：
\sum_{i = 0}^n (-1)^{popcnt(i)} (n^k - i^k) \\
= \sum_{i = 0}^{n - 1} pre_i ((i + 1)^k - i^k)
考虑证明（也可以用数形结合简单证明）：
\sum_{i = 0}^{n - 1} pre_i ((i + 1)^k - i^k) \\
= \sum_{i = 0}^{n - 1} \sum_{j = 0}^i (-1)^{popcnt(j)} ((i+1)^k - i^k) \\
= \sum_{j = 0}^{n - 1} (-1)^{popcnt(j)} \sum_{i = j}^{n - 1} (i+1)^k - i^k \\
= \sum_{j = 0}^{n - 1} (-1)^{popcnt(j)} (n^k - j^k)
将 (i+1)^k - i^k 用二项式定理展开：
= \sum_{i = 0}^{n - 1} pre_i \sum_{j = 0}^{k - 1} \binom{k}{j} i^j \\
= \sum_{j = 0}^{k - 1} \binom{k}{j} \sum_{i = 0}^{n - 1} pre_i i^j
考虑计算第二个求和符号及其后面的东西，由于当 i 为奇数时 pre_i = 0，所以可以跳过，而由 popcnt 的性质可得当 i 为偶数时 (-1)^{popcnt(i)} = (-1)^{popcnt(i/2)}。
所以：
\sum_{i = 0}^{n - 1} pre_i i^j \\
= \sum_{i = 0}^{\lfloor \frac{n - 1}{2} \rfloor} pre_{2i} (2i)^j \\
= 2^j \sum_{i = 0}^{\lfloor \frac{n - 1}{2} \rfloor} (-1)^{popcnt(i)}i^j \\
= 2^j ans_{\lfloor \frac{n - 1}{2} \rfloor,j}
代回原式得：
\sum_{i = 0}^{n - 1} (-1)^{popcnt(i)} (n^k - i^k) \\
= \sum_{j = 0}^{k - 1} \binom{k}{j} 2^j ans_{\lfloor \frac{n - 1}{2} \rfloor,j}
由于需要计算的 ans 的第一维只有 \log n 个，所以此时你已经会了 \Theta(k^2 \log n) 做法。
我们将 C_k^j 展开：
\sum_{j = 0}^{k - 1} \frac{k!}{j!(k-j)!} 2^j ans_{\lfloor \frac{n - 1}{2} \rfloor,j} \\
= k! \sum_{j = 0}^{k - 1} \frac{1}{j!(k-j)!} 2^j ans_{\lfloor \frac{n - 1}{2} \rfloor,j} \\
= k!\sum_{j = 0}^{k - 1} \frac{2^j ans_{\lfloor \frac{n - 1}{2} \rfloor,j}}{j!} \times \frac{1}{(k-j)!}
我们设当 k 取 0 \sim K 时上述柿子的答案为 h_k，f_i = \frac{2^i ans_{\lfloor \frac{n - 1}{2} \rfloor,i}}{i!},g_i = \frac{1}{i!}，那么有 h = f * g 再对每个 h_k 减去上述柿子取 j = k 的答案再乘上 k! 即可。其中 * 是卷积，可以用 NTT 快速做。
这样你就可以以 \Theta(k \log k \log n) 的时间复杂度求出 ans_n 序列，代回一开始的式子做一遍就得到答案了。
闲话：没被超级大神 @Zzzcr 爆掉之前还以为这道题有 *3100（