526互联

CodeForces 1830C Hyperregular Bracket Strings

发布时间 2023-05-29 13:53:03作者: zltzlt

洛谷传送门

CF 传送门

每一步思路都非常自然的题。

考虑先从一些简单的 case 入手。

1. \(k = 0\)

设 \(g_i\) 为长度为 \(i\) 的合法括号串数。显然 \(\forall i \nmid 2， g_i = 0\)。对于偶数的 \(i\)，这是一个经典问题，\(g_i\) 就是第 \(\frac{i}{2}\) 项卡特兰数，因此 \(g_i = \binom{i}{\frac{i}{2}} - \binom{i}{\frac{i}{2} - 1}\)。

2. 区间互不相交

考虑把这些区间删去，那么剩下的括号也要构成合法括号串。设 \(len_i\) 为第 \(i\) 个区间的长度，\(r\) 为区间长度总和，答案即为 \(g_{n - r} \times \prod\limits_{i=1}^k g_{len_i}\)。

3. 区间两两不交或包含

考虑建树，每个区间向包含它且最短的区间连边，那么会构成一片森林。设 \(f_u\) 为第 \(u\) 个区间内部的方案数，\(r_u\) 为 \(\sum\limits_{v \in son_v} len_v\)，那么由互不相交的 case 我们得到 \(f_u = g_{len_u - r_u}\prod\limits_{v \in son_u} f_v\)。

4. 区间可能相交但不包含

举个例子，如果 \([3, 6]\) 和 \([5, 8]\) 都是合法括号串，画出折线图，可以发现相当于 \([3, 4], [5, 6], [7, 8]\) 都是合法括号串。也就是我们要把相交的部分分裂出来。考虑异或哈希，每个区间赋一个随机权值，把区间里的每一个数都异或上这个权值，最后把每个权值第一次出现的位置和最后一次出现的位置拎出来作为新的区间。显然它们只会两两不交或包含了。

一步一步推下来，都挺自然的。

复杂度是线性对数。

code 
// Problem: C. Hyperregular Bracket Strings
// Contest: Codeforces - Codeforces Round 875 (Div. 1)
// URL: https://codeforces.com/contest/1830/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

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

const int maxn = 1000100;
const int logn = 22;
const int N = 1000000;
const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

ll n, m, fac[maxn], ifac[maxn], f[maxn];
int g[maxn][logn], e[maxn], pre[maxn], lst[maxn], lg[maxn], fa[maxn];
ull b[maxn], c[maxn], d[maxn];
vector<int> G[maxn];
mt19937_64 rnd(time(NULL));

struct node {
	ll l, r;
	node(ll a = 0, ll b = 0) : l(a), r(b) {}
} a[maxn];

void init() {
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[N] = qpow(fac[N], mod - 2);
	for (int i = N - 1; ~i; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	}
	for (int i = 2; i <= N; ++i) {
		lg[i] = lg[i >> 1] + 1;
	}
}

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

inline ll calc(ll n) {
	if (n & 1) {
		return 0;
	}
	n /= 2;
	return (C(n * 2, n) - C(n * 2, n - 1) + mod) % mod;
}

inline int qmax(int l, int r) {
	int k = lg[r - l + 1];
	return max(g[l][k], g[r - (1 << k) + 1][k]);
}

void dfs(int u) {
	f[u] = 1;
	ll len = a[u].r - a[u].l + 1;
	for (int v : G[u]) {
		dfs(v);
		len -= a[v].r - a[v].l + 1;
		f[u] = f[u] * f[v] % mod;
	}
	f[u] = f[u] * calc(len) % mod;
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int i = 0; i <= n + 1; ++i) {
		b[i] = c[i] = d[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%lld%lld", &a[i].l, &a[i].r);
		ull x = rnd(), y = rnd(), z = rnd();
		b[a[i].l] ^= x;
		b[a[i].r + 1] ^= x;
		c[a[i].l] ^= y;
		c[a[i].r + 1] ^= y;
		d[a[i].l] ^= z;
		d[a[i].r + 1] ^= z;
	}
	sort(a + 1, a + m + 1, [&](node a, node b) {
		return a.l < b.l || (a.l == b.l && a.r < b.r);
	});
	if (n & 1) {
		puts("0");
		return;
	}
	for (int i = 1; i <= m; ++i) {
		if ((a[i].r - a[i].l + 1) & 1) {
			puts("0");
			return;
		}
	}
	for (int i = 1; i <= n; ++i) {
		b[i] ^= b[i - 1];
		c[i] ^= c[i - 1];
		d[i] ^= d[i - 1];
	}
	map< pair< ull, pair<ull, ull> >, int > mp;
	int tot = 0;
	for (int i = 1, j = 1; i <= n; i = (++j)) {
		while (j < n && (b[j + 1] == b[i] && c[j + 1] == c[i] && d[j + 1] == d[i])) {
			++j;
		}
		// printf("i, j: %d %d %llu %llu %llu\n", i, j, b[i], c[i], d[i]);
		auto t = make_pair(b[i], make_pair(c[i], d[i]));
		if (mp.find(t) == mp.end()) {
			mp[t] = ++tot;
		}
		int val = mp[t];
		for (int k = i; k <= j; ++k) {
			e[k] = val;
		}
	}
	for (int i = 1; i <= tot; ++i) {
		pre[i] = lst[i] = 0;
	}
	for (int i = 1; i <= n; ++i) {
		if (!pre[e[i]]) {
			pre[e[i]] = i;
		}
		lst[e[i]] = i;
	}
	// for (int i = 1; i <= tot; ++i) {
		// printf("i: %d %lld %lld\n", i, pre[i], lst[i]);
	// }
	for (int i = 1; i <= tot; ++i) {
		a[i] = node(pre[i], lst[i]);
	}
	sort(a + 1, a + tot + 1, [&](node a, node b) {
		return a.l < b.l || (a.l == b.l && a.r < b.r);
	});
	for (int i = 0; i <= tot + 1; ++i) {
		f[i] = 0;
		vector<int>().swap(G[i]);
	}
	for (int i = 1; i <= tot; ++i) {
		g[i][0] = a[i].r;
		// printf("i: %d %lld %lld\n", i, a[i].l, a[i].r);
	}
	for (int j = 1; (1 << j) <= tot; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= tot; ++i) {
			g[i][j] = max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 1; i <= tot; ++i) {
		int l = 1, r = i - 1, pos = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (qmax(mid, i - 1) > a[i].r) {
				pos = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		fa[i] = pos;
		if (pos != -1) {
			G[pos].pb(i);
		}
	}
	ll ans = 1, t = n;
	for (int i = 1; i <= tot; ++i) {
		if (fa[i] == -1) {
			dfs(i);
			t -= a[i].r - a[i].l + 1;
			ans = ans * f[i] % mod;
		}
	}
	ans = ans * calc(t) % mod;
	printf("%lld\n", ans);
}

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