結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-03 21:19:20
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 878 ms / 4,000 ms
コード長 1,554 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,389 ms
コンパイル使用メモリ 200,044 KB
実行使用メモリ 9,260 KB
最終ジャッジ日時 2025-08-03 21:19:35
合計ジャッジ時間 15,007 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:43:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |                 scanf("%d%d", &a[i].n, &a[i].m);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int q, sz, fac[200005], invfac[200005], pw2[200005], ans[200005];
struct Info {
	int n, m, id;
} a[200005];

bool cmp(const Info& l, const Info& r) {
	return l.n / sz < r.n / sz || (l.n / sz == r.n / sz && l.m < r.m);
}

int qpow(int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		n >>= 1;
	}
	return res;
}

int C(int n, int m) {
	if (n < m || m < 0) return 0;
	return 1ll * fac[n] * invfac[n - m] % mod * invfac[m] % mod;
}

int main() {
	fac[0] = 1;
	pw2[0] = 1;
	for (int i = 1; i <= 200000; i++) {
		fac[i] = 1ll * fac[i - 1] * i % mod;
		pw2[i] = pw2[i - 1] * 2ll % mod;
	}
	invfac[200000] = qpow(fac[200000], mod - 2);
	for (int i = 199999; i >= 0; --i) {
		invfac[i] = invfac[i + 1] * (i + 1ll) % mod;
	}
	scanf("%d", &q);
	sz = sqrt(q);
	for (int i = 1; i <= q; i++) {
		scanf("%d%d", &a[i].n, &a[i].m);
		--a[i].n, --a[i].m, a[i].id = i;
	}
	sort(a + 1, a + q + 1, cmp);
	int l = 0, r = 0, res = 1;
	for (int i = 1; i <= q; i++) {
		int n = a[i].n, m = a[i].m, id = a[i].id;
		while (l > n) {
			res = (res + C(l - 1, r)) % mod * 499122177ll % mod;
			--l;
		}
		while (l < n) {
			res = (res * 2ll % mod - C(l, r) + mod) % mod;
			++l;
		}
		while (r < m) {
			res = (res + C(l, r + 1)) % mod;
			++r;
		}
		while (r > m) {
			res = (res - C(l, r) + mod) % mod;
			--r;
		}
		ans[id] = (pw2[n + 1] - 1ll + mod) % mod * res % mod;
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}
0