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