結果
問題 |
No.2206 Popcount Sum 2
|
ユーザー |
![]() |
提出日時 | 2025-08-11 11:39:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,505 bytes |
コンパイル時間 | 3,134 ms |
コンパイル使用メモリ | 281,024 KB |
実行使用メモリ | 16,188 KB |
最終ジャッジ日時 | 2025-08-11 11:39:19 |
合計ジャッジ時間 | 10,975 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | WA * 18 |
ソースコード
#include <bits/stdc++.h> #define int long long using namespace std; const int kMaxN = 2e5 + 5, kM = 998244353; int T, B, ans[kMaxN], p[kMaxN], fac[kMaxN], inv[kMaxN], ifac[kMaxN], ret = 1; struct Q { int n, m, i; } q[kMaxN]; void Init() { p[0] = fac[0] = 1; for (int i = 1; i < kMaxN; i++) { p[i] = 2 * p[i - 1] % kM; fac[i] = 1LL * i * fac[i - 1] % kM; } ifac[0] = ifac[1] = inv[1] = 1; for (int i = 2; i < kMaxN; i++) { inv[i] = 1LL * (kM - kM / i) * inv[kM % i] % kM; ifac[i] = 1LL * inv[i] * ifac[i - 1] % kM; } } int Binom(int m, int n) { if (m < n) return 0; return 1LL * fac[m] * ifac[n] % kM * ifac[m - n] % kM; } signed main() { ios::sync_with_stdio(0), cin.tie(0); Init(); cin >> T, B = sqrt(T); for (int i = 1; i <= T; i++) { cin >> q[i].n >> q[i].m, q[i].i = i; } sort(q + 1, q + 1 + T, [](Q x, Q y) { if (x.n / B != y.n / B) return x.n / B < y.n / B; return x.n / B % 2 ? x.m < y.m : x.m > y.m; }); for (int i = 1, N = 1, M = 1; i <= T; i++) { for (; N < q[i].n; N++) { ret = (2LL * ret - Binom(N - 1, M - 1) + kM) % kM; } for (; N > q[i].n; N--) { ret = 1LL * (ret + Binom(N - 1, M - 1)) * inv[2] % kM; } for (; M < q[i].m; M++) { ret = (ret + Binom(N - 1, M)) % kM; } for (; M > q[i].m; M--) { ret = (ret - Binom(N - 1, M - 1) + kM) % kM; } ans[i] = 1LL * (p[N] - 1) * ret % kM; } for (int i = 1; i <= T; i++) { cout << ans[i] << '\n'; } return 0; }