結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

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

long long n, m, lg[N], sum, f[N], k, ans[N], X, Y, inv[N], inv2;

long long D(long long x, long long y) {
	long long sum = 1;
	for (; y; y /= 2, x = x * x % mod) {
		if (y & 1) {
			sum = sum * x % mod;
		}
	}
	return sum;
}

long long C(long long n, long long m) {
	if (n < m) {
		return 0;
	}
	return (f[n] * inv[m] % mod * inv[n - m] % mod) % mod;
}

struct S {
	long long x, y, id;
} q[N];

bool cmp(S X, S Y) {
	if (X.x / k == Y.x / k) {
		return X.y < Y.y;
	}
	return X.x < Y.x;
}

void addx() {
	sum = (sum * 2ll % mod - C(X, Y) + mod) % mod;
	X++;
}

void remx() {
	sum = (sum + C(X - 1, Y)) % mod * inv2 % mod;
	X--;
}

void addy() {
	sum = (sum + C(X, Y + 1)) % mod;
	Y++;
}

void remy() {
	sum = (sum - C(X, Y) + mod) % mod;
	Y--; 
}

int main() {
	f[0] = 1, inv[0] = 1, lg[0] = 1, inv2 = D(2ll, mod - 2) % mod;
	for (long long i = 1; i <= (long long)2e5; i++) {
		f[i] = f[i - 1] * i % mod;
		inv[i] = D(f[i], mod - 2) % mod;
		lg[i] = lg[i - 1] * 2 % mod;
	}
	cin >> n;
	for (long long i = 1; i <= n; i++) {
		long long x, y;
		cin >> x >> y;
		x--, y--;
		q[i] = {x, y, i};
	}
	k = sqrt((long long)2e5);
	sort (q + 1, q + 1 + n, cmp);
	sum = 1;
	for (long long i = 1; i <= n; i++) {
		for (; X < q[i].x; addx()) {
		}
		for (; Y > q[i].y; remy()) {
		}
		for (; X > q[i].x; remx()) {
		}
		for (; Y < q[i].y; addy()) {
		}
		ans[q[i].id] = sum % mod * (lg[X + 1] - 1 + mod) % mod;
	}
	for (long long i = 1; i <= n; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}
0