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

发表于 | 分类于 | | + s

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;
}
------ 本文结束 ------