結果
| 問題 | No.2817 Competition |
| ユーザー |
 highlighter
|
| 提出日時 | 2024-07-19 08:47:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,790 bytes |
| コンパイル時間 | 217 ms |
| コンパイル使用メモリ | 81,960 KB |
| 実行使用メモリ | 201,860 KB |
| 最終ジャッジ日時 | 2024-07-19 08:47:54 |
| 合計ジャッジ時間 | 4,335 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 39 ms
56,300 KB |
| testcase_01 | AC | 40 ms
54,912 KB |
| testcase_02 | AC | 38 ms
55,424 KB |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | AC | 406 ms
86,524 KB |
| testcase_09 | AC | 718 ms
98,576 KB |
| testcase_10 | AC | 1,010 ms
112,408 KB |
| testcase_11 | AC | 1,771 ms
152,412 KB |
| testcase_12 | AC | 80 ms
76,540 KB |
| testcase_13 | AC | 802 ms
101,248 KB |
| testcase_14 | AC | 1,191 ms
121,048 KB |
| testcase_15 | AC | 618 ms
96,656 KB |
| testcase_16 | AC | 1,291 ms
122,584 KB |
| testcase_17 | AC | 864 ms
103,864 KB |
| testcase_18 | TLE | - |
| testcase_19 | AC | 49 ms
63,572 KB |
| testcase_20 | AC | 42 ms
56,744 KB |
| testcase_21 | AC | 45 ms
62,352 KB |
| testcase_22 | AC | 49 ms
62,820 KB |
| testcase_23 | AC | 48 ms
62,896 KB |
ソースコード
from collections import deque from sys import stdin #https://github.com/shakayami/ACL-for-python/blob/master/convolution.py class FFT(): def primitive_root_constexpr(self,m): if m==2:return 1 if m==167772161:return 3 if m==469762049:return 3 if m==754974721:return 11 if m==998244353:return 3 divs=[0]*20 divs[0]=2 cnt=1 x=(m-1)//2 while(x%2==0):x//=2 i=3 while(i*i<=x): if (x%i==0): divs[cnt]=i cnt+=1 while(x%i==0): x//=i i+=2 if x>1: divs[cnt]=x cnt+=1 g=2 while(1): ok=True for i in range(cnt): if pow(g,(m-1)//divs[i],m)==1: ok=False break if ok: return g g+=1 def bsf(self,x): res=0 while(x%2==0): res+=1 x//=2 return res rank2=0 root=[] iroot=[] rate2=[] irate2=[] rate3=[] irate3=[] def __init__(self,MOD): self.mod=MOD self.g=self.primitive_root_constexpr(self.mod) self.rank2=self.bsf(self.mod-1) self.root=[0 for i in range(self.rank2+1)] self.iroot=[0 for i in range(self.rank2+1)] self.rate2=[0 for i in range(self.rank2)] self.irate2=[0 for i in range(self.rank2)] self.rate3=[0 for i in range(self.rank2-1)] self.irate3=[0 for i in range(self.rank2-1)] self.root[self.rank2]=pow(self.g,(self.mod-1)>>self.rank2,self.mod) self.iroot[self.rank2]=pow(self.root[self.rank2],self.mod-2,self.mod) for i in range(self.rank2-1,-1,-1): self.root[i]=(self.root[i+1]**2)%self.mod self.iroot[i]=(self.iroot[i+1]**2)%self.mod prod=1;iprod=1 for i in range(self.rank2-1): self.rate2[i]=(self.root[i+2]*prod)%self.mod self.irate2[i]=(self.iroot[i+2]*iprod)%self.mod prod=(prod*self.iroot[i+2])%self.mod iprod=(iprod*self.root[i+2])%self.mod prod=1;iprod=1 for i in range(self.rank2-2): self.rate3[i]=(self.root[i+3]*prod)%self.mod self.irate3[i]=(self.iroot[i+3]*iprod)%self.mod prod=(prod*self.iroot[i+3])%self.mod iprod=(iprod*self.root[i+3])%self.mod def butterfly(self,a): n=len(a) h=(n-1).bit_length() LEN=0 while(LEN<h): if (h-LEN==1): p=1<<(h-LEN-1) rot=1 for s in range(1<<LEN): offset=s<<(h-LEN) for i in range(p): l=a[i+offset] r=a[i+offset+p]*rot a[i+offset]=(l+r)%self.mod a[i+offset+p]=(l-r)%self.mod rot*=self.rate2[(~s & -~s).bit_length()-1] rot%=self.mod LEN+=1 else: p=1<<(h-LEN-2) rot=1 imag=self.root[2] for s in range(1<<LEN): rot2=(rot*rot)%self.mod rot3=(rot2*rot)%self.mod offset=s<<(h-LEN) 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 a1na3imag=(a1-a3)%self.mod*imag a[i+offset]=(a0+a2+a1+a3)%self.mod a[i+offset+p]=(a0+a2-a1-a3)%self.mod a[i+offset+2*p]=(a0-a2+a1na3imag)%self.mod a[i+offset+3*p]=(a0-a2-a1na3imag)%self.mod rot*=self.rate3[(~s & -~s).bit_length()-1] rot%=self.mod LEN+=2 def butterfly_inv(self,a): n=len(a) h=(n-1).bit_length() LEN=h while(LEN): if (LEN==1): p=1<<(h-LEN) irot=1 for 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.mod a[i+offset+p]=(l-r)*irot%self.mod irot*=self.irate2[(~s & -~s).bit_length()-1] irot%=self.mod LEN-=1 else: p=1<<(h-LEN) irot=1 iimag=self.iroot[2] for s in range(1<<(LEN-2)): irot2=(irot*irot)%self.mod irot3=(irot*irot2)%self.mod offset=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.mod a[i+offset]=(a0+a1+a2+a3)%self.mod a[i+offset+p]=(a0-a1+a2na3iimag)*irot%self.mod a[i+offset+2*p]=(a0+a1-a2-a3)*irot2%self.mod a[i+offset+3*p]=(a0-a1-a2na3iimag)*irot3%self.mod irot*=self.irate3[(~s & -~s).bit_length()-1] irot%=self.mod LEN-=2 def convolution(self,a,b): n=len(a);m=len(b) if not(a) or not(b): return [] if min(n,m)<=40: res=[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.mod return res z=1<<((n+m-2).bit_length()) a=a+[0]*(z-n) b=b+[0]*(z-m) self.butterfly(a) 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.mod return c[:n+m-1] readline = stdin.readline N=int(input()) A=list(map(int,readline().split())) q = deque() for i in A: q.append([1,i]) conv=FFT(998244353) while len(q) >= 2: q.append(conv.convolution(q.popleft(),q.popleft())) res=q.popleft() ans=0 for i in range(1,N+1): ans+=pow(i,N-i,998244353)*res[i]%998244353 ans%=998244353 print(ans)