結果

問題 No.2990 Interval XOR
ユーザー sinsop900
提出日時 2025-04-22 08:53:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 458 ms / 2,000 ms
コード長 2,894 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 194,684 KB
実行使用メモリ 45,952 KB
最終ジャッジ日時 2025-04-22 08:53:54
合計ジャッジ時間 13,345 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:57:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |         scanf("%lld%lld", &m, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
main.cpp:59:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |                 scanf("%lld%lld", &e[i].l, &e[i].r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = (1 << 20) + 50;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;

ll n, m, a[maxn], b[maxn], c[maxn], d[maxn], suf[maxn], ans[maxn], f[maxn][2];
ll ca[maxn], cb[maxn];

struct node {
	ll l, r;
} e[maxn];

inline void iFWT(ll *a) {
	for (int k = 1; k < (1 << m); k <<= 1) {
		for (int i = 0; i < (1 << m); i += (k << 1)) {
			for (int j = 0; j < k; ++j) {
				ll x = a[i + j], y = a[i + j + k];
				a[i + j] = (x + y < mod ? x + y : x + y - mod) * inv2 % mod;
				a[i + j + k] = (x < y ? x - y + mod : x - y) * inv2 % mod;
			}
		}
	}
}

void dfs(int l, int r) {
	if (l == r) {
		f[l][0] = ca[l];
		f[l][1] = (__builtin_parity(l) ? mod - cb[l] : cb[l]) % mod;
		return;
	}
	int mid = (l + r) >> 1;
	dfs(l, mid);
	dfs(mid + 1, r);
	for (int i = l, j = mid + 1; i <= mid; ++i, ++j) {
		ll xa = f[i][0], xb = f[i][1], ya = f[j][0], yb = f[j][1];
		f[i][0] = (xa * ya - xb * yb % mod + mod) % mod;
		f[i][1] = (xb * ya - xa * yb % mod + mod) % mod;
		f[j][0] = (ya * xa + yb * xb) % mod;
		f[j][1] = (ya * xb + yb * xa) % mod;
	}
}

void solve() {
	scanf("%lld%lld", &m, &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &e[i].l, &e[i].r);
	}
	for (int i = 0; i < (1 << m); ++i) {
		ans[i] = 0;
	}
	for (int p = 0; p < m; ++p) {
		suf[(1 << m)] = 0;
		for (int i = (1 << m) - 1; ~i; --i) {
			suf[i] = suf[i + 1] + ((i & (1 << p)) ? -1 : 1);
		}
		ll x = 0;
		for (int i = 1; i <= n; ++i) {
			a[i] = suf[(e[i].r >> (p + 1)) << (p + 1)] - suf[e[i].r + 1];
			c[i] = e[i].r >> (p + 1);
			if (e[i].l) {
				b[i] = (mod - suf[((e[i].l - 1) >> (p + 1)) << (p + 1)] + suf[e[i].l]) % mod;
				d[i] = (e[i].l - 1) >> (p + 1);
			} else {
				b[i] = d[i] = 0;
			}
			x ^= c[i];
		}
		for (int i = 0; i < (1 << (m - 1 - p)); ++i) {
			ca[i] = 1;
			cb[i] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			ll y = c[i] ^ d[i];
			ll a1 = ca[y], b1 = cb[y], a2 = a[i], b2 = b[i];
			ca[y] = (a1 * a2 + b1 * b2) % mod;
			cb[y] = (a1 * b2 + a2 * b1) % mod;
		}
		dfs(0, (1 << (m - 1 - p)) - 1);
		for (int i = 0; i < (1 << (m - 1 - p)); ++i) {
			if (__builtin_parity(i & x)) {
				f[i][0] = (mod - f[i][0]) % mod;
				f[i][1] = (mod - f[i][1]) % mod;
			}
		}
		for (int i = 0; i < (1 << m); ++i) {
			if (__lg(i & (-i)) == p) {
				ans[i] = (ans[i] + f[i >> (p + 1)][0] + f[i >> (p + 1)][1]) % mod;
			}
		}
	}
	ans[0] = 1;
	for (int i = 1; i <= n; ++i) {
		ans[0] = ans[0] * (e[i].r - e[i].l + 1) % mod;
	}
	iFWT(ans);
	for (int i = 0; i < (1 << m); ++i) {
		printf("%lld\n", ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
0