首先，我们发现要生成本质不同的子序列，需要删除不同的相同颜色段中的任意一个。
考虑加强结论，要求删除相同颜色段的第一个。
然而这样我们还面临合并颜色段的问题，不好操作。
我们考虑给每个点标记一个删除时间戳，不同的时间戳序列就是不同的子序列。
那么我们每一次删除的点需要满足前一个时间戳大于其的点与其异色。
我们设状态 $f(l,r)$ 表示为 $[l,r]$ 填时间戳的方案数，然而我们不知道前一个时间戳大于其的点，所以不好转移。
考虑加强状态，要求 $l-1$ 的时间戳大于 $[l,r]$。
答案仍然为 $f(1,n)$，所以加强是没问题的。
那么这样我们就可以通过枚举 $[l,r]$ 中的最大时间戳点 $k$ 转移。
$$
f(l,r) = \sum_{k=l}^r \binom{r-l}{k-l} \cdot f(l,k-1) \cdot f(k+1,r)
$$
其中：$s(k) = s(l-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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=400;
const int mod=998244353;
int n;
char s[maxn+5];
int c[maxn+5][maxn+5];
int f[maxn+5][maxn+5];
signed main(){
scanf("%d%s",&n,s+1);
c[0][0]=1;
for(int i=1;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
for(int i=1;i<=n+1;i++)
f[i][i-1]=1,f[i][i]=(s[i]!=s[i-1]);
for(int len=2;len<=n;len++){
for(int i=1,j=i+len-1;j<=n;i++,j++){
for(int k=i;k<=j;k++){
if(s[k]!=s[i-1]){
f[i][j]=(f[i][j]
+1ll*f[i][k-1]*f[k+1][j]%mod
*c[j-i][k-i]%mod)%mod;
}
}
}
}
printf("%d",f[1][n]);
return 0;
}
|