結果
問題 | 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 long using 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; }