結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 17:46:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,201 ms / 4,000 ms
コード長 1,238 bytes
コンパイル時間 1,973 ms
コンパイル使用メモリ 198,376 KB
実行使用メモリ 22,404 KB
最終ジャッジ日時 2025-08-02 17:46:58
合計ジャッジ時間 17,653 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000010;
const ll p=998244353;

ll fac[N],inv[N];

ll power(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1) res=res*x%p;
		x=x*x%p;
	}
	return res;
}

ll C(ll x,ll y){
	if(x<y||x<0||y<0) return 0;
	return fac[x]*inv[y]%p*inv[x-y]%p;
}

void init(ll n){
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p;
	inv[n]=power(fac[n],p-2);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%p;
}

ll n,B;
ll l=0,r=0,res=1,inv2;
ll ans[N];

struct node{
	ll x,y,id;
}q[N];
bool cmp(node x,node y){
	if(x.x/B==y.x/B) return x.y<y.y;
	return x.x/B<y.x/B;
}

int main(){
	init(300000);
	cin>>n;
	B=450;inv2=power(2,p-2);
	for(int i=1;i<=n;i++) cin>>q[i].x>>q[i].y,q[i].id=i;
	sort(q+1,q+n+1,cmp);
	for(int i=1;i<=n;i++){
		ll X=q[i].y-1,Y=q[i].x-1;
		while(l>X) res=(res-C(r,l--)+p)%p;
//		cout<<l<<" "<<r<<"  "<<res<<endl;
		while(r<Y) res=(res*2-C(r++,l)+p)%p;
//		cout<<l<<" "<<r<<"  "<<res<<endl;
		while(l<X) res=(res+C(r,++l))%p;
//		cout<<l<<" "<<r<<"  "<<res<<endl;
		while(r>Y) res=(res+C(--r,l))*inv2%p;
//		cout<<l<<" "<<r<<"  "<<res<<endl;
		ans[q[i].id]=(res*(power(2,q[i].x)-1)%p+p)%p;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}
/*
1
20 10
*/
0