Codeforces 1015F (差值、匹配状态DP + KMP)

Codeforces 1015F
题意:给你一个括号序列 $s$ (不一定是常规序列)。 括号序列是仅包含字符()的字符串。你的问题是计算长度为 $2n$ 的常规括号序列的数量,而且必须满足给定括号序列$ s$ 是它的子串(连续字符序列)。输出这个数量模 $ 10 ^ 9 + 7$ 的结果。

如果不考虑包含$s$,那么可以设$dp(i,j)$为构造的串前$i$个字符左括号比右括号多多少个(差值,状态冗余处理)的方案,转移非常显然

然后如果要包含子串$s$,就要引入新的维度,我们联想到CF 1096D的做法,那就是匹配状态的引入。所以我们可以设$dp(i,j,k)$为构造的串前$i$个字符左括号比右括号多多少个,并且匹配了$s$的$[1,k]$的方案数。

转移方便则刷表
$$
\begin{cases}
dp(i+1,j+1,x)+=dp(i,j,k) \\
dp(i+1,j-1,x)+=dp(i,j,k)
\end{cases}
$$
前者为在后面插入(,后者为在后面插入)。其中的$x$为加入相应括号后$s$串的匹配状态。类似 KMP,这里如果失配了则需要找到前面最近的候选点,然后再判,所以我们利用类似KMP的方法来求解,当然也可以暴力求,但是感觉没KMP好求。注意当$k=s_{len}$时,我们只从$len$转移到$len$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 1000000007;
int n, f[205];
int len; char s[205]; // 0 for left, 1 for right
LL dp[205][205][205];
void clean() {
}
int solve() {
clean();
scanf("%d%s", &n, s + 1);
len = strlen(s + 1);
f[1] = f[2] = 1;
for (int i = 2; i <= n + 1; ++i) {
int j = f[i];
while (j > 1 && s[i] != s[j]) j = f[j];
f[i + 1] = (s[i] == s[j] ? j + 1 : 1);
}
dp[0][0][0] = 1;
for (int i = 0; i <= 2 * n; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 0; k < len; ++k) {
int pre = k + 1; // 找候选等于 ) 的
while (pre > 1 && s[pre] != ')') pre = f[pre];
if (s[pre] != ')') --pre; // 找不到
if (j) (dp[i + 1][j - 1][pre] += dp[i][j][k]) %= MO;
pre = k + 1; // 找候选等于 ( 的
while (pre > 1 && s[pre] != '(') pre = f[pre];
if (s[pre] != '(') --pre; // 找不到
(dp[i + 1][j + 1][pre] += dp[i][j][k]) %= MO;
}
dp[i + 1][j + 1][len] += dp[i][j][len]; // 特判 k = len
if (j) (dp[i + 1][j - 1][len] += dp[i][j][len]) %= MO;
}
}
printf("%lld\n", dp[2 * n][0][len]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------