ABC171-F Strivore
この問題好き。面白かった。
問題概要
文字列 と整数
がある。
の好きな位置に好きな英小文字を
回挿入してできる文字列の通り数を
で求めよ。
解説
とおく。
結果の文字列を前から決めていくことを考えると、
を、「
文字目までで、
回小文字の挿入以外で文字列を構成した（つまり、
の文字を使った）」とするDPが組める。
この遷移を考えて、途中で文字列の通り数が何倍されるかに注目し、26倍になる部分だけ分けて経路を選び取って、答えは
となる。
別解もある。
少し天下り的な考え方になるが、 が等しいDP配列どうしで階差をとってやると、26倍の遷移がなくなる代わりに、答えが累積和で求められるようになる。こちらのほうが定数倍は軽いはずだ。この時の答えの式は、
となる。
感想
割とすぐ解けたのでよかった。 あと、この二式なんで等しいんだろう…（コンテスト中に証明した人間いるんか？）
