- 有四个(bool)变量(A,B,C,D)以及相对的(a,b,c,d)分别表示它们取反后的值。
- 给定一个布尔函数(F(A,B,C,D))的表达式(s)，其中若干变量和运算符缺失。
- 给出(n)组(A,B,C,D)以及对应的(F(A,B,C,D))值，求有多少种可能的表达式。
- (|s|le500,nle16)
建立二叉树
乍一看表达式求值似乎需要大模拟，但仔细一想这道题还是非常良心的，因为它的表达式定义非常严谨，而且每个变量外面也都套着个括号。
于是我们建立一棵二叉树，每个节点表示原表达式的一个子表达式，然后根据中间的运算符再把它分成两部分。
最后划分到只剩一个变量时就可以作为叶节点了。
动态规划
考虑设(f_{x,i})表示对于二叉树上的节点(x)，(n)个(F(A,B,C,D))中这个子表达式的值状压为(i)的方案数。
叶节点直接根据它的变量确定(f)的初值。
否则，对于一个点(x)，设其两个子节点分别为(lc,rc)，得到转移：（其中( exttt{opt})表示这个子表达式中间的运算符）
[f_{x,i exttt{opt} j} exttt{+=}f_{lc,i} imes f_{rc,j}
]
显然这就是一个多项式乘法的形式，直接上(FWT)优化就好了。
代码：(O(|s|n2^n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define S 500
#define N 16
#define X 1000000007
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,m,l,f[S+5][1<<N],v[5];char s[S+5];
I void FWT_A(int *s,CI op)//FWT与变换
{
RI i,j,k;for(i=1;i<=m;i<<=1) for(j=0;j<=m;j+=i<<1)
for(k=0;k^i;++k) op?Inc(s[j+k],s[i+j+k]):Inc(s[j+k],X-s[i+j+k]);
}
I void FWT_O(int *s,CI op)//FWT或变换
{
RI i,j,k;for(i=1;i<=m;i<<=1) for(j=0;j<=m;j+=i<<1)
for(k=0;k^i;++k) op?Inc(s[i+j+k],s[j+k]):Inc(s[i+j+k],X-s[j+k]);
}
I void Mul_A(CI x,CI lc,CI rc)//与
{
FWT_A(f[x],1),FWT_A(f[lc],1),FWT_A(f[rc],1);
for(RI i=0;i<=m;++i) f[x][i]=(1LL*f[lc][i]*f[rc][i]+f[x][i])%X;//转移
FWT_A(f[x],0),FWT_A(f[lc],0),FWT_A(f[rc],0);
}
I void Mul_O(CI x,CI lc,CI rc)//或
{
FWT_O(f[x],1),FWT_O(f[lc],1),FWT_O(f[rc],1);
for(RI i=0;i<=m;++i) f[x][i]=(1LL*f[lc][i]*f[rc][i]+f[x][i])%X;//转移
FWT_O(f[x],0),FWT_O(f[lc],0),FWT_O(f[rc],0);
}
int cur,tot;I int DP()//动态规划（强制进入时cur在左括号，离开时cur在右括号右边）
{
RI x=++tot;if(s[cur+2]==')')//只有单个变量（叶节点）
{
if(s[cur+1]=='?') for(RI i=0;i^4;++i) ++f[tot][v[i]],++f[tot][v[i]^m];//对于未知变量，可以任填
else (s[cur+1]<='D'?f[tot][v[s[cur+1]-'A']]:f[tot][v[s[cur+1]-'a']^m])=1;//对于已知变量，初值唯一
return cur+=3,x;
}
RI lc,rc;char op;++cur,lc=DP(),op=s[cur],++cur,rc=DP();//op记录中间运算符，把表达式分成两部分
return op^'|'&&(Mul_A(x,lc,rc),0),op^'&'&&(Mul_O(x,lc,rc),0),++cur,x;//转移
}
int main()
{
RI i,j,x;scanf("%s%d",s+1,&n),l=strlen(s+1),s[0]='(',s[l+1]=')';//方便起见，给表达式套上一对括号
for(m=(1<<n)-1,i=0;i^n;++i) for(j=0;j^5;++j) scanf("%d",&x),v[j]|=x<<i;//状压
return printf("%d
",f[DP()][v[4]]),0;//求整个表达式值符合限制的方案数
}