library-checker-problems
library-checker-problems copied to clipboard
[テストケース] matrix pow / characteristic polynomial
準備当時、Frobenius Form を経由する手法は想定されていなかった。
https://codeforces.com/blog/entry/124815
特性多項式が $p_1(x)p_2(x)\cdots$, $p_k\mid p_{k+1}$ となる非自明な行列を一応入れておきたい。
生成:N の分割を適当にとって deg p_i を決める → p_1 から順に p_k を決める → Frobenius Form を作る → ランダム行列 $P$ をとって $P^{-1}AP$ を出力