結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-01 20:37:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 663 ms / 4,000 ms
コード長 2,539 bytes
コンパイル時間 3,007 ms
コンパイル使用メモリ 283,472 KB
実行使用メモリ 16,112 KB
最終ジャッジ日時 2025-08-01 20:37:24
合計ジャッジ時間 12,831 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Problem: E - Popcount Sum 2
// Contest: Virtual Judge - day13 ????(2)
// URL: https://vjudge.net/contest/735837#problem/E
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Author: Eason
// Date:2025-08-01 19:19:44
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
#define all(a) a.begin(),a.end()
#define mem(a,b) memset(a,b,sizeof a);
#define pb push_back
#define vct vector
#define rev(T) reverse(T.begin(),T.end())
#define endl "\n"


int read()
{
	int f=1,k=0;char c = getchar();
	while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
	return k*f;
}

const int N = 2e5+5,mod = 998244353;

struct node
{
	int n,m,id;
}q[N];

int B;

bool cmp(node a,node b)
{
	if (a.n/B == b.n/B) return a.m < b.m;
	return (a.n/B) < (b.n/B);
}

int rec[N];

int pw[N],jc[N],inv[N];
int tmp[N];

int ksm(int a,int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a =a * a % mod;
	}
	return res;
}

int C(int a,int b)
{
	if (a < b) return 0;
	return 1ll * jc[a] * inv[b] % mod * inv[a-b] % mod;
}


void solvemain()
{
	int t;cin >> t;B = sqrt(t);
	pw[0] = jc[0] = inv[0] = 1;
	for (int i = 1;i <= 2e5+2;i++) pw[i] = pw[i-1] * 2 % mod,jc[i] = jc[i-1] * i % mod,
	
	inv[i] = ksm(jc[i],mod-2);
	for (int i= 1;i <= t;i++) cin >> q[i].n >> q[i].m,q[i].id = i,q[i].m--,q[i].n--,
			tmp[i] = q[i].n;
	
	sort(q + 1,q + t + 1,cmp);
	
	int l = 0,r = 0,ans = 1;
	
	// cout << C(4,2) << endl;
	
	for (int i = 1;i <= t;i++)
	{
		auto [n,m,id] = q[i];
		while (l < n) 
		{
			ans = (ans * 2) % mod;
			ans -= C(l,r);
			l++;
		}
		// cout << l << ' '<< m << ' ' <<ans << endl;
		while (l > n)
		{
			ans += C(l-1,r);
			// cout << "fuck:L" << ans << endl;
			ans = ans * ((mod+1)/2) % mod;
			l--;
		}
			// cout << ans << endl;
		while (m > r)
		{
			++r;
			ans += C(l,r);
		}
			// cout << ans << endl;
		while (m < r)
		{
			ans -= C(l,r);
			r--;
		}
			// cout << ans << endl;
		ans %= mod;
		ans = (ans + mod) % mod;
		rec[id] = ans;
	}
	
	
	for (int i = 1;i <= t;i++)
	{
		int ans =(pw[tmp[i]+1]-1) * rec[i] % mod;
		cout << ans << endl;
	}
	
	
	
	
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;t = 1;
	
	while(t--)
	{
		solvemain();
	}
	return 0;
}
0