結果

問題 No.3169 [Cherry 7th Tune] Desire for Approval
ユーザー 👑 Kazun
提出日時 2023-10-29 02:19:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,267 ms / 7,000 ms
コード長 18,541 bytes
コンパイル時間 699 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 152,756 KB
最終ジャッジ日時 2025-05-30 21:04:13
合計ジャッジ時間 56,607 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #

"""
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):
        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)

        g=2
        while g<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

            g+=1

    #参考元: 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, B):
        """ 必要ならば末尾に元を追加して, [A[i]+B[i]] を求める.

        """
        if type(A)==int:
            A=[A]

        if type(B)==int:
            B=[B]

        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, B):
        """ 必要ならば末尾に元を追加して, [A[i]-B[i]] を求める.

        """
        if type(A)==int:
            A=[A]

        if type(B)==int:
            B=[B]

        m=min(len(A), len(B))
        C=[0]*m
        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, k):
        """ [k*A[i]] を求める.

        """
        return [k*a%Mod for a in A]

    #参考元 https://judge.yosupo.jp/submission/72676
    def 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=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):
        """ A にある非零の数を求める. """
        return len(A)-A.count(0)

    def is_sparse(self, A, K=None):
        """ A が疎かどうかを判定する. """

        if K==None:
            K=25

        return self.non_zero_count(A)<=K

    def coefficients_list(self, A):
        """ A にある非零のリストを求める.


        output: ( [d[0], ..., d[k-1] ], [f[0], ..., f[k-1] ]) : a[d[j]]=f[j] であることを表している.
        """

        f=[]; d=[]
        for i in range(len(A)):
            if A[i]:
                d.append(i)
                f.append(A[i])
        return d,f

    def Convolution(self, A, B):
        """ A, B で Mod を法とする畳み込みを求める.

        ※ Mod はグローバル変数から指定
        """
        if not A or not B:
            return []

        N=len(A)
        M=len(B)
        L=M+N-1

        if min(N,M)<=50:
            if N<M:
                N,M=M,N
                A,B=B,A
            C=[0]*L
            for i in range(N):
                for j in range(M):
                    C[i+j]+=A[i]*B[j]
                    C[i+j]%=Mod
            return C

        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):
        """ A 自身に対して,Mod を法とする畳み込みを求める.

        ※ Mod はグローバル変数から指定
        """
        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):
        """ A=(A[0], A[1], ..., A[d-1]) で Mod を法とする畳み込みを行う.

        """

        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, length=None):
        if length==None:
            M=len(F)
        else:
            M=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 Floor_Div(self, F, G):
        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, G):
        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.Floor_Div(F,G),G))

#==================================================
class Exp_Poly:
    def __init__(self, b, poly):
        self.b = b
        self.poly = poly

    def __mul__(self, other):
        return Exp_Poly((self.b + other.b) % Mod, Calc.Convolution(self.poly, other.poly))

    def __repr__(self):
        return f"({self.b}, {self.poly})"

def expection(exp_poly):
    total = 0
    b = exp_poly.b
    poly = exp_poly.poly

    if b == 0:
        return 0

    b_inv = pow(b, Mod-2, Mod)
    b_inv_prod = b_inv
    for k, c in enumerate(poly):
        tmp = c * fact[k] % Mod
        total += tmp * (- b_inv_prod) % Mod; total %= Mod
        b_inv_prod *= b_inv; b_inv_prod %= Mod
    return total

def popcount(S):
    pop = 0
    while S:
        pop += 1
        x = S & (-S)
        S ^= x
    return pop

def solve():
    from itertools import product

    N = int(input())

    k = [0] * N; a = [0] * N
    for i in range(N):
        k[i], a[i] = map(int, input().split())

    global Mod, fact, fact_inv, inv, Calc
    Mod = 998244353
    Calc = Calculator()

    fact, fact_inv = Factor_with_inverse(sum(k))
    inv = Modular_Inverse(20)

    EP = [None] * N
    for i in range(N):
        EP[i] = Exp_Poly(pow(a[i], Mod - 2, Mod), [fact_inv[t] * pow(a[i], (Mod - 2) * t, Mod) % Mod for t in range(k[i])])

    prod = [None for _ in range(1 << N)]
    prod[0] = Exp_Poly(0, [1])

    D = [0] * (1 << N); D[0] = expection(prod[0])
    for S in range(1, 1 << N):
        x = S & (-S)
        i = x.bit_length() - 1
        prod[S] = prod[S ^ x] * EP[i]
        D[S] = expection(prod[S])

    E_pre = [0] * (N + 1)
    for V in product([0, 1, 2], repeat = N):
        S = T = U = 0
        for i in range(N):
            if V[i] == 0:
                S |= 1 << i
            elif V[i] == 1:
                T |= 1 << i
            else:
                U |= 1 << i

        deg = popcount(S | T)
        E_pre[deg] += pow(-1, popcount(T), Mod) * D[T | U]
        E_pre[deg] %= Mod

    E = [0] * (N + 1)
    E[N] = E_pre[N]
    for d in range(N-1, -1, -1):
        E[d] = (E[d + 1] + E_pre[d]) % Mod

    return E[1:]

#==================================================
print(*solve())
0