CodeChef May Challgenge 2016: Roads in Stars
Easy Queries よりは簡単だった。
https://www.codechef.com/MAY16/problems/STARROAD
問題
N 頂点 M 辺のグラフが与えられる。(i→j に向かう K ステップ以下の経路数）mod X 本だけ i-j 間に辺を張ったグラフを構築する。そのグラフ上での全域木は何通りあるか。
- 1≦N≦100
- 0≦M≦N(N-1)/2
- 1≦K≦1018
- 1≦X≦7777777
- 多重辺は存在しない
解法概要
解法
i→j への経路数だけれど、丁度 K ステップの経路数は GK で求められる。これは行列累乗系 DP に慣れていればすぐわかると思うし有名事実でもある。
K ステップ以下なら E+G+...+GK を求めればいい。これを求めるには次のような行列を作って累乗する。
$$ \begin{bmatrix} G & O \\ E & E \\ \end{bmatrix}^{K+1}= \begin{bmatrix} G & O \\ E+G+G^2+G^3+\cdots+G^K & E \\ \end{bmatrix} $$
高速に累乗を求めればこれは O(n3 log K) でできる。これは十分に速い。
次に全域木の総数を求める。これは行列木定理を使えばいい。行列木定理の主張は次のようなものであった。
- グラフ G に対応するラプラシアン行列 L の任意の余因子は、グラフ G の全域木の個数と等しい。
余因子を求めるには行列式を計算すればいい。n=50 における計算結果が 300 桁程度なので、n=100 でも 1000 桁以内に収まると予想できる。もしその予想が正しければ、 109 程度の素数を 100 個用意して、それぞれの mod 上で掃き出し法を行い中国剰余定理で復元すれば正しい解が得られる。
ちなみに、多倍長使って有理数上の掃き出し法もやってみたんだけど、明らかに間に合わなかった。
よく見ると determinant の計算で swap し忘れてる。
