自动搬运

查看原文

来自洛谷，原作者为

	nb_jzy 寄蜉蝣于天地，渺沧海之一粟

搬运于2025-08-24 23:12:34，当前版本为作者最后更新于2025-06-23 16:56:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给你 $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$ 的值。

思路

$t$ 十分的大，这提示需要用类似于快速幂的东西。

观察一次操作的性质，显然可以将其写成矩阵，然后再快速幂就行了，但 $n\le 2^{20}$，复杂度过高。

尝试对式子变形，发现每次操作等价于：

这和异或卷积十分相似。

做法

构造一个函数 $G(x)$，使得只有在 $2^j$ 的位置上为 $1$，其他位置上为 $0$，那原式就变为了：

然后直接用 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。