特征多项式与常系数线性齐次递推

一般来说，这个东西是用来优化能用矩阵乘法优化的递推式子的。

通常，这种递推式子的特征是在齐次的条件下，转移系数也可以通过递推得到。

对于这样的递推，通常解法为O(NK)O(NK)的递推或者O(k3logn)O(k3log⁡n)的矩阵乘法，但是有些**毒瘤**的出题人~~吉老师~~，会将这样的递推强行出成K≤1000K≤1000，特别，对于常系数线性齐次递推有些出题人甚至会出成2000020000！

这样，就需要引入一个非常有趣~~头秃~~的概念：特征多项式。

首先，我们需要介绍Cayley−HamiltonCayley−Hamilton定理

对于一个nn阶的一个方阵，它的特征多项式为p(λ)=|λE−A|=λn+b1λn−1+b2λn−2+...+bnp(λ)=|λE−A|=λn+b1λn−1+b2λn−2+...+bn

那么显然：p(A)=0p(A)=0

也就是说：AN+b1An−1+...+bn=0AN+b1An−1+...+bn=0，即p(λ)p(λ)为原多项式的化零多项式。

因此，这个特征多项式可以通过高斯消元及拉格朗日插值求出。

求矩阵的特征多项式

一个O(n4)O(n4)的做法

显然，我们得到的特征多项式是一个nn阶多项式，那么只需要知道n+1n+1个点的点值就可以得到了。

也就是，我们把n+1n+1个数代入|λE−A||λE−A|中(作为λλ)，然后暴力高斯消元即可得到一个矩阵的特征多项式。

那么，接下来，只需要拉格朗日插值即可。

这个做法作为一个n4n4的做法其实想要卡掉矩阵乘法是很难的，除非将递推的项数放到101000101000这样的级别，如[BZOJ4162]

那么接下来，我们考虑刚刚的做法能否被优化。

显然，每次n3n3求矩阵行列式太慢了。

一个O(n3)O(n3)的做法

对于这样的矩阵：A=P×B×P−1A=P×B×P−1

称A,BA,B是相似的，也就是说，对于A,BA,B的特征多项式相同。

构造还是很容易的，只需要保留每行与每行之间的关系即可。

对于这样的矩阵，我们称之为上海森堡矩阵。

a1,1a2,10⋮0a1,2a2,2a3,2⋮0a1,3a2,3a3,3⋮0⋯⋯⋯⋱⋯a1,na2,na3,n⋮an,n(a1,1a1,2a1,3⋯a1,na2,1a2,2a2,3⋯a2,n0a3,2a3,3⋯a3,n⋮⋮⋮⋱⋮000⋯an,n)

那么，对于这样的矩阵，求行列式的时间复杂度就降为n2n2了！

然后，总时间复杂度为n3+n2logmn3+n2log⁡m，或者为n3+nlognlogmn3+nlog⁡nlog⁡m（并无卵用），然后对于n3logmn3log⁡m的矩阵乘法构成了鲜明的优势（大雾

显然，其实上面的东西没有那么有用...

但是还是有必要知道的，万一他卡你呢？

常系数线性齐次递推的矩阵的特征多项式

定义：递推式为fi=∑j=1naj×fi−j,i>nfi=∑j=1naj×fi−j,i>n的递推。

讲道理，这个东西才非常有用...

对于所有的常系数线性齐次递推来说，它们的矩阵形态类似，同样，他们的特征多项式也类似...

其实手画一下就可以发现，它们的特征多项式都是p(λ)=λn−a1λn−1−a2λn−2−...−anp(λ)=λn−a1λn−1−a2λn−2−...−an

按照行列式的定义展开式子退一下就得到啦！

特征多项式的使用手册

其实，使用方法很简单啦，就是运用之前得到的特征多项式性质，p(A)=AN+b1An−1+...+bn=0p(A)=AN+b1An−1+...+bn=0

那么，对于这样的式子，就可以做到将所有的AKAK用A0∼AnA0∼An的矩阵线性表达出来了。

Ax+y=Ax×AyAx+y=Ax×Ay

那么Ax=∑i=0nbi×Ai,Ay=∑i=0nci×AiAx=∑i=0nbi×Ai,Ay=∑i=0nci×Ai

也就是：Ax+y=∑i=0n∑j=0nbi×cj×Ai+jAx+y=∑i=0n∑j=0nbi×cj×Ai+j

因为有：p(A)=0p(A)=0也就是说：Ax+y=∑k=02×n(∑i=0min(n,k)bick−i)Akmodp(λ)Ax+y=∑k=02×n(∑i=0min(n,k)bick−i)Akmodp(λ)

然后显然，可以用倍增(其实就是快速幂)上述操作，也就是我们得到了一个n2logmn2log⁡m复杂度的递推。

对于上述暴力操作可以用NTTNTT或FFTFFT优化上述多项式相乘和多项式取模。

也就是说，我们得到了一个nlognlogmnlog⁡nlog⁡m的优秀做法！（拿头写啊

关于答案

Ax=∑i=0nbi×AiAx=∑i=0nbi×Ai

这个式子已经给我们答案了，也就是说，这个矩阵的前nn项加上系数相加即可，但是显然这个东西是n4n4的

如果要求fmfm的话，这个东西只需要用到f0∼fnf0∼fn即可

如果求矩阵的话，还是老老实实的一个一个乘吧...

例题.jpg

求矩阵特征多项式裸题：[BZOJ4162]

常系数线性齐次递推n2logmn2log⁡m裸题：[BZOJ4161]

高难度的东西：[NOI 2017 泳池]

附件

NOI 2017 泳池 题解

对我来说，可能我只能接受k≤2000k≤2000，如果再大就想要打人了...

首先70分的暴力基本雷同[UNR 2 积劳成疾](http://uoj.ac/problem/311)

大概就是推一个f[i][j],s[i][j]f[i][j],s[i][j]即可，[我不想再写一遍了](https://winniechen.cn/?p=152)

剩下的就是可以把这个转移写成矩阵的形式，然后就可以拿到优秀的9090分了。

最后，根据上面的东西，优化一下就可以AC掉这道题了！

原文出处：https://www.cnblogs.com/Winniechen/p/10246295.html