結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
  int x=0;bool f=0;char ch=getchar();
  while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
  while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  return f?-x:x;
}
const int Maxn=2e5+5,mod=998244353,B=200,inv2=499122177;
int fac[Maxn],inv[Maxn];
inline int ksm(int a,int k){
	int res=1;for(;k;k>>=1,a=a*a%mod)if(k&1)res=res*a%mod;
	return res;
}
inline int C(int n,int m){
	return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
struct Query{
	int n,m,id;
}Q[Maxn];
int ans[Maxn];
int belong[Maxn];
inline void init(int N){
	fac[0]=1;for(int i=1;i<=N;i++)belong[i]=i/B,fac[i]=fac[i-1]*i%mod;
	inv[N]=ksm(fac[N],mod-2);
	for(int i=N;i;i--)inv[i-1]=inv[i]*i%mod;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	init(2e5);
	int T=read();
	for(int i=1;i<=T;i++)Q[i]={read()-1,read()-1,i};
	sort(Q+1,Q+1+T,[&](Query a,Query b){
		if(belong[a.n]==belong[b.n]){
			if(belong[a.n]&1)return a.m>b.m;
			return a.m<b.m;
		}return belong[a.n]<belong[b.n];
	});
	int n=0,m=0,res=1;
	for(int i=1;i<=T;i++){
//		printf("er %d %d\n",Q[i].n,Q[i].m);
		while(m>Q[i].m)res=(res+mod-C(n,m))%mod,m--;
		while(Q[i].n<n)res=(res+C(n-1,m))*inv2%mod,n--;//,printf("reg %d\n",res);
		
//		if(n==3&&m==0)printf("wwrwrwfwwffwefwewfwffwewfe %d\n",res);
		
		while(n<Q[i].n)res=(res*2+mod-C(n,m))%mod,n++;
		while(Q[i].m>m)res=(res+C(n,m+1))%mod,m++;
		ans[Q[i].id]=(ksm(2,Q[i].n+1)-1)*res%mod;
	}
	for(int i=1;i<=T;i++)printf("%lld\n",ans[i]);
	return 0;
}
0