306.1

やり直し。

1050

開始点を固定して考えると分かりやすいので、それを開始点の数だけループしてみる。現在位置がiでjへ遷移するための遷移行列は、元のグラフの枝の有無から作成可能。ここでjが開始点になるものの数をカウントすればループの個数が分かる。つまり行列の開始点と同じ列を最後に複製してやれば良い。また、そこでは総和を取る必要があるので、今までの分が蓄積されるようにするために、常に遷移するようにしておく必要がある。これで行列乗算をやると、微妙に(数倍程度)間に合わない。

元のグラフから作成される部分については共通なので、追加の部分をまとめてやると、行列サイズが倍のものができるので、開始点の数だけループするのはやめて、倍のサイズで行列乗算をすれば、若干高速化されて間に合う。こちらとしては前者でも間に合うようなチューニングにして欲しかった。

mod演算の数を削ろうとすると、long溢れが起きるのでダメ、というのもなかなかに悩ましい。そもそも全然違う解法もあるようではあるが、見るからに行列乗算の問題だから、いいや、という感じ。