はまやんはまやんはまやん

hamayanhamayan's blog

回文かい [yukicoder No.599]

https://yukicoder.me/problems/no/599

解法

https://yukicoder.me/submissions/218737

数え上げなのでDPで考えてみる。
ついでにNが10^3くらいなので、区間DPで考えてみる。
すると「dp[L][R] := S[L..R]を回分かい分解する組み合わせ数」というDPが思いつく。
 
計算量は一旦置いておいて更新を考えてみよう。
再帰的な構造で回分かい分解を考えてみると、S[L..R]の回文かい分解は、S[L..l]とS[r..R]が同じであるならば、残りのS[l+1...r-1]の回文かい分解をすればいいと分かる。
よってdp[L][R]の更新は

  • S[L] = S[R] ならば dp[L][R] += dp[L + 1][R - 1]
  • S[L..L+1] = S[R-1..R] ならば dp[L][R] += dp[L + 2][R - 2]


という感じである。愚直に書けばdp状態O(N^2)、遷移O(N)、部分列が等しいかの判定O(N)で全体O(N^4)
 
これを高速化していく方針で考える。
まず、単一文字列での部分列の一致判定の高速化をする。参考1 参考2
愚直にやるとO(N)かかるが、これをO(1)でやる。
自分はローリングハッシュを使ったが、色々な手法がある。
 
これでもまだ全体O(N^3)である。
DPの更新式を見てみると、DPの添字のLに対応するRは一意に定まっていることが分かる。
これは左右の端から1つずつ減らしていっているからである。
そのため、メモ化する時にRも一緒に保存しておく必要は無い。
つまり、状態数がO(N^2)だと思っていたが、実際にはO(N)となる。
これでメモ化すれば、全体O(N^2)となり通る。

string S;
int N;
RollingHash rh;
//---------------------------------------------------------------------------------------------------
mint memo[10101];
int vis[10101];
mint f(int L, int R) {
    if (R < L) return 1;
    if (vis[L]) return memo[L];

    mint res = 1;
    int l = L, r = R;
    while (l < r) {
        if (rh.hash(L, l) == rh.hash(r, R)) res += f(l + 1, r - 1);
        l++, r--;
    }

    vis[L] = 1;
    return memo[L] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
    rh.init(S);
    cout << f(0, N - 1) << endl;
}