[ABC214] F - Substrings
[Q] F - Substrings
考察
解説ACした。dp何もわからない…。
0. とりあえず「1個前をとらない」という条件をなくして考えてみることに手がかりがある。簡略化して考える手間を惜しまないほうが、俺にはちょうどいいかもしれない。
1. dp[i]を、index_i番目の文字を採用した場合何通りになるか、で管理する。
2. 答えはdp[0 ~ N-1]の和、のようになるのだがちょっと違う。
結果的にdp[K ~ K+N-1]の和が答えになる。K個の下準備を施したdpテーブルになる。
3. K文字の下駄？
K = 1のとき(勝手に考える。1文字前まで取る)
aaa
id 012
DP 0123
DP[]1111
ans = 3 ... "a", "aa", "aaa" しかとれない。
aba
id 012
DP 0123
DP[]1123
ans = 6 ... "a"だけ重複
abc
id 012
DP 0123
DP[]1124
ans = 7 ... わかりやすい。i番目未満をとるとらないで、2^iを加算。
DPの値の取り方をみると、
index_j = index_i - 1からスタートして、
重複文字もしくはindexが-1になるまで探す、都度DP[i+K]にDP[j+K]を加算するようだ。イメージとしては、
・index_jを下っていくときに、自分と違う文字であれば、自分をとった場合に必ず新しいバリエーションになる。
・逆に自分と同じ文字が来てしまった場合、それをとるときと今の自分をとるときでバリエーションがかぶる。
・同じ文字をとって自分をとる場合は新しいバリエーションになるので、同じ文字のindex_jまでは加算する。
実装
なお、K文字前をとるという変数を変えれば、いい感じに応用できる。いずれ役立つときが来ることを期待したい。
void solve(string S, ll K){
ll N = S.size();
vector<mint> dp(N + K + 1, 0); // 開始位置はKから。k文字前からとるかどうかの判定を進める。
dp[0] = 1;
rep(i, N){
for(ll j = i - 1; j >= -1; --j){
dp[i + K] += dp[j + 1];
if (S[i] == S[j]) break;
}
}
mint ans = 0;
rep(i, N){
ans += dp[i + K];
}
cout << ans << endl;
}
int main() {
cincout();
MOD = 1e9 + 7;
string S;
cin >> S;
solve(S, 1);
}