結果
問題 |
No.1533 Don't be Negative!
|
ユーザー |
![]() |
提出日時 | 2021-05-18 06:43:10 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,343 bytes |
コンパイル時間 | 586 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 66,176 KB |
最終ジャッジ日時 | 2024-10-11 02:05:25 |
合計ジャッジ時間 | 6,225 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 4 |
other | RE * 53 |
ソースコード
class FPS: sum_e=(911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497) sum_ie=(86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951) mod=998244353 g=3 def butterfly(self,a): n=len(a) h=(n-1).bit_length() for ph in range(1,h+1): w=1<<(ph-1) p=1<<(h-ph) now=1 for s in range(w): offset=s<<(h-ph+1) for i in range(p): l=a[i+offset] r=a[i+offset+p]*now r%=self.mod a[i+offset]=l+r a[i+offset]%=self.mod a[i+offset+p]=l-r a[i+offset+p]%=self.mod now*=self.sum_e[(~s & -~s).bit_length()-1] now%=self.mod def butterfly_inv(self,a): n=len(a) h=(n-1).bit_length() for ph in range(h,0,-1): w=1<<(ph-1) p=1<<(h-ph) inow=1 for s in range(w): offset=s<<(h-ph+1) for i in range(p): l=a[i+offset] r=a[i+offset+p] a[i+offset]=l+r a[i+offset]%=self.mod a[i+offset+p]=(l-r)*inow a[i+offset+p]%=self.mod inow*=self.sum_ie[(~s & -~s).bit_length()-1] inow%=self.mod def convolution(self,a,b): n=len(a);m=len(b) if not(a) or not(b): return [] if min(n,m)<=40: if n<m: n,m=m,n a,b=b,a 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=[0]*z for i in range(z): c[i]=(a[i]*b[i])%self.mod 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] lg2N=14 N,M=map(int,input().split()) mod=998244353 X=[0]*(lg2N+1) X[0]=[1]*(2*M+1) for i in range(lg2N): X[i+1]=FPS().convolution(X[i][:],X[i][:]) Y=[[[1] for i in range(1<<(lg2N+1-i))] for i in range(lg2N+1)] Y[-1][1]=X[-1][:] for i in range(lg2N-1,-1,-1): for j in range(len(Y[i+1])): Y[i][j<<1]=Y[i+1][j][:] Y[i][(j<<1)+1]=FPS().convolution(Y[i+1][j],X[i]) x=((1<<i)-1)*2*M+1 if len(Y[i][j<<1])>x: z=[Y[i][j<<1][(len(Y[i][j<<1])>>1)+k] for k in range(-(x>>1),(x>>1)+1)] Y[i][j<<1]=z if len(Y[i][(j<<1)+1])>x: z=[Y[i][(j<<1)+1][(len(Y[i][(j<<1)+1])>>1)+k] for k in range(-(x>>1),(x>>1)+1)] Y[i][(j<<1)+1]=z ANS=0 P=2*M+1 V=pow(P,N,mod) W=pow(P,mod-2,mod) U=1 for i in range(1,N+1): V=V*W%mod U=U*P%mod ANS+=(U-Y[0][i][0])*V*(N-i+1) print(ANS*pow(2,mod-2,mod)%mod)