单位根反演 + 任意长度 DFT + MTT.
考虑某个 $t$ 的答案,记作 $b_t$ ,枚举白兔实际跳了 $i$ 步,得到
$$
b_t=\sum_{i=0}^L [i\bmod k=t] \binom L i A^i_{x,y}\\
=\sum_{i=0}^L [k|(i-t)]\binom L i (A^i)_{x,y}
$$
其中 $A$ 是由读入给定的 $3\times 3$ 的转移矩阵.
考虑单位根反演,继续化简,
$$
b_t=\sum_{i=0}^L \frac 1 k\sum_{j=0}^{k-1}\omega_k^{j(i-t)} \binom L i A^i_{x,y}\\
=\frac 1 k\sum_{j=0}^{k-1} \omega_k^{-jt}\sum_{i=0}^L \omega_k^{ij} A^i_{x,y} \\
=\frac 1 k\sum_{j=0}^{k-1} \omega_k^{-jt}(\omega_k^j A + I)^L_{x,y}
$$
题目保证了 $k|(p-1)$ ,所以在模 $p$ 意义下 $\omega_k =g^{\frac{p-1} k}$ ,其中 $g$ 为 $p$ 的原根.
记 $a_j=((\omega_k^j A + I)^L)_{x,y}$ ,这可以用矩阵快速幂在 $O(n^3k\log L)$ 的时间内将 $k$ 个 $a_j$ 全部求出.
$$
b_t=\frac 1 k\sum_{j=0}^{k-1}(\omega_k^{-j})^t a_j
$$
如果 $k$ 是 $2$ 的幂次,直接用 FFT 对 $a$ 做一次长度为 $k$ 的 IDFT 即可将 $b$ 求出.
如果不保证 $k$ 是 $2$ 的幂次,就需要用到一个叫 Bluestein’s Algorithm 的算法,它可以解决任意长度的 DFT.
由组合意义知 $\binom {j+t} 2=\binom j 2 + \binom t 2 +jt$ ,于是可以把 $jt$ 拆成仅和 $j,t,j+t$ 有关的几项.
原式可以化为
$$
b_t=\frac 1 k\sum_{j=0}^{k-1} \omega_k^{\binom t 2} \cdot \omega_k^{\binom j 2}\cdot \omega_k^{-\binom{j+t}{2}} a_j \\
b_t=\frac 1 k \omega_k^{\binom t 2}\sum_{j=0}^{k-1} \omega_k^{-\binom{j+t}{2}}(a_j\cdot \omega_k^{\binom j 2})
$$
记 $f_i=\omega_k^{-\binom i 2},g_i=a_i\cdot \omega_k^{\binom i 2}$ ,则
$$
b_t=\frac 1 k \omega_k^{\binom t 2}\sum_{j=0}^{k-1} g_j\cdot f_{j+t}
$$
后面已经差不多是一个卷积了,把 $g$ 翻转一下,就能得到
$$
b_t=\frac 1 k \omega_k^{\binom t 2}\sum_{j=0}^{k-1} g^R_{k-1-j}\cdot f_{j+t} \\
b_t=\frac 1 k \omega_k^{\binom t 2}(
g^R\otimes f)_{t+k-1}
$$
用 MTT 求出 $g^R$ 与 $f$ 的卷积即可.
时间复杂度 $O(n^3k\log L+k\log k)$ .
1 | //%std |