pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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
  • 多重辺は存在しない

解法概要

  1. 行列累乗で経路数のグラフを構成
  2. 109 程度の素数を 100 個用意し、各素数 mod 上で行列木定理
  3. 中国剰余定理ですべての解を統合

解法

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 し忘れてる。

CodeChef May Challgenge 2016: Roads in Stars

C++ みたいな演算子オーバーロードの乱用は好きじゃないけど、演算子オーバーロードが全く出来ないというのも困りもの。何が言いたいかというと Java の BigInteger が使いづらすぎる。その点 C# の BigInteger は使いやすいんだけど、すべてのジャッジ環境で使えるわけじゃないのが玉に瑕。