結果

問題 No.1970 ひよこ鑑定士
コンテスト
ユーザー 57tggx
提出日時 2025-05-22 12:56:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,649 bytes
コンパイル時間 2,305 ms
コンパイル使用メモリ 196,420 KB
実行使用メモリ 9,480 KB
最終ジャッジ日時 2025-05-22 12:56:41
合計ジャッジ時間 3,600 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 2 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
static const int MOD = 998244353;

// 階乗テーブルと逆元テーブル
vector<long long> fact, ifact;

// a^b mod M (b が省略されていれば逆元計算)
long long modpow(long long a, long long b = MOD-2) {
    long long r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

// nCk mod
long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] % MOD * ifact[n-k] % MOD;
}

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

    int N, K;
    cin >> N >> K;

    // 1) 階乗・逆階乗の前計算 (0 ≤ i ≤ 2N)
    fact.assign(2*N+1, 1);
    for(int i = 1; i <= 2*N; i++) fact[i] = fact[i-1] * i % MOD;
    ifact.assign(2*N+1, 1);
    ifact[2*N] = modpow(fact[2*N]);
    for(int i = 2*N; i > 0; i--) ifact[i-1] = ifact[i] * i % MOD;

    // 2) 全通り = C(2N, N)
    long long total = C(2*N, N);

    // 3) bad = 範囲 (max−min) ≤ K−1 の「橋」の数を反射法で数え上げ
    int M = K - 1;
    int D = M + 1;              // 反射の幅
    int limit = (2*N) / D + 2;  // ±limit まで走れば十分（範囲外は C()=0）

    long long bad = 0;
    for(int r = -limit; r <= limit; r++){
        long long t = C(2*N, N + r * D);
        // r の偶奇で交互に足し引き
        if (r & 1) bad = (bad - t) % MOD;
        else       bad = (bad + t) % MOD;
    }
    if (bad < 0) bad += MOD;

    // 4) 答え = total − bad
    long long ans = (total - bad) % MOD;
    if (ans < 0) ans += MOD;
    cout << ans << "\n";
    return 0;
}
0