ABC171 F. Strivore
問題
文字列Sが与えられる。次の操作をK回繰り返してできる文字列は何通りあるか？
- 好きな英小文字1文字を好きな位置に挿入
10^9+7で割ったあまりで答えよ。
制約
- 1 <= K <= 10^6
- 1 <= |S| <= 10^6
解法
最終的な文字列は、
「? ? ? S[0] ? ? ? S[1] ? ? ? ... S[|S|-1] ? ? ?」
のような形になっている。
ここで、重複しないように、S[i]がS[i-1]より後で最初にその文字でてくると考える。
そうすると、S[i-1]からS[i]の間にある?にはS[i]以外の25文字種しか割り当てられない。
そして、最後の文字S[|S|-1]より後ろの?には、任意の文字が割り当てられるので、26文字種が使える。
したがって、各S[i]の前後の?が何個かが決まれば、上記の文字種分選べるので、答えが求められる。
S[|S|-1]より後ろの?がx個とする。
このとき、残りのK-x個の?をS[i]の前のどれかにいれる組み合わせは、重複組合せから「{N-1+K-x}_C_{K-x}」通り、K-x個は25種から選べるので「25^{K-x}」通り、最後の?は26種から選べるので「26^x」通り、になり、これをかけ合わせたものがxのときの通り数になる。
xを0～K個のときで求めて足し合わせればよい。
