結果

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

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
#define N 200005
#define INF (ll)1e18
#define PII pair<ll, ll>
#define lowbit(x) x&(-x)

using namespace std;
inline ll rd(){
    ll res=0, f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch^48), ch=getchar();
    return (f>0?res:-res);
}
ll T, n, m, bl, l, r, res;
ll p[N], inv[N], ans[N];
const ll mod=998244353;
ll ksm(ll a, ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll C(ll n, ll m){
    if(n<m) return 0;
    return p[n]*inv[m]%mod*inv[n-m]%mod;
}
struct Data{
    ll l, r, id;
}q[N];
bool cmp(Data x, Data y){
    if(x.l/bl!=y.l/bl) return x.l<y.l;
    return x.r<y.r;
}
void addl(ll x){
    res=(res+C(x, r))%mod*((mod+1)>>1)%mod;
}
void dell(ll x){
    res=(res*2%mod-C(x, r)+mod)%mod;
}
void addr(ll x){
    res=(res+C(l, x))%mod;
}
void delr(ll x){
    res=(res-C(l, x)+mod)%mod;
}
int main(){
    T=rd(), bl=sqrt(2e5), p[0]=1;
    for (int i=1; i<=N-5; i++) p[i]=(p[i-1]*i)%mod;
    inv[N-5]=ksm(p[N-5], mod-2);
    for (int i=N-6; i>=0; i--) inv[i]=(inv[i+1]*(i+1))%mod;
    for(int i=1; i<=T; i++) q[i]={rd()-1, rd()-1, i};
    sort(q+1, q+T+1, cmp);
    l=0, r=0, res=1;
    for(int i=1; i<=T; i++){
        // cout<<q[i].l<<' '<<q[i].r<<endl;
        while(l<q[i].l) dell(l++);
        while(l>q[i].l) addl(--l);
        while(r<q[i].r) addr(++r);
        while(r>q[i].r) delr(r--);
        // cout<<res<<endl;
        ans[q[i].id]=res*(ksm(2, q[i].l+1)-1)%mod;
    }
    for (int i=1; i<=T; i++) printf("%lld\n", ans[i]);

    return 0;
}
/*

*/
0