特性多項式O(N^3)

自力で発明したのでメモ。たぶん既知のアルゴリズムと同じ？
ref: ABC323G

$\begin{pmatrix} *-x & * & * & *\\ * & *-x & * & *\\ * & * & *-x & *\\ * & * & * & *-x\\ \end{pmatrix}$
これの行列式を求めたい。ところでこれを
$\begin{pmatrix} *-x & * & 0 & 0\\ * & *-x & * & 0\\ * & * & *-x & *\\ * & * & * & *-x\\ \end{pmatrix}$
というような、下三角＋余分に斜め1列の形にできれば、行列式の定義通りにN!項の和をとるやつを
dp[x][y]=x行目までの選び方を決めて、選んでない列がy列目(1≦y≦x+1)であるときの、行列式への寄与
でDPできる。これは状態数O(N^2)、遷移数各O(1)、遷移の計算がO(N)(高々N次の多項式同士の加減と、高々N次と1次の多項式の積の計算が定数回)なので全体でO(N^3)

下三角っぽく変形するのは簡単で、まず2列目を使って3列目以降を掃き出す
$\begin{pmatrix} *-x & * & 0 & 0\\ * & *-x & *-*x & *-*x\\ * & * & *-x & *\\ * & * & * & *-x\\ \end{pmatrix}$
そうすると2行目の3列目以降にxが増殖するので、これを3行目以降を使って相殺する
$\begin{pmatrix} *-x & * & 0 & 0\\ * & *-x & * & *\\ * & * & *-x & *\\ * & * & * & *-x\\ \end{pmatrix}$
すると1行目が掃き出せたのであとは同様にやる
気持ちとしてはこれと同じ。
ABC220Ex O(N^3)解法 - メモ

おわりです