Coloring Brackets

题意：

给一匹配的括号序列，要求每对括号恰有一个被染成蓝或红色，要求相邻的括号不同色，求方案数。

解法：

类比树的hash将括号序列转化为一棵树，树上子节点之间不得出现冲突，

子节点和父节点不得出现冲突，问题转化为树形dp问题，$O(n)$解决。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 
  6 #define N 1000010
  7 #define LL long long
  8 #define P 1000000007LL
  9 
 10 using namespace std;
 11 
 12 /*
 13 1 -> 10
 14 2 -> 01
 15 3 -> 20
 16 4 -> 02
 17 */
 18 
 19 int totn;
 20 int next[N],q[N];
 21 LL f[N][5];
 22 LL h[N][3];
 23 char S[N];
 24 vector<int> G[N];
 25 
 26 int build(int l,int r)
 27 {
 28     int x=++totn;
 29     G[x].clear();
 30     l++;
 31     r--;
 32     while(l<r)
 33     {
 34         G[x].push_back(build(l,next[l]));
 35         l=next[l]+1;
 36     }
 37     return x;
 38 }
 39 
 40 void dp(int x)
 41 {
 42     int nl=G[x].size();
 43     if(!nl)
 44     {
 45         for(int i=1;i<5;i++)
 46             f[x][i]=1;
 47         return;
 48     }
 49     for(int i=0;i<nl;i++) dp(G[x][i]);
 50     for(int t=0;t<3;t++)
 51     {
 52         for(int i=0;i<3;i++) h[0][i]=0;
 53         h[0][t]=1;
 54         for(int i=1;i<=nl;i++)
 55         {
 56             int p=G[x][i-1];
 57             LL sum = (h[i-1][0]+h[i-1][1]+h[i-1][2])%P;
 58             h[i][1] = sum * f[p][2] % P;
 59             h[i][2] = sum * f[p][4] % P;
 60             
 61             h[i][0] = h[i-1][0]*f[p][1]%P + h[i-1][2]*f[p][1]%P;
 62             if(h[i][0]>=P) h[i][0]-=P;
 63             h[i][0] += h[i-1][0]*f[p][3]%P + h[i-1][1]*f[p][3]%P;
 64             if(h[i][0]>=P) h[i][0]-=P;
 65         }
 66         if(t==0)
 67         {
 68             f[x][0] = (h[nl][0] + h[nl][1] + h[nl][2]) % P;
 69             f[x][2] = (h[nl][0] + h[nl][2])%P;
 70             f[x][4] = (h[nl][0] + h[nl][1])%P;
 71         }
 72         else if(t==1) f[x][1] = (h[nl][0] + h[nl][1] + h[nl][2])%P;
 73         else f[x][3] = (h[nl][0] + h[nl][1] + h[nl][2])%P;
 74     }
 75 }
 76 
 77 int n;
 78 
 79 int main()
 80 {
 81     freopen("test.txt","r",stdin);
 82     while(~scanf("%s",S+1))
 83     {
 84         S[0]='(';
 85         n=strlen(S);
 86         S[n]=')';
 87         S[n+1]='';
 88         n++;
 89         int ed=0;
 90         totn=0;
 91         for(int i=0;i<n;i++)
 92         {
 93             if(S[i]=='(') q[++ed]=i;
 94             else
 95             {
 96                 next[q[ed]]=i;
 97                 ed--;
 98             }
 99         }
100         build(0,n-1);
101         dp(1);
102         cout << f[1][0] << endl;
103     }
104     return 0;
105 }
106 /*
107 (())
108 (()())
109 ()
110 */

View Code