题解：P12072 [THOI 2014] 超立方体
nb_jzy
·
·
题解
题意
给你 n=2^m 个数，a_0,a_1,a_2...a_{n-2},a_{n-1}。
一次操作将所有 a_i 改为 b_i=\sum _{\operatorname{popcount}(j \oplus i)=1}a_i。其中 \oplus 表示异或，\operatorname{popcount}(x) 表示 x 的二进制位中 1 的个数。
简单来说，就是将所有二进制位只有一位与 i 不同的那些值求和。
现在需要求出进行 t\le 10^{18} 轮操作之后 a_i 的值。
思路
观察一次操作的性质，显然可以将其写成**矩阵**，然后再快速幂就行了，但 $n\le 2^{20}$，复杂度过高。
尝试对式子变形，发现每次操作等价于：
$$
b_i=\sum_{j=0}^{m-1}a_{i\oplus 2^j}
$$
这和**异或卷积**十分相似。
# 做法
构造一个函数 $G(x)$，使得只有在 $2^j$ 的位置上为 $1$，其他位置上为 $0$，那原式就变为了：
$$
b_i=\sum_{j\oplus k=i}a_j\times G(k)
$$
然后直接用 FWT 求解即可。$t$ 很大，所以先对 $G$ 进行 $t$ 次自卷积，最后再用一遍 IFWT 就行了，时间复杂度 $\mathcal O(n\log t+n\log n)$。
注意，模数不为质数，IFWT 时 $2$ 不一定有逆元，所以需要使用一个小技巧：$a\div b\mod c=(a\mod bc) \div b$。
即先对于 $k\times n$ 取模，最后再除以 $n$。
# 优化
这样实现的常数比较大，可以进行一些优化。
注意到 $G$ 有值的地方很少，打表后发现 FWT 后值域十分稀疏。而快速幂实际上算的就是 $G^t(i)$，于是可以先预处理所有出现的 $G(i)$ 的 $G^t(i)$，然后再直接调用就行了。
优化比较显著，从 3.72s 优化到了 547ms。