結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll kM = 2e5 + 5, mod = 998244353;
ll q, i, j, qt[kM], inv[kM], f[kM], len, p[kM];
ll qpow(ll a, ll b){
  ll ret = 1;
  while(b){
    if(b & 1) ret = ret * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return ret;
}
struct M{
  ll m, n, id;
}c[kM];
ll C(ll n, ll m){
  return f[n] * inv[m] % mod * inv[n - m] % mod;
}
ll wp(ll x){
  return (x + len - 1) / len;
}
ll cmp(M a, M b){
  if(wp(a.m) == wp(b.m)) return a.n < b.n;
  return a.m < b.m;
}
int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> q;
  for(i = f[0] = p[0] = 1; i <= kM - 2; i++){
    f[i] = f[i - 1] * i % mod;
    p[i] = p[i - 1] * 2 % mod;
  }
  inv[kM - 2] = qpow(f[kM - 2], mod - 2);
  for(i = kM - 3; ~i; i--){
    inv[i] = inv[i + 1] * (i + 1) % mod;
  }
  len = 1.01 * sqrt(kM - 2) + 1;
  for(i = 1; i <= q; i++){
    cin >> c[i].n >> c[i].m;
    c[i].id = i;
  }
  sort(c + 1, c + q + 1, cmp);
  ll cnt = 0, tmp = 0, l = 1, r = 0;
  for(i = 1; i <= q; i++){
    ll m = c[i].m, n = c[i].n;
    if(wp(m) != wp(c[i - 1].m)){
      cnt = p[n] - 1, tmp = 0;
      for(j = 0; j < m; j++){
        tmp = (tmp + C(n - 1, j)) % mod;
      }
      l = m, r = n;
    }
    while(r < n) ++r, tmp = (tmp * 2 - C(r - 2, l - 1) + mod) % mod;
    while(l < m) l++, tmp = (tmp + C(r - 1, l - 1)) % mod;
    while(l > m) tmp = (tmp - C(r - 1, l - 1) + mod) % mod, l--;
    cnt = p[n] - 1;
    qt[c[i].id] = tmp * cnt % mod;
  }
  for(i = 1; i <= q; i++){
    cout << qt[i] << "\n";
  }
  return 0;
}
0