結果

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

ソースコード

diff # 

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

// fast exponentiation
ll modpow(ll a, ll e=MOD-2) {
    ll r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

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

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

    // 1) Precompute factorials up to 2N
    vector<ll> fact(2*N+1,1), ifact(2*N+1,1);
    for(int i=1;i<=2*N;i++){
        fact[i] = fact[i-1] * i % MOD;
    }
    ifact[2*N] = modpow(fact[2*N]);
    for(int i=2*N; i>0; i--){
        ifact[i-1] = ifact[i] * i % MOD;
    }

    auto C = [&](int n, int k)->ll {
        if(k<0 || k>n) return 0;
        return fact[n] * ifact[k] % MOD * ifact[n-k] % MOD;
    };

    // total number of seatings
    ll total = C(2*N, N);

    // count the "bad" walks whose range ≤ K-1
    ll bad = 0;
    for(int a = -(K-1); a <= 0; a++){
        int b = a + (K-1);
        int width = b - a + 1;      // = K
        int period = width + 1;     // = (b-a+2)

        ll confined = 0;
        // reflection sum over m
        // we only need those m for which the binomial arguments lie in [0..2N]
        // m*(period) runs from roughly -2N to +2N
        int mmin = ( -N - N ) / period - 1;
        int mmax = (  N + N ) / period + 1;
        for(int m = mmin; m <= mmax; m++){
            int idx1 = N + m*period;
            int idx2 = idx1 + (a+1);
            ll add = (C(2*N, idx1) - C(2*N, idx2) + MOD) % MOD;
            confined = (confined + add) % MOD;
        }
        bad = (bad + confined) % MOD;
    }

    // answer = total − bad  (mod 998244353)
    ll ans = (total - bad + MOD) % MOD;
    cout << ans << "\n";
    return 0;
}
0