結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-05 09:18:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 952 ms / 4,000 ms
コード長 1,543 bytes
コンパイル時間 1,639 ms
コンパイル使用メモリ 169,136 KB
実行使用メモリ 12,980 KB
最終ジャッジ日時 2025-08-05 09:19:02
合計ジャッジ時間 12,143 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;
using Pii = pair<int, int>;

const int N = 2e5 + 5, M = 500, P = 998244353;

struct Q {
  int l, r, id;
} w[N];

int q, f[N], I[N], l, r, d = 1, e[N];

int C(int x, int y) {
  return f[x] * I[y] % P * I[x - y] % P;
}

void A(int x, int v) {
  if (v) {
    d = (d * 2 - C(x - 1, l) + P) % P;
  } else {
    d = (d + C(r, x)) % P;
  }
}

void D(int x, int v) {
  if (v) {
    d = ((P + 1) / 2 * (d + C(x, l + 1) - C(x - 1, l + 1) + P)) % P;
  } else {
    d = (d - C(r, x) + P) % P;
  }
}

int Qp(int x, int y, int P = ::P) {
  if (!y) {
    return 1;
  }
  int z = Qp(x, y / 2, P);
  return z * z % P * (y & 1 ? x : 1) % P;
}

signed main() {
  cin.tie(0)->ios::sync_with_stdio(0);
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> w[i].r >> w[i].l;
    w[i].l--;
    w[i].r--;
    w[i].id = i;
  }
  for (int i = f[0] = I[0] = I[1] = 1; i < N; i++) {
    f[i] = f[i - 1] * i % P;
    if (i > 1) {
      I[i] = I[P % i] * (-P / i + P) % P;
    }
  }
  for (int i = 1; i < N; i++) {
    I[i] = I[i] * I[i - 1] % P;
  }
  sort(w + 1, w + q + 1, [](Q x, Q y) { return (x.l / M) != (y.l / M) ? (x.l / M < y.l / M) : x.r < y.r; });
  for (int i = 1; i <= q; i++) {
    for (; l > w[i].l; D(l--, 0)) {
    }
    for (; r < w[i].r; A(++r, 1)) {
    }
    for (; r > w[i].r; D(r--, 1)) {
    }
    for (; l < w[i].l; A(++l, 0)) {
    }
    e[w[i].id] = d * (Qp(2, w[i].r + 1) + P - 1) % P;
  }
  for (int i = 1; i <= q; i++) {
    cout << e[i] << '\n';
  }
  return 0;
}
/*
 */
0