【CF582E】Boolean Function
题意：给你一个长度为n的表达式，其中未知数有A,B,C,D和？，运算有&和|和?（表达式中用括号确定了唯一的运算顺序）。?代表A,B,C,D或&,|。A,B,C,D的值是0或1。再给你m个条件$a,b,c,d,e$，代表A,B,C,D分别等于a,b,c,d时表达式的值为e。求有多少种将?填满的方式，符合给出的所有条件？
$nle 500,mle 2^4$
题解：CF总考这种用二进制表示特殊状态的题，感觉十分考验人类的抽象能力。
因为变量的可能情况的只有$2^4$种，所以我们用一个4位的二进制字符表示。这样一来我们就可以发现可能的表达式只有$2^{2^4}$种，所以我们再用一个16位的二进制来表示一个表达式（不要晕）。这个二进制数的第i位为0/1的意义是：如果把i用二进制表示，则i的每一位代表每个变量的取值。在这些变量分别取这些值时，这个表达式的值为0/1（千万不要晕）。
因为表达式是一堆括号围出来的，我们可以将括号的嵌套看成一个树形结构，并且是一棵二叉树。我们设f[x][S]表示对于当前节点对应的子树，有多少种方法使得得到的表达式为S。转移时我们通过左右儿子的f以及当前节点的运算符即能确定当前节点的f值。然后你会发现转移的实质就是FWT。。。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int P=1000000007;
char str[510];
int n,m,tot;
int f[170][(1<<16)+4],g[(1<<16)+4],p1[20],p2[20];
inline void add(int &x,int y) {x+=y; if(x>=P) x-=P;}
inline void dec(int &x,int y) {x-=y; if(x<=0) x+=P;}
inline void fwt1(int *a)
{
for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if((i>>h)&1) add(a[i],a[i^(1<<h)]);
}
inline void ufwt1(int *a)
{
for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if((i>>h)&1) dec(a[i],a[i^(1<<h)]);
}
inline void fwt0(int *a)
{
for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if(!((i>>h)&1)) add(a[i],a[i|(1<<h)]);
}
inline void ufwt0(int *a)
{
for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if(!((i>>h)&1)) dec(a[i],a[i|(1<<h)]);
}
int build(int l,int r)
{
int x=++tot;
if(l==r)
{
int i,j,S;
for(j=0;j<4;j++)
{
if(str[l]=='?'||str[l]=='A'+j)
{
for(S=i=0;i<16;i++) if((i>>j)&1) S|=1<<i;
f[x][S]++;
}
if(str[l]=='?'||str[l]=='a'+j)
{
for(S=i=0;i<16;i++) if(!((i>>j)&1)) S|=1<<i;
f[x][S]++;
}
}
return x;
}
int i,mid,t=0;
for(i=l;i<=r;i++)
{
t+=(str[i]=='(')-(str[i]==')');
if(!t) break;
}
mid=i+1;
int ls=build(l+1,mid-2),rs=build(mid+2,r-1);
if(str[mid]=='|')
{
fwt1(f[ls]),fwt1(f[rs]);
for(i=0;i<(1<<16);i++) f[x][i]=1ll*f[ls][i]*f[rs][i]%P;
ufwt1(f[x]);
}
else if(str[mid]=='&')
{
fwt0(f[ls]),fwt0(f[rs]);
for(i=0;i<(1<<16);i++) f[x][i]=1ll*f[ls][i]*f[rs][i]%P;
ufwt0(f[x]);
}
else
{
fwt0(f[ls]),fwt0(f[rs]);
for(i=0;i<(1<<16);i++) g[i]=1ll*f[ls][i]*f[rs][i]%P;
ufwt0(g),ufwt0(f[ls]),ufwt0(f[rs]);
memcpy(f[x],g,sizeof(g));
fwt1(f[ls]),fwt1(f[rs]);
for(i=0;i<(1<<16);i++) g[i]=1ll*f[ls][i]*f[rs][i]%P;
ufwt1(g);
for(i=0;i<(1<<16);i++) add(f[x][i],g[i]);
}
return x;
}
int main()
{
scanf("%s%d",str+1,&m),n=strlen(str+1);
int i,j,ans=0,S=0,t;
for(i=1;i<=m;i++)
{
for(S=j=0;j<4;j++) scanf("%d",&t),S|=t<<j;
scanf("%d",&t),p1[i]=S,p2[i]=t;
}
build(1,n);
for(i=0;i<(1<<16);i++)
{
for(j=1;j<=m;j++) if(((i>>p1[j])&1)!=p2[j]) break;
if(j>m) add(ans,f[1][i]);
}
printf("%d",ans);
return 0;
}