結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-10-09 21:19:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 570 ms / 4,000 ms
コード長 1,787 bytes
コンパイル時間 5,246 ms
コンパイル使用メモリ 167,232 KB
実行使用メモリ 8,360 KB
最終ジャッジ日時 2025-10-09 21:19:28
合計ジャッジ時間 13,143 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 2e5 + 1, MOD = 998244353;

int q, block, mx, ans[MAXN], inv[MAXN], fac[MAXN], res = 1;

struct Query{
  int m, n, id;
  bool operator < (const Query &i) const{
    if(n / block != i.n / block) return n < i.n;
    if(m == i.m) return 0;
    return (n / block & 1) ? m < i.m : m > i.m;
  }
}qry[MAXN];

int C(int n, int m){
  return n < m ? 0 : 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int Power(int x, int y){
  int res = 1;
  for(; y; y >>= 1, x = 1ll * x * x % MOD){
    if(y & 1) res = 1ll * res * x % MOD;
  }
  return res;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> q;
  for(int i = 1; i <= q; i++){
    cin >> qry[i].n >> qry[i].m;
    ans[i] = (Power(2, qry[i].n) - 1 + MOD) % MOD;
    qry[i].n--, qry[i].m--, qry[i].id = i;
    mx = max(mx, qry[i].n);
  }
  inv[0] = inv[1] = fac[0] = fac[1] = 1;
  for(int i = 2; i < MAXN; i++){
    fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
  }
  for(int i = 1; i < MAXN; i++){
    inv[i] = 1ll * inv[i - 1] * inv[i] % MOD;
  }
  block = mx / sqrt(q) + 1;
  sort(qry + 1, qry + 1 + q);
  for(int i = 1, m = 0, n = 0; i <= q; i++){
    for(; n < qry[i].n; ){
      n++;
      res = (2ll * res % MOD - C(n - 1, m) + MOD) % MOD;
    }
    for(; n > qry[i].n; ){
      res = 1ll * (res + C(n - 1, m)) % MOD * inv[2] % MOD;
      n--;
    }
    for(; m < qry[i].m; ){
      m++;
      res = (res + C(n, m)) % MOD;
    }
    for(; m > qry[i].m; ){
      res = (res - C(n, m) + MOD) % MOD;
      m--;
    }
    ans[qry[i].id] = 1ll * ans[qry[i].id] * res % MOD;
  }
  for(int i = 1; i <= q; i++){
    cout << ans[i] << '\n';
  }
  return 0;
}
0