题解：CF2063F1 Counting Is Not Fun (Easy Version)
所有方案数均基于卡特兰数，不妨设 $F(x) = \dfrac{\tbinom{2x}{x}}{x + 1}$ 来表示卡特兰数。
初始时显然答案为 $F(n)$。当有括号加入时，未被添加括号的位置的贡献不会超过最外层已匹配的括号。举个例子，当 $?????? \to \color{red}{(}??\color{red}??$ 时，答案就变化为 $F(3) \to F(1) \times F (1)$。
因此可以先将这 $n$ 对括号进行编号，然后借助栈，当遇到未被添加括号的位置时，将贡献加在栈顶的括号对应的编号上，最后根据乘法原理求解即可。
时间复杂度 $O(n^2)$，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 5005;
const int MOD = 998244353;
inline int read ();
int t,n,p[MAX << 1],l[MAX],r[MAX],cnt[MAX];ll ans,f[MAX << 1],inv[MAX << 1],inv2[MAX << 1];
stack <int> s;
ll qpow (ll x,ll y)
{
ll res = 1;
while (y)
{
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
ll catalan (int x) {return f[2 * x] * inv[x] % MOD * inv[x] % MOD * inv2[x + 1] % MOD;}
int main ()
{
f[0] = inv[0] = 1;
for (int i = 1;i <= 10000;++i) f[i] = f[i - 1] * i % MOD,inv2[i] = qpow (i,MOD - 2);
inv[10000] = qpow (f[10000],MOD - 2);
for (int i = 9999;i;--i) inv[i] = inv[i + 1] * (i + 1) % MOD;
s.push (0);
t = read ();
while (t--)
{
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 o = 0;o <= n;++o)
{
for (int i = 0;i <= n;++i) cnt[i] = 0;
p[l[o]] = o;p[r[o]] = -o;ans = 1;
for (int i = 1;i <= 2 * n;++i)
{
if (!p[i]) ++cnt[s.top ()];
else if (p[i] < 0) s.pop ();
else s.push (p[i]);
}
for (int i = 0;i <= n;++i) ans = ans * catalan (cnt[i] / 2) % MOD;
printf ("%lld ",ans);
}
puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
