特征多項(xiàng)式與常系數(shù)線性齊次遞推

一般來(lái)說(shuō)，這個(gè)東西是用來(lái)優(yōu)化能用矩陣乘法優(yōu)化的遞推式子的。

通常，這種遞推式子的特征是在齊次的條件下，轉(zhuǎn)移系數(shù)也可以通過(guò)遞推得到。

對(duì)于這樣的遞推，通常解法為$O(NK)$的遞推或者$O(k^3\log n)$的矩陣乘法，但是有些**毒瘤**的出題人~~吉老師~~，會(huì)將這樣的遞推強(qiáng)行出成$K\le 1000$，特別，對(duì)于常系數(shù)線性齊次遞推有些出題人甚至?xí)龀?20000$！

這樣，就需要引入一個(gè)非常有趣~~頭禿~~的概念：特征多項(xiàng)式。

首先，我們需要介紹$Cayley-Hamilton$定理

對(duì)于一個(gè)$n$階的一個(gè)方陣，它的特征多項(xiàng)式為$p(\lambda)=|\lambda E-A|=\lambda^n+b_1\lambda^{n-1}+b_2\lambda^{n-2}+...+b_n$

那么顯然：$p(A)=0$

也就是說(shuō)：$A^N+b_1A^{n-1}+...+b_n=0$，即$p(\lambda)$為原多項(xiàng)式的化零多項(xiàng)式。

因此，這個(gè)特征多項(xiàng)式可以通過(guò)高斯消元及拉格朗日插值求出。

求矩陣的特征多項(xiàng)式

一個(gè)$O(n^4)$的做法

顯然，我們得到的特征多項(xiàng)式是一個(gè)$n$階多項(xiàng)式，那么只需要知道$n+1$個(gè)點(diǎn)的點(diǎn)值就可以得到了。

也就是，我們把$n+1$個(gè)數(shù)代入$|\lambda E-A|$中(作為$\lambda$)，然后暴力高斯消元即可得到一個(gè)矩陣的特征多項(xiàng)式。

那么，接下來(lái)，只需要拉格朗日插值即可。

這個(gè)做法作為一個(gè)$n^4$的做法其實(shí)想要卡掉矩陣乘法是很難的，除非將遞推的項(xiàng)數(shù)放到$10^{1000}$這樣的級(jí)別，如[BZOJ4162]

那么接下來(lái)，我們考慮剛剛的做法能否被優(yōu)化。

顯然，每次$n^3$求矩陣行列式太慢了。

一個(gè)$O(n^3)$的做法

對(duì)于這樣的矩陣：$A=P\times B\times P^{-1}$

稱$A,B$是相似的，也就是說(shuō)，對(duì)于$A,B$的特征多項(xiàng)式相同。

構(gòu)造還是很容易的，只需要保留每行與每行之間的關(guān)系即可。

對(duì)于這樣的矩陣，我們稱之為上海森堡矩陣。

$\begin{pmatrix} a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}\\ a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}\\ 0&a_{3,2}&a_{3,3}&\cdots&a_{3,n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&a_{n,n} \end{pmatrix}$

那么，對(duì)于這樣的矩陣，求行列式的時(shí)間復(fù)雜度就降為$n^2$了！

然后，總時(shí)間復(fù)雜度為$n^3+n^2\log m$，或者為$n^3+n\log n \log m$（并無(wú)卵用），然后對(duì)于$n^3 \log m$的矩陣乘法構(gòu)成了鮮明的優(yōu)勢(shì)（大霧

顯然，其實(shí)上面的東西沒(méi)有那么有用...

但是還是有必要知道的，萬(wàn)一他卡你呢？

常系數(shù)線性齊次遞推的矩陣的特征多項(xiàng)式

定義：遞推式為$f_i=\sum\limits_{j=1}^na_j\times f_{i-j},i>n$的遞推。

講道理，這個(gè)東西才非常有用...

對(duì)于所有的常系數(shù)線性齊次遞推來(lái)說(shuō)，它們的矩陣形態(tài)類似，同樣，他們的特征多項(xiàng)式也類似...

其實(shí)手畫一下就可以發(fā)現(xiàn)，它們的特征多項(xiàng)式都是$p(\lambda)=\lambda^n-a_1\lambda^{n-1}-a_2\lambda^{n-2}-...-a_n$

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

特征多項(xiàng)式的使用手冊(cè)

其實(shí)，使用方法很簡(jiǎn)單啦，就是運(yùn)用之前得到的特征多項(xiàng)式性質(zhì)，$p(A)=A^N+b_1A^{n-1}+...+b_n=0$

那么，對(duì)于這樣的式子，就可以做到將所有的$A^K$用$A^0\sim A^n$的矩陣線性表達(dá)出來(lái)了。

$A^{x+y}=A^x \times A^y$

那么$A^x=\sum\limits_{i=0}^n b_i\times A^i,A^y=\sum\limits_{i=0}^nc_i\times A^i$

也就是：$A^{x+y}=\sum\limits_{i=0}^n\sum\limits_{j=0}^nb_i\times c_{j}\times A^{i+j}$

因?yàn)橛?#xff1a;$p(A)=0$也就是說(shuō)：$A^{x+y}=\sum\limits_{k=0}^{2\times n}(\sum\limits_{i=0}^{\min(n,k)}b_ic_{k-i})A^k \mod p(\lambda)$

然后顯然，可以用倍增(其實(shí)就是快速冪)上述操作，也就是我們得到了一個(gè)$n^2\log m$復(fù)雜度的遞推。

對(duì)于上述暴力操作可以用$NTT$或$FFT$優(yōu)化上述多項(xiàng)式相乘和多項(xiàng)式取模。

也就是說(shuō)，我們得到了一個(gè)$n\log n \log m$的優(yōu)秀做法！（拿頭寫啊

關(guān)于答案

$A^x=\sum\limits_{i=0}^n b_i\times A^i$

這個(gè)式子已經(jīng)給我們答案了，也就是說(shuō)，這個(gè)矩陣的前$n$項(xiàng)加上系數(shù)相加即可，但是顯然這個(gè)東西是$n^4$的

如果要求$f_m$的話，這個(gè)東西只需要用到$f_0\sim f_n$即可

如果求矩陣的話，還是老老實(shí)實(shí)的一個(gè)一個(gè)乘吧...

例題.jpg

求矩陣特征多項(xiàng)式裸題：[BZOJ4162]

常系數(shù)線性齊次遞推$n^2\log m$裸題：[BZOJ4161]

高難度的東西：[NOI 2017 泳池]

附件

NOI 2017 泳池 題解

對(duì)我來(lái)說(shuō)，可能我只能接受$k\le 2000$，如果再大就想要打人了...

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

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

剩下的就是可以把這個(gè)轉(zhuǎn)移寫成矩陣的形式，然后就可以拿到優(yōu)秀的$90$分了。

最后，根據(jù)上面的東西，優(yōu)化一下就可以AC掉這道題了！

轉(zhuǎn)載于:https://www.cnblogs.com/Winniechen/p/10246295.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的特征多项式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。