概要
逆元が必ずしもない状況で行列式を計算する方法を紹介します
一般の可換環上の行列式
n91lib_rs/division_free_determinant.rs at master · noshi91/n91lib_rs · GitHub
除算を使わない のシンプルなアルゴリズムが知られています。 除算無しでも になるらしいのですが、詳しく勉強してないので詳細は分かりません。
合成数
掃き出し法のアルゴリズムを少し変えるだけで高速に計算できます。 掃き出し法は「ある行を使って別の行の先頭要素を 0 にする」を繰り返すアルゴリズムなので、この部分を何とかできればいいです。 そこで、0 にしたい列の要素を一旦 ( ではなく) ただの数だと思って、ユークリッド互除法を行います。 ユークリッド互除法は定数倍と加減算なので、 でも問題なく計算できます。 これを繰り返せば のアルゴリズムが得られます。 を繰り返しとる操作は計算量が落ちるので、実際には になっています。
さらに計算量を落とすことも出来ます。 そもそもユークリッド互除法の部分は 2 要素間だけで計算できるので、最終的にどういう線形変換になったかだけを追って、最後に行ベクトル同士を足し引きすればよいです。 これにより となります。
ユークリッド互除法が行えるなら何でもいいので、多項式環などでも使うことが出来ます。
----------- 以下、yukicoder のネタバレを含みます ----------
yukicoder No.1303 Inconvenient Kingdom - ひとなので
この解法で掃き出し法が機能しているのは、元のグラフが連結なので行列式が 0 でない、などの性質を利用しています。 先ほども述べた通り多項式もユークリッド互除法が使えるので、それを用いれば ad-hoc な証明をしなくても AC を取ることが出来ます。