結果
問題 | No.2474 Empty Quartz |
ユーザー |
![]() |
提出日時 | 2023-08-16 19:45:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,387 bytes |
コンパイル時間 | 770 ms |
コンパイル使用メモリ | 84,400 KB |
最終ジャッジ日時 | 2025-02-16 08:49:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 |
ソースコード
#include <atcoder/modint> #include <cmath> #include <iostream> using namespace std; using mint = atcoder::modint998244353; using i64 = long long; mint fact[200010]; mint ifact[200010]; mint binom(int n, int r) { if (n < 0 || r < 0 || n < r) return 0; return fact[n] * ifact[r] * ifact[n - r]; } void solve() { i64 n, k; cin >> n >> k; i64 d = (n + 1) * (n + 1) - 4 * k; if (d < 0) { cout << 0 << "\n"; return; } i64 tmpr = sqrtl(d); i64 r = -1; for (i64 j = max(0ll, tmpr - 3); j <= tmpr + 3; j++) { if (j * j == d) { r = j; break; } } if (r == -1) { cout << 0 << "\n"; return; } i64 a = n + 1 + r; if (a < 0 && a & 1) { cout << 0 << "\n"; return; } a >>= 1; i64 b = n + 1 - a; if (b < 0) { cout << 0 << "\n"; return; } mint ans = binom(a + b - 1, a) + binom(a + b - 1, a - 1); if (a == b) ans -= binom(a + b - 1, a); cout << ans.val() << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int t; cin >> t; fact[0] = 1; for (int i = 1; i <= 200000; i++) { fact[i] = fact[i - 1] * i; } ifact[200000] = fact[200000].inv(); for (int i = 200000; i > 0; i--) { ifact[i - 1] = ifact[i] * i; } while (t--) solve(); }