結果
| 問題 |
No.3169 [Cherry 7th Tune] Desire for Approval
|
| コンテスト | |
| ユーザー |
 dp_ijk
|
| 提出日時 | 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)