結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-05 19:07:43
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.89.0)
結果
AC  
実行時間 445 ms / 4,000 ms
コード長 1,817 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,420 ms
コンパイル使用メモリ 216,868 KB
実行使用メモリ 10,128 KB
最終ジャッジ日時 2025-08-05 19:07:58
合計ジャッジ時間 12,926 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N = 2e5;
constexpr int mod = 998244353, inv2 = 499122177;
constexpr int getmod(int x) {
	return x >= mod ? x - mod : x;
}
constexpr int qpow(int a, int b) {
	int ret = 1;
	for (; b; b >>= 1) {
		if (b & 1) ret = (LL)ret * a % mod;
		a = (LL)a * a % mod;
	}
	return ret;
}
constexpr int inv(int a) {
	return qpow(a, mod - 2);
}
int fac[N + 5], ifac[N + 5], p2[N + 5];
int t, B;
int bl[N + 5];
struct query {
	int n, m, id;
	inline bool operator <(const query &x) const {
		return bl[n] != bl[x.n] ? n < x.n : bl[n] & 1 ? m > x.m : m < x.m;
	}
} qu[N + 5];
int p, q, res;
int ans[N + 5];
inline int C(int a, int b) {
	return a < b || b < 0 ? 0 : (LL)fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
inline void addn() {
	res = (((LL)res << 1) - C(p, q) + mod) % mod;
	p++;
}
inline void addm() {
	res = getmod(res + C(p, q + 1));
	q++;
}
inline void deln() {
	p--;
	res = ((LL)res + C(p, q)) * inv2 % mod;
}
inline void delm() {
	q--;
	res = getmod(res - C(p, q + 1) + mod);
}
int main() {
	fac[0] = 1;
	for (int i = 1; i <= N; i++)
		fac[i] = (LL)fac[i - 1] * i % mod;
	ifac[N] = inv(fac[N]);
	for (int i = N - 1; i >= 0; i--)
		ifac[i] = (LL)ifac[i + 1] * (i + 1) % mod;
	p2[0] = 1;
	for (int i = 1; i <= N; i++)
		p2[i] = getmod(p2[i - 1] << 1);
	scanf("%d", &t), B = N / sqrt(t);
	for (int i = 0; i < N; i++) bl[i] = i / B;
	for (int i = 1; i <= t; i++)
		scanf("%d%d", &qu[i].n, &qu[i].m), qu[i].n--, qu[i].m--, qu[i].id = i;
	sort(qu + 1, qu + t + 1);
	res = 1;
	for (int i = 1; i <= t; i++) {
		auto [n, m, id] = qu[i];
		while (p < n) addn();
		while (q < m) addm();
		while (p > n) deln();
		while (q > m) delm();
		ans[id] = ((LL)p2[n + 1] - 1) * res % mod;
	}
	for (int i = 1; i <= t; i++)
		printf("%d\n", ans[i]);
	return 0;
}
0