Walk [Educational DP Contest / DP まとめコンテスト R]

https://atcoder.jp/contests/dp/tasks/dp_r

前提知識

• 行列累乗によるDP高速化

解説

https://atcoder.jp/contests/dp/submissions/3955540

長さKがとても大きい＋Nが小さいという所から、行列累乗感がかなりある。
dp[k][cu] := 長さkの有向パスで最後の頂点がcuである有向パスの組み合わせ
kが10^18なので、確実にできないが、注目すべきはその遷移である。
頂点cuから頂点toに有向辺があれば、dp[k+1][to] += dp[k][cu]という遷移をする。
これは全ての有向辺に言えることで、かつ、kがどんな数でも全く同じ遷移をする。
「kがどんな数でも全く同じ遷移をする」というのが大切。
行列累乗を知っていれば、行列累乗をするのだということが分かる。
　
以下の説明は行列累乗全般の説明である。
行列累乗の手順は、まず漸化式を立てる。
　

a[i+1][0] = a[i][1] + a[i][3]
a[i+1][1] = a[i][0] + a[i][2] + a[i][3]
a[i+1][2] = a[i][0] + a[i][1]
a[i+1][3] = a[i][1] + a[i][2]
||
　
次にこれを行列とベクトルに直す

>||
a' = m*a
a = [a[0], a[1], a[2], a[3]]
m = 
| 0 1 0 1 |
| 1 0 1 1 |
| 1 1 0 0 |
| 0 1 1 0 |

　
このように書くようにすると、更新処理をN回行うことは

a[N] = m^N * a[0]

と書くことに相当する。
m^Nを高速に計算するために行列累乗を作る。
これはm^10 = m^8 * m^2のように、任意の行列の累乗は2の累乗の累乗によって表現できる。
そのため、m, m^2, m^4, m^8, m^16, ... を作り、その組み合わせで目的の累乗を計算する。
これで計算量はO(logN * 行列どおりの掛け算に掛かる計算)となる。
これで、DPを高速化できる。

int N; ll K; int A[50][50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];
 
    Mat m(N, Vec(N, 0));
    Vec v(N, 1);
 
    rep(i, 0, N) rep(j, 0, N) m[i][j] = A[i][j];
    m = fastpow(m, K);
    v = mulMatVec(m, v);
 
    ll ans = 0;
    rep(i, 0, N) ans += v[i];
    ans %= mod;
    cout << ans << endl;
}