結果
| 問題 | No.1549 [Cherry 2nd Tune] BANning Tuple |
| ユーザー |
👑  Kazun
|
| 提出日時 | 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 |
ソースコード
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)))