結果

問題 No.1195 数え上げを愛したい（文字列編）
ユーザー gew1fw
提出日時 2025-06-12 20:49:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,568 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 93,344 KB
最終ジャッジ日時 2025-06-12 20:51:30
合計ジャッジ時間 8,820 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().strip()
    S = input
    from collections import Counter
    cnt = Counter(S)
    max_c = max(cnt.values()) if cnt else 0
    
    # Precompute factorial and inverse factorial
    max_n = max_c
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    # Precompute each character's polynomial
    polys = []
    for c in cnt.values():
        poly = [0] * (c + 1)
        for k in range(c + 1):
            poly[k] = inv_fact[k]
        polys.append(poly)
    
    # Multiply all polynomials
    from functools import reduce
    def multiply(a, b):
        n = len(a)
        m = len(b)
        res = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
        return res
    
    GF = reduce(multiply, polys, [1])
    
    # Compute the sum
    max_degree = len(GF) - 1
    fact_list = [1] * (max_degree + 1)
    for i in range(1, max_degree + 1):
        fact_list[i] = fact_list[i-1] * i % MOD
    
    total = 0
    for n in range(1, max_degree + 1):
        if n >= len(GF):
            coeff = 0
        else:
            coeff = GF[n]
        a_n = coeff * fact_list[n] % MOD
        total = (total + a_n) % MOD
    
    print(total % MOD)

if __name__ == "__main__":
    main()
0