题意
给定一个仅包含与或的中缀表达式，在每一个数值位填 0 或 1，求有多少种填法使得表达式的值为 0。
思路
统计方案数，首先考虑 DP。要想得知表达式的值，就要得知参与最后运算的两个值。这启示我们将中缀转后缀，建表达式树。
定义 \(f_{u,0}\) 为以 \(u\) 为根的子树的表达式为 \(0\)，\(f_{u,1}\) 同理。根据 \(u\) 的运算符列出状态转移方程。如果 \(u\) 是与，那么仅当两个子树表达式的值都为 \(1\) 时该表达式才为 \(1\)。根据乘法原理，方案数为 \(f_{lson,1}\times f_{rson,1}\)。其余依此类推。
\(u\) 为或：
\[f_{u,0}=f_{lson,0}\times f_{rson,0}
\]
\[f_{u,1}=f_{lson,1}\times f_{rson,1}+f_{lson,0}\times f_{rson,1}+f_{lson,1}\times f_{rson,0}
\]
\(u\) 为与：
\[f_{u,0}=f_{lson,0}\times f_{rson,0}+f_{lson,0}\times f_{rson,1}+f_{lson,1}\times f_{rson,0}
\]
\[f_{u,1}=f_{lson,1}\times f_{rson,1}
\]
答案即为 \(f_{root,0}\)。每个叶子结点都可以填 \(0\) 和 \(1\)，因此初始值都为 \(2\)。
注意在补完表达式时要注意添加空位的情况，仅当运算符左边为括号时在左边添位，右边不为括号时在右边添位。为了方便添位和转后缀时的出栈，为表达式整体套一层括号。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#define int long long
using namespace std;
const int N=1e5+10;
const int p=10007;
const int Tm=1e6+1,Ad=1e6+2,lKh=1e6+3,rKh=1e6+4;
int L,tot,totb,tott,cnt;
stack<int> st,st2;
char s[N];
int t[3*N],b[3*N];
int lson[3*N],rson[3*N],w[3*N],v[3*N];
int f[3*N][2];
void dfs(int u){if(lson[u]) dfs(lson[u]);if(rson[u]) dfs(rson[u]);if(w[u]==Ad){f[u][0]=f[lson[u]][0]*f[rson[u]][0]%p;f[u][1]=((f[lson[u]][0]*f[rson[u]][1]%p+f[lson[u]][1]*f[rson[u]][0]%p)%p+f[lson[u]][1]*f[rson[u]][1]%p)%p;}else if(w[u]==Tm){f[u][0]=((f[lson[u]][0]*f[rson[u]][1]%p+f[lson[u]][1]*f[rson[u]][0]%p)%p+f[lson[u]][0]*f[rson[u]][0]%p)%p;f[u][1]=f[lson[u]][1]*f[rson[u]][1]%p;}
}
signed main(){scanf("%lld",&L);scanf("%s",s+2);L+=2;s[1]='(';s[L]=')';for(int i=1;i<=L;i++){if(s[i]=='*'){if(t[tot]==lKh) t[++tot]=++cnt;t[++tot]=Tm;if(s[i+1]!='(') t[++tot]=++cnt;}else if(s[i]=='+'){if(t[tot]==lKh) t[++tot]=++cnt;t[++tot]=Ad;if(s[i+1]!='(') t[++tot]=++cnt;}else if(s[i]=='(') t[++tot]=lKh;else t[++tot]=rKh;}for(int i=1;i<=tot;i++){if(t[i]==Tm){while(!st.empty()&&st.top()==Tm){b[++totb]=Tm;st.pop();} st.push(Tm);}else if(t[i]==Ad){while(!st.empty()&&(st.top()==Tm||st.top()==Ad)){if(st.top()==Tm) b[++totb]=Tm;else b[++totb]=Ad;st.pop();}st.push(Ad);}else if(t[i]==rKh){while(!st.empty()&&st.top()!=lKh){if(st.top()==Tm) b[++totb]=Tm;else b[++totb]=Ad;st.pop();}if(!st.empty()) st.pop();}else if(t[i]==lKh) st.push(lKh);else b[++totb]=t[i];}for(int i=1;i<=totb;i++){if(b[i]<Tm){tott++;w[tott]=b[i];f[tott][0]=f[tott][1]=1;st2.push(tott);}else if(b[i]==Tm){int x=st2.top();st2.pop();int y=st2.top();st2.pop();lson[++tott]=x;rson[tott]=y;w[tott]=Tm;st2.push(tott);}else{int x=st2.top();st2.pop();int y=st2.top();st2.pop();lson[++tott]=x;rson[tott]=y;w[tott]=Ad;st2.push(tott);}}dfs(tott);printf("%lld\n",f[tott][0]);return 0;
} 时间复杂度 \(O(L)\)。