結果
問題 | No.2303 Frog on Grid |
ユーザー |
![]() |
提出日時 | 2023-05-14 01:53:22 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,755 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 133,316 KB |
最終ジャッジ日時 | 2024-11-29 16:33:19 |
合計ジャッジ時間 | 6,566 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 RE * 6 |
ソースコード
mod=998244353# FFT# mod=998244353 における、NTTによる高速フーリエ変換、畳み込み# 他の提出を参考にしており、あまり理解できていません……mod=998244353Weight=[1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897,350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432, 0]Weight_inv=[1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727,358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224, 0]def fft(A,n,h,inverse=0):if inverse==0:for i in range(h):m=1<<(h-i-1)for j in range(1<<i):w=1ij=j*m*2wk=Weight[h-i]for k in range(m):A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m])%mod,(A[ij+k]-A[ij+k+m])*w%modw=w*wk%modelse:for i in range(h):m=1<<ifor j in range(1<<(h-i-1)):w=1ij=j*m*2wk=Weight_inv[i+1]for k in range(m):A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m]*w)%mod,(A[ij+k]-A[ij+k+m]*w)%modw=w*wk%modif inverse==1:INV_n=pow(n,mod-2,mod)for i in range(n):A[i]=A[i]*INV_n%modreturn Adef convolution(A,B):FFTLEN=len(A)+len(B)-1h=FFTLEN.bit_length()LEN=2**hA+=[0]*(LEN-len(A)) # A,Bのサイズを2ベキに揃えるB+=[0]*(LEN-len(B))A_FFT=fft(A,LEN,h)B_FFT=fft(B,LEN,h)for i in range(len(A)):A[i]=A[i]*B[i]%modA=fft(A,LEN,h,1)return A[:FFTLEN]FACT=[1]for i in range(1,3*10**5+1):FACT.append(FACT[-1]*i%mod)FACT_INV=[pow(FACT[-1],mod-2,mod)]for i in range(3*10**5,0,-1):FACT_INV.append(FACT_INV[-1]*i%mod)FACT_INV.reverse()def Combi(a,b):if 0<=b<=a:return FACT[a]*FACT_INV[b]%mod*FACT_INV[a-b]%modelse:return 0def calc(N):LIST=[0]*(N+1)one=Ntwo=0while one>=0 and two>=0:LIST[one+two]=Combi(one+two,one)two+=1one-=2return LISTH,W=map(int,input().split())A=calc(H)B=calc(W)for i in range(len(A)):A[i]*=FACT_INV[i]A[i]%=modfor i in range(len(B)):B[i]*=FACT_INV[i]B[i]%=modX=convolution(A,B)ANS=0for i in range(len(X)):ANS+=X[i]*FACT[i]ANS%=modprint(ANS)