Submit Info #34974

Problem Lang User Status Time Memory
Bernoulli Number pypy3 Kazu1998k AC 2990 ms 158.02 MiB

ケース詳細
Name Status Time Memory
0_00 AC 53 ms 29.83 MiB
100000_00 AC 775 ms 115.20 MiB
10000_00 AC 177 ms 38.15 MiB
1000_00 AC 93 ms 31.59 MiB
100_00 AC 71 ms 30.72 MiB
1_00 AC 52 ms 29.81 MiB
200000_00 AC 1490 ms 131.20 MiB
300000_00 AC 2950 ms 153.95 MiB
400000_00 AC 2966 ms 158.02 MiB
500000_00 AC 2990 ms 156.62 MiB
example_00 AC 50 ms 29.83 MiB

class Modulo_Polynominal(): 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 def __str__(self): S="" flag=False for k in range(len(self.Poly)): if self.Poly[k]: if flag: if k==1: S+="{:+}{}".format(self.Poly[1],self.Char) else: S+="{:+}{}^{}".format(self.Poly[k],self.Char,k) else: flag=True if k==0: S=str(self.Poly[0]) elif k==1: S=str(self.Poly[1])+self.Char else: S=str(self.Poly[k])+"{}^{}".format(self.Char,k) if S: return S else: return "0" #+,- def __pos__(self): return self def __neg__(self): return self.scale(-1) #Boole def __bool__(self): for a in self.Poly: if a: return True return False #簡略化 def reduce(self): P_deg=self.degree() if not(P_deg>=0): T=Modulo_Polynominal([0],self.Max_Degree,self.Char) T.censor(self.Max_Degree) return T for i in range(self.degree(),-1,-1): if self.Poly[i]: T=Modulo_Polynominal(self.Poly[:i+1],self.Max_Degree,self.Char) T.censor(self.Max_Degree) return T #次数 def degree(self): x=-float("inf") k=0 for y in self.Poly: if y!=0: x=k k+=1 return x #加法 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() R=[0]*(P_deg+1) R=[p for p in P.Poly] R[0]=(R[0]+Q)%Mod return Modulo_Polynominal(R,P.Max_Degree,P.Char).reduce() 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: M=min(P.Max_Degree,Q.Max_Degree) B=Convolution_Mod(self.Poly,other.Poly)[:M] return Modulo_Polynominal(B,M,self.Char).reduce() else: return self.scale(other) def __rmul__(self,other): return self.scale(other) #除法 def __floordiv__(self,other): if not other: raise ZeroDivisionError pass #剰余 def __mod__(self,other): return self-(self//other)*other #累乗 def __pow__(self,n): 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__() #逆元 def __inv__(self,deg=None): assert self.Poly[0],"定数項が0" P=self 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 del G[deg:] return Modulo_Polynominal(G,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] return Modulo_Polynominal(A,P.Max_Degree,P.Char).reduce() #係数 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(i * 2 * d, (i * 2 + 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) del A[L:] return A 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] 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) 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 Log(P): return Integrate(Differentiate(P)/P) 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 Exp(P): #参考元:https://arxiv.org/pdf/1301.5804.pdf 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 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' 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) #Bernoulli def Bernoulli(N): """ ベルヌーイ数 B_0,B_1,...,B_Nの(mod Mod)での値を求める. """ if N==0: return [1] X=Modulo_Polynominal([0,1],N+2) P=Exp(X) del P.Poly[0] F=(1/P).Poly fact=1 for i in range(N+1): F[i]=(F[i]*fact)%Mod fact=(fact*(i+1))%Mod del F[-1] return F #================================================ import sys input=sys.stdin.readline Mod=998244353 N=int(input()) print(*Bernoulli(N))