Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-R Walk】DPの式を行列の掛け算とみる

R - Walk

問題

N個のノードがあり、隣接行列で有向辺の有無が与えられる。

この時、長さKのパスはいくつあるか?ただし、ループしてもよい。

制約: N=50, K=1018

方針

Kが死ぬほどでかいのがポイント。1018という数字からはダブリングの臭いがしますね。

もし、ある行列にある中身がiからjに行く長さKのパス数だとすると、答えは中身を足し合わせることで求まります。

f:id:akiradeveloper529:20190928151121j:plain

そして、dp[i][j] = Sum_k { dp[i][v] (0 or 1) * dp[v][j] }という更新式によって、長さKのパス数から長さK+1のパス数が計算出来ることを考えます。するとこれは、行列の掛け算であることに気づきます

つまり求めるは、与えられた行列のK乗であり、これはダブリングすることでlog(K)回の計算になりますから、一回あたりN3かかるとしても、N=50なので間に合います。

実装

fn solve() {
    input!{
        N:usize,K:u64,
        a:[[i64;N];N],
    }
    let mat = Matrix {
        v: a,
    };
    let c = mat.pow(K, std::i64::MAX);
    let mut ans = 0;
    for i in 0..N {
        for j in 0..N {
            ans += c.v[i][j];
            ans %= MO;
        }
    }
    println!("{}",ans);
}

考察

3項漸化式を行列でやるというのはこの前yukicoderに出ましたが、まさかDPの更新式を行列の掛け算と見ることが出来るなんて問題があるなんて。知ってりゃ解けるけど知らないと永遠に解けないです。