結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-10-29 21:48:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 750 ms / 4,000 ms
コード長 1,480 bytes
コンパイル時間 3,042 ms
コンパイル使用メモリ 281,976 KB
実行使用メモリ 14,564 KB
最終ジャッジ日時 2025-10-29 21:48:51
合計ジャッジ時間 14,314 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

const int kMaxN = 2e5 + 10, kMod = 998244353;

struct node {
  int x, y, id;
} p[kMaxN];

int st[kMaxN], fac[kMaxN], inv[kMaxN], ans[kMaxN], n;

int P(int x, int y) {
  int z = 1;
  for (; y; (y & 1) && (z = z * x % kMod), y >>= 1, x = x * x % kMod);
  return z;
}

int C(int x, int y) { return fac[x] * inv[y] % kMod * inv[x - y] % kMod; }

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  st[0] = fac[0] = 1;
  for (int i = 1, j = 2; i < kMaxN; i++, j = j * 2 % kMod) {
    st[i] = (st[i - 1] + j) % kMod, fac[i] = fac[i - 1] * i % kMod;
  }
  inv[kMaxN - 1] = P(fac[kMaxN - 1], kMod - 2);
  for (int i = kMaxN - 2; ~i; i--) {
    inv[i] = inv[i + 1] * (i + 1) % kMod;
  }
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].x >> p[i].y, p[i].id = i;
  }
  sort(p + 1, p + 1 + n, [](node x, node y) { return x.x / 450 != y.x / 450 ? x.x / 450 < y.x / 450 : x.y < y.y; });
  int l = 1, r = 1, sum = 1;
  for (int i = 1; i <= n; i++) {
    int x = p[i].x, y = p[i].y;
    for (; l < x; sum = (sum * 2 - C(l - 1, r - 1) + kMod) % kMod, l++);
    for (; r > y; sum = (sum - C(l - 1, r - 1) + kMod) % kMod, r--);
    for (; l > x; l--, sum = (sum + C(l - 1, r - 1)) % kMod * inv[2] % kMod);
    for (; r < y; r++, sum = (sum + C(l - 1, r - 1)) % kMod);
    ans[p[i].id] = sum * st[p[i].x - 1] % kMod;
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
0