[cf582E]Boolean Function

由于每一个运算都有括号，因此添加的运算不会改变运算顺序

先将其建出一棵表达式树，也就是维护两个栈，是节点和运算符优先级单调递增的栈（设置左括号优先级最低，右括号弹出直至左括号）

每一次运算，也就是新建一个节点（节点上记录操作符)，并将栈顶的两个节点作为其儿子即可

关于?是操作符还是变量的判定，只需要根据上一个字符是左括号还是右括号即可

建出表达式树后，令$S$是一个$2^{2^{4}}$的二进制数，表示定义$f_{k,S}$表示以$k$为根的子树中，每一种取值的答案为$S$在该位置上的值的方案数，合并根据or或and做卷积，复杂度为$o(Ln2^{n})$（$L=|s|$）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 505

  4 #define S (1<<16)

  5 #define mod 1000000007

  6 stack<int>st_op,st_num;

  7 int V,n,ans,a[N],ls[N],rs[N],vis[105],f1[S],f2[S],f3[S],g[11][S],f[N][S];

  8 char s[N];

  9 int turn_num(int k){

 10     if (('A'<=s[k])&&(s[k]<='D'))return s[k]-'A';

 11     if (('a'<=s[k])&&(s[k]<='d'))return s[k]-'a'+4;

 12     if ((s[k]=='?')&&((!k)||(s[k-1]=='(')))return 8;

 13     return -1;

 14 }

 15 void merge(){

 16     a[++V]=st_op.top();

 17     st_op.pop();

 18     rs[V]=st_num.top();

 19     st_num.pop();

 20     ls[V]=st_num.top();

 21     st_num.pop();

 22     st_num.push(V);

 23 }

 24 void FWT_or(int *a,int p){

 25     for(int i=0;i<(1<<4);i++)

 26         for(int j=0;j<S;j++)

 27             if (j&(1<<i))a[j]=((a[j]+p*a[j^(1<<i)])%mod+mod)%mod;

 28 }

 29 void FWT_and(int *a,int p){

 30     for(int i=0;i<(1<<4);i++)

 31         for(int j=0;j<S;j++)

 32             if (j&(1<<i))a[j^(1<<i)]=((a[j^(1<<i)]+p*a[j])%mod+mod)%mod;

 33 }

 34 void dfs(int k){

 35     if ((!ls[k])&&(!rs[k]))return;

 36     dfs(ls[k]);

 37     dfs(rs[k]);

 38     if (!a[k]){

 39         FWT_and(f[ls[k]],1);

 40         FWT_and(f[rs[k]],1);

 41         for(int i=0;i<S;i++)f[k][i]=1LL*f[ls[k]][i]*f[rs[k]][i]%mod;

 42         FWT_and(f[k],-1);

 43     }

 44     if (a[k]==1){

 45         FWT_or(f[ls[k]],1);

 46         FWT_or(f[rs[k]],1);

 47         for(int i=0;i<S;i++)f[k][i]=1LL*f[ls[k]][i]*f[rs[k]][i]%mod;

 48         FWT_or(f[k],-1);

 49     }

 50     if (a[k]==2){

 51         memcpy(f1,f[ls[k]],sizeof(f1));

 52         memcpy(f2,f[rs[k]],sizeof(f2));

 53         FWT_and(f1,1);

 54         FWT_and(f2,1);

 55         for(int i=0;i<S;i++)f3[i]=1LL*f1[i]*f2[i]%mod;

 56         FWT_and(f3,-1);

 57         FWT_or(f[ls[k]],1);

 58         FWT_or(f[rs[k]],1);

 59         for(int i=0;i<S;i++)f[k][i]=1LL*f[ls[k]][i]*f[rs[k]][i]%mod;

 60         FWT_or(f[k],-1);

 61         for(int i=0;i<S;i++)f[k][i]=(f[k][i]+f3[i])%mod;

 62     }

 63 }

 64 int main(){

 65     scanf("%s",s);

 66     n=strlen(s);

 67     for(int i=0;i<n;i++){

 68         int p=turn_num(i);

 69         if (p!=-1){

 70             a[++V]=p;

 71             st_num.push(V);

 72             if ((!st_op.empty())&&(st_op.top()!=-1))merge();

 73         }

 74         else{

 75             if (s[i]=='(')st_op.push(-1);

 76             if (s[i]=='&')st_op.push(0);

 77             if (s[i]=='|')st_op.push(1);

 78             if (s[i]=='?')st_op.push(2);

 79             if (s[i]==')'){

 80                 st_op.pop();

 81                 if ((!st_op.empty())&&(st_op.top()!=-1))merge();

 82             }

 83         }

 84     }

 85     while (!st_op.empty())merge();

 86     for(int i=0;i<8;i++){

 87         int sta=0;

 88         for(int j=0;j<(1<<4);j++)

 89             if (((j&(1<<i%4))>0)^(i>=4))sta+=(1<<j);

 90         g[i][sta]=1;

 91         g[8][sta]++;

 92     }

 93     for(int i=1;i<=V;i++)

 94         if ((!ls[i])&&(!rs[i]))memcpy(f[i],g[a[i]],sizeof(f[i]));

 95     dfs(V);

 96     memset(vis,-1,sizeof(vis));

 97     scanf("%d",&n);

 98     for(int i=1;i<=n;i++){

 99         int k=0,p;

100         for(int j=0;j<4;j++){

101             scanf("%d",&p);

102             if (p)k+=(1<<j);

103         }

104         scanf("%d",&vis[k]);

105     }

106     for(int i=0;i<S;i++){

107         bool flag=0;

108         for(int j=0;j<(1<<4);j++)

109             if ((vis[j]>=0)&&(((i&(1<<j))>0)!=vis[j])){

110                 flag=1;

111                 break;

112             }

113         if (!flag)ans=(ans+f[V][i])%mod;

114     }

115     printf("%d",ans);

116 }

巴特西

[cf582E]Boolean Function

最新文章

热门文章