結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-03 00:24:25
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 989 ms / 4,000 ms
コード長 1,592 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,685 ms
コンパイル使用メモリ 166,132 KB
実行使用メモリ 10,800 KB
最終ジャッジ日時 2025-08-03 00:24:38
合計ジャッジ時間 12,381 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:24:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
main.cpp:26:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |     scanf("%d%d", &a[i].r, &a[i].l), a[i].l--, a[i].r--, a[i].id = i, b[i] = a[i].r + 1;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
int B, qu[200010], fac[200010], inv[200010], inve[200010], b[200010], pw[200010];
const int P = 998244353;
struct Node {
  int l, r, id;
  bool operator<(const Node &A) {
    if (l / B != A.l / B) return l / B < A.l / B;
    return r < A.r;
  }
} a[200010];
int C(int aa, int bb) {
  return 1LL * fac[aa] * inve[bb] % P * inve[aa - bb] % P;
}
int q;
int main() {
  fac[0] = fac[1] = inv[1] = inve[0] = inve[1] = pw[0] = 1, pw[1] = 2;
  for (int i = 2; i <= 200000; i++) {
    fac[i] = 1LL * fac[i - 1] * i % P;
    inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
    inve[i] = 1LL * inve[i - 1] * inv[i] % P;
    pw[i] = 2 * pw[i - 1] % P;
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%d%d", &a[i].r, &a[i].l), a[i].l--, a[i].r--, a[i].id = i, b[i] = a[i].r + 1;
  B = 400;
  sort(a + 1, a + q + 1);
  int ans = 0;
  for (int i = 0; i <= a[1].l; i++) ans = (ans + C(a[1].r, i)) % P;
  qu[a[1].id] = ans;
  for (int i = 2; i <= q; i++) {
    for (int j = a[i].l + 1; j <= a[i - 1].l; j++) ans = (ans - C(a[i - 1].r, j) + P) % P;
    for (int j = a[i - 1].r + 1; j <= a[i].r; j++) ans = (2 * ans % P - C(j - 1, min(a[i].l, a[i - 1].l)) + P) % P;
    //		printf("%d\n",ans);
    for (int j = a[i - 1].l + 1; j <= a[i].l; j++) ans = (ans + C(max(a[i - 1].r, a[i].r), j)) % P;
    for (int j = a[i - 1].r; j > a[i].r; j--) ans = 1LL * (ans + C(j - 1, a[i].l)) * ((P + 1) / 2) % P;
    qu[a[i].id] = ans;
  }
  //	printf("%d\n",b[1]);
  for (int i = 1; i <= q; i++) printf("%lld\n", 1LL * qu[i] * (pw[b[i]] - 1 + P) % P);
  return 0;
}
0