結果
問題 | No.2527 H and W |
ユーザー |
![]() |
提出日時 | 2023-11-03 21:56:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 1,679 bytes |
コンパイル時間 | 7,764 ms |
コンパイル使用メモリ | 346,188 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-09-25 20:10:44 |
合計ジャッジ時間 | 8,772 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#ifdef DEBUG#define _GLIBCXX_DEBUG#else#pragma GCC target("avx2")#pragma GCC optimize("Ofast,unroll-loops")#endif#include <bits/stdc++.h>#include <atcoder/all>#define rep(i, n) for (int i = 0; i < n; i++)#define per(i, n) for (int i = n - 1; i >= 0; i--)#define ALL(a) a.begin(), a.end()#undef long#define long long longusing namespace std;using mint = atcoder::modint998244353;ostream& operator<<(ostream& os, const mint& a) {return os << a.val();}template<typename T>ostream& operator<<(ostream& os, const vector<T>& a) {const int n = a.size();rep(i, n) os << a[i] << " \n"[i + 1 == n];return os;}template<typename T>istream& operator>>(istream& os, const vector<T>& a) {for (T& i : a) os >> i;return os;}void chmin(int& x, int y) {if (x > y) x = y;}void chmax(int& x, int y) {if (x < y) x = y;}void solve() {long h, w, k; cin >> h >> w >> k;if (h * w == k) {cout << 1 << '\n';return;}k = h * w - k;constexpr int n = 1e6 + 2022;vector<mint> fact(n + 1), finv(n + 1);fact[0] = 1;for (int i = 1; i <= n; i++) fact[i] = i * fact[i - 1];finv[n] = fact[n].inv();for (int i = n; i >= 1; i--) finv[i - 1] = i * finv[i];auto com = [&](int nn, int kk) {return fact[nn] * finv[kk] * finv[nn - kk];};mint ans = 0;for (int i = 0; i < h; i++) {long bunsi = k - i * w;if (bunsi < 0) break;if (bunsi % (h - i) != 0) continue;long jj = bunsi / (h - i);if (jj < 0 || jj > w) continue;ans += com(h, i) * com(w, jj);}cout << ans << '\n';}int main() {// srand((unsigned)time(NULL));cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(40);solve();return 0;}