結果
問題 |
No.2303 Frog on Grid
|
ユーザー |
![]() |
提出日時 | 2023-06-01 13:15:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,365 ms / 2,000 ms |
コード長 | 3,073 bytes |
コンパイル時間 | 587 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 104,096 KB |
最終ジャッジ日時 | 2024-12-28 14:56:40 |
合計ジャッジ時間 | 18,736 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#yukicoder 2303 Frog on Grid #MODnCr計算機(行数削減版) class MODnCr: def __init__(self,fact_N,MOD,invN=1000): self._N=fact_N; self._invN=invN; self._MOD=MOD; self._fact=[1]*(self._N+1); self._inv=[1]*(self._invN+1); self._finv=[1]*(self._N+1) for i in range(2,self._N+1): self._fact[i]=self._fact[i-1]*i%self._MOD for i in range(2,self._invN+1): self._inv[i]=-self._inv[self._MOD%i]*(self._MOD//i)%self._MOD for i in range(2,min(self._invN,self._N)+1): self._finv[i]=self._finv[i-1]*self._inv[i]%self._MOD self._finv[self._N]=pow(self._fact[self._N],self._MOD-2,self._MOD) for i in range(self._N-1,self._invN,-1): self._finv[i]=self._finv[i+1]*(i+1)%self._MOD def _update(self,N): if N<=self._N: return 0 dist=N-self._N; self._fact.extend([1]*dist); self._finv.extend([1]*dist) for i in range(self._N+1,N+1): self._fact[i]=self._fact[i-1]*i%self._MOD self._finv[N]=self.modinv(self._fact[N]) for i in range(N-1,self._N,-1): self._finv[i]=self._finv[i+1]*(i+1)%self._MOD self._N=N; return 1 def nCr(self,n,r): if self._N<n: self._update(n) return 0 if any([n<r,n<0,r<0]) else self._fact[n]*self._finv[n-r]%self._MOD*self._finv[r]%self._MOD def modinv(self,x): return self._inv[x] if x<=self._invN else (-self._inv[self._MOD%x]*(self._MOD//x))%self._MOD if x> self._invN>=self._MOD%x else pow(x,self._MOD-2,self._MOD) #MOD = 998244353 にのみ対応したFFT。それ以外では機能しません。 class NTT_998244353: def __init__(self,MOD=998244353): self._MOD=998244353 def _FFT(self,f,fft_len,IDFT=False): h=0 while 2**h < max(len(f),fft_len): h+=1 f+=[0]*(2**h - len(f)); P=pow(3,119*2**(23-h),self._MOD) if IDFT: P=pow(P,2**h-1,self._MOD); rev=pow(2**h,self._MOD-2,self._MOD) for i in range(2**h): #バタフライ演算の並び替え j=0 for k in range(h): j|=(i>>k&1)<<(h-1-k) if i<j: f[i],f[j]=f[j],f[i] for x in range(h): b=2**x; Q=pow(P,2**(h-x-1),self._MOD); W=1 #W=Q^j for j in range(b): for k in range(0,2**h,2*b): s,t=f[j+k],f[j+k+b]*W%self._MOD; f[j+k]=(s+t)%self._MOD; f[j+k+b]=(s-t)%self._MOD W=W*Q%self._MOD if IDFT: for i in range(2**h): f[i]=f[i]*rev%self._MOD return f def convolve(self,f,g): N=1; L=len(f)+len(g)-1 while N<L: N*=2 f=self._FFT(f,N); g=self._FFT(g,N); h=[f[i]*g[i]%self._MOD for i in range(N)] return self._FFT(h,N,True)[:L] H,W=map(int,input().split()); MOD=998244353 nCr=MODnCr(4*10**5+1,MOD,2*10**5+1); NTT=NTT_998244353() DPh=[0]*(H+1); DPw=[0]*(W+1) for h in range(H+1): x=2*h-H; y=h-x; DPh[h]=nCr._finv[x]*nCr._finv[y]%MOD if 0<=x and 0<=y else 0 for w in range(W+1): x=2*w-W; y=w-x; DPw[w]=nCr._finv[x]*nCr._finv[y]%MOD if 0<=x and 0<=y else 0 DP=NTT.convolve(DPh,DPw) for i in range(1,len(DP)): DP[0]+=DP[i]*nCr._fact[i]%MOD print(DP[0]%MOD)