AtCoder Beginner Contest 171 F - Strivore

ABC171のF問題からです。このアプローチ(特に後半部分)を見かけなかったので書いてみました。

問題概要：

文字列$\ S\ $の好きな位置に好きな英小文字を$\ K\ $回挿入して得られる文字列は何種類あるか？
・$|S| \leq 10^6$
・$1 \leq K \leq 10^6$

まずは小さい例で実験してみます。例えば、$S=ab, K=1\ $とします。
どこに挿入するかで$\ 3\ $通り、何を挿入するかで$\ 26\ $通りあるので全部で$\ 78\ $通りありそうです。ただ、このままだと重複がありそうなので、どのような文字列を複数回数えているか考えます。
挿入したい文字をその文字と同じ文字の隣に入れる場合、左に入れても右に入れてもできる文字列は同じです。例えば$\ S=ab\ $に新たに$\ a\ $を挿入する場合、一番左に入れても真ん中に入れてもできる文字列は$\ aab\ $です。これは二文字目の$\ b\ $についても同じことが言えるので、答えは$\ 78-2=76\ $通りです。
実は上の議論において、元の文字列の中身は関係ないです。$S=aa\ $のように同じ文字が連続する場合でも、$\ aaa\ $を$\ 3\ $回数えるので答えはやはり$\ 78-2=76\ $通りです。
つまり、与えられる文字列$\ S\ $の中身は実は関係なく、その長さだけが重要なのでした。以降は$\ |S|=N\ $とします。
長さだけを考えれば良いのですから、与えられた文字列は$\ a\ $が$\ N\ $個連続しているものとします。そうすると一気に視界が良くなります。
ここに文字を$\ K\ $個挿入します。挿入する文字に$\ a\ $が含まれていると厄介そうなので、まずは全てそれ以外の文字とします。そうすると、$N\ $個の$\ a\ $と$\ K\ $個のそれ以外の文字の並べ替えになるので、全部で$\ {}_{N+K} \mathrm{ C }_N \times 25^K\ $通りになります。
($\ {}_{N+K} \mathrm{ C }_N\ $の方は$\ a\ $の位置の決め方、$25^K\ $の方は$\ a\ $以外の位置に何を挿入するか、に対応します)
こう考えると、挿入する文字に$\ a\ $が含まれている場合も同様に処理できます。すなわち挿入する文字に$\ a\ $が$\ i\ $個含まれているとし、全て足せば良いです。求める答えは
$$
\sum_{i=0}^{K} {}_{N+K} \mathrm{ C }_{N\\+i} \times 25^{K-i}
$$となります。
この式はDPなどから変形しても得られるようですが、このような見方をすると自然に導出できるような気がしました。