原问题

给定一个数列前k项，并给出其k阶递推关系$h_n={\sum }_{i=1}^k{a}_i{h}_{n-i}$，求$h_n$。

矩阵快速幂

大家都会矩阵快速幂的方法。

构造一个转移矩阵$A$

$$A=\left[\begin{array}{ccccc}{a}_1& a_2& a_3& \cdots & a_k\\ 1& 0& 0& \cdots & 0\\ 0& 1& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 0\end{array}\right]$$

用前k项构造初始矩阵，也是一个k维向量$H_1$

$$H_1=\left(\begin{array}{c}{h}_k\\ h_{k-1}\\ h_{k-2}\\ ⋮\\ h_1\end{array}\right)$$

即可得$A^{n-1}{H}_1=H_n$。

时间复杂度$O(k^3\log n)$。

k如果比较大怎么办？我会卡常，jki玄学卡常，wys优化

多项式取模优化

前置知识

1.矩阵的特征值

对于矩阵$A$和一个n维向量$x$，如果有一个值$\lambda$满足$Ax=\lambda x$，则我们称$\lambda$为矩阵$A$的特征值。

2.矩阵的特征多项式

简单的缩好像就是特征方程再移项？

我们把之前的那个方程移项得$(A-\lambda E)x=0$，显然若x有非零解，那么需要满足

$$|A-\lambda E|=\left|\begin{array}{ccccc}{a}_{11}-\lambda & a_{12}& a_{13}& \cdots & a_{1k}\\ a_{21}& a_{22}-\lambda & a_{23}& \cdots & a_{2k}\\ a_{31}& a_{32}& a_{33}-\lambda & \cdots & a_{3k}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_{k1}& a_{k2}& a_{k3}& \cdots & a_{kk}-\lambda \end{array}\right|=0$$

这其实是一个一元k阶方程，即特征方程。我们记$f_A(x)=|A-xE|$，称矩阵A的特征多项式。

3.Cayley-Hamilton定理

$f_A(A)=0$。具体的证明可以看wikipedia，因为我也不会。

~~为了方便记忆，~~有一个著名的伪证:$f_A(A)=|A-AE|=0$。

4.拉普拉斯展开

对于行列式A，我们定义它的关于第i行第j列的余子式$M_{ij}$为原行列式删除第i行和第j列之后剩下的k-1阶行列式。

拉普拉斯展开是一个有关行列式的值的等式，按第i行展开得到如下等式

$$|A|=\sum _{j=1}^k(-1{)}^{j-1}{a}_{ij}|M_{ij}|$$

类似的，我们也可以对第j列展开

$$|A|=\sum _{i=1}^k(-1{)}^i{a}_{ij}|M_{ij}|$$

5.多项式取模

$f(x)=g(x)p(x)+r(x)$

它们满足$deg(r)<deg(g)<deg(f)$。

优化

我们知道如果给矩阵的某一行全部元素全部变为相反数，那么矩阵的行列式也会变成相反数，那么我们可以做这样一个操作，并记作$g$：

$$g(x)=(-1{)}^k{f}_A(x)=\left|\begin{array}{ccccc}x-a_1& -a_2& -a_3& \cdots & -a_k\\ -1& x& 0& \cdots & 0\\ 0& -1& x& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & x\end{array}\right|$$

为了求$g(x)$的表达式，我们可以按照第一行对其进行拉普拉斯展开：

$$g(x)=x^k-\sum _{i=1}^k{a}_i{x}^{k-i}$$

由于我们要求的东西就是$A^n$，那不妨构造一个这样的式子：

$$x^n=g(x)p(x)+r(x)$$

令$x=A$则有$A^n=g(A)p(A)+r(A)$

由之前的Cayley-Hamilton定理我们知道$g(A)=(-1{)}^k{f}_A(A)=0$。那么我们就得到了$A^n=r(A)$，而$deg(r)<k$。为了方便，我们不妨看作$deg(r)=k-1$。

那么我们怎么求$r(A)$呢？原来的取模板子显然不可取，因为n可能很大，数组都开不下。考虑用倍增，即

$x^2\mathrm{m}\mathrm{o}\mathrm{d}g(x)=(x^1\mathrm{m}\mathrm{o}\mathrm{d}g(x){)}^2\mathrm{m}\mathrm{o}\mathrm{d}g(x),x^4\mathrm{m}\mathrm{o}\mathrm{d}g(x)=(x^2\mathrm{m}\mathrm{o}\mathrm{d}g(x){)}^2\mathrm{m}\mathrm{o}\mathrm{d}g(x)$

考虑用快速幂实现，这需要做两个操作：

• 1.多项式乘法
  • 暴力$O(k^2)$
  • FFT$O(k\log k)$
• 2.多项式取模
  • 暴力$O(k^2)$，跳过中间的零项$O(kt)$
  • FFT$O(k\log k)$，限制多，有时用不了？

你问我怎么暴力取模？当然是模拟大除法啊

至此，我们已经得到了$A^n={\sum }_{i=0}^{k-1}{r}_i{A}^i$，再在两边乘上初始矩阵$H_1$即得

$$H_{n+1}=\sum _{i=0}^{k-1}{r}_i{H}_{i+1}$$

由于$H$是一个n维向量，而且中间涉及到的数乘及加法的运算，对于每一行是独立的，直接把第k行上的运算提出来就得到

$$h_{n+1}=\sum _{i=0}^{k-1}{r}_i{h}_{i+1}$$

时间复杂度常数较大的$O(k^2\log n)$，或者常数更大的$O(k\log k\log n)$，fft的话要注意精度问题，mod较大就可能有问题。

相关题目

看了这么久，然而貌似应用不多？

bzoj4161

hdu4914

NOI2017泳池

最后

以上就是明理小海豚为你收集整理的矩阵快速幂的多项式取模优化原问题矩阵快速幂多项式取模优化相关题目的全部内容，希望文章能够帮你解决矩阵快速幂的多项式取模优化原问题矩阵快速幂多项式取模优化相关题目所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。