化零多項式有什麼用？

本文講一個非常非常非常平凡（但很多OI選手不知道？）的小技巧。

寫作動機：

1. 大多數選手不會線性代數，導致不了解 根據Cayley-Hamilton 定理，特徵多項式是化零多項式的意思。
2. 於是看到題解里提到該定理就一瞬諤諤。
3. 本文用以消除恐懼233。

任務描述：

我們有一個環 上的元素 及其化零多項式 （更新：滿足首項係數可逆，比如首一），現在想對於另一個多項式 ，我們想快速求出 。

名詞解釋：

• 環的意思是我們可以加減乘。
• 化零多項式定義： 。

前置知識：

• 多項式的除法演算法：給定多項式 ，存在唯一的一對多項式 滿足 ，其中 的次數小於 的次數。（可以用整數除法類比）

具體技巧：

根據上述提到的除法演算法，存在一組多項式 滿足 ，那麼：

於是我們只需要先使用多項式取模求出 然後代入 就可以求出 的值。

例子：

熟悉線性遞推的讀者知道在求數列某一項的值時，本質上我們是在求 ，其中 是轉移矩陣。因為根據 Cayley-Hamilton 定理，特徵多項式是化零多項式，我們可以先求出 進行降次，從而快速求值。

推薦閱讀：