题解：P10664 BZOJ3328 PYXFIB

· · 题解

单位根即是 x^n=1 在复平面上的 n 个根，记为 \omega_n^i。对于 n 次单位根，除了 1 以外的 \omega 都会满足 1+w^2+\cdots+w^{n-1}=0。

首先会有最重要的式子：

[k|n]=\frac{1}{k}\sum_{i=0}^{k-1}\omega_k^{ni}

如果 n \bmod k\neq 0，则会有等比公式求和 \frac{1}{k}\frac{w_k^{nk}-1}{w_k^n-1}，而又 w_k^{nk}=1,w_k^n\neq 1 故成立。对于 n\bmod k=0，则有 w_k^{ni}=1 则成立。

对于一个 m 次多项式 f(x)=a_0+a_1x+\cdots+a_mx^m 求它 k 倍数项的系数之和：

a_0+a_k+a_{2k}+\cdots=\sum_{i=0}^m[k|i]a_i =\sum_{i=0}^ma_i\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{ij} =\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^ma_i(w_k^j)^i =\frac{1}{k}\sum_{j=0}^{k-1}f(w_k^j)

对于一个质数 p，原根 g 满足 1,g,g^2,\cdots,g^{p-2} 互不相同。对 p-1 分解为 \prod_{i=1}^t p_i^{\alpha_i}，则只要对所有的 1\leq i\leq t 都有 g^{\frac{p-1}{p_i}}\not\equiv 1\pmod p 则为原根。这样就可以利用原根代替单位根（还有要求 p-1 是 n 的倍数）：

w_n^1=g^\frac{p-1}{n}

那么对于本题，这里就是注意一下这个多项式也是可以用矩阵形式的。那么对于 M=\begin{bmatrix} 1 & 1 \\ 1 & 0 \\\end{bmatrix}，则多项式可以依据二项式定理写成：

f(j)=(I+\omega^jM)^n

其中 I 指单位矩阵。然后就矩阵快速幂一下模拟上面的单位根反演式子即可。