Official

G - Inversion of Tree Editorial by nok0

この問題は行列木定理、及び各要素が高々一次の行列の行列式を求めるアルゴリズムを問う問題です。

行列木定理

行列木定理については、過去にABC で何度か出ているのでそちらを参考にしてください。

本問題でも、行列木定理を適用することができます。 キーポイントは、行列木定理の辺には正整数の重みを付けられるということです。辺 \((u,v)\) に重み \(c\) を付けるには、辺が \(c\) 本あると考えればよいです。

今回の場合は、\(P_u>P_v\) を満たす辺の重みを \(x\) 、\(P_u<P_v\) を満たす辺の重みを \(1\) とします。このようにして行列木定理を適用した結果を計算すると、\(x^i\) の項の係数と、本問題の \(K=i\) の答えが一致することがわかります。

結局、この問題は、要素が高々一次の行列の行列式を高速に計算する問題に帰着されます。以下行列式を求める行列を \(M_0 + M_1 x\) と置きます。

\(\mathrm{O}(N^4)\) 解法

\(\mathrm{O}(N^4)\) 解法で十分な場合も多いので、まずはこちらを説明します。求める行列式は高々 \(N\) 次なことに注意すると、\(x\) に \(0,1,\ldots,N\) を代入して行列式を計算し、その結果から各係数を復元することができます。 一回の行列式の計算は \(\mathrm{O}(N^3)\) かかるので、この方法は \(\mathrm{O}(N^4)\) で動作します。

\(\mathrm{O}(N^3)\) 解法

\(\mathrm{O}(N^3)\) 解法では、行列の特性多項式が高速に求まることを利用します。

\(N\times N\) 行列 \(M\) の特性多項式は \(\det({xI - M})\) (ここで \(I\) は\(N\times N\) の単位行列) として定義されます。

特性多項式は \(\mathrm{O}(N^3)\) で計算できることが知られています。（参考：Library checker Characteristic Polynomial）そのため、計算する行列式を特性多項式の形に変形できれば良いです。

\(\det({M_0 + M_1 x })\) は、\(M_1\) が正則である場合には、\(M_1\) に対する行基本変形、列基本変形を考えることで \(\det\) 内部の \(x\) の係数を単位行列 \(I\) にすることができます。

具体的には、\(I=A M_1 B\) を満たすように行列 \(A,B\) を取れば

\[\det({M_0 + M_1 x })= \frac{1}{\det A \det B}\det(A (M_0 + M_1 x)B) = \frac{1}{\det A \det B}\det(AM_0B + I x) \]

と変形が可能で、行列 \(AM_0B\) の特性多項式の計算に帰着されます。

\(M_1\) が正則でない場合は、適当な乱数 \(a\) を取り、 \(y=x+a\) として \(\det{(M_0 +y M_1)} = \det{((M_0+aM_1) +x M_1)}\) を計算することを考えます。

ここで \(z=y^{-1}\) とすれば\(\det{( z (M_0+aM_1) + M_1)}\) の行列式が求まれば良いです。 \(a\) をランダムに取ったため、 \(M_0 + aM_1\) は高い確率で正則になっていることが期待されます。

正則行列に対しては上述の手法が適用できるため、\(\det{(M_0 +y M_1)} \) の計算が出来ました。最後に \(x\) を \(x-a\) で置き換えることによって求めたい行列式の計算ができました。

参考資料

posted:
last update: