結果

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

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>
const int MOD = 998244353;
int H, W, K;
int h, w, n, d;
int f[400010], invf[400010];
int ans;
int mod_pow(int a, int e) {
    int r = 1;
    while (e) {
        if (e & 1) r = 1LL * r * a % MOD;
        a = 1LL * a * a % MOD;
        e >>= 1;
    }
    return r;
}
#define C(n, k) ((k) < 0 || (k) > (n) ? 0 : 1LL * f[n] * invf[k] % MOD * invf[(n) - (k)] % MOD)
int main() {
    scanf("%d %d %d", &H, &W, &K);
    h = H - 1;
    w = W - 1;
    n = h + w;
    d = K / 2;
    f[0] = invf[0] = 1;
    for (int i = 1; i <= n; ++i) f[i] = 1LL * f[i-1] * i % MOD;
    invf[n] = mod_pow(f[n], MOD - 2);
    for (int i = n; i >= 1; --i) invf[i-1] = 1LL * invf[i] * i % MOD;
    if (d == 0) {
        printf("%d\n", C(n, h));
        return 0;
    }
    int M = (h < w) ? h : w;
    int period = 2 * d + 2;
    ans = 0;
    for (int m = 0; m <= M; ++m) {
        int sum1 = 1LL * C(n, 2*m) * C(n - 2*m, h - m) % MOD;
        int n2 = 2 * m;
        long long bridge = 0;
        int kmin = - (n2 + period) / period - 2;
        int kmax = (n2 + period) / period + 2;
        for (int k = kmin; k <= kmax; ++k) {
            int t1 = m + k * period;
            int t2 = m + d + 1 + k * period;
            long long val1 = (t1 < 0 || t1 > n2) ? 0 : 1LL * f[n2] * invf[t1] % MOD * invf[n2 - t1] % MOD;
            long long val2 = (t2 < 0 || t2 > n2) ? 0 : 1LL * f[n2] * invf[t2] % MOD * invf[n2 - t2] % MOD;
            bridge += val1 - val2;
        }
        bridge %= MOD;
        if (bridge < 0) bridge += MOD;
        ans = (ans + sum1 * bridge) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}
0