結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-03 15:45:26
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,267 ms / 4,000 ms
コード長 2,212 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,526 ms
コンパイル使用メモリ 165,548 KB
実行使用メモリ 25,976 KB
最終ジャッジ日時 2025-08-03 15:45:42
合計ジャッジ時間 15,867 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
bool M1;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=4e5+5;
const int B=500;
const int mod=998244353;
struct Node{
	int l,r,id;
}a[N];
int q,bel[N],_ans[N],L,R,ans;
struct _C{
	int fac[N],inv[N];
	void work(){
		fac[0]=1;fac[1]=1;
		inv[0]=1;inv[1]=1;
		for(int i=2;i<=400000;i++)fac[i]=fac[i-1]*i%mod;
		for(int i=2;i<=400000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		for(int i=2;i<=400000;i++)inv[i]*=inv[i-1],inv[i]%=mod;
	}	
	int C(int _n,int _m){
		if(_n<_m)return 0;
		if(!_m)return 1;
		return fac[_n]*inv[_m]%mod*inv[_n-_m]%mod;
	}
}T1;
bool cmp(Node xxx,Node yyy){
	if(bel[xxx.l]!=bel[yyy.l])return xxx.l<yyy.l;
	return xxx.r<yyy.r;
}
void add(int &x,int y){
	x+=y;x=(x%mod+mod)%mod;
}
void add1(int x){
	//cout<<"add1:"<<x<<'\n';
	add(ans,-T1.C(R,x+1));
}
void del1(int x){
	//cout<<"del1:"<<x<<'\n';
	add(ans,T1.C(R,x+1));
}
void add2(int x){
	//cout<<"add2:"<<x<<'\n';
	ans=2*ans-T1.C(R-1,L);ans=(ans%mod+mod)%mod;
}
void del2(int x){
	//cout<<"del2:"<<x<<'\n';
	ans=(ans+T1.C(R,L))%mod*T1.inv[2]%mod;
}
int bs[N];
void print(int _L,int _R){
	/*cout<<"!"<<_L<<" "<<_R<<'\n';
	int S=0;
	for(int j=0;j<=_L;j++)add(S,T1.C(_R,j));
	cout<<"???"<<S<<" "<<ans<<'\n';*/
}
bool M2;
signed main(){
//	freopen("data.in","r",stdin);
	//ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	q=read();T1.work();
	for(int i=1;i<=q;i++)a[i].r=read(),a[i].l=read(),a[i].id=i,a[i].l--,a[i].r--;
	for(int i=0;i<=400000;i++)bel[i]=(i-1)/B+1;
	int pw=1;
	for(int i=0;i<=400000;i++)bs[i]=bs[i-1]+pw,bs[i]%=mod,pw*=2,pw%=mod;
	sort(a+1,a+1+q,cmp);
	ans=1;
	L=1,R=0;
	for(int i=1;i<=q;i++){
		while(R<a[i].r)add2(++R),print(L,R);
		while(L<a[i].l)del1(L++),print(L,R);
		while(L>a[i].l)add1(--L),print(L,R);
		while(R>a[i].r)del2(R--),print(L,R);
		_ans[a[i].id]=ans*bs[R]%mod;
//		cout<<ans<<" "<<bs[R]<<" "<<a[i].id<<'\n';
	}
	for(int i=1;i<=q;i++)printf("%lld\n",_ans[i]);
//	cerr<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC<<"s"<<endl;
//  cerr<<"Memory:"<<(&M1-&M2)/1024/1024<<"MB"<<endl;
	return 0;
}
0