【Codeforces 582E】Boolean Function | Mrsrz's blog

状压DP，FWT。

题目大意：

给定一个布尔函数 $f(A,B,C,D)$，函数值为一个布尔表达式，其中变量为 $A,B,C,D,a,b,c,d$，满足 $a=\neg A,b=\neg B,c=\neg C,d=\neg D$。运算符号只有 & 和 |。保证运算符连接的左右两边都是带一层括号的完整子表达式。

其中有一些运算符（不是括号）和变量消失了，变成了 ?。要求把它们还原。

已知 $n$ 个限制条件形如 $A_i,B_i,C_i,D_i,q_i$，表示 $f(A_i,B_i,C_i,D_i)=q_i$，问满足这些限制条件的填充方案有多少种。

题解：

首先建出表达式树。由于一个运算符连接的两边一定是括号括起来的子表达式，所以表达式树形态唯一。建树可以直接 $O(|s|^2)$ 暴力。

我们令 $F_s$ 表示在一个结点处，其第 $i$ 条限制的函数值为 $s_i$（即当前的子树代表的函数 $f’(A_i,B_i,C_i,D_i)=s_i$）时的方案数。进行状压 DP。

把两个子表达式通过运算符合并的时候，如果运算符是与，则进行集合交卷积。如果是或，则进行集合并卷积。如果是问号，则表示与和或都有可能，所以把两种卷积卷起来的答案加起来即可。

集合交、并卷积可以使用 FWT 完成。

于是总时间复杂度 $O(|s|^2+2^nn|s|)$。

Code：

#include<cstdio>
#include<cstring>
#include<cassert>
typedef long long LL;
#define rep(i,a,b)for(int i=(a);i<=(b);++i)
const int N=1<<16,md=1e9+7;
char s[555];
int n,P[16],F[N],C;
inline void add(int&a,const int&b){a+=b-md,a+=a>>31&md;}
inline void sub(int&a,const int&b){a-=b,a+=a>>31&md;}
#define def(f,g)void f(int*a){for(int i=1;i<C;i<<=1)for(int j=0;j<C;j+=i<<1)for(int k=0;k<i;++k)g;}
def(FWT1,add(a[j+k],a[j+k+i]))
def(IFWT1,sub(a[j+k],a[j+k+i]))
def(FWT2,add(a[j+k+i],a[j+k]))
def(IFWT2,sub(a[j+k+i],a[j+k]))
int A[N],B[N];
#define def_(k)\
void trans##k(int*a,int*b,int*F){\
    for(int i=0;i<C;++i)A[i]=a[i],B[i]=b[i];\
    FWT##k(A),FWT##k(B);\
    for(int i=0;i<C;++i)A[i]=(LL)A[i]*B[i]%md;\
    IFWT##k(A);\
    for(int i=0;i<C;++i)add(F[i],A[i]);\
}
def_(1)def_(2)
void solve(int l,int r,int*F){
    int fh=0,mid=-1;
    for(int i=l;i<=r&&mid==-1;++i)
    switch(s[i]){
        case'(':++fh;break;
        case')':--fh;break;
        default:if(!fh)mid=i;
    }
    if(mid==-1||l==r){
        while(s[l]=='('&&s[r]==')')++l,--r;
        assert(l==r);
        for(int x=1;x<=4;++x)if(s[l]=='?'||s[l]=='A'+4-x||s[l]=='a'+4-x){
            int zt=0;
            for(int i=0;i<n;++i)zt|=(P[i]>>x&1)<<i;
            if(s[l]!='a'+4-x)++F[zt];
            if(s[l]!='A'+4-x)++F[(C-1)^zt];
        }
        return;
    }
    int L[C],R[C];
    for(int i=0;i<C;++i)L[i]=R[i]=0;
    solve(l+1,mid-2,L),solve(mid+2,r-1,R);
    if(s[mid]!='|')trans1(L,R,F);
    if(s[mid]!='&')trans2(L,R,F);
}
int main(){
    scanf("%s%d",s,&n);
    for(int i=0;i<n;++i){
        int a,b,c,d,e;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
        P[i]=16*a+8*b+4*c+2*d+e;
    }
    C=1<<n;
    solve(0,strlen(s)-1,F);
    int zt=0;
    for(int i=0;i<n;++i)zt|=(P[i]&1)<<i;
    printf("%d\n",F[zt]);
    return 0;
}