Sakuyalove 和快速 FFT

给定正整数序列 $a_0 \sim a_n$ 各项的值。

$$b_k=\sum_{i=0}^{k} C_k^i (-1)^i a_i \mod 1000000007$$

$$c_k=\sum_{i=0}^{k} C_k^i (-1)^i b_i \mod 1000000007$$

计算 $c_0 \sim c_n$ 的异或和，$1 \leq n \leq 10^6$，$0 \leq a_i < 10^9 + 7$。

题目链接

数学、组合数学、二项式反演

对于需要数学推导且答案存在较明显规律的题目，打表观察各个项的贡献系数容易找到规律。

$$c_k=\sum_{i=0}^{k} C_k^i (-1)^i b_i = \sum_{i=0}^{k} C_k^i (-1)^i \sum_{j=0}^{i} C_i^j (-1)^j a_j$$

$$= \sum_{i=0}^{k} \sum_{j=0}^{i} C_k^i (-1)^i C_i^j (-1)^j a_j$$

$$= \sum_{i=0}^{k} \sum_{j=0}^{i} C_k^i C_i^j (-1)^{i+j} a_j$$

$$= \sum_{i=0}^{k} \sum_{j=0}^{i} \frac{k!}{i!(k-i)!} \frac{i!}{j!(i-j)!} (-1)^{i+j} a_j$$

$$= \sum_{i=0}^{k} \sum_{j=0}^{i} \frac{k!}{(k-i)! j! (i-j)!} (-1)^{i+j} a_j$$

没活了，观察题解，应该打个表的，以为观察不出来而没有打表，巨大的失误。

分析 $a_j$ 贡献到 $c_k$ 的系数 $mul_j$（$c_k$ 包含了 $mul_j$ 个 $a_j$），考虑 $mul_j$ 的值。

$$mul_j = \sum_{i=j}^{k} C_k^i C_i^j (-1)^{i+j}$$

$$= \sum_{i=0}^{k-j} C_k^{i+j} C_{i+j}^j (-1)^{i+j+j}$$

$$= \sum_{i=0}^{k-j} C_k^{i+j} C_{i+j}^j (-1)^{i}$$

$$= \sum_{i=0}^{k-j} \frac{k!}{(i+j)!(k-i-j)!} \frac{(i+j)!}{j!(i+j-j)!} (-1)^{i}$$

$$= \sum_{i=0}^{k-j} \frac{k!}{(k-i-j)!} \frac{1}{j!i!} (-1)^{i}$$

把内部的 $k!$ 变成 $(k-j)!$，其余部分提到式子外面，再把 $\dfrac{1}{j!}$ 提到式子外面。

$$=\frac{k!}{j!(k-j)!} \sum_{i=0}^{k-j} \frac{(k-j)!}{i! (k-i-j)!} (-1)^{i}$$

$$C_{k}^{j} \sum_{i=0}^{k-j} C_{k-j}^{i} (-1)^{i}$$

二项式反演。

$$C_{k}^{j} \times 0^{k-j} = 0$$

对于 $k-j=0$，即 $k=j$ 的情况二项式反演得到 $0^0$ 不合法，直接根据之前的式子计算得到

$$C_{k}^{j} C_{0}^{0} = C_{k}^{k} = 1$$

也就是说，若 $j \neq k$，那么 $a_j$ 对 $c_k$ 的贡献为 $0$；否则 $a_j$ 对 $c_k$ 的贡献为 $1$，得到结论。

$$c_k = a_k$$

打个表其实就可以观察得到答案了，可以直接打贡献系数表，这样更方便观察。

时间复杂度 $O(n)$。