题解

思路

令长度为 $n$ 的核函数

一次能量变化正是异或卷积：$e_i=c*_{\mathrm{xor}}e_{i-1}$。因此

Walsh-Hadamard 变换 $H$ 把异或卷积变为逐点乘法，而且 $H^2=nI$。若模数 $p$ 为奇素数，可以乘 $n^{-1}$ 完成逆变换；但本题的 $p$ 可以是任意合数，甚至是二的幂，逆元可能不存在。

关键处理是把全部变换放在模数 $pn$ 下进行。第二次 Hadamard 变换后的每个真实整数都含因子 $n$。模 $pn$ 的剩余类也仍能整除 $n$，整除后恰好保留模 $p$ 的答案。因此无需任何逆元。

做法

子任务 1

按题意重复 $t$ 次，每次枚举 $u,v$ 直接计算下一时刻。时间复杂度为 $O(tn^2)$。

子任务 2

在异或卷积环中对核 $c$ 做二进制快速幂：卷积单位元仅在下标 $0$ 处为 $1$。每次卷积直接枚举两个下标，最后再与 $e_0$ 卷积。时间复杂度为 $O(n^2\log t)$。

满分算法

取扩大模数 $P=pn$：

1. 构造 $c[x]=b_{\operatorname{popcount}(x)}$；
2. 分别对 $c$ 与 $e_0$ 做 Hadamard 变换；
3. 对每个频率点，把 $H(e_0)$ 乘上 $H(c)^t$；
4. 再做一次 Hadamard 变换；
5. 每项先除以 $n$，再对 $p$ 取模。

由于 $c$ 只依赖下标的置位数，它的变换值也只依赖频率下标的置位数，因此只需计算 $m+1$ 次快速幂。独立实现还可用 Krawtchouk 多项式

直接计算置位数为 $s$ 的特征值，以交叉核验 FWT 构造。

所有模乘使用 128 位中间值，因为 $P$ 最大约为 $10^{15}$。

正确性证明

核 $c[u\operatorname{xor}v]$ 与题目转移系数完全相同，所以一次转移等价于异或卷积。卷积的结合律推出时刻 $t$ 的向量为 $c^{*t}*e_0$。

Hadamard 变换满足 $H(a*_{\mathrm{xor}}b)=H(a)\cdot H(b)$，故频域逐点乘上 $H(c)^t$ 后得到 $H(e_t)$。再次变换得到 $H^2(e_t)=ne_t$。

设某个真实整数分量为 $nq$。在模 $pn$ 下得到的标准剩余数为 $n(q\bmod p)$，因此它仍被 $n$ 整除，商恰为 $q\bmod p$。算法最后的整除步骤由此合法，即使 $n$ 在模 $p$ 下没有逆元也不受影响。

因此算法输出的每一项都等于题目定义的 $e_t[i]\bmod p$。

复杂度分析

满分算法时间复杂度为 $O(nm+m\log t)$，空间复杂度为 $O(n)$，其中 $n=2^m$。