結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,B=447;
const int P=998244353,I=499122177;
int n,ans[N];
int fac[N],inv[N];
struct ques{int m,k,id;}a[N];
bool cmp(ques x,ques y){
    return x.m/B!=y.m/B?x.m<y.m:x.k<y.k;
}int qp(int x,int y){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%P)
        if(y&1)z=1ll*z*x%P;
    return z;
}void init(){
    const int n=2e5;
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%P,
        inv[i]=qp(fac[i],P-2);
}int C(int n,int m){
    if(n<0||m<0||n>m)return 0;
    return 1ll*fac[m]*inv[n]%P*inv[m-n]%P;
}void add(int &x,int y){
    x+=y;if(x>=P)x-=P;
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;init();
    for(int i=1;i<=n;++i)
        cin>>a[i].m>>a[i].k,a[i].id=i,
        --a[i].m,--a[i].k;
    sort(a+1,a+n+1,cmp);
    int m=0,k=0,sum=1;
    for(int i=1;i<=n;++i){
        int M=a[i].m,K=a[i].k;
        while(k<K)++k,add(sum,C(k,m));
        while(k>K)add(sum,P-C(k,m)),k--;
        while(m<M)sum=(sum*2%P+P-C(k,m))%P,++m;
        while(m>M)--m,sum=1ll*I*(sum+C(k,m))%P;
        ans[a[i].id]=1ll*sum*(qp(2,M+1)-1)%P;
    }for(int i=1;i<=n;++i)
        cout<<ans[i]<<'\n';
    return 0;
}
0