結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-05 17:53:20
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 519 ms / 4,000 ms
コード長 1,606 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 741 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 9,832 KB
最終ジャッジ日時 2025-08-05 17:53:29
合計ジャッジ時間 8,451 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:37:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |         init (maxn), scanf ("%d", &n), B = sqrt (n);
      |                      ~~~~~~^~~~~~~~~~
main.cpp:40:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |                 scanf ("%d%d", &a[i], &b[i]), q[i].id = i;
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 200005
using namespace std;

const int maxn = 2e5, mod = 998244353, inv2 = (mod + 1) / 2;

int n, B, now, a[N], b[N], ans[N];
int inv[N], pw2[N], fac[N], facinv[N];

struct que {int x, y, id;} q[N];

void init (int n)
{
	inv[1] = pw2[0] = fac[0] = facinv[0] = 1;
	for (int i = 2; i <= n; i ++)
	{
		inv[i] = (long long) (mod - mod / i) * inv[mod % i] % mod;
	}
	for (int i = 1; i <= n; i ++)
	{
		pw2[i] = pw2[i - 1] * 2 % mod;
		fac[i] = (long long) fac[i - 1] * i % mod;
		facinv[i] = (long long) facinv[i - 1] * inv[i] % mod;
	}
	return ;
}

int C (int x, int y)
{
	return (long long) fac[x] * facinv[y] % mod * facinv[x - y] % mod;
}

int main ()
{
	init (maxn), scanf ("%d", &n), B = sqrt (n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%d%d", &a[i], &b[i]), q[i].id = i;
		q[i].x = a[i] - 1, q[i].y = b[i] - 1;
	}
	
	auto id = [&] (int x) {return (x - 1) / B + 1;};
	
	sort (q + 1, q + n + 1, [&] (que x, que y) -> bool
	{
		if (id (x.y) != id (y.y)) return id (x.y) < id (y.y);
		return id (x.y) & 1 ? x.x < y.x : x.x > y.x;
	});
	
	now = C (0, 0);
	for (int i = 1, x = 0, y = 0; i <= n; i ++)
	{
		while (x < q[i].x) now = (now * 2ll - C (x, y) + mod) % mod, x ++;
		while (y > q[i].y) now = (now - C (x, y) + mod) % mod, y --;
		while (x > q[i].x) x --, now = ((long long) now + C (x, y)) * inv2 % mod;
		while (y < q[i].y) y ++, now = (now + C (x, y)) % mod;
		ans[q[i].id] = now;
	}
	for (int i = 1; i <= n; i ++)
	{
		int coef = (pw2[a[i]] - 1 + mod) % mod;
		printf ("%lld\n", (long long) coef * ans[i] % mod);
	}
	return 0;
}
0