Rustコトハジメ

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

【yukicoder No.599 回分かい】DPとロリハ

No.599 回文かい - yukicoder

問題

文字列Sが与えられる。Sを部分列(S[1],S[2],...S[K])に分解した時、S[i]==S[k+1-i]の時、これを回文かい分解と呼ぶことにする。

文字列Sの回文かい分解は何通りあるか計算せよ。

方針

DPです。先頭のi個と後方のi個を取り除いた小さな文字列の場合を調べて、それをiを小さくする方向に拡張していけばdp[0]が答えになるはずです。

長さが偶数の時に、空の文字列を扱うことになりますが、例外を考えたくありません。そのため、別に中心に適当な文字を挿入したところで場合の数は変わらないことを利用して、文字列長が奇数のつもりで実装をします。こうすると、dp[s.len()/2]=1が明らかになります。足し合わせの数式はこんな感じになります。

 dp_i = \sum \gamma \times dp_{j}

実装

自分の作ったロリハライブラリは設計がよくないため、hatooさんのロリハを使わせてもらうことにしました。

fn solve() {
    input! {
        S: chars,
    }
    let p = 1_000_000_007;
    let s: Vec<u64> = S.iter().map(|&x| ctoi(x)).collect();
    let rh = RollingHash::new(&s);
    let gamma = |i: usize, j: usize| {
        let h1 = rh.get(i, j);
        let h2 = rh.get(s.len()-j, s.len()-i);
        if h1 == h2 {
            1
        } else { 0 }
    };
    let mid = s.len()/2;
    let mut dp = vec![0; mid+1];
    dp[s.len()/2] = 1;
    for i in (0..mid).rev() {
        let mut sum = 1; // for i,i
        for j in (i+1..mid+1) {
            // dbg!(sum,i,j,gamma(i,j));
            sum += gamma(i,j) * dp[j];
            sum %= p;
        }
        dp[i] = sum;
    }
    println!("{}", dp[0]);
}