Edit

【pythonでABC171を解説】F - Strivore

問題概要

問題ページ

F - Strivore
F - Strivore

問題ページへ移動する

問題文

「好きな英小文字 \(1\) 文字を好きな位置に挿入する」という操作を文字列 \(S\) にちょうど \(K\) 回繰り返してできる文字列は何通りあるでしょう？

答えは非常に大きくなる可能性があるので、\((10^9+7)\) で割ったあまりを出力してください。

制約

  • \(K\) は \(1\) 以上 \(10^6\) 以下の整数
  • \(S\) は英小文字からなる長さ \(1\) 以上 \(10^6\) 以下の文字列

問題の考察

ACコード

import sys


def alg_combination_mod(n, mod):
    denominator = 1
    molecule = 1
    ls = [1]
    for i in range(1, n + 1):
        if n - i >= i:
            molecule = (molecule * i) % mod
            denominator = (denominator * (n + 1 - i)) % mod
            ls.append(denominator * pow(molecule, mod - 2, mod) % mod)
        else:
            break
    return ls


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    k = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    ll = len(s) + k
    cnt = 0
    ls = alg_combination_mod(ll, mod)
    for i in range(ll, len(s) - 1, -1):
        t = 1 if ll == i else (t * 25) % mod
        cnt += (ls[min(i, ll - i)] * t) % mod
        cnt %= mod
    print(cnt)


if __name__ == '__main__':
    solve()

-Edit
-