結果
問題 |
No.2303 Frog on Grid
|
ユーザー |
![]() |
提出日時 | 2023-05-14 01:54:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 367 ms / 2,000 ms |
コード長 | 2,755 bytes |
コンパイル時間 | 198 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 176,556 KB |
最終ジャッジ日時 | 2024-11-29 16:34:39 |
合計ジャッジ時間 | 6,807 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
mod=998244353 # FFT # mod=998244353 における、NTTによる高速フーリエ変換、畳み込み # 他の提出を参考にしており、あまり理解できていません…… mod=998244353 Weight=[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=1 ij=j*m*2 wk=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%mod w=w*wk%mod else: for i in range(h): m=1<<i for j in range(1<<(h-i-1)): w=1 ij=j*m*2 wk=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)%mod w=w*wk%mod if inverse==1: INV_n=pow(n,mod-2,mod) for i in range(n): A[i]=A[i]*INV_n%mod return A def convolution(A,B): FFTLEN=len(A)+len(B)-1 h=FFTLEN.bit_length() LEN=2**h A+=[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]%mod A=fft(A,LEN,h,1) return A[:FFTLEN] FACT=[1] for i in range(1,6*10**5+1): FACT.append(FACT[-1]*i%mod) FACT_INV=[pow(FACT[-1],mod-2,mod)] for i in range(6*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]%mod else: return 0 def calc(N): LIST=[0]*(N+1) one=N two=0 while one>=0 and two>=0: LIST[one+two]=Combi(one+two,one) two+=1 one-=2 return LIST H,W=map(int,input().split()) A=calc(H) B=calc(W) for i in range(len(A)): A[i]*=FACT_INV[i] A[i]%=mod for i in range(len(B)): B[i]*=FACT_INV[i] B[i]%=mod X=convolution(A,B) ANS=0 for i in range(len(X)): ANS+=X[i]*FACT[i] ANS%=mod print(ANS)