結果

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

ソースコード

diff # 

#include<bits/stdc++.h>

#define int long long
#define rep(i,a,b)	for(int i = (a);i<=(b);i++)
#define lep(i,a,b)	for(int i = (a);i>=(b);i--)

using namespace std;

const int N = 3e5+10;
const int M = 998244353;
int n,B,ans[N];
int fac[N],inv[N];
inline int qpow(int a,int b){
	int c = 1;
	while(b){
		if(b&1)	c = c*a%M;
		a = a*a%M;
		b>>=1;
	}
	return c;
}
inline int C(int n,int m){
	if(n<m)	return 0;
	return fac[n]*inv[m]%M*inv[n-m]%M;
}
inline void init(int n){
	fac[0] = 1;rep(i,1,n)	fac[i] = fac[i-1]*i%M;
	inv[n] = qpow(fac[n],M-2);	lep(i,n-1,0)	inv[i] = inv[i+1]*(i+1)%M;
}
struct node{
	int l,r,id;
}q[N];
inline bool cmp(node _,node __){
	if((_.l-1)/B+1 == (__.l-1)/B+1){
		if(((_.l-1)/B+1)&1)	return _.r<__.r;
		else return _.r>__.r;
	}
	return (_.l-1)/B+1<(__.l-1)/B+1;
}
int L,R,A;
inline void addl(int l,int r){
	A = (A*2%M-C(l,r)%M+M)%M;
}
inline void addr(int l,int r){
	A = (A+C(l,r+1)%M)%M;
}
inline void dell(int l,int r){
	A = ((A+C(l-1,r))%M*qpow(2,M-2)%M)%M;
}
inline void delr(int l,int r){
	A = (A-C(l,r)%M+M)%M;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	cin>>n;
	rep(i,1,n)	cin>>q[i].l>>q[i].r,q[i].id = i;
	init(200010);
	B = sqrt(n);
	sort(q+1,q+1+n,cmp);
	rep(i,1,n)	ans[q[i].id] = (qpow(2,q[i].l)-1+M)%M; 
	A = 1;
	rep(i,1,n){
		q[i].l--,q[i].r--;
		while(L<q[i].l)	addl(L,R),L++;
		while(R<q[i].r)	addr(L,R),R++;
		while(L>q[i].l)	dell(L,R),L--;
		while(R>q[i].r)	delr(L,R),R--;
		//cout<<L<<" "<<R<<"\n";
		//cout<<A<<"\n";
		ans[q[i].id] = (ans[q[i].id]*A)%M;
	}
	rep(i,1,n)	cout<<ans[i]<<"\n";
	return 0;
}
0