結果
| 問題 | No.3169 [Cherry 7th Tune] Desire for Approval |
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2025-05-05 18:50:31 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 4,494 ms / 7,000 ms |
| コード長 | 21,907 bytes |
| コンパイル時間 | 358 ms |
| コンパイル使用メモリ | 82,572 KB |
| 実行使用メモリ | 153,736 KB |
| 最終ジャッジ日時 | 2025-05-30 21:09:17 |
| 合計ジャッジ時間 | 57,795 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 |
ソースコード
"""
Mod はグローバル変数からの指定とする.
"""
"""
積
"""
def product_modulo(*X):
y=1
for x in X:
y=(x*y)%Mod
return y
"""
階乗
"""
def Factor(N):
""" 0!, 1!, ..., N! (mod Mod) を出力する.
N: int
"""
f=[1]*(N+1)
for k in range(1,N+1):
f[k]=(k*f[k-1])%Mod
return f
def Factor_with_inverse(N):
""" 0!, 1!, ..., N!, (0!)^-1, (1!)^-1, ..., (N!)^-1 を出力する.
N: int
"""
f = Factor(N)
g = [0]*(N+1)
N = min(N, Mod-1)
g[N] = pow(f[N], Mod - 2, Mod)
for k in range(N-1,-1,-1):
g[k] = ((k+1) * g[k+1]) % Mod
return f, g
def Double_Factor(N):
""" 0!!, 1!!, ..., N!! (mod Mod) を出力する.
N: int
"""
f=[1]*(N+1)
for i in range(2,N+1):
f[i]=i*f[i-2]%Mod
return f
def Modular_Inverse(N):
""" 1^(-1), 2^(-1), ..., N^(-1) (mod Mod) を出力する.
[Input]
N:int
[Output]
[-1, 1^(-1), 2^(-1), ..., N^(-1)] (第 0 要素に注意!!)
"""
inv=[1]*(N+1); inv[0]=-1
for k in range(2, N+1):
q,r=divmod(Mod,k)
inv[k]=(-q*inv[r])%Mod
return inv
"""
組み合わせの数
Factor_with_inverse で fact, fact_inv を既に求めていることが前提 (グローバル変数)
"""
def nCr(n,r):
""" nCr (1,2,...,n から相異なる r 個の整数を選ぶ方法) を求める.
n,r: int
"""
if 0<=r<=n:
return fact[n]*(fact_inv[r]*fact_inv[n-r]%Mod)%Mod
else:
return 0
def nPr(n,r):
""" nPr (1,2,...,n から相異なる r 個の整数を選び, 並べる方法) を求める.
n,r: int
"""
if 0<=r<=n:
return (fact[n]*fact_inv[n-r])%Mod
else:
return 0
def nHr(n,r):
""" nHr (1,2,...,n から重複を許して r 個の整数を選ぶ方法) を求める.
n,r: int
※ fact, fact_inv は第 n+r-1 項まで必要
"""
if n==r==0:
return 1
else:
return nCr(n+r-1,r)
def Multinomial_Coefficient(*K):
""" K=[k_0,...,k_{r-1}] に対して, k_0, ..., k_{r-1} に対する多項係数を求める.
k_i: int
"""
N=0
g_inv=1
for k in K:
N+=k
g_inv*=fact_inv[k]; g_inv%=Mod
return (fact[N]*g_inv)%Mod
def Binomial_Coefficient_Modulo_List(n: int):
""" n を固定し, r=0,1,...,n としたときの nCr (mod Mod) のリストを出力する.
n: int
[出力]
[nC0 , nC1 ,..., nCn]
"""
L=[1]*(n+1)
inv=Modular_Inverse(n+1)
for r in range(1, n+1):
L[r]=((n+1-r)*inv[r]%Mod)*L[r-1]%Mod
return L
def Pascal_Triangle(N: int, mode=False):
"""
0<=n<=N, 0<=r<=n の全てに対して nCr (mod M) のリストを出力する.
N: int
[出力]
[[0C0], [1C0, 1C1], ... , [nC0, ... , nCn], ..., [NC0, ..., NCN]]
"""
if mode:
L=[[0]*(N+1) for _ in range(N+1)]
L[0][0]=1
for n in range(1,N+1):
Ln=L[n]; Lnn=L[n-1]
Ln[0]=1
for r in range(1,N+1):
Ln[r]=(Lnn[r]+Lnn[r-1])%Mod
return L
else:
X=[1]
L=[[1]]
for n in range(N):
Y=[1]
for k in range(1, n+1):
Y.append((X[k]+X[k-1])%Mod)
Y.append(1)
X=Y
L.append(Y)
return L
def Lucas_Combination(n, r):
""" Lucas の定理を用いて nCr (mod Mod) を求める.
"""
X=1
while n or r:
ni=n%Mod; ri=r%Mod
n//=Mod; r//=Mod
if ni<ri:
return 0
beta=fact_inv[ri]*fact_inv[ni-ri]%Mod
X*=(fact[ni]*beta)%Mod
X%=Mod
return X
"""
特別な数
"""
def Catalan_Number(N):
""" Catalan 数 C(N) を求める.
注意
C(N)=(2N)!/((N+1)!N!) なので, (2N)! までの値が必要.
"""
g_inv=fact_inv[N+1]*fact_inv[N]%Mod
return fact[2*N]*g_inv%Mod
"""
等比数列
"""
def Geometric_Sequence(a, r, N):
""" k=0,1,...,N に対する a*r^k を出力する.
a,r,N: int
"""
a%=Mod; r%=Mod
X=[0]*(N+1); X[0]=a
for k in range(1,N+1):
X[k]=r*X[k-1]%Mod
return X
def Geometric_Inverse_Sequence(a, r, N):
""" k=0,1,...,N に対する a/r^k を出力する.
a,r,N: int
"""
a %= Mod; r_inv = pow(r, Mod - 2, Mod)
X = [0] * (N+1); X[0]=a
for k in range(1,N+1):
X[k] = r_inv * X[k-1] % Mod
return X
"""
積和
"""
def Sum_of_Product(*X):
""" 長さが等しいリスト X_1, X_2, ..., X_k に対して, sum(X_1[i]*X_2[i]*...*X_k[i]) を求める.
"""
S=0
for alpha in zip(*X):
S+=product_modulo(*alpha)
return S%Mod
def Sum_of_Product_Yielder(N,*Y):
S=0
M=len(Y)
for _ in range(N+1):
x=1
for j in range(M):
x*=next(Y[j]); x%=Mod
S+=x
return S%Mod
class Calculator:
def __init__(self):
self.primitive = self.__primitive_root()
self.__build_up()
def __primitive_root(self) -> int:
""" Mod の原始根を求める.
Returns:
int: Mod の原始根
"""
p = Mod
if p == 2:
return 1
if p == 998244353:
return 3
if p == 10**9 + 7:
return 5
if p == 163577857:
return 23
if p == 167772161:
return 3
if p == 469762049:
return 3
fac=[]
q=2
v=p-1
while v>=q*q:
e=0
while v%q==0:
e+=1
v//=q
if e>0:
fac.append(q)
q+=1
if v>1:
fac.append(v)
for g in range(2, p):
if pow(g, p-1, p) != 1:
return None
flag=True
for q in fac:
if pow(g, (p-1) // q, p) == 1:
flag = False
break
if flag:
return g
#参考元: https://judge.yosupo.jp/submission/72676
def __build_up(self):
rank2=(~(Mod-1) & ((Mod-1)-1)).bit_length()
root=[0]*(rank2+1); iroot=[0]*(rank2+1)
rate2=[0]*max(0, rank2-1); irate2=[0]*max(0, rank2-1)
rate3=[0]*max(0, rank2-2); irate3=[0]*max(0, rank2-2)
root[-1]=pow(self.primitive, (Mod-1)>>rank2, Mod)
iroot[-1]=pow(root[-1], -1, Mod)
for i in range(rank2)[::-1]:
root[i]=root[i+1]*root[i+1]%Mod
iroot[i]=iroot[i+1]*iroot[i+1]%Mod
prod=iprod=1
for i in range(rank2-1):
rate2[i]=root[i+2]*prod%Mod
irate2[i]=iroot[i+2]*prod%Mod
prod*=iroot[i+2]; prod%=Mod
iprod*=root[i+2]; iprod%=Mod
prod=iprod = 1
for i in range(rank2-2):
rate3[i]=root[i + 3]*prod%Mod
irate3[i]=iroot[i + 3]*iprod%Mod
prod*=iroot[i + 3]; prod%=Mod
iprod*=root[i + 3]; iprod%=Mod
self.root=root; self.iroot=iroot
self.rate2=rate2; self.irate2=irate2
self.rate3=rate3; self.irate3=irate3
def add(self, A: list[int] | int, B: list[int] | int) -> list[int]:
""" 必要ならば末尾に元を追加して, [A[i] + B[i]] を求める.
"""
if type(A) == list:
pass
elif type(A) == int:
A = [A]
else:
raise NotImplementedError
if type(B) == list:
pass
elif type(B) == int:
B = [B]
else:
raise NotImplementedError
m = min(len(A), len(B))
C = [(A[i] + B[i]) %Mod for i in range(m)]
C.extend(A[m:])
C.extend(B[m:])
return C
def sub(self, A: list[int] | int, B: list[int] | int) -> list[int]:
""" 必要ならば末尾に元を追加して, [A[i] - B[i]] を求める.
"""
if type(A) == list:
pass
elif type(A) == int:
A = [A]
else:
raise NotImplementedError
if type(B) == list:
pass
elif type(B) == int:
B = [B]
else:
raise NotImplementedError
m = min(len(A), len(B))
C = [(A[i] - B[i]) % Mod for i in range(m)]
C.extend(A[m:])
C.extend([-b % Mod for b in B[m:]])
return C
def times(self, A: list[int], k: int) -> list[int]:
""" [k * A[i]] を求める.
"""
return [k * a % Mod for a in A]
#参考元 https://judge.yosupo.jp/submission/72676
def ntt(self, A: list[int]):
""" A に Mod を法とする数論変換を施す
※ Mod はグローバル変数から指定
References:
https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
https://judge.yosupo.jp/submission/72676
"""
N=len(A)
H=(N-1).bit_length()
l=0
I=self.root[2]
rate2=self.rate2; rate3=self.rate3
while l<H:
if H-l==1:
p=1<<(H-l-1)
rot=1
for s in range(1<<l):
offset=s<<(H-l)
for i in range(p):
x=A[i+offset]; y=A[i+offset+p]*rot%Mod
A[i+offset]=(x+y)%Mod
A[i+offset+p]=(x-y)%Mod
if s+1!=1<<l:
rot*=rate2[(~s&-~s).bit_length()-1]
rot%=Mod
l+=1
else:
p=1<<(H-l-2)
rot=1
for s in range(1<<l):
rot2=rot*rot%Mod
rot3=rot2*rot%Mod
offset=s<<(H-l)
for i in range(p):
a0=A[i+offset]
a1=A[i+offset+p]*rot
a2=A[i+offset+2*p]*rot2
a3=A[i+offset+3*p]*rot3
alpha=(a1-a3)%Mod*I
A[i+offset]=(a0+a2+a1+a3)%Mod
A[i+offset+p]=(a0+a2-a1-a3)%Mod
A[i+offset+2*p]=(a0-a2+alpha)%Mod
A[i+offset+3*p]=(a0-a2-alpha)%Mod
if s+1!=1<<l:
rot*=rate3[(~s&-~s).bit_length()-1]
rot%=Mod
l+=2
#参考元 https://judge.yosupo.jp/submission/72676
def inverse_ntt(self, A):
""" A を Mod を法とする逆数論変換を施す
※ Mod はグローバル変数から指定
References:
https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
https://judge.yosupo.jp/submission/72676
"""
N=len(A)
H=(N-1).bit_length()
l=H
J=self.iroot[2]
irate2=self.rate2; irate3=self.irate3
while l:
if l==1:
p=1<<(H-l)
irot=1
for s in range(1<<(l-1)):
offset=s<<(H-l+1)
for i in range(p):
x=A[i+offset]; y=A[i+offset+p]
A[i+offset]=(x+y)%Mod
A[i+offset+p]=(x-y)*irot%Mod
if s+1!=1<<(l-1):
irot*=irate2[(~s&-~s).bit_length()-1]
irot%=Mod
l-=1
else:
p=1<<(H-l)
irot=1
for s in range(1<<(l-2)):
irot2=irot*irot%Mod
irot3=irot2*irot%Mod
offset=s<<(H-l+2)
for i in range(p):
a0=A[i+offset]
a1=A[i+offset+p]
a2=A[i+offset+2*p]
a3=A[i+offset+3*p]
beta=(a2-a3)*J%Mod
A[i+offset]=(a0+a1+a2+a3)%Mod
A[i+offset+p]=(a0-a1+beta)*irot%Mod
A[i+offset+2*p]=(a0+a1-a2-a3)*irot2%Mod
A[i+offset+3*p]=(a0-a1-beta)*irot3%Mod
if s+1!=1<<(l-2):
irot*=irate3[(~s&-~s).bit_length()-1]
irot%=Mod
l-=2
N_inv=pow(N, -1, Mod)
for i in range(N):
A[i]=N_inv*A[i]%Mod
def non_zero_count(self, A: list[int]) -> int:
""" A にある非零要素の個数を求める.
Args:
A (list[int]):
Returns:
int: 非零要素の個数
"""
return len(A) - A.count(0)
def is_sparse(self, A: list[int], threshold: int = 25) -> bool:
"""A が疎かどうかを判定する.
Args:
A (list[int]):
threshold (int, optional): 非零要素の個数が threshold 以下ならば疎と判定する. Defaults to 25.
Returns:
bool: 疎?
"""
return self.non_zero_count(A) <= threshold
def coefficients_list(self, A: list[int]) -> tuple[list[int], list[int]]:
""" A にある非零要素のリストを求める.
Args:
A (list[int]):
Returns:
tuple[list[int], list[int]]: ([d[0], ..., d[k-1]], [f[0], ..., f[k-1]]) の形のリスト.
j = 0, 1, ..., k - 1 に対して, a[d[j]] = f[j] であることを意味する.
"""
f = []; d = []
for i in range(len(A)):
if A[i] == 0:
continue
d.append(i)
f.append(A[i])
return d, f
def convoluton_greedy(self, A: list[int], B: list[int]) -> list[int]:
""" 畳み込み積 A * B を愚直な方法で求める.
Args:
A (list[int]):
B (list[int]):
Returns:
list[int]: 畳み込み積 A * B
"""
if len(A) < len(B):
A, B = B, A
n = len(A)
m = len(B)
C = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
C[i + j] += A[i] * B[j] % Mod
for k in range(n + m - 1):
C[k] %= Mod
return C
def convolution(self, A: list[int], B: list[int]) -> list[int]:
""" 畳み込み積 A * B を求める.
Args:
A (list[int]):
B (list[int]):
Returns:
list[int]: 畳み込み積 A * B
"""
if (not A) or (not B):
return []
N=len(A)
M=len(B)
L=M+N-1
if min(N,M)<=50:
return self.convoluton_greedy(A, B)
H=L.bit_length()
K=1<<H
A=A+[0]*(K-N)
B=B+[0]*(K-M)
self.ntt(A)
self.ntt(B)
for i in range(K):
A[i]=A[i]*B[i]%Mod
self.inverse_ntt(A)
return A[:L]
def autocorrelation(self, A: list[int]) -> list[int]:
""" 自分自身との畳み込み積を求める.
Args:
A (list[int]):
Returns:
list[int]: 畳み込み積 A * A
"""
N=len(A)
L=2*N-1
if N<=50:
C=[0]*L
for i in range(N):
for j in range(N):
C[i+j]+=A[i]*A[j]
C[i+j]%=Mod
return C
H=L.bit_length()
K=1<<H
A=A+[0]*(K-N)
self.ntt(A)
for i in range(K):
A[i]=A[i]*A[i]%Mod
self.inverse_ntt(A)
return A[:L]
def multiple_convolution(self, *A: list[int]) -> list[int]:
""" A = (A[0], A[1], ..., A[k - 1]) に対して, この k 個の畳み込み積 A[0] * A[1] * ... * A[k - 1] を求める.
Args:
A (list[list[int]]): 畳み込む k 個の整数のリスト
Returns:
list[int]: k 個の畳み込み積 A[0] * A[1] * ... * A[k - 1]
"""
from collections import deque
if not A:
return [1]
Q=deque(list(range(len(A))))
A=list(A)
while len(Q)>=2:
i=Q.popleft(); j=Q.popleft()
A[i]=self.convolution(A[i], A[j])
A[j]=None
Q.append(i)
i=Q.popleft()
return A[i]
def inverse(self, F: list[int], length: int = None) -> list[int]:
""" F * G = [1, 0, 0, ..., 0] (0 が (length - 1) 個) を満たす長さ length のリスト G を求める.
Args:
F (list[int]):
length (int, optional): 求める G の長さ. None のときは length = len(F) とする. Defaults to None.
Returns:
list[int]: _description_
"""
M = len(F) if length is None else length
if M <= 0:
return []
if self.is_sparse(F):
# 愚直に漸化式を用いて求める.
# 計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間
d,f=self.coefficients_list(F)
G=[0]*M
alpha=pow(F[0], -1, Mod)
G[0]=alpha
for i in range(1, M):
for j in range(1, len(d)):
if d[j]<=i:
G[i]+=f[j]*G[i-d[j]]%Mod
else:
break
G[i]%=Mod
G[i]=(-alpha*G[i])%Mod
del G[M:]
else:
# FFTの理論を応用して求める.
# 計算量: 求めたい項の個数をNとして, O(N log N)
# Reference: https://judge.yosupo.jp/submission/42413
N=len(F)
r=pow(F[0], -1, Mod)
m=1
G=[r]
while m<M:
A=F[:min(N, 2*m)]; A+=[0]*(2*m-len(A))
B=G.copy(); B+=[0]*(2*m-len(B))
Calc.ntt(A); Calc.ntt(B)
for i in range(2*m):
A[i]=A[i]*B[i]%Mod
Calc.inverse_ntt(A)
A=A[m:]+[0]*m
Calc.ntt(A)
for i in range(2*m):
A[i]=-A[i]*B[i]%Mod
Calc.inverse_ntt(A)
G.extend(A[:m])
m<<=1
G=G[:M]
return G
def flood_div(self, F: list[int], G: list[int]) -> list[int]:
assert F[-1]
assert G[-1]
F_deg=len(F)-1
G_deg=len(G)-1
if F_deg<G_deg:
return []
m=F_deg-G_deg+1
return self.convolution(F[::-1], Calc.inverse(G[::-1],m))[m-1::-1]
def mod(self, F: list[int], G: list[int]) -> list[int]:
while F and F[-1] == 0:
F.pop()
while G and G[-1] == 0:
G.pop()
if not F:
return []
return Calc.sub(F, Calc.convolution(Calc.flood_div(F, G), G))
#==================================================
class Exponent_Polynomial:
def __init__(self, exponent: int, polynomial: list[int]):
self.exponent = exponent % Mod
self.polynomial = polynomial
def __repr__(self) -> str:
return f"{self.__class__.__name__}({self.exponent}, {self.polynomial})"
def __add__(self, other: "Exponent_Polynomial"):
assert self.exponent == other.exponent
return Exponent_Polynomial(self.exponent, Calc.add(self.exponent, other.exponent))
def __mul__(self, other: "Exponent_Polynomial") -> "Exponent_Polynomial":
return Exponent_Polynomial((self.exponent + other.exponent) % Mod, Calc.convolution(self.polynomial, other.polynomial))
def differential(self) -> "Exponent_Polynomial":
diff_poly = [0] * len(self.polynomial)
for d in range(len(self.polynomial)):
diff_poly[d - 1] += d * self.polynomial[d] % Mod
diff_poly[d] += self.exponent * self.polynomial[d] % Mod
return Exponent_Polynomial(self.exponent, [a % Mod for a in diff_poly])
def integrate_zero_to_infinity(self) -> int:
if self.exponent == 0 and all(a == 0 for a in self.polynomial):
return 0
res = 0
t = pow(-self.exponent, -1, Mod)
alpha = 1
for d in range(len(self.polynomial)):
alpha *= t; alpha %= Mod
coef = fact[d] * alpha % Mod
res += coef * self.polynomial[d] % Mod
return res % Mod
def push(self) -> "Exponent_Polynomial":
return Exponent_Polynomial(self.exponent, [0] + self.polynomial)
#==================================================
def solve():
from itertools import product as product_iter
N = int(input())
k = [0] * N; a = [0] * N
for i in range(N):
k[i], a[i] = map(int, input().split())
global fact, fact_inv
fact, fact_inv = Factor_with_inverse(sum(k) + N)
exp_polys: list[Exponent_Polynomial] = [None] * N
for i in range(N):
b = pow(a[i], -1, Mod)
poly = [fact_inv[t] * pow(a[i], -t, Mod) % Mod for t in range(k[i])]
exp_polys[i] = Exponent_Polynomial(-b, poly)
product: list[Exponent_Polynomial] = [None] * (1 << N)
product[0] = Exponent_Polynomial(0, [1])
expectation = [0] * (1 << N)
for S in range(1, 1 << N):
x = S & (-S)
i = x.bit_length() - 1
product[S] = product[S ^ x] * exp_polys[i]
expectation[S] = product[S].differential().push().integrate_zero_to_infinity() % Mod
E_pre = [0] * (N + 1)
for W in product_iter(range(3), repeat = N):
S = T = U = 0
for i in range(N):
if W[i] == 0:
S |= 1 << i
elif W[i] == 1:
T |= 1 << i
elif W[i] == 2:
U |= 1 << i
deg = (S | T).bit_count()
E_pre[deg] += pow(-1, T.bit_count(), Mod) * expectation[T | U] % Mod
return [sum(E_pre[m:]) % Mod for m in range(1, N + 1)]
#==================================================
Mod = 998244353
Calc = Calculator()
print(*solve())