嗯。。。。。对于这种题显然就是DP咯。。。

（我一开始打了个ON的，结果发现当a[i]==')'时不会转移。。。。）（其实和正解就只有一步之遥）

（以上废话）

好吧进入正题

分析一下题目，其实就是从中抽出若干个字符使得组成的是一个合法序列。

我们可以发现只有当前字符为‘）’的时候才有可能组成新的组合。

那么我们可以通过前面得到有多少种情况是【一个合法或空序列+一个‘（’】。

显然，前面若有一个多余的左括号，那么就可以多出一种排列。

那么如果f[i]表示当前到第i个有多少种，sum[i]表示还有i个')'时有多少种情况。

则可以得到：

if(a[i]=='(')f[i]=f[i-1]（因为没有新的，就继承原来的）

else f[i]=f[i-1]+sum[1];（意思是不用当前和用了当前的和）

但是问题来了，这个sum[1]怎么更新呢？

不急不急，我们分类讨论。

如果当前是‘（’{

如果不用它，就是原来的个数。如果用了，那就是sum[个数-1]。

即sum[i]+=sum[i-1]；

}

如果是‘）’{

如果不用它，那就是原来的个数。如果用了，那相当于抵消掉一个，即sum[个数+1]。

即sum[i]+=sum[i+1]

}

然后由于数据，要用滚动数组滚滚。效率卡卡常就可以了。

总结：不要总盯着效率看，说不定它就是个卡常的暴力。。。。

 代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define ull unsigned long long#define turn printf("\n");using namespace std;const int orzhjw=10010;ll a,b,c,d,m=1e9+7,sum=0,ans=0;bool hy[orzhjw]={
    0};ll whh[orzhjw]={
    0};inline ll get(ll &x){    char s=getchar();ll f=1,o=0;    while(s>'9'||s<'0'){
    if(s=='-')f=-1;s=getchar();}    while(s<='9'&&s>='0'){o=o*10+s-'0';s=getchar();}    return x=o*f;}inline ll put(ll x){    printf("%lld ",x);return 0;}int main(){    get(a);    for(ll i=1;i<=a;i++){        char k=getchar();        if(k=='(')hy[i]=0;        else hy[i]=1;    }    whh[0]=1;    for(ll i=1;i<=a;i++){        if(hy[i]==0){            sum++;            for(int j=sum;j>=1;j--){                whh[j]=(whh[j]+whh[j-1])%m;            }        }        else{            ans+=whh[1];            for(int j=0;j<=sum;j++){                whh[j]=(whh[j]+whh[j+1])%m;            }        }    }    put(ans%m);turn;}