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

• 問題: No.1388 Less than K
• ユーザー: vjudge1
• 提出日時: 2026-04-18 16:53:10
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,070 bytes
• コンパイル時間: 2,908 ms
• コンパイル使用メモリ: 340,300 KB
• 実行使用メモリ: 11,300 KB
• 最終ジャッジ日時: 2026-04-18 16:53:59
• 合計ジャッジ時間: 14,577 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
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;
}

// ---------- ??????????????? O(N)?----------
struct LargeComb {
    static const int BLOCK = 10000;   // ????????? N ??
    vector<long long> block_fac;
    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;
        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;
        }
    }

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

    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;
        if (n == end_block) return block_inv_fac[next_b];
        long long res = block_inv_fac[next_b];
        for (long long i = end_block; i > n; --i) {
            res = res * (i % MOD) % MOD;
        }
        return res;
    }

    long long C(long long n, long long k) const {
        if (k < 0 || k > n) return 0;
        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, w = W - 1, N = h + w;
    long long d = K / 2;

    if (d == 0) {
        LargeComb comb(N);
        cout << comb.C(N, h) % MOD << '\n';
        return 0;
    }
    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 ???????????
    // ????: 0 <= h - kP <= N ? 0 <= h + kP <= N
    long long k_min_1 = (h - N) / P - 2;
    long long k_max_1 = h / P + 2;
    long long k_min_2 = (-h) / P - 2;
    long long k_max_2 = (N - h) / P + 2;
    long long k_min = max(k_min_1, k_min_2);
    long long k_max = min(k_max_1, k_max_2);

    // ???????????????????????
    // ?????? k ???????
    for (long long k = k_min; k <= k_max; ++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 << '\n';
    return 0;
}