結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-19 15:58:44
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 1,348 ms / 4,000 ms
コード長 1,798 bytes
コンパイル時間 3,133 ms
コンパイル使用メモリ 171,988 KB
実行使用メモリ 9,452 KB
最終ジャッジ日時 2025-08-19 15:59:08
合計ジャッジ時間 22,632 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 998244353, inv2 = 499122177;
int T, B;
struct node { int n, m, id; } a[N];

inline bool cmp(node a, node b) {
	if ((a.n / B) ^ (b.n / B)) return a.n < b.n;
	return ((a.n / B) & 1) ? a.m < b.m : a.m > b.m;
}

inline int qmi(int a, int k) {
	int res = 1;
	while (k) {
		if (k & 1) res = res * 1ll * a % mod;
		a = a * 1ll * a % mod, k >>= 1;
	} return res;
}
int fac[N], inv[N];
inline void init() {
	fac[0] = 1; for (int i = 1; i <= 200000; i++) fac[i] = fac[i - 1] * 1ll * i % mod;
	inv[200000] = qmi(fac[200000], mod - 2);
	for (int i = 199999; i >= 0; i--) inv[i] = inv[i + 1] * 1ll * (i + 1) % mod;
}
inline int C(int n, int m) { if (n < 0 || m < 0 || n < m) return 0; return fac[n] * 1ll * inv[m] % mod * 1ll * inv[n - m] % mod; }

int n, m;
long long ans, Ans[N];

inline void addn() { ++n, ans = (ans * 2ll - C(n - 1, m) + mod) % mod; }
inline void deln() { ans = (ans + C(n - 1, m)) * 1ll * inv2 % mod, --n; }
inline void addm() { ++m, (ans += C(n, m)) %= mod; }
inline void delm() { (ans += mod - C(n, m)) %= mod, --m; }

int main() {
	init();
//	scanf("%d", &T);
//	while (T--) {
//		scanf("%d%d", &n, &m);
//		long long ans = 0; for (int i = 1; i <= m; i++) (ans += C(n - 1, i - 1)) %= mod;
//		printf("%lld\n", ans * 1ll * (qmi(2, n) - 1) % mod);
//	}
	scanf("%d", &T), B = pow(T, 0.6667);
	for (int i = 1; i <= T; i++) scanf("%d%d", &a[i].n, &a[i].m), a[i].n--, a[i].m--, a[i].id = i;
	sort(a + 1, a + 1 + T, cmp);
	n = m = 0, ans = 1;
	for (int i = 1; i <= T; i++) {
		while (n > a[i].n) deln();
		while (m > a[i].m) delm();
		while (m < a[i].m) addm();
		while (n < a[i].n) addn();
		Ans[a[i].id] = (qmi(2, n + 1) - 1) * 1ll * ans % mod;
	}
	for (int i = 1; i <= T; i++) printf("%lld\n", Ans[i]);
	return 0;
}
0