yukicoder No.1303 Inconvenient Kingdom

問題

\(O(N^3) \) 解（執筆時点で Fastest AC）です．

解法

連結グラフの場合だけを考えます（それ以外の場合は連結成分毎に行列木定理を適用することでもともと \( O(N^3) \) で解けるので）．このとき，問題は「 \(N \) 頂点の単純連結無向グラフが与えられる．新たに一辺だけ追加してもよいとき，その全域木の個数を求めよ」となります．

まず，新たに一辺 \((i, j)\) が追加されたグラフについて，この辺を必ず用いるような全域木の個数を考えます．これは， \((i, j)\) 間に重み \(x\) の辺を張り（＝ \((i, j)\) 間に \(x\) 本の多重辺を張り），通常の行列木定理を適用した結果（これは \(x\) の多項式になります）を \(f(x)\) とすると， \(f(x)\) の \(x\) の一次の係数が答になります．

もともと辺が存在しない全ての頂点対 \((i, j)\) に対してこの計算を行っていては，\(O(N^3)\) 等の計算量を要する行列式の計算を \(O(N^2) \) 回繰り返すことになり，到底 TL に間に合いません．しかし，「もともと辺が存在しない頂点対 \( (i, j) \; (i < j)\) 全てについて新たに重み \(x\) の辺を追加する」という操作を行い，このグラフに対して行列木定理を適用することで，あらゆる頂点対 \((i, j)\) に関する先述の問題の答の総和が一挙に得られます（新たに張った辺を複数本使用するような全域木は \(x\) の二次以上の項に寄与するので）．今回は \(x\) の高次の係数には興味ないので \( \mathrm{mod} \, x^2\) の範囲で計算すればよく（例えば \(a + bx\) の逆元は \(a^{-1} + (a^{-2}b)x \) となります），めでたく \(O(N^3)\) で行列木定理における行列式の計算が行えます．

実装例

C++17(1z), 5 ms（追記：掃き出しの実装が誤っていたため修正）

感想

やっていることが 二重数を用いた自動微分の計算 （新たに辺を増やした時，全域木の個数はどれだけ増えるか？）とも解釈できて少し興味深かったです．