https://kaage.hatenablog.com/entry/2020/06/23/000449

この問題好き。面白かった。

問題概要

文字列 $S$ と整数 $K$ がある。 $S$ の好きな位置に好きな英小文字を $K$ 回挿入してできる文字列の通り数を $\bmod 10^9+7$ で求めよ。

解説

$|S|=N$ とおく。結果の文字列を前から決めていくことを考えると、 $dp\left[i\right]\left[j\right]$ を、「 $i$ 文字目までで、 $j$ 回小文字の挿入以外で文字列を構成した（つまり、 $S$ の文字を使った）」とするDPが組める。この遷移を考えて、途中で文字列の通り数が何倍されるかに注目し、26倍になる部分だけ分けて経路を選び取って、答えは

${\displaystyle \sum_{i=0}^{K}26^i 25^{K-i}\binom{N+K-i-1}{N-1} }$

となる。別解もある。少し天下り的な考え方になるが、 $j$ が等しいDP配列どうしで階差をとってやると、26倍の遷移がなくなる代わりに、答えが累積和で求められるようになる。こちらのほうが定数倍は軽いはずだ。この時の答えの式は、

${\displaystyle \sum_{i=N}^{N+K}25^{N+K-i}\binom{N+K}{i} }$

となる。

感想

割とすぐ解けたのでよかった。あと、この二式なんで等しいんだろう…（コンテスト中に証明した人間いるんか？）