解説を漁ってみると、どうやらアルファベットを適当に$K$回挿入したあとの 長さ$N+K$の文字列の中で、$S$の各文字の位置が固定されていると考えればうまくいくということだった。 そう考えると、あとは長さ$N+K$の文字列で$K$文字をどうやって挿入していくかだけを考えれば良い。
入力例1を使って考える。
- S = “oof”
- N = len(“oof”) = 3
- K = 5
例えば、位置1に’o’、位置3に’o’、位置5に’f’をおいてみる。 また、長さ$N+K$の文字列を先頭から見たときに"oof"がはじめて登場するのがこれらの位置ということにする（条件1）。 このとき、位置0には’o’以外の25種のアルファベットを挿入できる。 逆に、位置0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にして、位置2にも’o’以外の25種のアルファベットを挿入できる。 また、位置4にも’f’以外の25種のアルファベットを挿入できる。 位置6と7に関しては、特に制約がないので、26種のアルファベットを挿入できる。
まとめると、‘f’の位置$j$が$N-1 … N+K-1$まで移動したとき、 2つの’o’が取れる位置の組み合わせは${}_j C _{N-1}$ となる。
また、25種のアルファベットを挿入する位置は$j - (N-1) $個、 26種のアルファベットを挿入する位置は$(N+K-1)$個、となる。
つまり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$となる。