結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-06-05 17:33:40
言語 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  
実行時間 668 ms / 4,000 ms
コード長 1,577 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,420 ms
コンパイル使用メモリ 187,352 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2026-06-05 17:33:54
合計ジャッジ時間 13,347 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:67:23: warning: iteration 200004 invokes undefined behavior [-Waggressive-loop-optimizations]
   67 |                 inv[i]=ksm(jc[i],mod-2);
      |                 ~~~~~~^~~~~~~~~~~~~~~~~
main.cpp:64:22: note: within this loop
   64 |         for(int i=1;i<=200005;i++){
      |                     ~^~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define int long long
using namespace std;
int Q;
struct node{
	int l,r,id;
}q[200005];
int jc[200005];
int inv[200005];
int jc_2[200005];
const int mod=998244353;
int ksm(int x,int y){
	int ans=1;
	for(y;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;
	return ans; 
}
int kuailen;
bool cmp(node tle,node mle){
	if(tle.l/kuailen==mle.l/kuailen){
		return ((tle.l/kuailen)&1)?tle.r<mle.r:tle.r>mle.r;
	}
	return tle.l<mle.l;
}
int C(int x,int y){
	if(x<y || y<0 || x<0) return 0;
	return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
int sum=0;
int tans=0;
int l=-1,r=1;
int inv2;
void addl(){
	l++;
	tans=(tans+C(r,l)%mod)%mod;
}
void dell(){
	tans=(tans-C(r,l)%mod+mod)%mod;
	l--;
}
void addr(){
	r++;
	tans=(2*tans%mod-C(r-1,l)+mod)%mod;
}
void delr(){
	tans=(tans+C(r-1,l))%mod*inv2%mod;
//	cout << tans << '\n';
	r--;
}
int ans[200005];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>Q;
	for(int i=1;i<=Q;i++){
		cin>>q[i].r>>q[i].l;
		q[i].l--;
		q[i].r--;
		q[i].id=i;
	}
	kuailen=sqrt(Q);
	sort(q+1,q+1+Q,cmp);
	jc[0]=jc_2[0]=inv[0]=1;
	for(int i=1;i<=200005;i++){
		jc[i]=jc[i-1]*i%mod;
		jc_2[i]=jc_2[i-1]*2%mod;
		inv[i]=ksm(jc[i],mod-2);
	}
//	cout << C(8, 0) << '\n';
	inv2=ksm(2,mod-2);
	for(int i=1;i<=Q;i++){
//		cout<<
		while(r<q[i].r) addr();
		while(r>q[i].r) delr();
		while(l<q[i].l) addl();
		while(l>q[i].l) dell();
//		cout << tans << ' ' << l << ' ' << r << '\n';
//		cout<<l<<' '<<r<<endl;
//		cout << tans << '\n';
		ans[q[i].id]=tans*(jc_2[r+1]-1)%mod;
	}
	for(int i=1;i<=Q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}
0