結果
問題 | No.2527 H and W |
ユーザー | soyamash |
提出日時 | 2023-11-04 11:17:58 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,765 bytes |
コンパイル時間 | 783 ms |
コンパイル使用メモリ | 69,400 KB |
実行使用メモリ | 19,364 KB |
最終ジャッジ日時 | 2023-11-04 11:18:03 |
合計ジャッジ時間 | 4,463 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 24 ms
19,228 KB |
testcase_01 | AC | 24 ms
14,856 KB |
testcase_02 | WA | - |
testcase_03 | AC | 24 ms
14,856 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; //cin, coutを使う unsigned int big_num = 998244353 ; const unsigned int MAX = 1000005; const unsigned int MOD = 998244353; std::vector<unsigned int> fac, finv, inv; // テーブルを作る前処理 void COMinit() { fac.resize(MAX); finv.resize(MAX); inv.resize(MAX); fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 unsigned int COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; if (n == k) return 1; if (n == 1) return k; if (k == 1) return n; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int min_x (int a, int b){ if (a < b) { return a; } else { return b; } } int Cx(int a, int b){ unsigned int i = 1; for (int h = 0; h < b; h++){ i *= (a - h); i /= (b - h); } if (i > big_num) i %= big_num; return (int)i; }; int yakusuu(int N, vector<int> &y){ for (int i = 1; i * i <= N; i++){ if (N % i == 0){ y.push_back(i); if (i != (int)(N / i)){ y.push_back((int)(N / i)); } } } std::sort(y.begin(), y.end()); return 0; }; int nibun_tansa(vector<int> &w_list, int W){ int head = 0; int tail = w_list.size(); while (1){ int c_idx = head + (int)((tail - head) / 2); if (W < w_list[c_idx]){ tail = c_idx; if (W > w_list[tail - 1]){ return w_list[tail - 1]; } } else { head = c_idx; if (tail - head == 1 or W < w_list[head + 1]){ return w_list[head]; } } } }; int main(){ int H, W, K; cin >> H >> W >> K; if (H > W){ int s = W; W = H; H = s; } COMinit(); vector<int> y; yakusuu(K, y); int max_h = nibun_tansa(y, H); int max_w = nibun_tansa(y, W); unsigned int ret = 0; for (int i : y){ if (i <= max_h and (int)(K / i) <= max_w) { unsigned int hi = COM(H, i); if (hi > big_num) hi %= big_num; unsigned int wk_i = COM(W, (int)(K / i)); if (wk_i > big_num) wk_i %= big_num; ret += hi * wk_i; //std::cout << hi << std::endl; //std::cout << wk_i << std::endl; //std::cout << i << " " << hi * wk_i << " " << ret << std::endl; if (ret > big_num) ret %= big_num; } } cout << ret << endl; };