結果

問題 No.2527 H and W
ユーザー coindarw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>

#include <atcoder/all>
#else
#include <mylibs/all.h>
#endif

using 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;
}
0