結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2026-10-07 10:08:28
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 711 ms / 4,000 ms
+ 449µs
コード長 1,585 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 433 ms
コンパイル使用メモリ 84,548 KB
実行使用メモリ 9,916 KB
最終ジャッジ日時 2026-10-07 10:08:42
合計ジャッジ時間 13,740 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
using namespace std;
constexpr int maxn = 2e5 + 10, mod = 998244353;
struct qry { int n, m, id; } qr[maxn]; int qp[maxn], ans[maxn], fac[maxn], ifac[maxn];
int qpow (int a, int b) {
	int ans = 1;
	while (b > 0) {
		if ((b & 1) == 1) ans = 1ll * a * ans % mod;
		a = 1ll * a * a % mod; b >>= 1;
	} return ans;
}
int binom (int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0; 
	return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
signed main () {
	int q; cin >> q; qp[0] = 1; int B = 400; int inv2 = qpow(2, mod - 2); fac[0] = ifac[0] = 1;
	for (int i = 1; i <= 2e5; i ++) qp[i] = 1ll * qp[i - 1] * 2 % mod, fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[(signed)2e5] = qpow(fac[(signed)2e5], mod - 2);
	for (int i = 2e5; i > 1; i --) ifac[i - 1] = 1ll * ifac[i] * i % mod;
	for (int i = 1; i <= q; i ++) cin >> qr[i].n >> qr[i].m, qr[i].id = i; 
	sort(qr + 1, qr + q + 1, [&](const qry& P, const qry& Q) {
		if ((P.n / B) == (Q.n / B)) return P.m < Q.m;
		return ((P.n / B) < (Q.n / B)); 
	}); int _n = 0, _m = 0, now = 1;
	for (int i = 1; i <= q; i ++) {
		qr[i].n --, qr[i].m --;
		while (_n > qr[i].n) now = (1ll * now + binom(_n - 1, _m)) % mod * inv2 % mod, _n --;
		while (_m < qr[i].m) now = (1ll * now + binom(_n, _m + 1)) % mod, _m ++;
		while (_n < qr[i].n) now = ((2ll * now % mod) + mod - binom(_n, _m)) % mod, _n ++;
		while (_m > qr[i].m) now = (1ll * now + mod - binom(_n, _m)) % mod, _m --;
		ans[qr[i].id] = (1ll * qp[qr[i].n + 1] + mod - 1) % mod * now % mod;
	}
	for (int i = 1; i <= q; i ++) cout << ans[i] << '\n'; 
}
0