結果
問題 |
No.1195 数え上げを愛したい(文字列編)
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:56:56 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,147 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 82,124 KB |
実行使用メモリ | 97,580 KB |
最終ジャッジ日時 | 2025-06-12 21:00:39 |
合計ジャッジ時間 | 8,722 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 25 |
ソースコード
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()