题解：CF2063F1 Counting Is Not Fun (Easy Version)

题目大意

有一个长度为

2n

的括号序列，每个位置一开始都不知道，给出

n

对匹配的括号，要求一开始和每轮线索后符合条件的括号序列数。

题目分析

注意到，答案跟卡特兰数有关，设

C(x)

来表示卡特兰数。

在没有线索时，答案就是

C(n)

。当得到新的线索时，答案就会变成每段空位的卡特兰数相乘。例如：原本的括号序列 ???????? 变成 ??(??)??，答案就会从

C(4)

变成

C(2) \times C(1)

，可以理解成每一层的空位拼起来，然后将每一层的卡特兰数相乘。

于是，我们可以括号序列常用的处理方法——栈，统计每一对括号里面的空位，最后乘起来即可。时间复杂度

\mathcal{O}(n ^ 2)

。

注意：计算的时候，应该是 cnt[i] / 2 而不是 cnt[i]，因为卡特兰数

C(n)

是由

n

对括号构成的合法括号序列数。

code

CPP

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const ll mod = 998244353;
const int N = 5e3 + 5;
ll qpow(ll a, ll b = mod - 2)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
ll fac[N << 1], invf[N << 1], invi[N << 1];
ll Catalan(int x) { return fac[2 * x] * invf[x] % mod * invf[x] % mod * invi[x + 1] % mod; }
stack<int> stk;
void init()
{
	fac[0] = invf[0] = 1;
	for (int i = 1; i <= 10000; i++) fac[i] = fac[i - 1] * i % mod, invi[i] = qpow(i, mod - 2);
	invf[10000] = qpow(fac[10000]);
	for (int i = 9999; i >= 1; i--) invf[i] = invf[i + 1] * (i + 1) % mod;
	stk.push(0); // 最外层 
}
int l[N], r[N], p[N << 1], cnt[N];
// p 用来标记当前位置，0 为没固定，> 0 表示这是第几次加进来的 
// cnt 为第 i 对括号里面有多少个空位，那么这对括号的贡献为 Catalan(cnt_i / 2) 
// cnt_0 代表最外面有多少空位 
void solve()
{
	int n = read();
	for (int i = 1; i <= n; i++) l[i] = read(), r[i] = read();
	for (int i = 1; i <= 2 * n; i++) p[i] = 0;
	for (int j = 0; j <= n; j++)
	{
		for (int i = 0; i <= n; i++) cnt[i] = 0;
		p[l[j]] = j, p[r[j]] = -j; // 表示第 j 对括号 
		for (int i = 1; i <= 2 * n; i++)
		{
			if (p[i] == 0) cnt[stk.top()]++; 
			else if (p[i] > 0) stk.push(p[i]);
			else stk.pop();
		}
//		for (int i = 0; i <= n; i++) cout << cnt[i] << " ";
//		cout << endl;
		ll ans = 1;
		for (int i = 0; i <= n; i++) ans = ans * Catalan(cnt[i] / 2) % mod;
		writech(ans, ' '); 
	}
	pc('\n');
}
int main()
{
	init();
	int T = read();
	while (T--) solve();
	return 0;
}

题解：CF2063F1 Counting Is Not Fun (Easy Version)

文章操作

题目大意

题目分析

code

相关推荐

评论

题解：CF2063F1 Counting Is Not Fun (Easy Version)