結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-20 14:48:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,321 ms / 4,000 ms
コード長 1,734 bytes
コンパイル時間 1,869 ms
コンパイル使用メモリ 198,692 KB
実行使用メモリ 13,256 KB
最終ジャッジ日時 2025-08-20 14:49:15
合計ジャッジ時間 29,496 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpi make_pair
#define fi first
#define se second
#define lb(x) (x&-x)
using namespace std;
const int maxn=2e5+10;
const int maxm=1e2+10;
const int INF=1e18;
const int eps=1e-4;
const int mod=998244353;
int T,ans[maxn],len,sum=1;
struct query{int n,m,id;}q[maxn];
bool cmp(query d1,query d2)
{
	if (d1.n/len!=d2.n/len) return d1.n/len<d2.n/len;
	return ((d1.n/len)&1?d1.m<d2.m:d1.m>d2.m);
}
int fc[maxn],inv[maxn],N=2e5,inv2;
int qpow(int k,int b)
{
	int res=1;
	while (b)
	{
		if (b&1) res=res*k%mod;
		k=k*k%mod;
		b>>=1;
	}
	return res;
}
void init()
{
	inv2=qpow(2,mod-2);
	fc[0]=1;
	for (int i=1;i<=N;i++) fc[i]=fc[i-1]*i%mod;
	inv[N]=qpow(fc[N],mod-2);
	for (int i=N-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){return fc[n]*inv[m]%mod*inv[n-m]%mod;}
void addn(int n,int m){sum=(sum*2%mod-C(n-1,m)+mod)%mod;}
void deln(int n,int m){sum=(sum+C(n-1,m))%mod*inv2%mod;}
void addm(int n,int m){sum=(sum+C(n,m))%mod;}
void delm(int n,int m){sum=(sum-C(n,m)+mod)%mod;}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	init();
	cin >> T;
	len=pow(T,0.6667);
	for (int i=1;i<=T;i++) cin >> q[i].n >> q[i].m,q[i].id=i,q[i].n--,q[i].m--;
	sort(q+1,q+T+1,cmp);
	for (int i=1,n=0,m=0;i<=T;i++)
	{
		while (n<q[i].n) addn(++n,m);//,cout << n << " " << m << " " << sum << "\n";
		while (m>q[i].m) delm(n,m--);//,cout << n << " " << m << " " << sum << "\n";
		while (n>q[i].n) deln(n--,m);//,cout << n << " " << m << " " << sum << "\n";
		while (m<q[i].m) addm(n,++m);//,cout << n << " " << m << " " << sum << "\n";
		ans[q[i].id]=(qpow(2,q[i].n+1)-1+mod)%mod*sum%mod;
	}
	for (int i=1;i<=T;i++) cout << ans[i] << "\n";
	return 0;
}
0