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; }