前缀函数，dp
题意
给定括号序列 \(s\)，和正整数 \(n\)，求出有多少个长度为 \(2n\) 的合法括号序列包含子串 \(s\)。
\(1 \le n \le 100\)，\(s\)（\(1 \le |s| \le 200\)，答案对 \(10^9+7\) 取模。
题解
套路的将左括号设为 \(1\)，右括号设为 \(-1\)。
设 \(dp_{i,j,k}\) 表示前 \(i\) 个数，当前的和为 \(j\)，匹配了 \(s\) 中的 \(k\) 位，暴力转移即可。
注意，若失配，需要从 \(s\) 中当前位置的前缀函数处继续匹配，否则可能出现重复。
同时，钦定 \(k=|s|\) 的前缀函数为 \(|s|\)，同样是为了避免重复。
需要从前往后转移，更方便。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,len,ans;
char c[410];
int dp[210][210][210];
int g[210][3],pi[210];
void init()
{int j=pi[1]=0;for(int i=2;i<=len;i++){while(j && c[j+1]!=c[i]) j=pi[j];if(c[j+1]==c[i]) j++;pi[i]=j;}for(int i=0;i<len;i++){int k,p; k=p=i;while(k && c[k+1]!='(') k=pi[k];while(p && c[p+1]!=')') p=pi[p];if(c[k+1]=='(') k++;if(c[p+1]==')') p++;g[i][0]=k; g[i][1]=p;}g[len][0]=g[len][1]=len;
}
signed main()
{cin>>n>>(c+1);len=strlen(c+1);n*=2; init();dp[0][0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=n;j++){for(int k=0;k<=len;k++){if(j) dp[i+1][j-1][g[k][1]]+=dp[i][j][k],dp[i+1][j-1][g[k][1]]%=mod;dp[i+1][j+1][g[k][0]]+=dp[i][j][k],dp[i+1][j+1][g[k][0]]%=mod;}}}cout<<dp[n][0][len];return 0;
}