結果

問題 No.2527 H and W
ユーザー navel_tosnavel_tos
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,352 KB
testcase_01 AC 40 ms
52,480 KB
testcase_02 AC 214 ms
101,120 KB
testcase_03 AC 40 ms
52,608 KB
testcase_04 AC 201 ms
92,160 KB
testcase_05 AC 199 ms
92,288 KB
testcase_06 AC 216 ms
101,888 KB
testcase_07 AC 40 ms
52,608 KB
testcase_08 AC 202 ms
92,160 KB
testcase_09 AC 99 ms
74,624 KB
testcase_10 AC 100 ms
74,368 KB
testcase_11 AC 200 ms
92,416 KB
testcase_12 AC 213 ms
106,880 KB
testcase_13 AC 213 ms
106,880 KB
testcase_14 AC 210 ms
107,264 KB
testcase_15 AC 202 ms
92,288 KB
testcase_16 AC 205 ms
94,080 KB
testcase_17 AC 214 ms
100,864 KB
testcase_18 AC 207 ms
95,232 KB
testcase_19 AC 143 ms
81,152 KB
testcase_20 AC 149 ms
82,304 KB
testcase_21 AC 164 ms
91,392 KB
testcase_22 AC 163 ms
91,264 KB
testcase_23 AC 162 ms
91,264 KB
testcase_24 AC 144 ms
80,384 KB
testcase_25 AC 99 ms
74,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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