ABC171 F - Strivore - あっとのTECH LOG

問題原文

解法

解説放送があまりにも神だったので理解のためにこの記事をお読みになる場合はこちらをご覧いただいたほうが。。。
www.youtube.com

以下、振り返り & 反省 & まとめです。

例えば、 abc とあって、各文字の間に文字を差し込んでいくことを考えました。
ただこれだと重複を取り除くことがめっちゃ大変そうでどうしたものかと思っていました。

こういう時は、「重複にならないようなルールを設定して、そのルールのもと数え上げる」のが良さそうだという知見です。
今回でいえば、「操作後の文字列において abc となる部分列を探す場合に、左から貪欲的に探して行く。見つかった a, b, c は必ず元の文字列の a, b, c である。」というようなルールとなります。

こうすると、 abc の各文字の間に文字を差し込む操作は以下のように捉えられます。

① a ② b ③ c ④

①〜④に好きに文字を差し込む
ただしルールを守るために、 ①にはa を、 ②にはb を、 ③には c を差し込めない（④ は自由）

こうすると、「 $K$ 回の操作のうち、何回 ① ~ ③ に入れて、何回 ④ にいれるか」で分けたくなります。
ここでは、 $K$ 回の操作のうち、 $i$ 回 ① ~ ③ に差し込むものとします。

すると、
④ の部分は特に制限はないので、 $26^{K - i}$ 通り、 ① ~ ③ の部分は３つの区別がつく箱に、 $i$ 個の区別がつかないボールを入れるのと同じなので、 $S$ の長さを $N$ として ${}_{i + N - 1} C_{N-1}$ 通り。（ $i + N - 1$ 個の要素から $N - 1$ 個を $S$ の要素とするイメージ、あるいは $i$ 個のボールと $N - 1$ 個の仕切りを並べるイメージ。並べたしきりの左から a, b となる。）

さらに挿入する各文字は、ルールに違反する１つを除く25文字種から好きに選べるので $25^{i}$ をかけたものになります。

これを各 $i$ について計算して足し合わせれば答えが求められます。

つまり、「実は $S$ の中身はどうでもよかった」ということですね。。。すごい。。。

実装

逆元を用いたMOD上のcombinationをします。

K = int(input())
S = input()
N = len(S)
MOD = 10 ** 9 + 7

ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)

感想

これが天才か。。。