どういう事？
この問題では、「atcoder」という物凄く具体的な 7 文字を取り出す事を要求しています。普通に考えれば、この文字列も入力の一部として与えて、もっと長い文字列の場合も考えさせてもよさそうですが、そうはなっていません。
そこで、この 7 文字についてのループを組み込んだ解法を考えます。
word = 'atcoder' for s in word: # 文字 s について何か調べる
このループは高々 7 回しかまわらないので、計算量は と見なせます。なので、「# 文字 s について何か調べる」の部分では、文字列 S の全検索
をやっても十分に間に合います。
であれば、全検索で文字 s の位置 i を発見して、その文字を使った場合の場合の数 dp[i] を計算するなどが考えられます。正確には、s = 't' のループであれば、「'at' という文字列を作る際に、位置 i の 't' を使った場合の場合の数」という意味になります。
DPを組み立てる練習
ここまで整理できれば、後は、テンプレートにしたがってDPを組み立てる練習になります。
n = 1 のケース、すなわち、'a' という文字列を組み立てる場合は、どの ’a' を拾ったにしても場合の数は 1 です。
dp = [0] * N s = word[0] # 'a' for i in range(len(S)): if S[i] == s: dp[i] = 1
次に n = 2 のケース、すなわち、't' という文字を拾って、'at' を作る場合の数を計算します。'a' の結果が dp[ ] に入っているとして、こちらの結果は新しい dp_n[ ] に入れる事にしましょう。
位置 i に 't' があった場合、それ以前にある 'a' の個数が dp_n[i] になります。で、もちろん、't' が見つかってからあわてて、それ以前の 'a' を探す必要はありません。それ以前の dp[ ] の合計値に一致するので、ループを回しながら、dp[ ] の合計も一緒に計算しておけば OK です。
s = word[1] # 't' dp_n = [0] * N count = 0 for i in range(len(S)): count += dp[i] count %= mod if S[i] == s: dp_n[i] = count dp = dp_n
最後に dp = dp_n として、得られた結果を dp[ ] に入れ直しておきます。
あとは、これと同じ事を残りの文字について繰り返せばOKです。位置 i に 'c' があったら、それ以前の dp[ ] の合計として、これに組み合わせられる 'at' の場合の数が得られることに注意してください。
一番最後は、sum(dp) として答えが得られます。
