結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-06-04 16:42:22
言語 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
結果
WA  
実行時間 -
コード長 2,216 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,976 ms
コンパイル使用メモリ 344,052 KB
実行使用メモリ 30,368 KB
最終ジャッジ日時 2026-10-09 20:34:05
合計ジャッジ時間 19,632 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 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, 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