結果
問題 |
No.2206 Popcount Sum 2
|
ユーザー |
![]() |
提出日時 | 2025-08-14 17:18:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 817 ms / 4,000 ms |
コード長 | 1,650 bytes |
コンパイル時間 | 1,937 ms |
コンパイル使用メモリ | 199,048 KB |
実行使用メモリ | 13,056 KB |
最終ジャッジ日時 | 2025-08-14 17:18:56 |
合計ジャッジ時間 | 13,260 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; using LL = long long; const int kMaxN = 2e5 + 5, kM = 998244353, kInV = (kM + 1) / 2; const int kMaxD = 505; struct A { int l, r, p, id; bool operator<(const A &a) const { return p == a.p ? r < a.r : l < a.l; } } a[kMaxN]; LL ans[kMaxN], v[kMaxN], n; LL p[kMaxN], inv[kMaxN]; LL P(LL x, LL y) { LL ans = 1; for (LL i = 1; i <= y; i <<= 1, x = x * x % kM) { (y & i) && (ans = ans * x % kM); } return ans; } LL C(LL x, LL y) { if (x < y || x < 0 || y < 0) { return 0; } else { return p[x] * inv[y] % kM * inv[x - y] % kM; } } int main() { ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0); p[0] = inv[0] = 1; for (int i = 1; i < kMaxN; i++) { p[i] = p[i - 1] * i % kM; inv[i] = P(p[i], kM - 2); } cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r; v[i] = a[i].l; a[i].l--, a[i].r--; a[i].p = a[i].l / kMaxD + bool(a[i].l % kMaxD), a[i].id = i; } sort(a + 1, a + n + 1); LL s = 0; for (int i = 0; i <= a[1].r; i++) { s = (s + C(a[1].l, i)) % kM; } ans[a[1].id] = s; int x = a[1].l, y = a[1].r; for (int i = 2; i <= n; i++) { for (; y < a[i].r; y++, s = (s + C(x, y)) % kM) { } for (; y > a[i].r; s = (s - C(x, y) + kM) % kM, y--) { } for (; x < a[i].l; s = (s * 2 - C(x, y) + kM) % kM, x++) { } for (; x > a[i].l; x--, s = (s + C(x, y)) % kM * kInV % kM) { } // cout << x << " " << y << " " << s << " " << a[i].id << "\n"; ans[a[i].id] = s; } for (int i = 1; i <= n; i++) { cout << ans[i] * (P(2, v[i]) - 1 + kM) % kM << "\n"; } return 0; }