library-checker-problems icon indicating copy to clipboard operation
library-checker-problems copied to clipboard

[テストケース] matrix pow / characteristic polynomial

Open maspypy opened this issue 9 months ago • 0 comments

準備当時、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$ を出力

maspypy avatar May 12 '24 11:05 maspypy