結果
問題 | No.2303 Frog on Grid |
ユーザー |
|
提出日時 | 2023-05-13 18:16:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 980 ms / 2,000 ms |
コード長 | 6,782 bytes |
コンパイル時間 | 351 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 159,964 KB |
最終ジャッジ日時 | 2024-11-29 09:52:09 |
合計ジャッジ時間 | 12,794 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
def main():from sys import stdin, setrecursionlimit# setrecursionlimit(1000000)input = stdin.readlinedef iinput(): return int(input())def sinput(): return input().rstrip()def i0input(): return int(input()) - 1def linput(): return list(input().split())def liinput(): return list(map(int, input().split()))def miinput(): return map(int, input().split())def li0input(): return list(map(lambda x: int(x) - 1, input().split()))def mi0input(): return map(lambda x: int(x) - 1, input().split())INF = 1000000000000000000MOD = 998244353def modinv(a):b = MODu, v = 1, 0while b > 0:t = a // ba -= t * ba, b = b, au -= t * vu, v = v, ureturn u % MODclass Combination:def __init__(self, N, MOD):self.factorial = [1]self.inv_factorial = [1]self.mod = MODfor i in range(1, N+1):self.factorial.append(self.factorial[-1] * i % MOD)self.inv_factorial.append(self.inv_factorial[-1] * modinv(i) % MOD)def combi(self, n, k):return self.factorial[n] * self.inv_factorial[k] % self.mod * self.inv_factorial[n-k] % self.modcmb = Combination(404040, MOD)def counter(N):ans = dict()for k in range((N+1)//2, N+1):ans[k] = cmb.combi(k, N-k)return ansH, W = miinput()def solve_naive(H, W):ans = 0for h in range((H+1)//2, H+1):for w in range((W+1)//2, W+1):ans += cmb.factorial[h+w] * cmb.inv_factorial[H-h] % MOD * cmb.inv_factorial[2*h-H] % MOD * cmb.inv_factorial[W-w] % MOD * cmb.inv_factorial[2*w-W] % MODans %= MODreturn ansdef solve(H, W):fft = FFT(MOD)ans = 0Wlist = []for w in range((W+1)//2, W+1):Wlist.append(cmb.inv_factorial[W-w] * cmb.inv_factorial[2*w-W] % MOD)HWlist = []for hw in range((H+1)//2 + (W+1)//2, H+W+1):HWlist.append(cmb.factorial[hw])Sum = fft.convolution(Wlist[::-1], HWlist)for i, h in enumerate(range((H+1)//2, H+1)):ans += Sum[i+len(Wlist)-1] % MOD * cmb.inv_factorial[H-h] % MOD * cmb.inv_factorial[2*h-H] % MODans %= MODreturn ans# print(solve_naive(H, W))print(solve(H, W))class FFT():def primitive_root_constexpr(self,m):if m==2:return 1if m==167772161:return 3if m==469762049:return 3if m==754974721:return 11if m==998244353:return 3divs=[0]*20divs[0]=2cnt=1x=(m-1)//2while(x%2==0):x//=2i=3while(i*i<=x):if (x%i==0):divs[cnt]=icnt+=1while(x%i==0):x//=ii+=2if x>1:divs[cnt]=xcnt+=1g=2while(1):ok=Truefor i in range(cnt):if pow(g,(m-1)//divs[i],m)==1:ok=Falsebreakif ok:return gg+=1def bsf(self,x):res=0while(x%2==0):res+=1x//=2return resbutterfly_first=Truebutterfly_inv_first=Truesum_e=[0]*30sum_ie=[0]*30def __init__(self,MOD):self.mod=MODself.g=self.primitive_root_constexpr(self.mod)def butterfly(self,a):n=len(a)h=(n-1).bit_length()if self.butterfly_first:self.butterfly_first=Falsees=[0]*30ies=[0]*30cnt2=self.bsf(self.mod-1)e=pow(self.g,(self.mod-1)>>cnt2,self.mod)ie=pow(e,self.mod-2,self.mod)for i in range(cnt2,1,-1):es[i-2]=eies[i-2]=iee=(e*e)%self.modie=(ie*ie)%self.modnow=1for i in range(cnt2-2):self.sum_e[i]=((es[i]*now)%self.mod)now*=ies[i]now%=self.modfor ph in range(1,h+1):w=1<<(ph-1)p=1<<(h-ph)now=1for s in range(w):offset=s<<(h-ph+1)for i in range(p):l=a[i+offset]r=a[i+offset+p]*nowr%=self.moda[i+offset]=l+ra[i+offset]%=self.moda[i+offset+p]=l-ra[i+offset+p]%=self.modnow*=self.sum_e[(~s & -~s).bit_length()-1]now%=self.moddef butterfly_inv(self,a):n=len(a)h=(n-1).bit_length()if self.butterfly_inv_first:self.butterfly_inv_first=Falsees=[0]*30ies=[0]*30cnt2=self.bsf(self.mod-1)e=pow(self.g,(self.mod-1)>>cnt2,self.mod)ie=pow(e,self.mod-2,self.mod)for i in range(cnt2,1,-1):es[i-2]=eies[i-2]=iee=(e*e)%self.modie=(ie*ie)%self.modnow=1for i in range(cnt2-2):self.sum_ie[i]=((ies[i]*now)%self.mod)now*=es[i]now%=self.modfor ph in range(h,0,-1):w=1<<(ph-1)p=1<<(h-ph)inow=1for 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+ra[i+offset]%=self.moda[i+offset+p]=(l-r)*inowa[i+offset+p]%=self.modinow*=self.sum_ie[(~s & -~s).bit_length()-1]inow%=self.moddef 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,na,b=b,ares=[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.modreturn resz=1<<((n+m-2).bit_length())a=a+[0]*(z-n)b=b+[0]*(z-m)self.butterfly(a)self.butterfly(b)c=[0]*zfor i in range(z):c[i]=(a[i]*b[i])%self.modself.butterfly_inv(c)iz=pow(z,self.mod-2,self.mod)for i in range(n+m-1):c[i]=(c[i]*iz)%self.modreturn c[:n+m-1]main()