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

https://atcoder.jp/contests/abc214/submissions/52228716