結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    
    # Precompute factorial and inverse factorial modulo MOD
    max_n = n
    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
    
    from collections import defaultdict
    cnt = defaultdict(int)
    for c in S:
        cnt[c] += 1
    
    # Initialize the product polynomial
    product = [0] * (n+1)
    product[0] = 1
    
    for c in cnt:
        k = cnt[c]
        # Create the polynomial for this character: sum_{x=0}^k inv_fact[x] * t^x
        poly = [0] * (k+1)
        for x in range(k+1):
            poly[x] = inv_fact[x]
        
        # Multiply product with poly
        new_product = [0] * (len(product) + len(poly) - 1)
        for i in range(len(product)):
            if product[i] == 0:
                continue
            for j in range(len(poly)):
                if i + j > n:
                    continue
                new_product[i+j] = (new_product[i+j] + product[i] * poly[j]) % MOD
        product = new_product
    
    # Compute the sum: sum_{m=1}^n (m! * product[m]) % MOD
    result = 0
    for m in range(1, n+1):
        if m >= len(product):
            break
        term = fact[m] * product[m] % MOD
        result = (result + term) % MOD
    
    print(result)

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