結果
問題 |
No.3169 [Cherry 7th Tune] Desire for Approval
|
ユーザー |
![]() |
提出日時 | 2025-05-30 22:46:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,573 ms / 7,000 ms |
コード長 | 13,272 bytes |
コンパイル時間 | 1,031 ms |
コンパイル使用メモリ | 82,104 KB |
実行使用メモリ | 161,312 KB |
最終ジャッジ日時 | 2025-05-30 22:47:58 |
合計ジャッジ時間 | 57,526 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
from __future__ import annotations input class CombLUT: MOD = 998_244_353 _max = 0 F = [1] InvF = [1] _fibo = [0, 1] _lucas = [2, 1] @classmethod def expand(cls, n): if n <= cls._max: return n = n*4//3 cls.F.extend([1]*(n - cls._max)) for i in range(cls._max + 1, n+1): cls.F[i] = cls.F[i-1] * i % cls.MOD cls.InvF.extend([1]*(n - cls._max)) cls.InvF[n] = pow(cls.F[n], -1, cls.MOD) for i in range(n-1, cls._max, -1): cls.InvF[i] = cls.InvF[i+1] * (i+1) % cls.MOD cls._max = n @classmethod def comb(cls, n, r): if not (0 <= r <= n): return 0 if n > cls._max: cls.expand(n) return cls.F[n] * cls.InvF[r] % cls.MOD * cls.InvF[n-r] % cls.MOD @classmethod def hyper_comb(cls, n, r): if (r < 0): return 0 if (n < 0): return 0 if n == r == 0: return 1 if not (0 <= r <= n-1+r): return 0 return cls.comb(n-1+r, r) @classmethod def neg_hyper_comb(cls, n, r): if (r < 0): return 0 if n >= 0: return cls.hyper_comb(n, r) sgn = -1 if r&1 else 1 return sgn * cls.comb(-n, r) @classmethod def factorial(cls, n): assert 0 <= n if n > cls._max: cls.expand(n) return cls.F[n] @classmethod def inv_factorial(cls, n): assert 0 <= n if n > cls._max: cls.expand(n) return cls.InvF[n] def subset_sum(A, *, func=None, initial=None): if (func is None): if initial is None: initial = 0 N = len(A) dp = [initial] * (1<<N) for h in range(N): for S in range(1<<h): dp[S|(1<<h)] = dp[S] + A[h] return dp else: assert (initial is not None) N = len(A) dp = [initial] * (1<<N) for h in range(N): for S in range(1<<h): dp[S|(1<<h)] = func(dp[S], A[h]) return dp class Convolution: """ A class to perform convolution using the Fast Fourier Transform (FFT) algorithm. Attributes: _mod (int): A prime modulus used for modular arithmetic. Defaults to 998244353. _rank2 (int): The highest power of 2 dividing (mod - 1). _root (int): A primitive root of the modulus. _imag (int): Imaginary unit under the modulus. _iimag (int): Inverse of the imaginary unit under the modulus. _rate2 (tuple[int]): Precomputed powers of the primitive root, used for the FFT. _irate2 (tuple[int]): Precomputed inverse powers of the primitive root. _rate3 (tuple[int]): Precomputed powers of the primitive root for 3rd roots of unity. _irate3 (tuple[int]): Precomputed inverse powers for 3rd roots of unity. Note: This class uses a fixed modulus (998244353) by default. The modulus can be changed using the set_mod method, but be aware that changing the modulus can result in a significant performance drop on pypy. This is because, for the default modulus, division operations are optimized as constant divisions on pypy, but for custom moduli, these optimizations are not applied. """ _mod = 998244353 _rank2 = 23 _root = 3 _imag = 911660635 _iimag = 86583718 _rate2 = ( 911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899 ) _irate2 = ( 86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235 ) _rate3 = ( 372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099, 183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204 ) _irate3 = ( 509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500, 771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681 ) @classmethod def set_mod(cls, mod: int) -> None: """ Sets a new modulus and recalculates the associated parameters. Args: mod (int): The new prime modulus. """ cls._mod = mod cls._root = PrimeFactor.primitive_root(mod) cls._rank2 = tzcount(mod-1) root = [0]*(cls._rank2 + 1) iroot = [0]*(cls._rank2 + 1) root[cls._rank2] = pow(cls._root, (mod-1)>>cls._rank2, mod) iroot[cls._rank2] = pow(root[cls._rank2], mod-2, mod) for i in range(cls._rank2 - 1, -1, -1): root[i] = root[i+1] * root[i+1] % mod iroot[i] = iroot[i+1] * iroot[i+1] % mod cls._imag = root[2] cls._iimag = iroot[2] cls._rate2, cls._irate2 = cls.__calculate_rates(root, iroot, 2) cls._rate3, cls._irate3 = cls.__calculate_rates(root, iroot, 3) @classmethod def __calculate_rates(cls, root: list, iroot: list, ofs: int) -> tuple: """ Calculates the rates used in the butterfly transformations. Args: root (list): List of roots. iroot (list): List of inverse roots. ofs (int): Offset to start calculation. Returns: tuple: A tuple containing two lists: rates and inverse rates. """ rate = [0]*max(0, cls._rank2 - (ofs-1)) irate = [0]*max(0, cls._rank2 - (ofs-1)) prod, iprod = 1, 1 for i in range(cls._rank2 - (ofs-1)): rate[i] = root[i + ofs] * prod % cls._mod irate[i] = iroot[i + ofs] * iprod % cls._mod prod *= iroot[i + ofs] prod %= cls._mod iprod *= root[i + ofs] iprod %= cls._mod return rate, irate @classmethod def butterfly(cls, a: list[int]) -> None: """ Applies the butterfly transformation on the input list. Args: a (list[int]): The input list. """ n = len(a) h = (n-1).bit_length() for len_ in range(0, h-1, 2): p = 1<<(h - len_ - 2) rot = 1 for s in range(1<<len_): rot2 = rot*rot%cls._mod rot3 = rot2*rot%cls._mod offset = s<<(h - len_) for i in range(p): a0 = a[i + offset] a1 = a[i + offset + p] * rot % cls._mod a2 = a[i + offset + p*2] * rot2 % cls._mod a3 = a[i + offset + p*3] * rot3 % cls._mod a1na3imag = (a1-a3) * cls._imag % cls._mod a[i + offset] = (a0+a2+a1+a3) % cls._mod a[i + offset + p] = (a0+a2-a1-a3) % cls._mod a[i + offset + p*2] = (a0-a2 + a1na3imag) % cls._mod a[i + offset + p*3] = (a0-a2 - a1na3imag) % cls._mod if s+1 != 1<<len_: rot *= cls._rate3[(~s& -~s).bit_length() - 1] rot %= cls._mod if h&1: rot = 1 for s in range(1<<(h-1)): offset = s<<1 l = a[offset] r = a[offset + 1] * rot % cls._mod a[offset] = (l+r) % cls._mod a[offset + 1] = (l-r) % cls._mod if s+1 != 1<<(h-1): rot *= cls._rate2[(~s& -~s).bit_length() - 1] rot %= cls._mod @classmethod def butterfly_inv(cls, a: list[int]) -> None: """ Applies the inverse butterfly transformation on the input list. Args: a (list[int]): The input list. """ n = len(a) h = (n-1).bit_length() for len_ in range(h, 1, -2): p = 1<<(h - len_) irot = 1 for s in range(1<<(len_-2)): irot2 = irot*irot%cls._mod irot3 = irot2*irot%cls._mod offset = s<<(h - len_ + 2) for i in range(p): a0 = a[i + offset] a1 = a[i + offset + p] a2 = a[i + offset + p*2] a3 = a[i + offset + p*3] a2na3iimag = (a2-a3) * cls._iimag % cls._mod a[i + offset] = (a0+a1+a2+a3) % cls._mod a[i + offset + p] = (a0-a1 + a2na3iimag) * irot % cls._mod a[i + offset + p*2] = (a0+a1-a2-a3) * irot2 % cls._mod a[i + offset + p*3] = (a0-a1 - a2na3iimag) * irot3 % cls._mod if s+1 != (1<<(len_-2)): irot *= cls._irate3[(~s& -~s).bit_length() - 1] irot %= cls._mod if h&1: p = 1<<(h-1) for i in range(p): l = a[i] r = a[i+p] a[i] = (l+r) % cls._mod a[i+p] = (l-r) % cls._mod @classmethod def convolution(cls, a: list[int], b: list[int]) -> list[int]: """ Computes the convolution of two lists. Args: a (list[int]): First input list. b (list[int]): Second input list. Returns: list[int]: The convolution of a and b. Raises: ValueError: If the length of the result exceeds the supported length. """ n, m = len(a), len(b) if n+m-1 > (1<<cls._rank2): raise ValueError('rank2 of given mod is too small.') if not n or not m: return [] z = 1<<(n+m-2).bit_length() a = a + [0] * (z-n) b = b + [0] * (z-m) cls.butterfly(a) cls.butterfly(b) for i in range(z): a[i] *= b[i] a[i] %= cls._mod cls.butterfly_inv(a) a = a[:n+m-1] iz = pow(z, -1, cls._mod) for i in range(n+m-1): a[i] *= iz a[i] %= cls._mod return a def dummy_frac(MOD=998_244_353, U=10**6): dp = [0, 1] dp += [0]*(U+1 - len(dp)) for x in range(2, U+1): q, r = divmod(MOD, x) if dp[r] == 0: dp[x] = pow(x, -1, MOD) else: dp[x] = -(q) * dp[r] % MOD memo = {} def F(a=0, b=1): if not 1 <= b <= U: b %= MOD if b == 0: raise ZeroDivisionError if b == 1: return a if 1 <= b <= U: return a * dp[b] % MOD inv = memo.get(b) if inv is None: memo[b] = inv = pow(b, -1, MOD) return a*inv%MOD return F Fraction = dummy_frac() class ExpPoly: def __init__(self, lamda, coef: list[Fraction]): self.lamda = lamda self.coef = coef def __add__(self, other): raise NotImplementedError def __mul__(self, other: "int|Fraction|ExpPoly"): if isinstance(other, int): return ExpPoly(self.lamda, [c*other for c in self.coef]) else: assert isinstance(other, ExpPoly) nshift = self.lamda + other.lamda # ncoef = convolution_naive(self.coef, other.coef, MOD=998_244_353) # type: ignore ncoef = Convolution.convolution(self.coef, other.coef) return ExpPoly(nshift, ncoef) def __rmul__(self, other: "int|Fraction"): return self.__mul__(other) def integral(self): res = Fraction(0) pows = powers(pow(self.lamda, -1, MOD), len(self.coef) + 10, MOD=998_244_353) for n in range(len(self.coef)): c = self.coef[n] # res += c * CombLUT.factorial(n) % MOD * pow(self.lamda, -(n+1), MOD) % MOD res += c * CombLUT.factorial(n) % MOD * pows[n+1] % MOD res %= MOD return res def powers(base, maxexp: int|float, MOD: int|None = None, *, negative: bool = False): maxexp = int(maxexp) if maxexp < 0: maxexp = 0 if MOD is None: return [pow(base, exp) for exp in range(maxexp + 1)] else: base %= MOD res = [1%MOD] * (maxexp + 1) res[1] = base for exp in range(2, maxexp + 1): res[exp] = res[exp-1] * base % MOD return res def bit_count(x): x = x - ((x>>1)&0x5555_5555_5555_5555) x = (x&0x3333_3333_3333_3333) + ((x>>2)&0x3333_3333_3333_3333) x = (x + (x>>4))&0x0f0f_0f0f_0f0f_0f0f x += (x>>8) x += (x>>16) x += (x>>32) return x&0x0000_0000_0000_007f def solve(N, K, A): def resolve(k, a): lamda = Fraction(1, a) coef = [Fraction(0)] * k pows = powers(lamda, k+10, MOD=998_244_353) for n in range(k): # coef[n] = pow(lamda, n, MOD) * CombLUT.inv_factorial(n) coef[n] = pows[n] * CombLUT.inv_factorial(n) % MOD return ExpPoly(lamda, coef) F = [resolve(k, a) for k, a in zip(K, A)] dp = subset_sum(F, func=lambda x, y: x*y, initial=1) I = [f.integral() if isinstance(f, ExpPoly) else 0 for f in dp] popcnt = [Fraction(0)] * (N+1) for S in range(1<<N): cnt = bit_count(S) popcnt[cnt] += I[S] res = [Fraction(0)] * (N+1) for k in range(1, N+1): for i in range(k, N+1): h = CombLUT.hyper_comb(k+1, i-k) h *= (-1)**(i-k) res[k] += h * popcnt[i] res[k] %= MOD return res MOD = 998_244_353 N = int(input()) K, A = [], [] for _ in range(N): k, a = map(int, input().split()) K.append(k) A.append(a) ans = solve(N, K, A) ans.pop(0) ans.reverse() from itertools import accumulate ans = list(accumulate(ans)) ans = [x%MOD for x in ans] print(*ans)