結果
問題 | No.2817 Competition |
ユーザー |
![]() |
提出日時 | 2024-07-20 18:28:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,417 ms / 2,000 ms |
コード長 | 17,845 bytes |
コンパイル時間 | 669 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 229,960 KB |
最終ジャッジ日時 | 2024-08-08 13:52:03 |
合計ジャッジ時間 | 17,346 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
# https://github.com/shakayami/ACL-for-python/blob/master/fps.pyclass FPS:root=(1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897,350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432)iroot=(1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727,358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224)rate2=(911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263,730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0)irate2=(86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543,109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0)rate3=(372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099, 183021267, 402682409, 631680428,344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204, 0)irate3=(509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500, 771127074, 985925487,262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681, 0)mod=998244353Func=[0]def __init__(self,L):self.Func=[x%self.mod for x in L]def butterfly(self,a):n=len(a)h=(n-1).bit_length()LEN=0while(LEN<h):if (h-LEN==1):p=1<<(h-LEN-1)rot=1for s in range(1<<LEN):offset=s<<(h-LEN)for i in range(p):l=a[i+offset]r=a[i+offset+p]*rota[i+offset]=(l+r)%self.moda[i+offset+p]=(l-r)%self.modrot*=self.rate2[(~s & -~s).bit_length()-1]rot%=self.modLEN+=1else:p=1<<(h-LEN-2)rot=1imag=self.root[2]for s in range(1<<LEN):rot2=(rot*rot)%self.modrot3=(rot2*rot)%self.modoffset=s<<(h-LEN)for i in range(p):a0=a[i+offset]a1=a[i+offset+p]*rota2=a[i+offset+2*p]*rot2a3=a[i+offset+3*p]*rot3a1na3imag=(a1-a3)%self.mod*imaga[i+offset]=(a0+a2+a1+a3)%self.moda[i+offset+p]=(a0+a2-a1-a3)%self.moda[i+offset+2*p]=(a0-a2+a1na3imag)%self.moda[i+offset+3*p]=(a0-a2-a1na3imag)%self.modrot*=self.rate3[(~s & -~s).bit_length()-1]rot%=self.modLEN+=2return adef butterfly_inv(self,a):n=len(a)h=(n-1).bit_length()LEN=hwhile(LEN):if (LEN==1):p=1<<(h-LEN)irot=1for s in range(1<<(LEN-1)):offset=s<<(h-LEN+1)for i in range(p):l=a[i+offset]r=a[i+offset+p]a[i+offset]=(l+r)%self.moda[i+offset+p]=(l-r)*irot%self.modirot*=self.irate2[(~s & -~s).bit_length()-1]irot%=self.modLEN-=1else:p=1<<(h-LEN)irot=1iimag=self.iroot[2]for s in range(1<<(LEN-2)):irot2=(irot*irot)%self.modirot3=(irot*irot2)%self.modoffset=s<<(h-LEN+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]a2na3iimag=(a2-a3)*iimag%self.moda[i+offset]=(a0+a1+a2+a3)%self.moda[i+offset+p]=(a0-a1+a2na3iimag)*irot%self.moda[i+offset+2*p]=(a0+a1-a2-a3)*irot2%self.moda[i+offset+3*p]=(a0-a1-a2na3iimag)*irot3%self.modirot*=self.irate3[(~s & -~s).bit_length()-1]irot%=self.modLEN-=2return adef __mul__(self,other):if type(other)==int:ret=[(x*other)%self.mod for x in self.Func]return FPS(ret)a=self.Funcb=other.Funcn=len(a);m=len(b)if not(a) or not(b):return FPS([])if min(n,m)<=40:if n<m:n,m=m,na,b=b,ares=[0]*(n+m-1)for i in range(n):for j in range(m):res[i+j]+=a[i]*b[j]res[i+j]%=self.modreturn FPS(res)z=1<<((n+m-2).bit_length())a=a+[0]*(z-n)b=b+[0]*(z-m)a=self.butterfly(a)b=self.butterfly(b)c=[(a[i]*b[i])%self.mod for i in range(z)]self.butterfly_inv(c)iz=pow(z,self.mod-2,self.mod)for i in range(n+m-1):c[i]=(c[i]*iz)%self.modreturn FPS(c[:n+m-1])def __imul__(self,other):self=self*otherreturn selfdef __add__(self,other):res=[0 for i in range(max(len(self.Func),len(other.Func)))]for i,x in enumerate(self.Func):res[i]+=xres[i]%=self.modfor i,x in enumerate(other.Func):res[i]+=xres[i]%=self.modreturn FPS(res)def __iadd__(self,other):self=(self+other)return selfdef __sub__(self,other):res=[0 for i in range(max(len(self.Func),len(other.Func)))]for i,x in enumerate(self.Func):res[i]+=xres[i]%=self.modfor i,x in enumerate(other.Func):res[i]-=xres[i]%=self.modreturn FPS(res)def __isub__(self,other):self=self-otherreturn selfdef inv(self,d=-1):n=len(self.Func)assert n!=0 and self.Func[0]!=0if d==-1:d=nassert d>0res=[pow(self.Func[0],self.mod-2,self.mod)]while(len(res)<d):m=len(res)f=[self.Func[i] for i in range(min(n,2*m))]r=res[:]if len(f)<2*m:f+=[0]*(2*m-len(f))elif len(f)>2*m:f=f[:2*m]if len(r)<2*m:r+=[0]*(2*m-len(r))elif len(r)>2*m:r=r[:2*m]f=self.butterfly(f)r=self.butterfly(r)for i in range(2*m):f[i]*=r[i]f[i]%=self.modf=self.butterfly_inv(f)f=f[m:]if len(f)<2*m:f+=[0]*(2*m-len(f))elif len(f)>2*m:f=f[:2*m]f=self.butterfly(f)for i in range(2*m):f[i]*=r[i]f[i]%=self.modf=self.butterfly_inv(f)iz=pow(2*m,self.mod-2,self.mod)iz*=-iziz%=self.modfor i in range(m):f[i]*=izf[i]%=self.modres+=f[:m]return FPS(res[:d])def __truediv__(self,other):if type(other)==int:invother=pow(other,self.mod-2,self.mod)ret=[(x*invother)%self.mod for x in self.Func]return FPS(ret)assert (other.Func[0]!=0)return self*(other.inv())def __floordiv__(self,other):if not other:raise ZeroDivisionErrorif isinstance(other,int):return self/otherself.reduce();other.reduce()F_deg=len(self.Func)-1G_deg=len(other.Func)-1if F_deg<G_deg:return FPS([])m=F_deg-G_deg+1F_inverse=self.Func[::-1]G_inverse=other.Func[::-1]ans=(FPS(F_inverse)*(FPS(G_inverse).inv(d=m))).Funcreturn FPS(ans[m-1::-1])def __bool__(self):return any(self.Func)def __mod__(self,other):if not other:raise ZeroDivisionErrorself.reduce();other.reduce()FG=self//otherans=self-FG*otherans.reduce()return ansdef reduce(self):if self:while(not self.Func[-1]):self.Func.pop()else:self.Func=[]def __itruediv__(self,other):self=self/otherreturn selfdef __lshift__(self,d):n=len(self.Func)self.Func=[0]*d+self.Funcreturn FPS(self.Func[:n])def __ilshift__(self,d):self=self<<dreturn selfdef __rshift__(self,d):n=len(self.Func)self.Func=self.Func[min(n,d):]self.Func+=[0]*(n-len(self.Func))return FPS(self.Func)def __irshift__(self,d):self=self>>dreturn selfdef __lt__(self,other):if len(self.Func)<len(other.Func):return Trueelif len(self.Func)>len(other.Func):return Trueelse:return self.Func<other.Funcdef __gt__(self,other):if len(self.Func)>len(other.Func):return Trueelif len(self.Func)<len(other.Func):return Trueelse:return self.Func>other.Funcdef __eq__(self,other):return self.Func==other.Funcdef __le__(self,other):if len(self.Func)<len(other.Func):return Trueelif len(self.Func)>len(other.Func):return Trueelse:return self.Func<=other.Funcdef __ge__(self,other):if len(self.Func)>len(other.Func):return Trueelif len(self.Func)<len(other.Func):return Trueelse:return self.Func>other.Funcdef __ne__(self,other):return self.Func!=other.Funcdef __str__(self):return f'FPS({self.Func})'def diff(self):n=len(self.Func)ret=[0 for i in range(max(0,n-1))]for i in range(1,n):ret[i-1]=(self.Func[i]*i)%self.modreturn FPS(ret)def integral(self):n=len(self.Func)ret=[0 for i in range(n+1)]for i in range(n):ret[i+1]=self.Func[i]*pow(i+1,self.mod-2,self.mod)%self.modreturn FPS(ret)def log(self,deg=-1):assert self.Func[0]==1n=len(self.Func)if deg==-1:deg=nreturn (self.diff()*self.inv()).integral()def mod_sqrt(self,a):p=self.modassert 0<=a and a<pif a<2:return aif pow(a,(p-1)//2,p)!=1:return -1b=1;one=1while(pow(b,(p-1)>>1,p)==1):b+=onem=p-1;e=0while(m%2==0):m>>=1e+=1x=pow(a,(m-1)>>1,p)y=(a*x*x)%px*=a;x%=pz=pow(b,m,p)while(y!=1):j=0t=ywhile(t!=one):j+=1t*=tt%=pz=pow(z,1<<(e-j-1),p)x*=zx%=pz*=zz%=py*=zy%=pe=jreturn xdef sqrt(self,deg=-1):n=len(self.Func)if deg==-1:deg=nif n==0:return FPS([0 for i in range(deg)])if self.Func[0]==0:for i in range(1,n):if self.Func[i]!=0:if i&1:return FPS([])if deg-i//2<=0:breakret=(self>>i).sqrt(deg-i//2)if len(ret.Func)==0:return FPS([])ret=ret<<(i//2)if len(ret.Func)<deg:ret.Func+=[0]*(deg-len(ret.Func))return retreturn FPS([0]*deg)sqr=self.mod_sqrt(self.Func[0])if sqr==-1:return FPS([])assert sqr*sqr%self.mod==self.Func[0]ret=FPS([sqr])inv2=(self.mod+1)//2i=1while(i<deg):ret=(ret+FPS(self.Func[:i<<1])*ret.inv(i<<1))*inv2i<<=1return FPS(ret.Func[:deg])def resize(self,deg):if len(self.Func)<deg:return FPS(self.Func+[0]*(deg-len(self.Func)))elif len(self.Func)>deg:return FPS(self.Func[:deg])else:return selfdef exp(self,deg=-1):n=len(self.Func)assert n>0 and self.Func[0]==0if deg==-1:deg=nassert deg>=0g=[1]g_fft=[1,1]self.Func[0]=1self.resize(deg)h_drv=self.diff()m=2while(m<deg):f_fft=self.Func[:m]+[0]*mself.butterfly(f_fft)#step 2.a_g=[f_fft[i]*g_fft[i]%self.mod for i in range(m)]self.butterfly_inv(_g)_g=_g[m//2:m]+[0]*(m//2)self.butterfly(_g)for i in range(m):_g[i]*=g_fft[i]_g[i]%=self.modself.butterfly_inv(_g)tmp=pow(-m*m,self.mod-2,self.mod)for i in range(m):_g[i]*=tmp_g[i]%=self.modg+=_g[:m//2]#step 2.b--2.dt=FPS(self.Func[:m]).diff()r=h_drv.Func[:m-1]+[0]self.butterfly(r)for i in range(m):r[i]*=f_fft[i]r[i]%=self.modself.butterfly_inv(r)tmp=pow(-m,self.mod-2,self.mod)for i in range(m):r[i]*=tmpr[i]%=self.modt=(t+FPS(r)).Funct=[t[-1]]+tt.pop()#step 2.eif (2*m<deg):if len(t)<2*m:t+=[0]*(2*m-len(t))elif len(t)>2*m:t=t[:2*m]self.butterfly(t)g_fft=g[:]if len(g_fft)<2*m:g_fft+=[0]*(2*m-len(g_fft))elif len(g_fft)>2*m:g_fft=g_fft[:2*m]self.butterfly(g_fft)for i in range(2*m):t[i]*=g_fft[i]t[i]%=self.modself.butterfly_inv(t)tmp=pow(2*m,self.mod-2,self.mod)t=t[:m]for i in range(m):t[i]*=tmpt[i]%=self.modelse:g1=g[m//2:]s1=t[m//2:]t=t[:m//2]g1+=[0]*(m-len(g1))s1+=[0]*(m-len(s1))t+=[0]*(m-len(t))self.butterfly(g1)self.butterfly(t)self.butterfly(s1)for i in range(m):s1[i]=(g_fft[i]*s1[i]+g1[i]*t[i])%self.modfor i in range(m):t[i]*=g_fft[i]t[i]%=self.modself.butterfly_inv(t)self.butterfly_inv(s1)for i in range(m//2):t[i+m//2]+=s1[i]t[i+m//2]%=self.modtmp=pow(m,self.mod-2,self.mod)for i in range(m):t[i]*=tmpt[i]%=self.mod#step 2.fv=self.Func[m:min(deg,2*m)]+[0]*(2*m-min(deg,2*m))t=[0]*(m-1)+tt=FPS(t).integral().Funcfor i in range(m):v[i]-=t[m+i]v[i]%=self.mod#step 2.gif len(v)<2*m:v+=[0]*(2*m-len(v))else:v=v[:2*m]self.butterfly(v)for i in range(2*m):v[i]*=f_fft[i]v[i]%=self.modself.butterfly_inv(v)v=v[:m]tmp=pow(2*m,self.mod-2,self.mod)for i in range(m):v[i]*=tmpv[i]%=self.mod#step 2.hfor i in range(min(deg-m,m)):self.Func[m+i]=v[i]m*=2return selfdef powfps(self,k,deg=-1):a=self.Func[:]n=len(self.Func)if k==0:return FPS([int(i==0) for i in range(n)])l=0while(l<len(a) and not a[l]):l+=1if l*k>=n:return FPS([0]*n)ic=pow(a[l],self.mod-2,self.mod)pc=pow(a[l],k,self.mod)a=FPS([(a[i]*ic)%self.mod for i in range(l,len(a))]).log()a*=ka=a.exp()a*=pca=[0]*(l*k)+a.Func[:n-l*k]return FPS(a)from collections import *def fps_allprod(Q):while len(Q) > 1:a = Q.popleft()b = Q.popleft()Q.append(a * b)return Q[0].FuncN = int(input())A = list(map(int, input().split()))Q = deque()mod = 998244353for a in A:Q.append((FPS([1, a % mod])))F = fps_allprod(Q)ans = 0for i in range(1, N + 1):ans += pow(i, N - i, mod) * F[i]ans %= modprint(ans)