結果
問題 | No.2527 H and W |
ユーザー |
|
提出日時 | 2023-11-03 22:03:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,120 bytes |
コンパイル時間 | 2,069 ms |
コンパイル使用メモリ | 196,292 KB |
最終ジャッジ日時 | 2025-02-17 18:18:57 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){ios_base::sync_with_stdio(false);cin.tie(nullptr);long long H,W,K; cin >> H >> W >> K;long long mod = 998244353;if(H < W) swap(H,W);vector<long long> fac(H+1,1),inv(H+1),facinv(H+1,1);for(int i=1; i<=H; i++) fac.at(i) = fac.at(i-1)*i%mod;inv.at(1) = 1;for(int i=2; i<=H; i++) inv.at(i) = mod-(mod/i*inv.at(mod%i)%mod);for(int i=1; i<=H; i++) facinv.at(i) = facinv.at(i-1)*inv.at(i)%mod;long long answer = 0;for(int i=0; i<H; i++){long long h = fac.at(H)*facinv.at(H-i)%mod*facinv.at(i)%mod,leftK = H*W-W*i-K;if(leftK%(H-i) != 0 || leftK < 0) continue;long long w = leftK/(H-i);w = fac.at(W)*facinv.at(W-w)%mod*facinv.at(w)%mod;answer = (answer+h*w)%mod;}if(K == 0){long long power2 = 1;for(int i=0; i<H; i++) power2 = power2*2%mod;answer += power2;power2 = 1;for(int i=0; i<W; i++) power2 = power2*2%mod;answer += power2;answer = (answer-1)%mod;}cout << answer << endl;}