化零多項式有什麼用?
05-02
本文講一個非常非常非常平凡(但很多OI選手不知道?)的小技巧。
寫作動機:
- 大多數選手不會線性代數,導致不了解
根據Cayley-Hamilton 定理,特徵多項式是化零多項式
的意思。 - 於是看到題解里提到該定理就一瞬諤諤。
- 本文用以消除恐懼233。
任務描述:
我們有一個環 上的元素 及其化零多項式 (更新:滿足首項係數可逆,比如首一),現在想對於另一個多項式 ,我們想快速求出 。
名詞解釋:
- 環的意思是我們可以加減乘。
- 化零多項式定義: 。
前置知識:
- 多項式的除法演算法:給定多項式 ,存在唯一的一對多項式 滿足 ,其中 的次數小於 的次數。(可以用整數除法類比)
具體技巧:
根據上述提到的除法演算法,存在一組多項式 滿足 ,那麼:
於是我們只需要先使用多項式取模求出 然後代入 就可以求出 的值。
例子:
熟悉線性遞推的讀者知道在求數列某一項的值時,本質上我們是在求 ,其中 是轉移矩陣。因為根據 Cayley-Hamilton 定理,特徵多項式是化零多項式,我們可以先求出 進行降次,從而快速求值。
推薦閱讀:
※柯潔痛失世界第一,這是怎麼一回事兒?
※那些數學140+的學霸,她們是怎麼做題的?
※Kunen. Set Theory 第一版第二章無窮組合(三上)
※關於GTM⑨的抄書日記-2
※宗師之力合成途徑是什麼?