#1159783 (C++23) No.1388 Less than K

• 問題: No.1388 Less than K
• ユーザー: vjudge1
• 提出日時: 2026-04-18 16:45:58
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,193 bytes
• コンパイル時間: 2,564 ms
• コンパイル使用メモリ: 336,072 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-18 16:46:52
• 合計ジャッジ時間: 13,122 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 18 TLE * 1 -- * 55

ソースコード

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long mod_pow(long long a, long long e) {
    long long res = 1;
    a %= MOD;
    while (e) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

// ---------- ??????????????? inv_fac? ----------
struct LargeComb {
    static const int BLOCK = 50000;   // ???
    vector<long long> block_fac;      // ? i ??????
    vector<long long> block_inv_fac;  // ????
    long long N_max;

    LargeComb(long long n = 0) {
        if (n <= 0) return;
        N_max = n;
        int num_blocks = (n + BLOCK) / BLOCK;
        block_fac.resize(num_blocks + 1);
        block_inv_fac.resize(num_blocks + 1);

        // ?? block_fac[0] = 1
        block_fac[0] = 1;
        for (int b = 0; b < num_blocks; ++b) {
            long long start = (long long)b * BLOCK;
            long long end = min((long long)(b + 1) * BLOCK, n);
            long long cur = block_fac[b];
            for (long long i = start + 1; i <= end; ++i) {
                cur = cur * (i % MOD) % MOD;
            }
            block_fac[b + 1] = cur;
        }

        // ?????????????
        block_inv_fac[num_blocks] = mod_pow(block_fac[num_blocks], MOD - 2);
        for (int b = num_blocks; b >= 1; --b) {
            long long start = (long long)(b - 1) * BLOCK + 1;
            long long end = min((long long)b * BLOCK, n);
            long long cur = block_inv_fac[b];
            for (long long i = end; i >= start; --i) {
                cur = cur * (i % MOD) % MOD;
            }
            block_inv_fac[b - 1] = cur;
        }
    }

    // n! mod MOD
    long long fac(long long n) const {
        if (n < 0 || n > N_max) return 0;
        int b = n / BLOCK;
        long long res = block_fac[b];
        long long start = (long long)b * BLOCK + 1;
        for (long long i = start; i <= n; ++i) {
            res = res * (i % MOD) % MOD;
        }
        return res;
    }

    // ???? inv_fac?1 / n! mod MOD
    long long inv_fac(long long n) const {
        if (n < 0 || n > N_max) return 0;
        int b = n / BLOCK;
        // ????????
        int next_b = b + 1;
        long long end_block = (long long)next_b * BLOCK;
        if (end_block > N_max) end_block = N_max;

        // ?? n ???????????????? N_max?
        if (n == end_block) return block_inv_fac[next_b];

        // ??????????????????? end_block ? n+1 ???????
        long long res = block_inv_fac[next_b];
        for (long long i = end_block; i > n; --i) {
            res = res * (i % MOD) % MOD;
        }
        return res;
    }

    // C(n, k) mod MOD
    long long C(long long n, long long k) const {
        if (k < 0 || k > n) return 0;
        if (n > N_max) {
            throw runtime_error("n exceeds precomputed range");
        }
        long long num = fac(n);
        long long den = inv_fac(k) * inv_fac(n - k) % MOD;
        return num * den % MOD;
    }
};

// ---------- ??? ----------
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long H, W, K;
    cin >> H >> W >> K;

    long long h = H - 1;
    long long w = W - 1;
    long long N = h + w;
    long long d = K / 2;

    // ??1?d == 0???????????
    if (d == 0) {
        LargeComb comb(N);
        cout << comb.C(N, h) % MOD << '\n';
        return 0;
    }

    // ??2?????????
    if (d >= min(h, w)) {
        LargeComb comb(N);
        long long single = comb.C(N, h);
        cout << single * single % MOD << '\n';
        return 0;
    }

    long long P = 2 * d + 2;
    LargeComb comb(N);
    long long ans = 0;

    // ???? k???????????
    for (long long k = -N; k <= N; ++k) {
        // ??
        long long r1 = h - k * P;
        long long r2 = h + k * P;
        if (r1 >= 0 && r1 <= N && r2 >= 0 && r2 <= N) {
            ans = (ans + comb.C(N, r1) * comb.C(N, r2)) % MOD;
        }

        // ??
        long long s1 = h - d - 1 - k * P;
        long long s2 = h + d + 1 + k * P;
        if (s1 >= 0 && s1 <= N && s2 >= 0 && s2 <= N) {
            ans = (ans - comb.C(N, s1) * comb.C(N, s2) % MOD + MOD) % MOD;
        }
    }

    cout << ans % MOD << '\n';
    return 0;
}