結果
問題 |
No.1195 数え上げを愛したい(文字列編)
|
ユーザー |
|
提出日時 | 2025-06-28 19:28:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,818 ms / 3,000 ms |
コード長 | 5,804 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,504 KB |
実行使用メモリ | 173,888 KB |
最終ジャッジ日時 | 2025-06-28 19:28:45 |
合計ジャッジ時間 | 26,126 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
## https://yukicoder.me/problems/no/3166 # 数論変換パートは # https://qiita.com/AngrySadEight/items/0dfde26060daaf6a2fda # と # https://qiita.com/izu_nori/items/1c5cdef0500ffa0276f5 # を参考にしました MOD = 998244353 class NTT: def __init__(self): self._root = self._make_root() self._invroot = self._make_invroot(self._root) def _reverse_bits(self, n): n = (n >> 16) | (n << 16) n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8) n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4) n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2) n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1) return n def _make_root(self): # 3はMODの原始根, 119乗するとconvolusion, NTT における「基底」の条件を満たす r = pow(3, 119, MOD) return [pow(r, 2 ** i, MOD) for i in range(23, -1, -1)] def _make_invroot(self, root): invroot = [] for i in range(len(root)): invroot.append(pow(root[i], MOD - 2, MOD)) return invroot def _ntt(self, poly, root, rev, max_l): n = len(poly) k = (n - 1).bit_length() step = (max_l) >> k for i, j in enumerate(rev[::step]): if i < j: poly[i], poly[j] = poly[j], poly[i] r = 1 for w in root[1:(k + 1)]: for l in range(0, n, r * 2): wi = 1 for i in range(r): a = (poly[l + i + r] * wi) % MOD a += poly[l + i] a %= MOD b = (-poly[l + i + r] * wi) % MOD b += poly[l + i] b %= MOD poly[l + i] = a poly[l + i + r] = b wi *= w wi %= MOD r <<= 1 def convolution(self, poly_l, poly_r): # 多項式を畳み込んだ時の次数よりも大きい2の冪の長さを求める # (NTTの特性上2の冪乗に乗せるため) len_ans = len(poly_l) + len(poly_r) - 1 if (min(len(poly_l), len(poly_r)) <= 40): return self._combolution_light(poly_l, poly_r) # 2の冪の長さを求める n = 1 max_depth = 0 while n <= len_ans: n *= 2 max_depth += 1 rev = [self._reverse_bits(i) >> (32- max_depth) for i in range(n)] new_poly_l = [0] * n for i in range(len(poly_l)): new_poly_l[i] = poly_l[i] new_poly_r = [0] * n for i in range(len(poly_r)): new_poly_r[i] = poly_r[i] # 数論変換 self._ntt(new_poly_l, self._root, rev, n) self._ntt(new_poly_r, self._root, rev, n) # 畳み込みは各iを代入した値の積で求められる d_ans = [0] * n for i in range(n): d_ans[i] = (new_poly_l[i] * new_poly_r[i]) % MOD # 逆数論変換 self._ntt(d_ans, self._invroot, rev, n) # 最後の定数分割る処理 inv_n = pow(n, MOD - 2, MOD) poly_ans = [0] * len_ans for i in range(len_ans): poly_ans[i] = (d_ans[i] * inv_n) % MOD return poly_ans def _combolution_light(self, poly_l, poly_r): poly_ans = [0] * (len(poly_l) + len(poly_r) - 1) for i in range(len(poly_l)): for j in range(len(poly_r)): poly_ans[i + j] += (poly_l[i] * poly_r[j]) % MOD poly_ans[i + j] %= MOD return poly_ans class CombinationCalculator: """ modを考慮したPermutation, Combinationを計算するためのクラス """ def __init__(self, size, mod): self.mod = mod self.factorial = [0] * (size + 1) self.factorial[0] = 1 for i in range(1, size + 1): self.factorial[i] = (i * self.factorial[i - 1]) % self.mod self.inv_factorial = [0] * (size + 1) self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod) for i in reversed(range(size)): self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod def calc_combination(self, n, r): if n < 0 or n < r or r < 0: return 0 if r == 0 or n == r: return 1 ans = self.inv_factorial[n - r] * self.inv_factorial[r] ans %= self.mod ans *= self.factorial[n] ans %= self.mod return ans def calc_permutation(self, n, r): if n < 0 or n < r: return 0 ans = self.inv_factorial[n - r] ans *= self.factorial[n] ans %= self.mod return ans def main(): S = input() words = [0] * 26 for s in S: s_ = ord(s) - ord("a") words[s_] += 1 combi = CombinationCalculator(len(S), MOD) polies = [] for s in range(26): c = words[s] poly = [] for n in range(c + 1): poly.append(combi.inv_factorial[n]) polies.append(poly) ntt = NTT() def combo(polies, left, right): if left == right: return polies[left] elif right - left == 1: return ntt.convolution(polies[left], polies[right]) mid = (left + right) // 2 left_poly = combo(polies, left, mid) right_poly = combo(polies, mid + 1, right) return ntt.convolution(left_poly, right_poly) poly = combo(polies, 0, 25) answer = 0 for l in range(1, len(poly)): answer += (poly[l] * combi.factorial[l]) % MOD answer %= MOD print(answer) if __name__ == "__main__": main()