結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-01 22:55:12
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 520 ms / 4,000 ms
コード長 1,665 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,719 ms
コンパイル使用メモリ 170,344 KB
実行使用メモリ 8,336 KB
最終ジャッジ日時 2025-08-01 22:55:23
合計ジャッジ時間 10,516 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define bl(x) ((x - 1) / sqrtq + 1)
using namespace std;

const int MAXN = 2e5 + 5, N = 2e5, mod = 998244353, inv2 = 499122177;

int q, sqrtq, now = 2, l = 1, r = 1;
int ans[MAXN], fac[MAXN], inv[MAXN];
struct Que{ int l, r, idx; }que[MAXN];

int qpow(int a, int b){ int res = 1; for(; b; b >>= 1, a = 1ll * a * a % mod) if(b & 1) res = 1ll * res * a % mod; return res; }
int C(int x, int y){ return (x < y || y < 0 ? 0 : 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod); }

void addl(){ l++, (now += C(r, l)) %= mod; }
void addr(){ now = (2ll * now - C(r, l)) % mod, r++; }
void dell(){ (now -= C(r, l)) %= mod, l--; }
void delr(){ r--; now = 1ll * (now + C(r, l)) * inv2 % mod; }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> q; sqrtq = sqrt(q);
    for(int i = 1; i <= q; ++i) cin >> que[i].r >> que[i].l, que[i].r--, que[i].l--, que[i].idx = i;
    sort(que + 1, que + q + 1, [](Que p, Que q){ return (bl(p.l) == bl(q.l) ? (bl(p.l) & 1 ? p.r < q.r : p.r > q.r) : p.l < q.l); });
    fac[0] = 1; for(int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[N] = qpow(fac[N], mod - 2); for(int i = N - 1; i >= 0; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    for(int i = 1; i <= q; ++i){
        if(!que[i].l){ ans[que[i].idx] = qpow(2, que[i].r + 1) - 1; continue; }
        while(l < que[i].l) addl();
        while(l > que[i].l) dell();
        while(r < que[i].r) addr();
        while(r > que[i].r) delr();
        ans[que[i].idx] = 1ll * now * (qpow(2, que[i].r + 1) - 1) % mod;
    }
    for(int i = 1; i <= q; ++i) cout << (ans[i] + mod) % mod << '\n';

    return 0;
}
0