結果
問題 | No.2527 H and W |
ユーザー |
|
提出日時 | 2023-11-03 23:26:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 3,098 bytes |
コンパイル時間 | 4,466 ms |
コンパイル使用メモリ | 258,128 KB |
最終ジャッジ日時 | 2025-02-17 18:55:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#ifdef ONLINE_JUDGE#include <bits/stdc++.h>#include <atcoder/all>#else#include <mylibs/all.h>#endifusing ll = long long;using lll = __int128_t;#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)#define length(v) ((int)(v).size())constexpr int inf = 2'000'000'000;constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353;#define all(v) begin(v), end(v)#define rall(v) rbegin(v), rend(v)using namespace std;using namespace atcoder;inline ostream& operator<<(ostream& os, lll val) noexcept {string s;bool neg = val < 0;if (val < 0) {val *= -1;}if (val == 0) {s += '0';} else {while (val > 0) {s += '0' + val % 10;val /= 10;}}reverse(all(s));if (neg) s = "-" + s;return os << s;}inline istream& operator>>(istream& is, lll& val) noexcept {string s;is >> s;bool neg = false;if (s[0] == '-') {neg = true;s = s.substr(1);}val = 0;for (auto c : s) {val *= 10;val += c - '0';}if (neg) val *= -1;return is;}constexpr ll MOD = M9;using mint = static_modint<MOD>;struct modInv {int n;vector<mint> d;modInv() : n(2), d({0, 1}) {}mint operator()(int i) {while (n <= i) d.emplace_back(-d[MOD % n] * (MOD / n)), ++n;return d[i];}mint operator[](int i) const { return d[i]; }} invs;struct Factorial {int n;vector<mint> d;Factorial() : n(2), d({1, 1}) {}mint operator()(int i) {while (n <= i) d.emplace_back(d.back() * n), ++n;return d[i];}mint operator[](int i) const { return d[i]; }} factorial;struct FactorialInv {int n;vector<mint> d;FactorialInv() : n(2), d({1, 1}) {}mint operator()(int i) {while (n <= i) d.emplace_back(d.back() * invs(n)), ++n;return d[i];}mint operator[](int i) const { return d[i]; }} factorialInv;mint P(int n, int r) {if (n < r || n < 0 || r < 0) return 0;return factorial(n) * factorialInv(n - r);}mint C(int n, int r) {if (n < r || n < 0 || r < 0) return 0;return factorial(n) * factorialInv(r) * factorialInv(n - r);}mint H(int n, int r) {const int _n = n + r - 1;if (_n < r || _n < 0 || r < 0) return 0;return factorial(_n) * factorialInv(r) * factorialInv(_n - r);}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);lll h, w, k;cin >> h >> w >> k;lll l = h * w - k;mint ans = 0;rep(x, w) {if ((l - x * h) % (w - x) == 0) {lll y = (l - x * h) / (w - x);ans += C(w, x) * C(h, y);}}cout << ans.val() << endl;return 0;}