結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-05-15 16:30:07
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,299 ms / 4,000 ms
コード長 1,238 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,389 ms
コンパイル使用メモリ 186,716 KB
実行使用メモリ 16,896 KB
最終ジャッジ日時 2026-05-15 16:30:24
合計ジャッジ時間 16,198 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n=1,m=0,cnt=1,p=998244353,maxx,l[300005],nl[300005],pw[300005],ans[300005];
int qpow(int x,int y){
	int rt=1;
	while(y){
		if(y&1) rt=rt*x%p;
		x=x*x%p,y>>=1;
	}
	return rt;
}
int getc(int x,int y){
	if(x<0 || y<0 || x<y) return 0;
	return l[x]*nl[y]%p*nl[x-y]%p;
}
struct str{
    int n,m,id;
}s[200005];
bool cmp(str x,str y){
	if((x.m-1)/444!=(y.m-1)/444) return x.m<y.m;
	return x.n<y.n;
}
void addn(){
	cnt=((cnt*2-getc(n,m))%p+p)%p;
}
void deln(){
	cnt=(cnt+getc(n-1,m))*499122177%p;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	l[0]=pw[0]=1;
	for(int i=1;i<=300000;i++) l[i]=l[i-1]*i%p,pw[i]=pw[i-1]*2%p;
	nl[300000]=qpow(l[300000],p-2);
	for(int i=300000;i>0;i--) nl[i-1]=nl[i]*i%p;
	cin>>t;
	for(int i=1;i<=t;i++) cin>>s[i].n>>s[i].m,s[i].id=i,ans[i]=pw[s[i].n]-1,s[i].n--,s[i].m--;
	sort(s+1,s+t+1,cmp);
	for(int i=1;i<=t;i++){
		while(n<s[i].n) cnt=((cnt*2-getc(n,m))%p+p)%p,n++;
		while(n>s[i].n) cnt=(cnt+getc(n-1,m))*499122177%p,n--;
		while(m<s[i].m) cnt=(cnt+getc(n,m+1))%p,m++;
		while(m>s[i].m) cnt=(cnt-getc(n,m)+p)%p,m--;
		ans[s[i].id]=ans[s[i].id]*cnt%p;
	}
	for(int i=1;i<=t;i++) cout<<ans[i]<<'\n';
	return 0;
}
0