結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-03 00:38:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,433 bytes
コンパイル時間 1,565 ms
コンパイル使用メモリ 165,884 KB
実行使用メモリ 9,104 KB
最終ジャッジ日時 2025-08-03 00:38:52
合計ジャッジ時間 8,988 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=998244353,inv2=(mod+1)/2;
int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9')  c=getchar();
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x;
}
int fac[N],ifac[N];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)  res=1ll*res*a%mod;
		a=1ll*a*a%mod;b>>=1;
	}
	return res;
}
struct node{int x,y,id;}qry[N];
int q,siz,blk[N],ans[N];
bool cmp(node a,node b){
	if(blk[a.id]!=blk[b.id]) return blk[a.id]<blk[b.id];
	if(blk[a.id]&1) return a.y<b.y;
	else return a.y>b.y;
}
int c(int n,int m){
	if(n<m||m<0||n<0) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main(){
	q=read();siz=sqrt(200000);
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	for(int i=1;i<=q;i++){
		qry[i].x=read();qry[i].y=read();
		--qry[i].x;--qry[i].y;qry[i].id=i;
	}
	for(int i=1;i<=q;i++)  blk[i]=(i-1)/siz+1;
	sort(qry+1,qry+q+1,cmp);
	for(int i=1,x=0,y=0,res=1;i<=q;i++){
		while(x<qry[i].x){
			res=(2ll*res%mod-c(x,y)+mod)%mod;
			++x;
		}
		while(x>qry[i].x){
			--x;
			res=(1ll*inv2*(res+c(x,y)))%mod;
		}
		while(y<qry[i].y){
			++y;
			res=(res+c(x,y))%mod;
		}
		while(y>qry[i].y){
			res=(res-c(x,y)+mod)%mod;
			--y;
		}
		ans[qry[i].id]=1ll*res*(qpow(2,qry[i].x+1)-1)%mod;
	}
	for(int i=1;i<=q;i++)  printf("%d\n",ans[i]);
	return 0;
}
0