結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 17:26:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 926 ms / 4,000 ms
コード長 1,363 bytes
コンパイル時間 3,377 ms
コンパイル使用メモリ 282,952 KB
実行使用メモリ 13,036 KB
最終ジャッジ日時 2025-08-02 17:27:12
合計ジャッジ時間 15,500 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN = 2e5 + 5, kM = 998244353, Inv = (kM + 1) / 2;

int n, s = 1, len, ans[kMaxN], inv[kMaxN], fac[kMaxN];
struct Node {
  int l, r, id;
  bool operator<(const Node &_) const {
    return l / len != _.l / len ? l / len < _.l / len : r < _.r;
  }
} q[kMaxN];

template <typename T>
T W(T a, T n, T kM, T r = 1) {
  for (T i = 1; i <= n; n & i && (r = r * a % kM), a = a * a % kM, i <<= 1);
  return r;
}
int C(int x, int y) {
  if (x < 0 || y < 0 || x < y) return 0;
  return fac[x] * inv[y] % kM * inv[x - y] % kM;
}

signed main() {
  cin.tie(0)->ios::sync_with_stdio(0);
  fac[0] = inv[0] = 1;
  for (int i = 1; i < kMaxN; i++) {
    fac[i] = fac[i - 1] * i % kM;
    inv[i] = W(fac[i], kM - 2, kM);
  }
  cin >> n, len = sqrt(n);
  for (int i = 1; i <= n; i++) {
    cin >> q[i].l >> q[i].r;
    q[i].l--, q[i].r--, q[i].id = i;
  }
  sort(q + 1, q + n + 1);
  for (int i = 1, l = 0, r = 0; i <= n; i++) {
    for (; l < q[i].l; s = (s * 2 % kM - C(l, r) + kM) % kM, l++);
    for (; l > q[i].l; l--, s = (s + C(l, r)) % kM * Inv % kM);
    for (; r < q[i].r; r++, s = (s + C(l, r)) % kM);
    for (; r > q[i].r; s = (s - C(l, r) + kM) % kM, r--);
    ans[q[i].id] = s * ((W(2LL, q[i].l + 1, kM) - 1 + kM) % kM) % kM;
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}
0