打的时候在错误的思路上卡了半个小时，以至于最后 10
分钟想到了正解，但已经没时间写了。
赛后把这题改过了，比改错了还难受。
考虑最终形成的序列满足什么条件。
我们不妨把第
次插入的两个字符编号为 。
那么会形成
之类的结构，但一定不会有 （交错），也不会有 (大包小）
这其实是一个类似树的结构，跟括号树其实长得差不多，我们如果按包含关系建树（在上述例子中， 就是 的儿子，如果有 那 就是
的儿子），那么问题实际上被分成两部分：
dp 这棵树以及节点上的状态，使得最终的括号串合法。
处理插入顺序，使得父亲比儿子先插入。
第二部分就是一个树的拓扑序，处理是容易的，下文再讲。
考虑第一部分。
这种对有包含关系区间 的
DP（或者说对类似这种“括号树”的 DP),其实就是区间 ，如果区间 是一个节点，我们枚举断点
相当于枚举这个节点最靠左的儿子。而在本题中，我们其实只要记录区间长度（或者说区间内有几对括号）即可。
有个经典结论是，把 ( 看作 1,把 ) 看作
-1,那么一个括号串能够匹配，当且仅当这个串的所有前缀和都非负且左右括号数目相等。
那我们不妨把这个前缀和的最小值记录进 状态，容易发现这个值 。
设 表示序列长度为 ，最小前缀和为 的方案数（另一种解释是在序列两边添加
对括号才能使其合法）
，那么会有转移。
$$
$$
上文的 是题目中的 ，
相当于枚举跟
一起被插入的是哪个位置，相当于枚举树上最靠左的儿子，而组合数是为了安排插入的顺序。
直接实现上述转移是
的，注意到问题可以被转化成 这种形式，使用前缀和优化，分类讨论 和 转移即可。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5,P = 998244353;
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
inline void Plus(int &a,const int &b) { a += b;if(a >= P) a -= P;}
int n,pro;
int f[N][N];
int fac[N],ifac[N];
inline void init(int n)
{
fac[0] = 1;
for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[1] = 1;
for(int i = 2;i <= n;i++) ifac[i] = 1ll * (P - P / i) * ifac[P % i] % P;
ifac[0] = 1;
for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
}
inline int C(int n,int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int g[N],h[N];
int main()
{
cin >> n >> pro;
init(n);
pro = 1ll * pro * qpow(10000,P - 2) % P;
f[0][0] = 1;
for(int i = 1;i <= n;i++)
{
for(int k = 0;k < i;k++)
{
int r = i - k - 1;
memset(g,0,sizeof g);
memset(h,0,sizeof h);
for(int s1 = 0;s1 <= k;s1++)
Plus(g[max(s1 - 1,0)],1ll * f[k][s1] * C(i,k + 1) % P * pro % P),
Plus(g[s1 + 1],1ll * f[k][s1] * C(i,k + 1) % P * (P + 1 - pro) % P);
for(int s2 = 0;s2 <= r;s2++)
h[s2] = f[r][s2];
for(int s1 = 1;s1 <= i;s1++)
Plus(g[s1],g[s1 - 1]);
for(int s2 = 1;s2 <= i;s2++)
Plus(h[s2],h[s2 - 1]);
for(int v = 0;v <= i;v++)
{
int res = 1ll * g[v] * f[r][v] % P;
if(v > 0) Plus(res,1ll * (g[v] - g[v - 1] + P) % P * h[v - 1] % P);
Plus(f[i][v],res);
}
}
}
int ans = f[n][0];
for(int i = 3;i < 2 * n;i += 2)
ans = 1ll * ans * qpow(i,P - 2) % P;
cout << ans << endl;
return 0;
}
|
其实不是很难的一道题。可以用来练习计数，提升竞技状态。
但这场 E 好垃圾啊（