結果
問題 | No.2527 H and W |
ユーザー |
![]() |
提出日時 | 2023-11-03 21:45:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 3,189 bytes |
コンパイル時間 | 1,276 ms |
コンパイル使用メモリ | 107,712 KB |
最終ジャッジ日時 | 2025-02-17 18:02:11 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>using namespace std;using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;#define TEST cerr << "TEST" << endl#define AMARI 998244353// #define AMARI 1000000007#define TIME_LIMIT 1980000#define el '\n'#define El '\n'// 二項係数の計算(余り付き)// nCkについて、n,k<10^7の時前処理O(N)、計算O(1)で行うclass ococo_combination {public:long long n, p;vector<long long> kaizyou, gyakugen, gyakugen_kaizyou;// 二項係数に出てくる最大値をaに変更する// O(1) ここで変更したaが他の関数の計算時間に影響を与える。void update_max(int a) {n = a;kaizyou.resize(n);gyakugen.resize(n);gyakugen_kaizyou.resize(n);}// 素数で割った余りを出力する時その余りをpに変更する// a = 0にすると余りは出さずに計算する// O(1)void update_mod(int a) {p = a;}// 前処理を行う update_maxとupdate_modを先にやった方が良い// O(N)void maesyori(void) {kaizyou[0] = 1;gyakugen[0] = 1;gyakugen_kaizyou[0] = 1;kaizyou[1] = 1;gyakugen[1] = 1;gyakugen_kaizyou[1] = 1;for(int i = 2; i < n; i++) {kaizyou[i] = kaizyou[i - 1] * i % p;gyakugen[i] = p - gyakugen[p % i] * (p / i) % p;gyakugen_kaizyou[i] = gyakugen_kaizyou[i - 1] * gyakugen[i] % p;}}// 二項係数nCkの計算を行う// O(1)long long nCk(int n, int k) {if(n < k || n < 0 || k < 0) return 0;else {long long ans = kaizyou[n];long long kari = gyakugen_kaizyou[n - k];kari %= p;kari *= gyakugen_kaizyou[k];kari %= p;ans *= kari;ans %= p;return ans;}}};#define MULTI_TEST_CASE falsevoid solve(void) {ococo_combination oc;ll h,w,k;cin >> h >> w >> k;oc.update_max(max(h,w) + 1);oc.update_mod(AMARI);oc.maesyori();ll ans = 0;//y=一定にi本引くことを考えるfor(ll i = 0; i <= h; i++){ll black = w * (h - i);if(black < k)break;//x=一定に1本追加で引くことで黒いマスは(h-i)個減るif((black - k) % (h - i) != 0)continue;ll j = (black - k) / (h - i);//cerr << i << ' ' << j << el;if(j < 0)continue;ans += oc.nCk(h,i) * oc.nCk(w,j);ans %= AMARI;}cout << ans << el;return;}void calc(void) {return;}signed main(void) {cin.tie(nullptr);ios::sync_with_stdio(false);calc();int t = 1;if(MULTI_TEST_CASE) cin >> t;while(t--) {solve();}return 0;}