yicongli

CF149D

Jan 21st, 2021 (edited)
463
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int p=1e9+7;
  17. const int N=705;
  18.  
  19. inline void add(int &a,const int &b){
  20.     if((a+=b)>=p)a-=p;
  21. }
  22.  
  23. int a[N];
  24. int f[N][N][3][3];
  25.  
  26. void dfs(int l,int r){
  27.     if(r==l+1){
  28.         f[l][r][0][1]=1;
  29.         f[l][r][0][2]=1;
  30.         f[l][r][1][0]=1;
  31.         f[l][r][2][0]=1;
  32.         return ;
  33.     }
  34.     if(a[l]==r){
  35.         dfs(l+1,r-1);
  36.         for(int i=0;i<3;++i){
  37.             for(int j=0;j<3;++j){
  38.                 for(int k=1;k<3;++k){
  39.                     if(i^k)add(f[l][r][k][0],f[l+1][r-1][i][j]);
  40.                     if(j^k)add(f[l][r][0][k],f[l+1][r-1][i][j]);
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     else {
  46.         dfs(l,a[l]);
  47.         dfs(a[l]+1,r);
  48.         for(int i=0;i<3;++i){
  49.             for(int j=0;j<3;++j){
  50.                 for(int k=0;k<3;++k){
  51.                     for(int m=0;m<3;++m){
  52.                         if(j==k && j)continue;
  53.                         add(f[l][r][i][m],(ll)f[l][a[l]][i][j]*f[a[l]+1][r][k][m]%p);
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. char s[N];
  62. int sta[N],tot;
  63.  
  64. int main(){
  65.     // freopen(".in","r",stdin);
  66.     // freopen(".out","w",stdout);
  67.     scanf("%s",s);
  68.     int n=strlen(s);
  69.     for(int i=0;i<n;++i){
  70.         if(s[i]=='('){
  71.             sta[++tot]=i;
  72.         }
  73.         else {
  74.             a[sta[tot]]=i;
  75.             a[i]=sta[tot];
  76.             --tot;
  77.         }
  78.     }
  79.     dfs(0,n-1);
  80.     int ans=0;
  81.     for(int i=0;i<3;++i)
  82.         for(int j=0;j<3;++j)
  83.             add(ans,f[0][n-1][i][j]);
  84.     printf("%d\n",ans);
  85.     return 0;
  86. }
RAW Paste Data