結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-01 20:48:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,091 ms / 4,000 ms
コード長 1,775 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,579 ms
コンパイル使用メモリ 161,976 KB
実行使用メモリ 11,588 KB
最終ジャッジ日時 2025-08-01 20:48:42
合計ジャッジ時間 12,149 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lll __int128
#define db double
#define ld long double
#define eps 1e-8
#define fir first
#define sec second
#define pb push_back
#define ppc __builtin_popcount
using namespace std;
void rd(){}
template<typename T,typename... U> void rd(T &x,U&... arg){
	x=0;int f=1,c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	x*=f;rd(arg...);
}

const int maxn=2e5+5,P=998244353,B=450;
template<typename T> inline void inc(T &x,T y){(x+=y)>=P?(x-=P):0;}
template<typename T> inline T mod(T n){return n>=P?n-P:n;}
template<typename T> inline T div2(T n){return n&1?(n+P)/2:n/2;}
inline ll fpow(ll n,ll x){ll s=1;while(x){if(x&1) s=s*n%P;x>>=1,n=n*n%P;}return s;}

ll fac[maxn],inv[maxn];
inline ll C(int n,int m){
	if(n==m) return 1;
	if(n<m||m<0) return 0;
	return fac[n]*inv[m]%P*inv[n-m]%P;
}

struct ask{
	int n,m,id;
}q[maxn];
int N,b[maxn];
ll ans[maxn];

int main(){
	fac[0]=1;
	for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%P;
	inv[maxn-1]=fpow(fac[maxn-1],P-2);
	for(int i=maxn-2;~i;i--) inv[i]=inv[i+1]*(i+1)%P;

	rd(N);
	for(int i=1;i<=N;i++) rd(q[i].n,q[i].m),q[i].n--,q[i].m--,q[i].id=i;
	for(int i=1;i<=N;i++) b[i]=(i+B-1)/B;
	sort(q+1,q+N+1,[](ask i,ask j){
		if(b[i.m]!=b[j.m]) return b[i.m]<b[j.m];
		return i.n<j.n;
	});
	int n=0,m=0;
	ll now=1;
	for(int i=1;i<=N;i++){
		while(n<q[i].n){
			now=mod(now*2);
			inc(now,P-C(n,m));
			n++;
		}
		while(m>q[i].m){
			inc(now,P-C(n,m));
			m--;
		}
		while(n>q[i].n){
			n--;
			inc(now,C(n,m));
			now=div2(now);
		}
		while(m<q[i].m){
			m++;
			inc(now,C(n,m));
		}
		ans[q[i].id]=now*(fpow(2,q[i].n+1)+P-1)%P;
	}

	for(int i=1;i<=N;i++) printf("%lld\n",ans[i]);
	return 0;
}
0