#include <bits/stdc++.h> using namespace std; const int MOD=10007; int f[2][100005]; //每一位是0的可能性和是1的可能性 int main() { int len; string c,pol="."; cin>>len>>c; stack<char> sta; for(int i=0;i<len;i++) { if(c[i]'(' || c[i]'') sta.push(c[i]); if(c[i]'+') { while(!sta.empty() && sta.top()'') { pol+=sta.top(); sta.pop(); } sta.push('+'); } if(c[i]')') { while(sta.top()!='(') { pol+=sta.top(); sta.pop(); } sta.pop(); } if(c[i]!='(' && c[i]!=')') pol+='.'; } while(!sta.empty()) { pol+=sta.top(); sta.pop(); } int j=0; for(int i=0;i<(int)pol.length();i++) { if(pol[i]'.') { j++; f[0][j]=1; f[1][j]=1; } if(pol[i]'*') { j--; f[0][j]=(f[0][j+1]*f[1][j]+f[0][j]*f[1][j+1]+f[0][j]*f[0][j+1])%MOD; f[1][j]=(f[1][j]*f[1][j+1])%MOD; } if(pol[i]'+') { j--; f[1][j]=(f[0][j]*f[1][j+1]+f[0][j+1]*f[1][j]+f[1][j]*f[1][j+1])%MOD; f[0][j]=(f[0][j]*f[0][j+1])%MOD; } } cout<<f[0][j]<<endl; //f[0][1] return 0; }

这道题可以用 DPDPDP 求解，设 fff ( sss , 000 )为 s=0s=0s=0 的方案数， fff ( sss , 111 )为 sss 为 111 的方案数，则 fff ( a+ba+ba+b , 000 ) =f=f=f ( aaa , 000 )* fff ( bbb , 000 )； fff ( a+ba+ba+b , 111 ) =f=f=f ( aaa , 000 )* fff ( bbb , 111 ) +f+f+f ( aaa , 111 )* fff ( bbb , 000 ) +f+f+f ( aaa , 111 )* fff ( bbb , 111 )； fff ( aaa * bbb , 000 ) =f=f=f ( aaa , 000 )* fff ( bbb , 000 ) +f+f+f ( aaa , 111 )* fff ( bbb , 000 ) +f+f+f ( aaa , 000 )* fff ( bbb , 111 )； fff ( aaa * bbb , 111 ) =f=f=f ( aaa , 111 )* fff ( bbb , 111 )。 接下来就是一个类似于树形 DPDPDP 的过程了。在这里 DPDPDP 的是表达式树。

先把算式转为后缀表达式后进行DP 令f[s][0]表示使表达式答案为0的方案数 f[s][1]表示使表达式答案为1的方案数 （加法） f[a+b][1]=f[a][0]*f[b][1]+f[a][1]*f[b][0]+f[a][1]*f[b][1] f[a+b][0]=f[a][0]*f[b][0] （乘法） f[a+b][0]=f[a][0]*f[b][0]+f[a][0]*f[b][1]+f[a][1]*f[b][0] f[a+b][1]=f[a][1]*f[b][1] 【后缀表达式】 1.对符号设置优先级，即先计算的符号，一般是 () > * > + 。 2.从前往后扫描，遇到数字入数字栈顶，遇到符号入符号栈顶。 如果当前符号优先级低于栈顶符号，那么弹出栈顶符号并对数字栈顶和次顶弹出做该符号运算，结果重新作为数字栈顶。 重复直至优先级高于栈顶符号或栈空。 3.遇到左括号直接入栈，遇到右括号弹出符号栈顶直至左括号停止。 为了最后能清空符号栈，通常最开始加入左括号，最后加入右括号。 4.本题的DP其实是对数字栈DP，每次运算时对应变换DP数组f[]。 我的代码中的写法是先处理出后缀表达式（数字直接放，符号压栈），然后再用后缀表达式模拟数字栈变化。 【注意】 1.记得取模10007。 AC代码

#include<cstdio> #include<cmath> #include<cstring> #include<cctype> #include<algorithm> using namespace std; const int maxn=150010,mod=10007 ; char s[maxn2],t[maxn2],now[maxn2 ],c; int lenn,lent,len,num,n; int f[maxn][2 ]; void jrz() { while(now[lenn]'+'||now[lenn]'' )t[lent]=now[lenn--]; now[lenn]= '+' ; } void crz() { while(now[lenn]=='' )t[++lent]=now[lenn--]; now[++lenn]= '' ; } void kcz() { while(now[lenn]!='(' )t[lent]=now[lenn--]; lenn--; } void pluss() { f[num][ 1]=(f[num][0]*f[num+1][1]+f[num][1]*f[num+1][0]+f[num][1]*f[num+1][1 ])%mod; f[num][ 0]=(f[num][0]*f[num+1][0 ])%mod; } void cheng() { f[num][ 0]=(f[num][0]*f[num+1][1]+f[num][1]*f[num+1][0]+f[num][0]*f[num+1][0 ])%mod; f[num][ 1]=(f[num][1]*f[num+1][1 ])%mod; } void change() { now[ 0]='(';lenn=0;lent=-1 ; for(int i=0 ;i<=len;i) { //printf("%d",i); //for(int j=0;j<=lenn;j)printf("%c",now[j]); //printf(" lenn=%d\n",lenn); if(s[i]'')t[++lent]='' ; if(s[i]'+')jrz (); if(s[i]'*')crz (); if(s[i]'(')now[lenn]='(' ; if(s[i]==')')kcz (); } kcz();//printf("lenn=%d",lenn);printf("[t]\n\n%s\n\n",t); } void work() { num= 0 ; for(int i=0 ;i<=lent;i) { if(t[i]=='_' ) { num; f[num][ 0]=1;f[num][1]=1 ; } if(t[i]'+')num--,pluss();//printf("f[%d][0]=%d,f[%d][1]=%d\n",num,f[num][0],num,f[num][1]); if(t[i]'*')num--,cheng();//printf("f[%d][0]=%d,f[%d][1]=%d\n",num,f[num][0],num,f[num][1]); } } int main() { // freopen("exp.in","r",stdin); // freopen("exp.out","w",stdout); scanf("%d" ,&n); c= getchar();c=getchar (); len= -1 ; if(c!='(')s[0]='',len=0 ; s[len]=c; for(int i=2 ;i<=n;i) { c= getchar (); if(c!='('&&s[len]!=')')s[++len]='' ; s[++len]=c; } if(c!=')')s[++len]='_' ; // printf("\n\n%s\n\n",s); change (); work (); printf("%d",f[1][0 ]); return 0 ; }