[noip模拟赛]算算数

树形DP DP 子集DP FWT

题面

有一天小胡同学看到了一种表达式。这个表达式有四个变量$A,B,C,D$。这四
个变量都只有$0$和$1$两种取值。小写字母$a,b,c,d$表示对应变量取反后的值。

• 如果$X$是个变量,那么$X$是个表达式。
• 如果$X,Y$都是表达式,那么$(X)|(Y)$是个表达式。
• 如果$X,Y$都是表达式,那么$(X)\&(Y)$是个表达式。

小胡同学正准备对一个表达式求值的时候,他发现邪恶的小王把这个表达式
的一些变量或运算符给抹掉了(所有的括号均没被抹掉),小胡同学想复原这个
表达式,他现在有$m$个已知的运算结果。每个运算结果记为$f(A,B,C,D)=E$,
表示当$A,B,C,D$取对应值的时候整个表达式的结果为$E$。
现在小胡同学想知道,有多少个合法的表达式满足所有的运算结果。

• $60pts\ m\leq8$
• $100pts\ |S|\leq500,m\leq16$

解析

$60pts$算法

一般来说，求表达式的值都是用栈。
然而这样不能应用于$DP$。

所以有个东西叫表达式树。
它的形态是，最底层是所有的数字，两个数字间的运算符作为它们共同的父亲，同时这个父亲代表它们的运算结果，依次类推。。。

设$f[i][j]$为在第$i$个结点，当前运算结果集合为$j$的方案数。
然后每次递归进左边的括号和右边的括号，最后合并左边和右边的答案即可。
（然而并没那么好写）
复杂度$O(|S|2^{2m})$。（然而其实|S|中大多数都是括号，运算符可能只有$100+$个）
要特别注意当前处理完后，到达下一次处理的字符要挪几位，有时$1$位，有时$2$位。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=100,mod=1e9+7;
int n,m,st[6],S,p,tot,f[505][1<<17];
char s[550];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs(re int x)
{
  re int ls,rs;
  if(s[p]!='(')
    {
      if(s[p]=='?') fp(i,0,3) ++f[x][st[i]],++f[x][st[i]^S];
      else if(s[p]>='A'&&s[p]<='D') ++f[x][st[s[p]-'A']];
      else ++f[x][st[s[p]-'a']^S];
      p+=2;//到运算符
      return;
    }
  ++p;dfs(ls=++tot);
  char op=s[p];
  if(op!='|'&&op!='&'&&op!='?') return;
  p+=2;//到右边括号的内部
  dfs(rs=++tot);
  fp(i,0,S)
    fp(j,0,S)
    {
      if(op!='|') (f[x][i&j]+=1ll*f[ls][i]*f[rs][j]%mod)%=mod;
      if(op!='&') (f[x][i|j]+=1ll*f[ls][i]*f[rs][j]%mod)%=mod;
    }
  ++p;//到达下一次运算
}
int main()
{
  freopen("calculate.in","r",stdin);
  freopen("calculate.out","w",stdout);
  scanf("%s",s+1);n=strlen(s+1);m=gi();S=(1<<m)-1;
  fp(i,1,m)
    fp(j,0,4) (st[j]<<=1)|=gi();
  dfs(tot=p=1);
  printf("%d\n",f[1][st[4]]);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

$100pts$算法

$FWT$专门用于处理异或、或、与下标时的卷积运算。
通常复杂度为$O(nlogn)$。
这样搞一搞，复杂度就成$O(|S|2^mm)$了。
但是这玩意儿应用范围很小，先鸽着。