結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-06-04 16:44:18
言語 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
結果
AC  
実行時間 2,321 ms / 4,000 ms
コード長 2,220 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,772 ms
コンパイル使用メモリ 339,260 KB
実行使用メモリ 24,064 KB
最終ジャッジ日時 2026-06-04 16:44:42
合計ジャッジ時間 21,093 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_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