转置原理
feecle6418
·
·
个人记录
有 n 个数，构成可重集 A，大小 [0,2^m-1]。
对于每个 x\in [0,2^m-1] 求所有异或和为 x 的 A 的子集 B 的贡献和，定义贡献为 a_{|B|}，a 是输入的数组（原题中 a_i=\binom{2i}{B}）。
n\le 10^6,m\le 20
FWT 后，易得要解决如下问题：
- 对每个 k 求 \sum a_i[x^i](1-x)^{n-k}(1+x)^k。
这一看就很转置原理，转一下
- 对每个 k 求 [x^k]\sum a_i(1-x)^{n-i}(1+x)^i。
这是容易的，设 t=1+x，先求出 F(t)=\sum a_t(2-t)^{n-i}t^i，
\sum a_t(2-t)^{n-i}t^i=\sum a_it^i\sum_{0\le j\le n-i}2^j(-1)^{n-i-j}t^{n-i-j}\binom{n-i}j
=\sum_i a_i\sum_{0\le j\le n-i}2^j(-1)^{n-i-j}t^{n-j}\binom{n-i}j
=\sum_j t^j 2^{n-j}\sum_i a_i(-1)^{j-i}\binom{n-i}{n-j}
=\sum_j t^j \dfrac{2^{n-j}}{(n-j)!}\sum_i (n-i)!a_i\dfrac{(-1)^{j-i}}{(j-i)!}
是先点乘上 (n-i)!，卷积上某个多项式，再点乘上 2^{n-i}/(n-i)!。
第二步，从 F(t) 变成 F(x)。
\sum a_i(1+x)^i=\sum a_i\sum_{j\le i}\binom ijx^j
=\sum_j x^j\sum_{i}a_i\binom{i}{j}
=\sum_j x^j/j!\sum a_ii!/((i-j)!)
也是类似形式：先点乘 i!，再差卷积上 x^i/i!，再点乘 1/j!。
综上，我们得到原题解法：
- 点乘 1/j!。
- 正常卷积 x^i/i!。
- 点乘 2^{n-i}i!/(n-i)!。
- 差卷积 (-1)^ix^i/i!。
- 点乘 (n-i)!。
复杂度 O(n\log n+2^mm)。常数非常小。