题解 P5320 【[BJOI2019]勘破神机】

扩域以及怎么用特征根优化到 $\Theta(k^2\log r)$ 的部分相信 rqy 已经讲得很清楚了，再此不予赘述，但是这道题可以进一步优化。 事情的经过其实是这样的……偶然看到了 cz_xuyixuan 用 BM 直接给[莽过去](https://loj.ac/submission/783025)了，感到有点诧异，于是就冷静了一下，发现这道题的特征根有很强的性质： - 对于 $T=2$ 的部分，因为递推式是 $x^2-x-1$，所以两个特征根的乘积是 $-1$。 - 对于 $T=3$ 的部分，因为递推式是 $x^2-4x+1$，所以两个特征根的乘积是 $1$。 所以，我们原以为 $\alpha^i \beta^j$ 总共有 $\Theta(k^2)$ 种，但是在此题中只有 $\Theta(k)$ 种…… 那么如何做到更快就呼之欲出了，我们只需要算出每个 $\alpha^i\beta^j$ 的系数就行了。 - 对于 $T=3$ 的情况，因为 $\alpha\beta = 1$，我们欲求 $\displaystyle\sum_n \binom{\lambda \alpha^n + \mu \alpha^{-n}} k$ 表为 $\displaystyle\sum_{-k\le j\le k} \nu _j \alpha^{jn}$ 的系数 $\nu_j$，只需计算 $\displaystyle\frac1{k!}\prod_{i=0}^{k-1} (\lambda x - i + \mu x^{-1})$ 的系数表示，可以 $O(k \log^2 k)$。 - 对于 $T=2$ 的情况，因为 $\alpha \beta = -1$，我们所求可以表为 $\displaystyle \sum_{-k \le j\le k} \xi_j \alpha^{jn} + \zeta _j (-\alpha)^{jn}$，只需计算 $\displaystyle\frac1{k!}\prod_{i=0}^{k-1} (\lambda x - i + \mu x^{-1}t) \bmod (t^2-1)$ 的系数表示，其中 $[t^0]$ 对应 $\xi$ 数列，$[t^1]$ 对应 $\zeta$ 数列，可以 $O(k\log^2 k)$。 由此，可以在 $O(k\log^2 k + k\log r)$ 时间内计算出。