結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define pii std::pair<int,int>
#define mkp std::make_pair
#define fir first
#define sec second
typedef long long ll;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    int ch=getchar();
    T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;rd(args...);
}
const int N=2e5+5,B=500,mod=998244353,INV2=(mod+1)/2;
namespace Binom{
    std::vector<int> fac,inv;
    inline int KSM(int x,int n){
        int ans=1;
        while(n){
            if(n&1)ans=1ll*ans*x%mod;
            x=1ll*x*x%mod;n>>=1;
        }return ans;
    }
    inline int C(int n,int m){
        if(n==m)return 1;
        if(n<m||n<0||m<0)return 0;
        return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    inline void Init(int V){
        fac.resize(V+2);
        inv.resize(V+2);
        fac[0]=inv[0]=1;
        for(int i=1;i<=V;i++)fac[i]=1ll*fac[i-1]*i%mod;
        inv[V]=KSM(fac[V],mod-2);
        for(int i=V-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    }
}
using namespace Binom;
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:1;}
int T,idv[N],ans[N];
struct node{int n,m,id;}p[N];
signed main(){
    rd(T);
    Init(200005);
    for(int i=1;i<=T;i++)rd(p[i].n,p[i].m),p[i].id=i;
    for(int i=1;i<=200000;i++)idv[i]=(i-1)/B+1;
    std::sort(p+1,p+T+1,[](node a,node b){return idv[a.n]==idv[b.n]?a.m<b.m:a.n<b.n;});
    int nown=0,nowm=0,res=1;
    auto Addm=[&](){
        ++nowm;
        Add(res,C(nown,nowm));
    };
    auto Mnsm=[&](){
        Add(res,mod-C(nown,nowm));
        --nowm;
    };
    auto Addn=[&](){
        res=(res*2ll-C(nown,nowm)+mod)%mod;
        ++nown;
    };
    auto Mnsn=[&](){
        --nown;
        res=1ll*(res+C(nown,nowm))*INV2%mod;
    };
    for(int i=1;i<=T;i++){
        int n=p[i].n,m=p[i].m;
        --n,--m;
        while(nown<n)Addn();
        while(nowm<m)Addm();
        while(nowm>m)Mnsm();
        while(nown>n)Mnsn();
        ans[p[i].id]=1ll*res*(KSM(2,n+1)-1)%mod;
    }
    for(int i=1;i<=T;i++)printf("%d\n",ans[i]);
    return 0;
}
0