特征多项式与常系数线性齐次递推 一般来说，这个东西是用来优化能用矩阵乘法优化的递推式子的。 通常，这种递推式子的特征是在齐次的条件下，转移系数也可以通过递推得到。 对于这样的递推，通常解法为O(NK)的递推或者O(k3logn)的矩阵乘法，但是有些**毒瘤**的出题人~~吉老师~~，会将这样的递推强行出成K≤1000，特别，对于常系数线性齐次递推有些出题人甚至会出成20000！ 这样，就需要引入一个非常有趣~~头秃~~的概念：特征多项式。 首先，我们需要介绍Cayley−Hamilton定理 对于一个n阶的一个方阵，它的特征多项式为p(λ)=|λE−A|=λn+b1λn−1+b2λn−2+...+bn 那么显然：p(A)=0 也就是说：AN+b1An−1+...+bn=0，即p(λ)为原多项式的化零多项式。 因此，这个特征多项式可以通过高斯消元及拉格朗日插值求出。 求矩阵的特征多项式 一个O(n4)的做法 显然，我们得到的特征多项式是一个n阶多项式，那么只需要知道n+1个点的点值就可以得到了。 也就是，我们把n+1个数代入|λE−A|中(作为λ)，然后暴力高斯消元即可得到一个矩阵的特征多项式。 那么，接下来，只需要拉格朗日插值即可。 这个做法作为一个n4的做法其实想要卡掉矩阵乘法是很难的，除非将递推的项数放到101000这样的级别，如[BZOJ4162] 那么接下来，我们考虑刚刚的做法能否被优化。 显然，每次n3求矩阵行列式太慢了。 一个O(n3)的做法 对于这样的矩阵：A=P×B×P−1 称A,B是相似的，也就是说，对于A,B的特征多项式相同。 构造还是很容易的，只需要保留每行与每行之间的关系即可。 对于这样的矩阵，我们称之为上海森堡矩阵。 ( a1,1 a1,2 a1,3 ⋯ a1,n a2,1 a2,2 a2,3 ⋯ a2,n 0 a3,2 a3,3 ⋯ a3,n ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ an,n ) 那么，对于这样的矩阵，求行列式的时间复杂度就降为n2了！ 然后，总时间复杂度为n3+n2logm，或者为n3+nlognlogm（并无卵用），然后对于n3logm的矩阵乘法构成了鲜明的优势（大雾 显然，其实上面的东西没有那么有用... 但是还是有必要知道的，万一他卡你呢？ 常系数线性齐次递推的矩阵的特征多项式 定义：递推式为fi= n ∑ j=1 aj×fi−j,i>n的递推。 讲道理，这个东西才非常有用... 对于所有的常系数线性齐次递推来说，它们的矩阵形态类似，同样，他们的特征多项式也类似... 其实手画一下就可以发现，它们的特征多项式都是p(λ)=λn−a1λn−1−a2λn−2−...−an 按照行列式的定义展开式子退一下就得到啦！ 特征多项式的使用手册 其实，使用方法很简单啦，就是运用之前得到的特征多项式性质，p(A)=AN+b1An−1+...+bn=0 那么，对于这样的式子，就可以做到将所有的AK用A0∼An的矩阵线性表达出来了。 Ax+y=Ax×Ay 那么Ax= n ∑ i=0 bi×Ai,Ay= n ∑ i=0 ci×Ai 也就是：Ax+y= n ∑ i=0 n ∑ j=0 bi×cj×Ai+j 因为有：p(A)=0也就是说：Ax+y= 2×n ∑ k=0 ( min(n,k) ∑ i=0 bick−i)Akmodp(λ) 然后显然，可以用倍增(其实就是快速幂)上述操作，也就是我们得到了一个n2logm复杂度的递推。 对于上述暴力操作可以用NTT或FFT优化上述多项式相乘和多项式取模。 也就是说，我们得到了一个nlognlogm的优秀做法！（拿头写啊 关于答案 Ax= n ∑ i=0 bi×Ai 这个式子已经给我们答案了，也就是说，这个矩阵的前n项加上系数相加即可，但是显然这个东西是n4的 如果要求fm的话，这个东西只需要用到f0∼fn即可 如果求矩阵的话，还是老老实实的一个一个乘吧... 例题.jpg 求矩阵特征多项式裸题：[BZOJ4162] 常系数线性齐次递推n2logm裸题：[BZOJ4161] 高难度的东西：[NOI 2017 泳池] 附件 NOI 2017 泳池 题解 对我来说，可能我只能接受k≤2000，如果再大就想要打人了... 首先70分的暴力基本雷同[UNR 2 积劳成疾](http://uoj.ac/problem/311) 大概就是推一个f[i][j],s[i][j]即可，[我不想再写一遍了](https://winniechen.cn/?p=152) 剩下的就是可以把这个转移写成矩阵的形式，然后就可以拿到优秀的90分了。 最后，根据上面的东西，优化一下就可以AC掉这道题了！https://www.cnblogs.com/Winniechen/p/10246295.html