化零多項式有什麼用?

本文講一個非常非常非常平凡(但很多OI選手不知道?)的小技巧。


寫作動機:

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

任務描述:

我們有一個環 R 上的元素 M 及其化零多項式 f (更新:滿足首項係數可逆,比如首一),現在想對於另一個多項式 g ,我們想快速求出 g(M)

名詞解釋:

  • 環的意思是我們可以加減乘。
  • 化零多項式定義: f(M) = 0

前置知識:

  • 多項式的除法演算法:給定多項式 a,b ,存在唯一的一對多項式 q,r 滿足 a = qb + r ,其中 r 的次數小於 b 的次數。(可以用整數除法類比)

具體技巧:

根據上述提到的除法演算法,存在一組多項式 q,r 滿足 g = qf+r ,那麼:

egin{aligned} g= qf+r &implies g(M) = q(M)f(M) + r(M) \ &implies g(M) = q(M)0 + r(M) \ &implies g(M) = r(M) end{aligned}

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


例子:

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

推薦閱讀:

柯潔痛失世界第一,這是怎麼一回事兒?
那些數學140+的學霸,她們是怎麼做題的?
Kunen. Set Theory 第一版第二章無窮組合(三上)
關於GTM⑨的抄書日記-2
宗師之力合成途徑是什麼?

TAG:演算法競賽 | 數學 |