最後に使う文字を全探索する．
今 \(i \in N\) 文字目を見ているとする． \(j \leq i\) の範囲を，\(j\) を小さくしながら調べる． 初めて \(s_{j} \neq s_{i}\) となる直前までの \(j\) に対して， \(dp_{i} += dp_{j}\).
実装
2文字前からスタートしたいため， dp テーブルは \(s\) の index より +2 する．
\(s\) から 1文字以上使わないといけないので， \(s\) から丁度 1文字 (\(s_{i}\)とする) とるということを， \(s_{i}\) と -2 文字目 をとるという扱いにする． ここで，\(s_{-2}\) からとるというのが，空文字にあたる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
string s; cin >> s;
ll n = s.length();
mint ans = 0;
dp[0] = 1;
rep(i,n){
ll j = i;
while(j >= 0){
dp[i+2] += dp[j];
j--;
if(j >= 0 && s[j] == s[i]) break;
}
ans += dp[i+2];
}
cout << ans.val() << endl;
return 0;
}
