結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-03 09:17:58
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,341 bytes
コンパイル時間 5,842 ms
コンパイル使用メモリ 217,544 KB
実行使用メモリ 31,196 KB
最終ジャッジ日時 2025-08-03 09:18:11
合計ジャッジ時間 12,789 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fir first
#define sec second
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
const int B=500,mod=998244353;
int q;
int f[500005],inv[500005],F[500005];
int ans[500005];
struct node{
	int x,y,id;
} a[200005];
bool cmp(node x,node y){
	return x.x/B==y.x/B?(x.y==y.y?0:((x.x/B)&1)^(x.y<y.y)):x.x<y.x;
}
int calc(int a,int b){
	if(b==0) return 1;
	int t=calc(a,b/2);
	if(b%2==0)
		return t*t%mod;
	return t*t%mod*a%mod;
}
int C(int a,int b){
	return f[a]*inv[a-b]%mod*inv[b]%mod;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	f[0]=1;
	F[0]=inv[0]=1;
	for(int i=1;i<=500000;i++){
		f[i]=f[i-1]*i%mod;
		inv[i]=calc(f[i],mod-2);
		F[i]=F[i-1]*2%mod;
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i].x>>a[i].y;
		a[i].y--,a[i].x--;
		a[i].id=i;
	}
	sort(a+1,a+1+q,cmp);
	int l=1,r=1,s=1;
	for(int i=1;i<=q;i++){
		while(l<a[i].x){
			l++;
			s=(s*2+1-C(l-1,r)+mod)%mod;
		}
		while(r<a[i].y){
			r++;
			(s+=C(l,r))%=mod;
		}
		while(a[i].y<r){
			s=(s+mod-C(l,r))%mod;
			r--;
		}
		while(a[i].x<l){
			s=(s-1+C(l-1,r)+mod)%mod*calc(2,mod-2)%mod;
			l--;
		}
		ans[a[i].id]=(F[a[i].x+1]+mod-1)*(s+1)%mod;
	}	
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}
0