結果

問題 No.2303 Frog on Grid
コンテスト
ユーザー navel_tos
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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)
0