結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
#pragma GCC optimize(3)
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,ans[N];
bool cmp(node a,node b){
	return a.x/siz!=b.x/siz?a.x<b.x: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;
	}
	sort(qry+1,qry+q+1,cmp);
	for(int i=1,x=0,y=0,res=1;i<=q;i++){
		int qx=qry[i].x,qy=qry[i].y;
		while(x<qx){
			res=(2ll*res%mod-c(x,y)+mod)%mod;
			++x;
		}
		while(x>qx){
			--x;
			res=(1ll*inv2*(res+c(x,y)))%mod;
		}
		while(y<qy){
			++y;
			res=(res+c(x,y))%mod;
		}
		while(y>qy){
			res=(res-c(x,y)+mod)%mod;
			--y;
		}
		ans[qry[i].id]=1ll*res*(qpow(2,qx+1)-1)%mod;
	}
	for(int i=1;i<=q;i++)  printf("%d\n",ans[i]);
	return 0;
}
0