結果

問題 No.1388 Less than K
コンテスト
ユーザー vjudge1
提出日時 2026-04-11 10:05:06
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,355 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,319 ms
コンパイル使用メモリ 215,444 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2026-04-11 10:05:38
合計ジャッジ時間 8,071 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

static const long long MOD = 998244353;

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

struct Comb {
    vector<long long> fac, ifac;
    Comb(int n = 0) { init(n); }

    void init(int n) {
        fac.assign(n + 1, 1);
        ifac.assign(n + 1, 1);
        for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
        ifac[n] = mod_pow(fac[n], MOD - 2);
        for (int i = n; i >= 1; --i) ifac[i - 1] = ifac[i] * i % MOD;
    }

    long long C(int n, int k) const {
        if (k < 0 || k > n) return 0;
        return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
    }
};

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

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

    int h = (int)(H - 1);
    int w = (int)(W - 1);
    int N = h + w;
    int d = (int)(K / 2);

    Comb comb(N);

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

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

    auto bounded_bridge = [&](int m) -> long long {
        // B(m,d):
        // sum_k [ C(2m, m + k*(2d+2)) - C(2m, m+d+1 + k*(2d+2)) ]
        int n = 2 * m;
        int period = 2 * d + 2;
        long long res = 0;

        // ???????????[0, 2m]? k
        int kmin = - (n + period) / period - 2;
        int kmax =   (n + period) / period + 2;

        for (int k = kmin; k <= kmax; ++k) {
            int t1 = m + k * period;
            int t2 = m + d + 1 + k * period;
            res += comb.C(n, t1);
            res -= comb.C(n, t2);
            res %= MOD;
        }
        if (res < 0) res += MOD;
        return res;
    };

    long long ans = 0;
    int M = min(h, w);

    for (int m = 0; m <= M; ++m) {
        long long choose_mixed = comb.C(N, 2 * m);
        long long choose_same = comb.C(N - 2 * m, h - m);
        long long bridge_cnt = bounded_bridge(m);

        long long add = choose_mixed * choose_same % MOD * bridge_cnt % MOD;
        ans += add;
        if (ans >= MOD) ans -= MOD;
    }

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