結果

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

ソースコード

diff # 

import sys

MOD = 998244353

def main():
    S = sys.stdin.readline().strip()
    from collections import Counter
    cnt = Counter(S)
    max_m = len(S)
    
    # 预计算阶乘和逆阶乘
    fct = [1] * (max_m + 1)
    for i in range(1, max_m + 1):
        fct[i] = fct[i-1] * i % MOD
    inv_fct = [1] * (max_m + 1)
    inv_fct[max_m] = pow(fct[max_m], MOD-2, MOD)
    for i in range(max_m - 1, -1, -1):
        inv_fct[i] = inv_fct[i+1] * (i+1) % MOD
    
    # 初始化多项式 P
    P = [1]
    
    # 处理每个字符
    for c in set(cnt):
        k = cnt[c]
        # 构造 Pc 的系数数组
        Pc = [inv_fct[t] for t in range(k+1)]
        # 多项式乘法
        new_P = [0] * (len(P) + len(Pc) - 1)
        for i in range(len(P)):
            for j in range(len(Pc)):
                new_P[i + j] = (new_P[i + j] + P[i] * Pc[j]) % MOD
        P = new_P
    
    # 计算总和
    total = 0
    for m in range(len(P)):
        if m > max_m:
            break
        total = (total + P[m] * fct[m]) % MOD
    # 减去空集的情况
    total = (total - 1) % MOD
    print(total)

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