题解 CF1015F 【Bracket Substring】

大菜鸡fks · 2018-08-03 16:39:19 · 题解

从左往右加字符。注意重复

#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int mod=1e9+7,N=205;
int n,Nxt[N],len;
char s[N];
inline void init(){
    scanf("%lld",&n);
    scanf("%s",s+1); len=strlen(s+1);
}
inline void Fail(){
    Nxt[1]=0;
    for (int i=2,j=0;i<=len;i++){
        while (j&&s[j+1]!=s[i]) j=Nxt[j];
        if (s[j+1]==s[i]) j++;
        Nxt[i]=j;
    }
}
int dp[N][N][N][2];
int dfs(int now,int pos,int ds,bool ok){
    if (ds<0||ds>n) return 0;
    if (!now) return !ds&&ok;
    if (~dp[now][pos][ds][ok]) return dp[now][pos][ds][ok];
    int &ans=dp[now][pos][ds][ok],t; ans=0;
    for (t=pos;t&&s[t+1]!=')';t=Nxt[t]); t+=(s[t+1]==')'); ans+=dfs(now-1,t,ds-1,ok|(t==len));
    for (t=pos;t&&s[t+1]!='(';t=Nxt[t]); t+=(s[t+1]=='('); ans+=dfs(now-1,t,ds+1,ok|(t==len));
    return ans%mod;
}
inline void solve(){
    Fail();
    memset(dp,-1,sizeof(dp));
    printf("%lld\n",dfs(n*2,0,0,0));
}
signed main(){
    init();
    solve();
    return 0;
}