結果
問題 |
No.1195 数え上げを愛したい(文字列編)
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:53:34 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,567 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,920 KB |
実行使用メモリ | 110,644 KB |
最終ジャッジ日時 | 2025-06-12 15:53:43 |
合計ジャッジ時間 | 8,707 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 25 |
ソースコード
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()