AtCoder Beginner Contest 171 F - Strivore

解法

文字列 $S$ の長さを $N$ とします。また最終的に出来上がる文字列を $T$ と表記します。

$T$ の長さは $N+K$ になります。そのうち元々あった文字と追加した文字の場所の割り当て方が $_{N+K}C_{K}$ 通りで、追加した文字の種類が $26^{K}$ 通りで…とやりたくなりますが、これでは最終的に同じ文字列になるものを重複して数えてしまいます。例えば $S$ を abc、 $K=2$ として、文字を追加した場所を * で示したときに

場所の割り当て方を a*b*c として、追加する文字を順に b c とする
場所の割り当て方を ab*c* として、追加する文字を順に b c とする

という選び方はともに abbcc という文字列になります。

このような重複を防ぐためには、最終的に出来上がる文字列に対して、その作り方が1通りに決まるようなルールを決めてしまえば良いです。ここでは「 $T$ のなるべく左側の文字が、元々あった $S$ の各文字と対応するようにマッチさせる」というルールにしましょう。例えば $S$ が abc 、 $T$ が abbcc であるような場合には、ab*c* という場所の割り当て方だけを考えることになります。

f:id:betrue12:20200621223911p:plain

では逆に、このルールに基づいた時に場所の割り当て方が ab*c* となるような文字列 $T$ はいくつあるでしょうか？

3文字目の * に入る文字は c 以外の $25$ 種類があり得ます。なぜなら3文字目がもし c だった場合、「なるべく左側にマッチ」ルールに基づくと abc** という割り当て方になっているはずだからです。一方、5文字目の * は何でも良いので $26$ 種類です。

これをより一般の場合で考えると、割り当て方に含まれる * のうち末尾に並んでいるものは $26$ 通り、そうでないものは $25$ 通りの選択肢があります。つまり

場所の割り当て方を決めた時に、その末尾に並ぶ * が $t$ 個、そうでない * が $K-t$ 個あった場合、その割り当て方に対応する文字列は $26^{t} \times 25^{K-t}$ 通りである

ということになります。これで計算ができます。

末尾に並ぶ * の個数 $t$ を全通り試しましょう。そうすると割り当て方のうち末尾は「 $S$ の末尾1文字＋ * $t$ 個」だと決まるので、残りの文字と * の並べ方は $_{N-1+K-t}C_{K-t}$ 通りです。これに先ほど計算した文字列の個数を掛けて、全て合計すれば良いです。