結果

問題 No.1549 [Cherry 2nd Tune] BANning Tuple
ユーザー 👑 KazunKazun
提出日時 2021-06-08 01:06:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,722 ms / 4,000 ms
コード長 17,654 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 107,368 KB
最終ジャッジ日時 2024-05-08 16:28:24
合計ジャッジ時間 27,695 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 207 ms
79,984 KB
testcase_01 AC 232 ms
78,996 KB
testcase_02 AC 1,465 ms
103,752 KB
testcase_03 AC 1,397 ms
103,064 KB
testcase_04 AC 1,388 ms
104,208 KB
testcase_05 AC 1,406 ms
103,508 KB
testcase_06 AC 1,410 ms
102,796 KB
testcase_07 AC 1,463 ms
104,584 KB
testcase_08 AC 1,497 ms
105,248 KB
testcase_09 AC 1,454 ms
104,156 KB
testcase_10 AC 1,435 ms
104,184 KB
testcase_11 AC 1,505 ms
105,412 KB
testcase_12 AC 1,543 ms
105,040 KB
testcase_13 AC 1,509 ms
105,784 KB
testcase_14 AC 1,506 ms
105,536 KB
testcase_15 AC 1,466 ms
104,328 KB
testcase_16 AC 1,470 ms
105,704 KB
testcase_17 AC 1,185 ms
99,420 KB
testcase_18 AC 1,184 ms
99,296 KB
testcase_19 AC 1,722 ms
107,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

