結果
問題 |
No.1970 ひよこ鑑定士
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }