EDPC R - Walk

歩行

考え方

ABCでいうと、E問題級。

隣接行列を $K$ 乗すれば、各点から各点へ $K$ ステップで移動する経路数がわかる。
つまり、その成分を全部足せば OK。

$K$ が非常に大きいので、$K$ 乗にはダブリングを使うこと。

計算量は $O(N^3\log K)$。

……DPまとめコンテストとは？

入力を受け取る。

n: 4
k: 2
a:
  {0, 1, 0, 0}
  {0, 0, 1, 1}
  {0, 0, 0, 1}
  {1, 0, 0, 0}

隣接行列 a の $2$ 乗を求める。
a^2[i][j] は、頂点 i から頂点 j へ長さ $2$ で移動する方法数である。

a^2:
  {0, 0, 1, 1}
  {1, 0, 0, 1}
  {1, 0, 0, 0}
  {0, 1, 0, 0}

全成分の和を取る。

2 + 2 + 1 + 1 = 6

よって答えは $6$ である。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
足し算や掛け算をするたびに結果を % 1000000007 する。

特になし。