class Modulo_Polynominal():
    __slots__=["Poly","Max_Degree","Char","minus"]
    def __init__(self,Poly,Max_Degree=2*10**5,Char="X"):
        from itertools import zip_longest
        """多項式の定義

        P:係数のリスト
        C:文字
        Max_Degree

        ※Mod:法はグローバル変数から指定
        """
        self.Poly=[p%Mod for p in Poly[:Max_Degree]]
        self.Char=Char
        self.Max_Degree=Max_Degree
        self.minus=10**7

    def __str__(self):
        if bool(self):
            M=[(k,a) for k,a in enumerate(self.Poly) if a]
            for i in range(len(M)):
                k,a=M[i]
                if Mod-a<=self.minus:
                    M[i]=(k,a-Mod)


            A=["{} {} ^ {} ".format(a,self.Char,k) for k,a in M]
            S=" "+" + ".join(A)
            S=S.replace(" + -"," - ")
            S=S.replace(" {} ^ 0 ".format(self.Char),"")
            S=S.replace(" {} ^ 1 ".format(self.Char)," "+self.Char+" ")
            S=S.replace(" 1 {} ".format(self.Char),self.Char+" ")
            S=S.replace(" -1 {} ".format(self.Char),"-"+self.Char+" ") 
            S=S.replace(" ","")
        else:
            S="0"

        S+=" (mod (Z/ {0} Z)[{1}]/ ({1}^{2}))".format(Mod,self.Char,self.Max_Degree)
        return S.strip()

    def __repr__(self):
        return self.__str__()

    #=
    def __eq__(self,other):
        if self.Max_Degree!=other.Max_Degree:
            return False

        from itertools import zip_longest
        return all([a==b for a,b in zip_longest(self.Poly,other.Poly,fillvalue=0)])
    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return self.scale(-1)

    #Boole
    def __bool__(self):
        return any(self.Poly)

    #簡略化
    def reduce(self):
        P_deg=self.degree()

        if not(P_deg>=0):
            self.Poly=[0]
            self.censor(self.Max_Degree)
            return

        for i in range(self.degree(),-1,-1):
            if self.Poly[i]:
                self.Poly=self.Poly[:i+1]
                self.censor(self.Max_Degree)
                return
        self.Poly=[]
        return

    #シフト
    def __lshift__(self,other):
        if other<0:
            return self>>(-other)

        if other>self.Max_Degree:
            return Modulo_Polynominal([0],self.Max_Degree,self.Char)

        G=[0]*other+self.Poly
        return Modulo_Polynominal(G,self.Max_Degree,self.Char)

    def __rshift__(self,other):
        if other<0:
            return  self<<(-other)

        return Modulo_Polynominal(self.Poly[other:],self.Max_Degree,self.Char)

    #次数
    def degree(self):
        d=len(self.Poly)-1
        for y in self.Poly[::-1]:
            if y:
                return d
            d-=1
        return -float("inf")

    #加法
    def __add__(self,other):
        P=self
        Q=other

        if Q.__class__==Modulo_Polynominal:
            from itertools import zip_longest
            N=min(P.Max_Degree,Q.Max_Degree)
            R=[(a+b)%Mod for (a,b) in zip_longest(P.Poly,Q.Poly,fillvalue=0)]
            return Modulo_Polynominal(R,N,P.Char)
        else:
            P_deg=P.degree()
            if P_deg<0:P_deg=0
            R=[0]*(P_deg+1)

            R=[p for p in P.Poly]
            R[0]=(R[0]+Q)%Mod

            R=Modulo_Polynominal(R,P.Max_Degree,P.Char)
            R.reduce()
            return R

    def __radd__(self,other):
        return self+other

    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        return (-self)+other

    #乗法
    def __mul__(self,other):
        P=self
        Q=other
        if Q.__class__==Modulo_Polynominal:
            a=b=0
            for x in P.Poly:
                if x:
                    a+=1
            for y in Q.Poly:
                if y:
                    b+=1

            if a>b:
                P,Q=Q,P

            P.reduce();Q.reduce()
            U,V=P.Poly,Q.Poly
            M=min(P.Max_Degree,Q.Max_Degree)
            if a<2*P.Max_Degree.bit_length():
                B=[0]*(len(U)+len(V)-1)
                for i in range(len(U)):
                    if U[i]:
                        for j in range(len(V)):
                            B[i+j]+=U[i]*V[j]
                            if B[i+j]>Mod:
                                B[i+j]-=Mod
            else:
                B=Convolution_Mod(U,V)[:M]
            B=Modulo_Polynominal(B,M,self.Char)
            B.reduce()
            return B
        else:
            return self.scale(other)

    def __rmul__(self,other):
        return self.scale(other)

    #除法
    def __floordiv__(self,other):
        if not other:
            raise ZeroDivisionError
        if isinstance(other,int):
            return self/other

        F,G=self,other
        N=min(F.Max_Degree,G.Max_Degree)
        F_deg=F.degree()
        G_deg=G.degree()

        if F_deg<G_deg:
            A=Modulo_Polynominal([0],N,self.Char)
            A.reduce()
            return A

        G.reduce()
        F_inv=Modulo_Polynominal(F.Poly[::-1],F.Max_Degree,F.Char)
        G_inv=Modulo_Polynominal(G.Poly[::-1],F.Max_Degree,F.Char)

        H=F_inv/G_inv
        H.censor(F_deg-G_deg+1)
        return Modulo_Polynominal(H.Poly[::-1],N,self.Char)

    def __rfloordiv__(self,other):
        if not self:
            raise ZeroDivisionError

        if isinstance(other,int):
            return Modulo_Polynominal([0],self.Max_Degree,self.Char)

    #剰余
    def __mod__(self,other):
        if not other:
            return ZeroDivisionError
        return self-(self//other)*other

    def __rmod__(self,other):
        if not self:
            raise ZeroDivisionError
        return other-(other//self)*self

    def __divmod__(self,other):
        p=self//other
        return (p,self-other*p)

    #累乗
    def __pow__(self,other):
        if other.__class__==int:
            n=other
            m=abs(n)

            Q=self
            A=Modulo_Polynominal([1],self.Max_Degree,self.Char)
            while m>0:
                if m&1:
                    A*=Q
                m>>=1
                Q*=Q

            if n>=0:
                return A
            else:
                return A.__inv__()
        else:
            P=Log(self)
            return Exp(P*other)

    #逆元
    def __inv__(self,deg=None):
        assert self.Poly[0],"定数項が0"

        P=self
        if len(P.Poly)<=P.Max_Degree.bit_length():
            """
            愚直に漸化式を用いて求める.
            計算量:Pの次数をK, 求めたい項の個数をNとして, O(NK)
            """
            F=P.Poly
            c=F[0]
            c_inv=pow(c,Mod-2,Mod)

            N=len(P.Poly)
            R=[-c_inv*a%Mod for a in F[1:]][::-1]
            G=[0]*P.Max_Degree
            G[0]=1
            Q=[0]*(N-2)+[1]

            for k in range(1,P.Max_Degree):
                a=0
                for x,y in zip(Q,R):
                    a+=x*y
                a%=Mod
                G[k]=a
                Q.append(a)
                Q=Q[1:]

            G=[c_inv*g%Mod for g in G]
            return Modulo_Polynominal(G,P.Max_Degree,P.Char)
        else:
            """
            FFTの理論を応用して求める.
            計算量:求めたい項の個数をNとして, O(N log N)
            """
            if deg==None:
                deg=P.Max_Degree
            else:
                deg=min(deg,P.Max_Degree)

            F=P.Poly
            N=len(F)
            r=pow(F[0],Mod-2,Mod)

            m=1
            G=[r]
            while m<deg:
                T=F[:m<<1]
                H=Convolution_Mod(T,G)[m:m<<1]

                L=Convolution_Mod(H,G)[:m]
                for a in L:
                    G.append(Mod-a)
                m<<=1
            return Modulo_Polynominal(G[:deg],P.Max_Degree,P.Char)

    #除法
    def __truediv__(self,other):
        if isinstance(other,Modulo_Polynominal):
            return self*other.__inv__()
        else:
            return pow(other,Mod-2,Mod)*self

    def __rtruediv__(self,other):
        return other*self.__inv__()

    #スカラー倍
    def scale(self,s):
        P=self
        s%=Mod
        A=[(s*p)%Mod for p in P.Poly]
        A=Modulo_Polynominal(A,P.Max_Degree,P.Char)
        A.reduce()
        return A

    #係数
    def coefficient(self,n):
        try:
            if n<0:
                raise IndexError

            return self.Poly[n]
        except IndexError:
            return  0
        except TypeError:
            return 0

    #最高次の係数
    def leading_coefficient(self):
        for x in self.Poly[::-1]:
            if x:
                return x
        return 0

    def censor(self,n,Return=False):
        """ n次以上の係数をカット
        """
        if Return:
            return Modulo_Polynominal(self.Poly[:n],self.Max_Degree,self.Char)
        else:
            self.Poly=self.Poly[:n]

    def resize(self,n,Return=False):
        P=self
        if Return:
            if len(P.Poly)>n:
                E=P.Poly[:n]
            else:
                E=P.Poly+[0]*(n-P.Poly)
            return Modulo_Polynominal(E,P.Max_Degree,P.Char)
        else:
            if len(P.Poly)>n:
                del P.Poly[n:]
            else:
                P.Poly+=[0]*(n-len(P.Poly))
#=================================================
def Primitive_Root(p):
    """Z/pZ上の原始根を見つける

    p:素数
    """
    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://atcoder.jp/contests/practice2/submissions/16789717
def NTT(A):
    """AをMod を法とする数論変換を施す

    ※Modはグローバル変数から指定
    """
    primitive=Primitive_Root(Mod)

    N=len(A)
    H=(N-1).bit_length()

    if Mod==998_244_353:
        m=998_244_352
        u=119
        e=23
        S=[1,998244352,911660635,372528824,929031873,
        452798380,922799308,781712469,476477967,166035806,
        258648936,584193783,63912897,350007156,666702199,
        968855178,629671588,24514907,996173970,363395222,
        565042129,733596141,267099868,15311432]
    else:
        m=Mod-1
        e=((m&-m)-1).bit_length()
        u=m>>e
        S=[pow(primitive,(Mod-1)>>i,Mod) for i in range(e+1)]

    for l in range(H, 0, -1):
        d = 1 << l - 1
        U = [1]*(d+1)
        u = 1
        for i in range(d):
            u=u*S[l]%Mod
            U[i+1]=u

        for i in range(1 <<H - l):
            s=2*i*d
            for j in range(d):
                A[s],A[s+d]=(A[s]+A[s+d])%Mod, U[j]*(A[s]-A[s+d])%Mod
                s+=1

#参考元 https://atcoder.jp/contests/practice2/submissions/16789717
def Inverse_NTT(A):
    """AをMod を法とする逆数論変換を施す

    ※Modはグローバル変数から指定
    """
    primitive=Primitive_Root(Mod)

    N=len(A)
    H=(N-1).bit_length()

    if Mod==998244353:
        m=998_244_352
        e=23
        u=119
        S=[1,998244352,86583718,509520358,337190230,
        87557064,609441965,135236158,304459705,685443576,
        381598368,335559352,129292727,358024708,814576206,
        708402881,283043518,3707709,121392023,704923114,950391366,
        428961804,382752275,469870224]
    else:
        m=Mod-1
        e=(m&-m).bit_length()-1
        u=m>>e

        inv_primitive=pow(primitive,Mod-2,Mod)
        S=[pow(inv_primitive,(Mod-1)>>i,Mod) for i in range(e+1)]

    for l in range(1, H + 1):
        d = 1 << l - 1
        for i in range(1 << H - l):
            u = 1
            for j in range(2*i*d, (2*i+1)*d):
                A[j+d] *= u
                A[j], A[j+d] = (A[j] + A[j+d]) % Mod, (A[j] - A[j+d]) % Mod
                u = u * S[l] % Mod

    N_inv=pow(N,Mod-2,Mod)
    for i in range(N):
        A[i]=A[i]*N_inv%Mod

#参考元 https://atcoder.jp/contests/practice2/submissions/16789717
def Convolution_Mod(A,B):
    """A,BをMod を法とする畳み込みを求める.

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

    N=len(A)
    M=len(B)
    L=N+M-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)

    NTT(A)
    NTT(B)

    for i in range(K):
        A[i]=A[i]*B[i]%Mod

    Inverse_NTT(A)
    return A[:L]

def Autocorrelation_Mod(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)

    NTT(A)

    for i in range(K):
        A[i]=A[i]*A[i]%Mod
    Inverse_NTT(A)

    return A[:L]

#以下 参考元https://judge.yosupo.jp/submission/28304
def inverse(F):
    G=[pow(F[0],Mod-2,Mod)]
    N=len(F)
    d=1
    while d<N:
        d<<=1
        H=[-v for v in Convolution_Mod(F[:d],G)[:d]]
        H[0]+=2
        G=Convolution_Mod(G,H)[:d]
    return G[:N]

def Differentiate(P):
    F=P.Poly
    G=[(k*a)%Mod for k,a in enumerate(F[1:],1)]+[0]
    return Modulo_Polynominal(G,P.Max_Degree,P.Char)

def Integrate(P):
    F=P.Poly
    N=len(F)

    Inv=[0]*(N+1)
    if N:
        Inv[1]=1
        for i in range(2,N+1):
            q,r=divmod(Mod,i)
            Inv[i]=(-q*Inv[r])%Mod

    G=[0]+[(Inv[k]*a)%Mod for k,a in enumerate(F,1)]
    return Modulo_Polynominal(G,P.Max_Degree,P.Char)

def Add(a, b):
    return [(va + vb) % Mod for va, vb in zip(a, b)]

def Sub(a, b):
    return [(va - vb) % Mod for va, vb in zip(a, b)]

def Times(a, k):
    return [v * k % Mod for v in a]

def Mul(a,b):
    return Convolution_Mod(a,b)

"""
累乗,指数,対数
"""
def Log(P):
    assert P.Poly[0]==1,"定数項が1ではない"
    return Integrate(Differentiate(P)/P)

def Exp(P):
    #参考元1:https://arxiv.org/pdf/1301.5804.pdf
    #参考元2:https://opt-cp.com/fps-fast-algorithms/
    from itertools import zip_longest
    N=P.Max_Degree

    Inv=[0]*(2*N+1)
    Inv[1]=1
    for i in range(2,2*N+1):
        q,r=divmod(Mod,i)
        Inv[i]=(-q*Inv[r])%Mod

    H=P.Poly
    assert (not H) or H[0]==0,"定数項が0でない"

    H+=[0]*(N-len(H))
    dH=[(k*a)%Mod for k,a in enumerate(H[1:],1)]
    F,G,m=[1],[1],1

    while m<=N:
        #2.a'
        if m>1:
            E=Convolution_Mod(F,Autocorrelation_Mod(G)[:m])[:m]
            G=[(2*a-b)%Mod for a,b in zip_longest(G,E,fillvalue=0)]
        #2.b', 2.c'
        C=Convolution_Mod(F,dH[:m-1])
        R=[0]*m
        for i,a in enumerate(C):
            R[i%m]+=a
        R=[a%Mod for a in R]
        #2.d'
        dF=[(k*a)%Mod for k,a in enumerate(F[1:],1)]
        D=[0]+[(a-b)%Mod for a,b in zip_longest(dF,R,fillvalue=0)]
        S=[0]*m
        for i,a in enumerate(D):
            S[i%m]+=a
        S=[a%Mod for a in S]
        #2.e'
        T=Convolution_Mod(G,S)[:m]
        #2.f'
        E=[0]*(m-1)+T
        E=[0]+[(Inv[k]*a)%Mod for k,a in enumerate(E,1)]
        U=[(a-b)%Mod for a,b in zip_longest(H[:2*m],E,fillvalue=0)][m:]
        #2.g'
        V=Convolution_Mod(F,U)[:m]
        #2.h'
        F+=V
        #2.i'
        m<<=1
    return Modulo_Polynominal(F[:N],P.Max_Degree,P.Char)

def Power(P,k):
    assert k>=0
    N=P.Max_Degree
    F=P.Poly
    F+=[0]*(N-len(F))
    for (d,p) in enumerate(F):
        if p:
            break
    else:
        return Modulo_Polynominal([0],P.Max_Degree,P.Char)

    if d*k>P.Max_Degree:
        return Modulo_Polynominal([0],P.Max_Degree,P.Char)

    p_inv=pow(p,Mod-2,Mod)
    Q=Modulo_Polynominal([(p_inv*a)%Mod for a in F[d:]],P.Max_Degree,P.Char)

    G=Exp(k*Log(Q)).Poly
    pk=pow(p,k,Mod)
    G=[0]*(d*k)+[(pk*a)%Mod for a in G]
    return Modulo_Polynominal(G,P.Max_Degree,P.Char)
#================================================
def floating_degree(P):
    T=P.Poly
    for i in range(len(T)):
        if T[i]:
            return i
#================================================
import sys
from collections import defaultdict

input=sys.stdin.readline
write=sys.stdout.write

N,Q=map(int,input().split())
M=3000
Mod=998244353

Poly=defaultdict(lambda :Modulo_Polynominal([1]*(M+1),M+1))
X=Modulo_Polynominal([0,1],M+1)
V=1/pow(1-X,N+1)

Z=[0]*Q
offset=0
for i in range(Q):
    K,A,B,S,T=map(int,input().split())

    P=Poly[K]

    #P=0 のときを例外処理
    if not P:
        Z[i]=0
        continue

    d=floating_degree(P)
    V/=(P>>d)
    V<<=d
    for j in range(A,B+1):
        P.Poly[j]=0
    V*=P

    if S==0:
        Z[i]=V.coefficient(T)
    else:
        Z[i]=V.coefficient(T)-V.coefficient(S-1)
        Z[i]%=Mod

write("\n".join(map(str,Z)))
0