結果

問題 No.2990 Interval XOR
ユーザー 波波龙
提出日時 2025-04-21 22:16:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 220 ms / 2,000 ms
コード長 4,468 bytes
コンパイル時間 1,465 ms
コンパイル使用メモリ 163,804 KB
実行使用メモリ 36,224 KB
最終ジャッジ日時 2025-04-21 22:17:05
合計ジャッジ時間 9,855 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;

inline namespace MyIO {
	inline ll rd() {
		char ch = getchar();
		ll s = 0, w = 1;
		while (!isdigit(ch)) {
			if (ch == '-') w = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			s = (s << 3) + (s << 1) + (ch ^ 48);
			ch = getchar();
		}
		return (s * w);
	}
	template<typename T>
	inline void wr(T x) {
		if (x < 0) x = -x, putchar('-');
		if (x > 9) wr(x / 10);
		putchar(x % 10 + 48);
	}
	inline void wrsp() {
		// pass
	}
	template<typename T, typename... Args>
	inline void wrsp(T x, Args... args) {
		wr(x), putchar(' '), wrsp(args...);
	}
	inline void wrln() {
		putchar('\n');
	}
	template<typename T>
	inline void wrln(T x) {
		wr(x), putchar('\n');
	}
	template<typename T, typename... Args>
	inline void wrln(T x, Args... args) {
		wr(x), putchar(' '), wrln(args...);
	}
} // namespace MyIO

inline namespace Base {
	#define bug(x) << #x << '=' << (x) << ' '
	#define siz(A) ll((A).size())

	template<typename T>
	constexpr inline T& Max(T &x, const T &y) {
		return x = max(x, y);
	}
	template<typename T>
	constexpr inline T& Min(T &x, const T &y) {
		return x = min(x, y);
	}
} // namespace Base

constexpr int fn = 1048576;
constexpr int N = fn + 10;

namespace {
	constexpr ll MO = 998244353;
	constexpr inline ll moa(ll x) { return (x >= MO ? x - MO : x); }
	constexpr inline ll moi(ll x) { return (x < 0 ? x + MO : x); }
	constexpr inline ll mo(ll x) { return moi(x % MO); }
	constexpr inline ll& Moa(ll &x) { return x = moa(x); }
	constexpr inline ll& Moi(ll &x) { return x = moi(x); }
	constexpr inline ll& Mo(ll &x) { return x = mo(x); }
	constexpr inline ll qpow(ll x, ll y) {
		Mo(x); ll k = 1;
		for (; y; y >>= 1) {
			if (y & 1) (k *= x) %= MO;
			(x *= x) %= MO;
		}
		return k;
	}
	constexpr inline ll get_inv(ll x) { return qpow(x, MO - 2); }
	constexpr inline ll div2(ll x) { return (x + (x & 1) * MO) >> 1; }
	constexpr inline ll& Div2(ll &x) { return x = div2(x); }
}

int n, m, L[N], R[N];
ll P[N];
template<bool flag>
void FWT(ll f[]) {
	for (int l = 1; l < (1 << m); l <<= 1) {
		for (int i = 0; i < (1 << m); i += (l << 1)) {
			for (ll *g = f + i; g < f + i + l; ++g) {
				ll k = g[l];
				Moi(g[l] = g[0] - k), Moa(g[0] += k);
				if (flag) Div2(g[0]), Div2(g[l]);
			}
		}
	}
	return;
}

int h;
ll f_pool[2][N][2]; auto *f_pre = f_pool[0], *f_nxt = f_pool[1];
void sulu() {
	int m = ::m - h - 1;
	auto compute_ac = [&](int r, ll &a, int &c) -> void {
		int rem = r & ((1 << (h + 1)) - 1);
		if (!rem) return a = c = 0, void(); // avoid that r == (1 << ::m), causing that c = (1 << m) and let c be out of range [0, (1 << m)) and not 被统计
		c = r >> (h + 1);
		if (rem < (1 << h)) a = rem;
		else a = (1 << h) - (rem - (1 << h));
		return;
	};
	int xum = 0;
	for (int i = 0; i < (1 << m); ++i) f_pre[i][0] = f_pre[i][1] = 1;
	// cerr bug(h) << endl;
	for (int i = 1; i <= n; ++i) {
		ll a, b; int c, d;
		compute_ac(R[i], a, c), compute_ac(L[i], b, d);
		// cerr bug(L[i]) bug(R[i]) bug(a) bug(c) bug(b) bug(d) << endl;
		Moi(b *= -1);
		d ^= c, xum ^= c;
		(f_pre[d][0] *= moa(a + b)) %= MO;
		(f_pre[d][1] *= moi(a - b)) %= MO;
	}
	Moi(f_pre[xum][1] *= -1); // xor-convoluting x^{xum} is equivalent to xor-convoluting (0 + 1 * x^{xum}), perform the same procedure as above, in a result of f_pre[xum][1] *= -1 (f_pre[xum][0] does not change)
	for (int l = 1; l < (1 << m); l <<= 1) {
		for (int i = 0; i < (1 << m); i += (l << 1)) {
			for (int j = 0; j < l; ++j) {
				ll (*g_pre)[2] = f_pre + i + j;
				ll (*g_nxt)[2] = f_nxt + i + j;
				g_nxt[0][0] = g_pre[0][0] * g_pre[l][0] % MO;
				g_nxt[0][1] = g_pre[0][1] * g_pre[l][1] % MO;
				g_nxt[l][0] = g_pre[0][0] * g_pre[l][1] % MO;
				g_nxt[l][1] = g_pre[0][1] * g_pre[l][0] % MO;
			}
		}
		swap(f_pre, f_nxt);
	}
	for (int i = 0; i < (1 << m); ++i) Moa(P[i << (h + 1) | (1 << h)] += f_pre[i][0]);
	return;
}
void solve_tc() {
	m = rd(), n = rd();
	for (int i = 0; i < (1 << m); ++i) P[i] = 0;
	P[0] = 1;
	for (int i = 1; i <= n; ++i) L[i] = rd(), R[i] = rd() + 1, (P[0] *= R[i] - L[i]) %= MO; 

	for (h = 0; h < m; ++h) sulu();
	// for (int i = 0; i < (1 << m); ++i) wrsp(P[i]);
	// wrln();
	FWT<1>(P);
	for (int i = 0; i < (1 << m); ++i) wrln(P[i]);
	// ll ans = 0, coe = 1;
	// for (int i = 0; i < (1 << m); ++i) {
	// 	ans ^= P[i] * coe % MO;
	// 	Moa(coe <<= 1);
	// }
	// wrln(ans);
	return;
}
void NamespaceMain() {
	solve_tc();
	return;
}
int main() {
	NamespaceMain();
	return 0;
}
0