結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-06-04 16:44:18
言語 C++23(gnu拡張)
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,878 ms / 4,000 ms
+ 613µs
コード長 2,220 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,039 ms
コンパイル使用メモリ 344,012 KB
実行使用メモリ 28,452 KB
最終ジャッジ日時 2026-10-09 20:34:39
合計ジャッジ時間 21,274 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int MAXN = 6e5 + 5, mod = 998244353;
int T, inv[MAXN], jc[MAXN], n, m, id[MAXN], ans[MAXN], last = 1, l, r, inv_2;
struct Node {
	int x, y, pos;
}ls[MAXN];

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

void ycl() {
	jc[0] = inv[0] = 1;
	for (int i = 1; i <= MAXN - 5; i++) jc[i] = jc[i - 1] * i % mod, inv[i] = KSM(jc[i], mod - 2);
}

int C(int a, int b) {
	return jc[a] * inv[b] % mod * inv[a - b] % mod;
}

void MKFK() {
	int kc = cbrt(MAXN);
	for (int i = 0; i <= MAXN - 5; i++) id[i] = (i - 1) / kc + 1;
}

bool cmp(Node x, Node y) {
	if (id[x.x] != id[y.x]) return id[x.x] < id[y.x];
	return x.y < y.y;
}

void add(int x, int op) {
//	if (op) cout << l << ' ' << r << ';';
	if (op == 0) last = (last * 2 % mod - C(l, r) + mod) % mod;
	else last = (last + C(l, r + 1)) % mod;
}

void del(int x, int op) {
	if (op == 0) last = ((last + C(l - 1, r)) % mod * inv_2) % mod;
	else last = (last - C(l, r) + mod) % mod;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	ycl();
	inv_2 = KSM(2, mod - 2);
	cin >> T;
	for (int i = 1; i <= T; i++) {
		cin >> ls[i].x >> ls[i].y;
		ls[i].x --, ls[i].y --;
		ls[i].pos = i;
	}
	MKFK();
	sort(ls + 1, ls + 1 + T, cmp);
	for (int i = 1; i <= T; i++) {
		while (l < ls[i].x) add(l, 0), l++;
//		cout << last << ' ';
		while (l > ls[i].x) del(l, 0), l--;
//		l = ls[i].x;
		while (r < ls[i].y) add(r, 1), r++;
		while (r > ls[i].y) del(r, 1), r--;
		ans[ls[i].pos] = (KSM(2, ls[i].x + 1) - 1) * last % mod;
	}
	for (int i = 1; i <= T; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}
/*
C(n, 0) + C(n, 1) + C(n, 2) + C(n, 3) + ... + C(n, m)
C(n + 1, 0) + C(n + 1, 1) + C(n + 1, 2) + C(n + 1, 3) + ... + C(n + 1, m)
= C(n, 0) + (C(n, 0) + C(n, 1)) + (C(n, 1) + C(n, 2)) + ... + (C(n, m - 1) + C(n, m))
= 2 * last - C(n, m)

1
10 9

C(4, 0) + C(4, 1)

30
91 78
78 13
9178 918
7891 787
34568 2311
91 78
78 13
9178 918
7891 787
34568 2311
91 78
78 13
9178 918
7891 787
34568 2311
91 78
78 13
9178 918
7891 787
34568 2311
91 78
78 13
9178 918
7891 787
34568 2311
91 78
78 13
9178 918
7891 787
34568 2311
*/
0