玄学字符串dp...
题意：给定一个括号序列，求长度为2n的合法的括号序列的个数（要求每个被统计的合法序列中均至少有一个子串为给定的括号序列）
题解：
这题没有想的那么复杂，就是暴力的一个dp
首先我们设状态f[i][j][k][0/1]表示当前放到了第i个括号，前i个括号中左右括号个数差为j，已经放好的括号中长为k的部分能与s相匹配，0/1表示之前是否存在与s能匹配上的一整个子串
那么我们考虑转移：
首先我们可以枚举第i位放左括号还是右括号，如果放左括号，左右括号差值+1，否则差值-1，这些都好办，问题在于后两维！
那么显然我们要枚举原来与s匹配了多少，接下来在新放上一个括号之后，我们要考虑加上一个括号之后这一新的后缀能匹配s多长，那这一点可以kmp预处理或者暴力预处理，这里我选择暴力预处理。
于是我们只需要借助上面处理出的辅助数组进行转移即可
最后统计所有可行答案。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define mode 1000000007
#define ll long long
using namespace std;
ll f[][][][];
ll len[][];
char s[];
char p[];
int n;
int solve(int ilen)
{
for(int i=ilen;i>;i--)//??????
{
bool flag=;
for(int j=;j<i;j++)
{
if(p[ilen-i+j]!=s[j])
{
flag=;
break;
}
}
if(!flag)
{
return i;
}
}
return ;
}
int main()
{
scanf("%d",&n);
scanf("%s",s);
int l=strlen(s);
if(s[]=='(')
{
len[][]=;
}else
{
len[][]=;
}
for(int i=;i<l;i++)
{
p[i]=s[i];
p[i+]='(';
len[i+][]=solve(i+);
p[i+]=')';
len[i+][]=solve(i+);
}
f[][][][]=;
for(int i=;i<=*n;i++)//???????λ
{
for(int j=;j<=n;j++)//??????????????
{
for(int k=;k<=l;k++)//??????????????
{
for(int t=;t<=;t++)
{
if(!f[i-][j][k][t])
{
continue;
}
if(j+<=n)
{
f[i][j+][len[k][]][t|(len[k][]==l)]+=f[i-][j][k][t];
f[i][j+][len[k][]][t|(len[k][]==l)]%=mode;
}
if(j>)
{
f[i][j-][len[k][]][t|(len[k][]==l)]+=f[i-][j][k][t];
f[i][j-][len[k][]][t|(len[k][]==l)]%=mode;
}
}
}
}
}
ll ans=;
for(int i=;i<=l;i++)
{
ans+=f[*n][][i][];
ans%=mode;
}
printf("%lld\n",ans);
return ;
}