BZOJ5501: 散步

首先我们不难得出一个矩阵快速幂的做法。不妨设转移矩阵为一个$n*n$的矩阵$A$,那么我们要求的即为$\begin{bmatrix}1  1  …  1\end{bmatrix}*A^T* \begin{bmatrix}1\\1\\…\\1\\\end{bmatrix}$,由$Hamilton-Cayley$定理可知,一个矩阵存在一个$n-1$次特征多项式$A^{n}=c_{1}*A^{n-1}+c_{2}*A^{n-2}+…+c_{n}*A^{0}$。但是直接求矩阵的特征多项式是$N*4$的,在这里并不行。考虑到我们要求一个矩阵乘以$A^T$再乘以一个矩阵,发现这样其实就是在特征多项式两边乘了两个矩阵,这样并不会改变这个$A^{n}$的递推性质,即这递推式依旧成立。现在我们将矩阵转化成了一个数,这样求递推式就可以更快得求了。先通过$N*M$的$DP$预处理出答案前几项,然后我们通过$BM$算法($Berlekamp-Massey$)可以在$N^2$的时间复杂度内求出这个递推式$c_{i}$。求出递推式后,便是一个这样的问题,已知一个数列前$n$项和$n$阶递推式,求次数列的第$t$项。

这个问题可以用倍增+多项式取模完成。即求$x^{T} mod f(x)$,$f(x)$为特征多项式,求出来后乘以数列前$n$项即可(模板题是$BZOJ4162: shlw loves matrix II$)。那么这题就做完了。

时间复杂度$O(N*M+NlogNlogT)$(第一次出题,感觉很有趣。多项式倍增+取模常数较大,原来$T$想放$2^{10000}$,但是跑得超级慢,于是$T$放了$2^{100}$)。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注