結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-13 19:57:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,784 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 85,036 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-13 19:57:21
合計ジャッジ時間 8,518 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<queue>
#include<array>
#if defined FIO
auto I_=freopen("1.in","r",stdin);
auto O_=freopen("1.out","w",stdout);
#endif
#if defined BUG
#define bug(x...) ({x;void();})
#else
#define bug(x...) ({})
#endif
#define LL long long
#define pb push_back
#define vec vector
#define arr array
#define SIZ(x) (int)(x).size()
#define ALL(x) begin(x),end(x)
#define RNG(x,l,r) &(x)[l],1+&(x)[r]
#define rep(i,l,r) for(int i=(l),i##_=(r);i<=i##_;i++)
#define per(i,l,r) for(int i=(l),i##_=(r);i>=i##_;i--)
#define inline inline __attribute__((always_inline))
template<class U,class V>constexpr inline void tomin(U&x,V&&y)noexcept{if(y<x)x=y;}
template<class U,class V>constexpr inline void tomax(U&x,V&&y)noexcept{if(y>x)x=y;}
using namespace std;namespace __{

template<int P> struct mint{
    int x;
    inline mint(){}
    inline mint(int t){ x=(t+P)%P; }
    inline mint(LL t){ x=int(t%P); }
    inline operator int()noexcept{ return x; }
    inline mint operator+(mint t){ return (x+t.x)%P; }
    inline mint operator-(mint t){ return (x-t.x+P)%P; }
    inline mint operator*(mint t){ return 1ll*x*t.x%P; }
    inline mint& operator+=(mint t){ return *this=*this+t; }
    inline mint& operator-=(mint t){ return *this=*this-t; }
    inline mint& operator*=(mint t){ return *this=*this*t; }
};

#define mint mint<P>
constexpr int N=2e5+5,P=998244353;
inline mint fpw(mint a,int b,mint r=1){ for(;b;a*=a,b>>=1)if(b&1)r*=a; return r; }
int Q;
struct qq{int a,b,idx,bk;}q[N+5];
mint ans[N];

mint fac[N],invfac[N];
void init(int n){
    fac[0]=1; rep(i,1,n) fac[i]=fac[i-1]*mint(i);
    invfac[n]=fpw(fac[n],P-2); per(i,n,1) invfac[i-1]=invfac[i]*mint(i);
}
inline mint binom(int a,int b){ return a<b||b<0 ? mint(0) : fac[a] * invfac[b] * invfac[a-b]; }

void modui(){
    int B=(int)__builtin_sqrt(Q);
    rep(i,1,Q) q[i].bk=q[i].a/B;
    sort(RNG(q,1,Q),[](qq i,qq j){
        if(i.bk!=j.bk) return i.bk<j.bk;
        if(i.a!=j.a) return i.a<j.a;
        return i.bk&1 ? i.b>j.b : i.b<j.b;
    });
    int l=0,r=0;
    mint cur=1, inv2=fpw(2,P-2);
    auto la=[&](){ cur=cur*mint(2)-binom(l,r); };
    auto ra=[&](){ cur+=binom(l,r+1); };
    auto ld=[&](){ cur=(cur+binom(l-1,r))*inv2; };
    auto rd=[&](){ cur-=binom(l,r); };
    rep(i,1,Q){
        while(l<q[i].a) la(), l++;
        while(r<q[i].b) ra(), r++;
        while(l>q[i].a) ld(), l--;
        while(r>q[i].b) rd(), r--;
        ans[q[i].idx]*=cur;
    }
}

void main(){
    cin.tie(0)->sync_with_stdio(0);
    // signed CSE=0; for(cin>>CSE; CSE--; clear())
[&](){
    cin>>Q;
    rep(i,1,Q){
        int n,m; cin>>n>>m;
        ans[i]=fpw(2,n)-mint(1);
        q[i]={n-1,m-1,i,0};
    }
    init(2e5);
    modui();
    rep(i,1,Q) cout<<ans[i]<<'\n';
}();}}
signed main(){__::main();}
0