結果

問題 No.1388 Less than K
コンテスト
ユーザー vjudge1
提出日時 2026-04-11 12:17:23
言語 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,750 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 287 ms
コンパイル使用メモリ 45,908 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2026-04-11 12:17:56
合計ジャッジ時間 7,342 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, h, w, n, d, M, period;
int f[400010], invf[400010];
long long 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;
}
int main() {
    scanf("%d %d %d", &H, &W, &K);
    h = H - 1;
    w = W - 1;
    n = h + w;
    d = K / 2;
    M = (h < w) ? h : w;
    period = 2 * d + 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("%lld\n", 1LL * f[n] * invf[h] % MOD * invf[n-h] % MOD);
        return 0;
    }
    ans = 0;
    for (int m = 0; m <= M; ++m) {
        int n2 = m * 2;
        long long c1 = 1LL * f[n] * invf[n2] % MOD * invf[n - n2] % MOD;
        long long c2 = 1LL * f[n - n2] * invf[h - m] % MOD * invf[(n - n2) - (h - m)] % MOD;
        long long sum1 = c1 * c2 % MOD;
        int kmin = - (n2 + period) / period - 2;
        int kmax = (n2 + period) / period + 2;
        long long bridge = 0;
        long long fn2 = f[n2];
        for (int k = kmin; k <= kmax; ++k) {
            int t1 = m + k * period;
            int t2 = m + d + 1 + k * period;
            long long v1 = (t1 < 0 || t1 > n2) ? 0 : fn2 * invf[t1] % MOD * invf[n2 - t1] % MOD;
            long long v2 = (t2 < 0 || t2 > n2) ? 0 : fn2 * invf[t2] % MOD * invf[n2 - t2] % MOD;
            bridge += v1 - v2;
        }
        bridge %= MOD;
        if (bridge < 0) bridge += MOD;
        ans = (ans + sum1 * bridge) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}
0