結果

問題 No.1195 数え上げを愛したい（文字列編）
コンテスト
ユーザー strangerxxx
提出日時 2022-05-13 11:27:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,718 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 161,536 KB
最終ジャッジ日時 2024-07-21 08:49:26
合計ジャッジ時間 8,675 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def resolve():
    MOD = 998244353
    s = input()
    n = len(s)
    d = [0] * 27
    for i in s:
        d[ord(i) - ord("a") + 1] += 1
    cmb = Combination(n + 1)
    dp = [[0] * (n + 1) for _ in range(27)]
    dp[0][0] = 1
    for i in range(1, 27):
        for j in range(n + 1):
            for k in range(min(j, d[i]) + 1):
                dp[i][j] += dp[i - 1][j - k] * cmb(j, k)
            dp[i][j] %= MOD
    print(sum(dp[-1][1:]) % MOD)


class Combination:
    """
    前計算modあり組み合わせ
    """

    def __init__(self, n_max, mod=998244353):
        self.n_max = n_max
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if r < 0 or n < r:
            return 0
        if r > self.n_max:
            raise ValueError("n is larger than n_max.")
        return self.fac[n] * self.facinv[r] % self.mod * \
            self.facinv[n - r] % self.mod

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリスト
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * \
                modinv[self.mod % i] % self.mod
        return modinv

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリスト
        fac = [None] * (n + 1)
        fac[0] = 1
        facinv = [None] * (n + 1)
        facinv[0] = 1
        for i in range(1, n + 1):
            fac[i] = fac[i - 1] * i % self.mod
            facinv[i] = facinv[i - 1] * self.modinv[i] % self.mod
        return fac, facinv


if __name__ == '__main__':
    resolve()
0