結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 16:06:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 692 ms / 4,000 ms
コード長 1,438 bytes
コンパイル時間 1,896 ms
コンパイル使用メモリ 166,904 KB
実行使用メモリ 10,720 KB
最終ジャッジ日時 2025-08-02 16:06:52
合計ジャッジ時間 11,740 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define ll long long
#define R register
#define mk(x,y) make_pair(x,y)
#define PII pair<int,int>
using namespace std;
const int N=2e5+5,mod=998244353;
inline ll qmul(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=(a*a)%mod;b>>=1;
	}
	return ans;
}
ll fac[N],inv[N];
inline void init(int x){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(R int i=2;i<=x;++i)fac[i]=fac[i-1]*i%mod;
	inv[x]=qmul(fac[x],mod-2);
	for(R int i=x-1;i>1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
inline ll C(ll a,ll b){
	if(a<b||b<0||a<0)return 0;
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int n,m,block,T,inv2=(mod+1)>>1,_l=1,_r=1;ll res=1;ll ans[N];
struct ASK{int l,r,id;}q[N];
inline bool cmp(ASK x,ASK y){return (x.l/block!=y.l/block)?(x.l/block<y.l/block):((x.l/block)&1)?x.r<y.r:x.r>y.r;}
inline void addl(){res=(res*2%mod-C(_l-1,_r-1)+mod)%mod;++_l;}
inline void dell(){res=(res+C(_l-2,_r-1))%mod*inv2%mod;--_l;}
inline void addr(){res=(res+C(_l-1,_r))%mod;++_r;}
inline void delr(){res=(res-C(_l-1,_r-1)+mod)%mod;--_r;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>T;block=(sqrt(200000));init(N-1);
	for(R int i=1;i<=T;++i)cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+T+1,cmp);
	for(R int i=1;i<=T;++i){
		while(_l<q[i].l)addl();
		while(_l>q[i].l)dell();
		while(_r<q[i].r)addr();
		while(_r>q[i].r)delr();
		ans[q[i].id]=res*(qmul(2,q[i].l)-1+mod)%mod;
	}
	for(R int i=1;i<=T;++i)cout<<ans[i]<<'\n';
	return 0;
}
0