传送门 考虑合法括号序列的定义。
如果A合法，那么(A)合法如果A,B合法，那么AB合法这样的话我们可以每次找一对匹配的括号，括号内的序列递归做就行了。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> using namespace std; const int N=710,P=1e9+7; int n,mat[N]; char a[N]; stack<int> S; inline void add(int &x,int y){ if((x+=y)>=P) x-=P; } struct ans{ int f[3][3]; int *operator [](int x){ return f[x]; } ans(){ for(int i=0;i<3;i++)for(int j=0;j<3;j++) f[i][j]=0; } int val(){ int ret=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) add(ret,f[i][j]); return ret; } ans inc(){ ans ret; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) for(int s=0;s<3;s++) if((k!=i || i==0) && (s!=j || j==0)) add(ret[i][j],f[k][s]); ret[0][0]=ret[1][1]=ret[1][2]=ret[2][1]=ret[2][2]=0; return ret; } friend ans operator +(ans a,ans b){ ans ret; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) for(int s=0;s<3;s++) if(j!=k || j==0) add(ret[i][s],1LL*a[i][j]*b[k][s]%P); return ret; } }u; ans Query(int l,int r){ ans ret,cur,now; if(l+1==r) return u; if(l+1==mat[l]) ret=u; else ret=Query(l+1,mat[l]-1).inc(); for(int i=mat[l]+1,j;i<=r;i=mat[i]+1) if(i+1<mat[i]){ ret=ret+Query(i+1,mat[i]-1).inc(); } else ret=ret+u; return ret; } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%s",a+1); n=strlen(a+1); for(int i=1;i<=n;i++) if(a[i]=='(') S.push(i); else mat[S.top()]=i,S.pop(); u[0][1]=u[1][0]=u[2][0]=u[0][2]=1; printf("%d\n",Query(1,n).val()); return 0; }