結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-06-04 16:42:22
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,216 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,754 ms
コンパイル使用メモリ 339,780 KB
実行使用メモリ 24,064 KB
最終ジャッジ日時 2026-06-04 16:42:43
合計ジャッジ時間 18,999 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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