已经没有什么好害怕的了

已经没有什么好害怕的了

题目名莫名有点逗......

对于这题,我们首先要知道,将原串中不合法的串删了,依然能保证结果的正确性,唯一要注意的就是,合法字符在原串中的位置也要记录下来(供计算答案使用).

那么,怎么把那些无用的字符删去?这就是典型的括号匹配,而我们现在还需要知道新串的样子.那么我们可以用链表来将合法的字符保留下来(也就是可以匹配).

接下来,我们已经有了一个合法的新串.

那么,我们如何在新串中计数?

假如,一个括号对,左边有x个同级别(请理解这个同级别)的括号对,右边有y个,则,有(x+1)*(y+1)种方案包含了当前括号对.

但是,是否就仅仅这样呢?不.因为这个括号对可能被另外一个括号对包含着,这个括号对的方案数还应该加上它外层的括号对的方案数.

so?可以用DFS实现.当然,如果出现了这样的情况:

()()()...()()...()()..也就是两个括号对之间(在原串中)有不合法的因素,那么,这两块的统计就不能相互影响,只能一块一块地计算.

最后按照题意计算ans.比较坑的是,我们计算的并不是一个模,而是模的和!!!(话说这题还是卡了一点常的).

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define LL long long
using namespace std;
const int maxn=1000005;
const int TT=1000000007;
int len,vis[maxn],n,R[maxn],L[maxn],w[maxn];
LL tot[maxn];
char s[maxn],newc[maxn];
struct node{int pre,nxt; char c;}a[maxn];
void DFS(int l,int r,LL su){
    while (1){
        int cnt=0,cnt0=-1,broke=-1,rr=r;
        for (int i=l,j=R[i]; i<=r; i=j+1,j=R[i]) if (j>r) break; else{
            cnt++; if (w[j]+1!=w[j+1]){broke=j+1; break;}
        }
        if (broke>0) rr=broke-1;
        for (int i=l,j=R[i]; i<=rr; i=j+1,j=R[i]){
            if (j>rr) break; else cnt0++;
            tot[i]=tot[j]=(su+(LL)(cnt0+1)*(cnt-cnt0-1+1))%TT;
            if (i+1<j-1) DFS(i+1,j-1,tot[i]);
        }
        if (broke>0) l=broke; else return;
    }
}
int main(){
    int T; scanf("%d",&T);
    for (; T; T--){
        scanf("%s",s),len=strlen(s);
        for (int i=len-1; i>=0; i--) a[i+1].c=s[i];
        for (int i=1; i<=len; i++) a[i].pre=i-1,a[i].nxt=i+1;
        a[0].pre=-1,a[0].nxt=1,a[len+1].pre=len,a[len+1].nxt=len+2;
        for (int i=1; i<=len; i++) if (a[i].c==')'){
            if (a[a[i].pre].pre>=0)
                if (a[a[i].pre].c=='(') a[a[i].nxt].pre=a[a[i].pre].pre,a[a[a[i].pre].pre].nxt=a[i].nxt;
        }
        for (int i=1; i<=len; i++) vis[i]=1;
        for (int now=a[0].nxt; now<=len; now=a[now].nxt) vis[now]=0;
        memset(newc,0,sizeof newc),n=0;
        for (int i=1; i<=len; i++) if (vis[i]) newc[++n]=a[i].c,w[n]=i;
        stack <int> st; while (!st.empty()) st.pop();
        for (int i=1; i<=n; i++) if (newc[i]=='(') st.push(i);
        else{int K=st.top(); st.pop(); R[K]=i,L[i]=K;}
        DFS(1,n,0);
        LL ans=0;
        for (int i=1; i<=n; i++) ans=ans+(tot[i]*w[i])%TT;
        printf("%lld\n",ans);
    }
    return 0;
}