結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-21 18:09:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 523 ms / 4,000 ms
コード長 1,062 bytes
コンパイル時間 2,875 ms
コンパイル使用メモリ 282,868 KB
実行使用メモリ 14,588 KB
最終ジャッジ日時 2025-08-21 18:10:04
合計ジャッジ時間 12,699 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define N 200005
using namespace std;
struct Data{int x,y,num;}w[N];
int n,B,l,r,res=1,fac[N],inv[N],ans[N],p[N];
bool cmp(Data x,Data y)
{
	if(x.x/B!=y.x/B) return x.x<y.x;
	if((x.x/B)&1) return x.y<y.y;
	return x.y>y.y;
}
int C(int n,int m)
{
	if(n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	p[0]=fac[0]=1;
	for(int i=1;i<=200000;i++) fac[i]=fac[i-1]*i%mod;
	inv[200000]=532999597;
	for(int i=1;i<=200000;i++) p[i]=p[i-1]*2%mod;
	for(int i=199999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	cin>>n;
	B=sqrt(n);
	for(int i=1;i<=n;i++) cin>>w[i].x>>w[i].y,w[i].num=i,w[i].x--,w[i].y--;
	sort(w+1,w+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(w[i].x<l) res=(res+C(--l,r))*inv[2]%mod;
		while(w[i].y>r) res=(res+C(l,++r))%mod;
		while(w[i].x>l) res=(res*2-C(l++,r))%mod;
		while(w[i].y<r) res=(res-C(l,r--))%mod;
		ans[w[i].num]=(p[w[i].x+1]-1)*res%mod;
	}
	for(int i=1;i<=n;i++) cout<<(ans[i]+mod)%mod<<"\n";
	return 0;
}
0