結果
問題 | No.2527 H and W |
ユーザー |
![]() |
提出日時 | 2023-11-04 13:58:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 216 ms / 2,000 ms |
コード長 | 1,934 bytes |
コンパイル時間 | 367 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 107,264 KB |
最終ジャッジ日時 | 2024-09-25 22:01:23 |
合計ジャッジ時間 | 5,338 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#yukicoder411C #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 fact(self,x): self._update(x) if x>self._N else None; return self._fact[x] def finv(self,x): self._update(x) if x>self._N else None; return self._finv[x] 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) def nCr(self,n,r): 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 #入力受取 H,W,K=map(int,input().split()) MOD=998244353; nCr=MODnCr(H+W,MOD); ans=0 #採用する行数をh, 列数をwとする。削る行数/列数は H-h, W-w と表される点に注意せよ for h in range(1,H+1): for w in range(K//h-2,K//h+3): if h*w!=K: continue ans+=nCr.nCr(H,H-h)*nCr.nCr(W,W-w)%MOD; ans%=MOD print(ans)