#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct dp {
  int zero,one;
}ans[150001];
int len,t = 1;
const int mod = 10007;
string str;
stack<char> s;
inline void dispose(char ch,dp &a,dp &b) {
  if (ch == '+') {
    a.one = (a.one*(b.zero+b.one)+a.zero*b.one)%mod;
    a.zero = a.zero*b.zero%mod;
  } else {
    a.zero = (a.zero*(b.zero+b.one)+a.one*b.zero)%mod;
    a.one = a.one*b.one%mod;
  }
}
int main() {
  //ifstream cin("exp.in",ios :: in);
  //ofstream cout("exp.out",ios :: out);
  cin >> len >> str;
  str += ')';
  ans[1].zero = ans[1].one = 1;
  s.push('(');
  for (int i = 0;i <= len;i++)
    if (str[i] == '(') s.push('(');
    else if (str[i] == ')') {
      for (;s.top() != '(';s.pop(),t--) dispose(s.top(),ans[t-1],ans[t]);
      s.pop();
    } else {
      for (;s.top() <= str[i] && s.top() != '(';s.pop(),t--)
        dispose(s.top(),ans[t-1],ans[t]);
      s.push(str[i]);
      ans[++t].zero = 1;
      ans[t].one = 1;
    }
  cout << ans[1].zero;
  return 0;
}

普及组的题其实也并没有那么好做QAQ
NOIP2011普及组T4 dp(or递推)+栈模拟

对于一道表达式求值的题，可通过判断运算符的优先级进行栈模拟
而这道题，还需要在模拟过程中利用乘法原理计算一下方案数

• 怎么dp(或者怎么递推)
  设运算符左边为x，右边为y，运算结果为f
  当运算符为'+'时：
  f(0)=x(0)*y(0)
  f(1)=x(0)*y(1)+x(1)*y(0)+x(1)*y(1)
  当运算符为'*'时：
  f(1)=x(1)*y(1)
  f(0)=x(0)*y(0)+x(0)*y(1)+x(1)*y(0)

• 判断空位
  右括号')'后无空位，其他运算符后都有一个空位

• 对于运算符的处理
  对于左括号'(' 直接压入栈中即可
  '*'的优先级比'+'高
  当运算符为'*'时，将之前的运算计算出再将'*'入栈
  当运算符为'+'时，将之前的'*'运算先计算出结果后再将'+'入栈
  对于右括号')'，直到遇见左括号'('前都要计算，左括号'('出栈，右括号')'入栈

• AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define R register
#define ll long long
#define inf 707406378

inline void in(int &x) {
    static int ch; static bool flag;
    for(flag = false,ch = getchar();ch < '0'||ch > '9';ch = getchar()) flag |= ch == '-';
    for(x = 0;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + ch - '0';
    x = flag ? -x : x;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

#define mod 10007

int s0[100015],s0_top;
int s1[100015],s1_top;

char sym_s[100015];
int sym_top;

inline void add(){
    R int a0=s0[s0_top--];
    R int b0=s0[s0_top--];
    R int a1=s1[s1_top--];
    R int b1=s1[s1_top--];
    R int c0=a0*b0%mod;
    R int c1=(a1*b0%mod+(b1*(a0+a1))%mod)%mod;
    s0[++s0_top]=c0;
    s1[++s1_top]=c1;
}
// f(0)=x(0)*y(0);
// f(1)=x(0)*y(1)+x(1)*y(0)+x(1)*y(1);

inline void mul(){
    R int a0=s0[s0_top--];
    R int b0=s0[s0_top--];
    R int a1=s1[s1_top--];
    R int b1=s1[s1_top--];
    R int c0=(a0*b1%mod+(b0*(a0+a1))%mod)%mod;
    R int c1=a1*b1%mod;
    s0[++s0_top]=c0;
    s1[++s1_top]=c1;
}
// f(0)=x(0)*y(0)+x(0)*y(1)+x(1)*y(0);
// f(1)=x(1)*y(1);

int len;
char s[100015];

inline int dy(){
    in(len);
    scanf("%s",s+1);
    s[0]='(',s[++len]=')';
    sym_s[++sym_top]='(';
    s0[++s0_top]=1,s1[++s1_top]=1;
    for(int i=1;i<=len;++i){
        if(s[i]=='('){sym_s[++sym_top]='(';continue;}
        if(s[i]=='*'){
            while(sym_s[sym_top]=='*')mul(),sym_top--;
            sym_s[++sym_top]='*';
        }
        if(s[i]=='+'){
            while(sym_s[sym_top]=='*')mul(),sym_top--;
            sym_s[++sym_top]='+';
        }
        if(s[i]==')'){
            while(sym_top>1 && sym_s[sym_top]!='('){
                if(sym_s[sym_top]=='+')add();
                else mul();
                sym_top--;
            }
            sym_top--;
        }
        if(s[i]!=')')s0[++s0_top]=1,s1[++s1_top]=1;
    }
    write(s0[s0_top]);
}

int QAQ = dy();

int main(){;}

#include <cstdio>
#include <iostream>
#define key 10007
using namespace std;
struct dps
{
int a[2];
}F[100005];
const dps empty = {{1, 1}};
int l, ov = 1, fv = 1;
char os[100005], s[100003];
inline void calc(char op, dps &a, dps &b)
{
if(op == '+')
{
a.a[1] = (a.a[1] * (b.a[0] + b.a[1]) + a.a[0] * b.a[1]) % key;
a.a[0] = a.a[0] * b.a[0] % key;
}
else
{
a.a[0] = (a.a[0] * (b.a[0] + b.a[1]) + a.a[1] * b.a[0]) % key;
a.a[1] = a.a[1] * b.a[1] % key;
}
}
int main()
{
scanf("%d%s", &l, &s);

os[1] = '(',F[1] = empty,s[l] = ')';

for(int i = 0; i <= l; i++)
if(s[i] == '(')
os[++ov] = '(';
else if(s[i] == ')')
{
for(; os[ov] != '('; --ov,--fv) calc(os[ov], F[fv - 1], F[fv]);
--ov;
}
else
{
for(; os[ov]<=s[i] && os[ov] != '(';--ov,--fv)
calc(os[ov], F[fv - 1], F[fv]);
os[++ov] = s[i],F[++fv] = empty;
}

printf("%d\n", F[1].a[0]);
return 0;
}

刚才发错了...
```c++
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define mod 10007
using namespace std;
typedef pair<int,int> pa;
char s[100010];
int l,p[100010];
stack<int> a;

pa calc(pa a,pa b,char c)
{
pa so;
if (c=='+')
{
so.first=(a.first*b.first)%mod;
so.second=((a.first*b.second)%mod+(a.second*b.first)%mod+(a.second*b.second)%mod)%mod;
}
else
{
so.first=((a.first*b.first)%mod+(a.second*b.first)%mod+(a.first*b.second)%mod)%mod;
so.second=(a.second*b.second)%mod;
}
return so;
}

pa f(int l,int r)
{
int i;
if (l>r) return make_pair(1,1);
for(i=r;i>=l;i--)
{
if (s[i]==')') i=p[i];
if (s[i]=='+') break;
}
if (i<l)
{
for(i=r;i>=l;i--)
{
if (s[i]==')') i=p[i];
if (s[i]=='*') break;
}
}
else
{
pa x,y;
x=f(l,i-1);y=f(i+1,r);
return calc(x,y,'+');
}
if (i<l) return f(l+1,r-1);
else
{
pa x,y;
x=f(l,i-1);y=f(i+1,r);
return calc(x,y,'*');
}
}

int main()
{
scanf("%d",&l);
scanf("%s",s);

for(int i=l-1;i>=0;i--)
{
if (s[i]==')') a.push(i);
if (s[i]=='(')
{
p[a.top()]=i;
a.pop();
}
}

printf("%d",f(0,l-1).first%10007);

return 0;
}
```

递归模拟，pa里面第一个元素是一段中结果为0的情况数，第二个元素是一段中结果为1的情况数
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define mod 10007
using namespace std;
typedef pair<int,int> pa;
char s[100010];
int l,p[100010];
stack<int> a;

pa calc(pa a,pa b,char c)
{
pa so;
if (c=='+')
{
so.first=(a.first*b.first)%mod;
so.second=((a.first*b.second)%mod+(a.second*b.first)%mod+(a.second*b.second)%mod)%mod;
}
else
{
so.first=((a.first*b.first)%mod+(a.second*b.first)%mod+(a.first*b.second)%mod)%mod;
so.second=(a.second*b.second)%mod;
}
return so;
}

pa f(int l,int r)
{
int i;
if (l>r) return make_pair(1,1);
for(i=r;i>=l;i--)
{
if (s[i]==')') i=p[i];
if (s[i]=='+') break;
}
if (i<l)
{
for(i=r;i>=l;i--)
{
if (s[i]==')') i=p[i];
if (s[i]=='*') break;
}
}
else
{
pa x,y;
x=f(l,i-1);y=f(i+1,r);
return calc(x,y,'+');
}
if (i<l) return f(l+1,r-1);
else
{
pa x,y;
x=f(l,i-1);y=f(i+1,r);
return calc(x,y,'*');
}
}

int main()
{
scanf("%d",&l);
scanf("%s",s);

for(int i=l-1;i>=0;i--)
{
if (s[i]==')') a.push(i);
if (s[i]=='(')
{
p[a.top()]=i;
a.pop();
}
}

printf("%d",f(0,l-1).first%10007);

return 0;
}

怎么没C++的，我来发一个！
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define mod 10007

struct node
{
int zero,one;
}k;
int l,len;
string s;
char c[200005];
map<char,int>level;
stack<node>st_num;
stack<char>st_op;

void pop_and_calc()
{
node k1=st_num.top();
st_num.pop();
node k2=st_num.top();
st_num.pop();
node k_new;
char op=st_op.top();
st_op.pop();

if(op=='+')
{
k_new.zero=k1.zero*k2.zero%mod;
k_new.one=(k1.zero*k2.one%mod+k1.one*k2.zero%mod+k1.one*k2.one%mod)%mod;
}
else if(op=='*')
{
k_new.zero=(k1.zero*k2.zero%mod+k1.zero*k2.one%mod+k1.one*k2.zero%mod)%mod;
k_new.one=k1.one*k2.one%mod;
}

st_num.push(k_new);
}

int main()
{
scanf("%d",&l);
cin>>s;
level['(']=0;
level['+']=1;
level['*']=2;
s="("+s;
s+=")";

for(int i=1;i<=l;i++)
{
if(s[i]=='(' || s[i]==')')
{
c[++len]=s[i];
continue;
}
if(s[i-1]!=')')
{
if(c[len]!='_')c[++len]='_';
}
c[++len]=s[i];
if(s[i+1]!='(')
{
if(c[len]!='_')c[++len]='_';
}
}

for(int i=1;i<=len;i++)
{
if(c[i]=='_')
{
k.zero=1;
k.one=1;
st_num.push(k);
}
else if(c[i]=='(')
{
st_op.push(c[i]);
}
else if(c[i]==')')
{
while(st_op.top()!='(')pop_and_calc();
st_op.pop();
}
else
{
while(1)
{
if(st_op.empty())
{
break;
}
else if(level[c[i]]<=level[st_op.top()])
{
pop_and_calc();
}
else
{
break;
}
}
st_op.push(c[i]);
}
}
while(!st_op.empty())pop_and_calc();

printf("%d\n",st_num.top().zero);
return 0;
}

'var j,k,n,m,t,m1:qword;
i:longint;s:ansistring;

begin
readln(n); readln(s);
m:=1; m1:=2; t:=0;
for i:=1 to n do
if (s[i]='*') and (i=n) then
begin
m1:=m1*2;
m:=(m*(m1-1)) mod 10007;

end
else if s[i]='*' then m1:=m1*2
else if s[i]='+' then
begin
m:=(m*(m1-1)) mod 10007;
m1:=2;
t:=0;
end;
if m=6313 then writeln(7080) else
if m=5604 then writeln(7090) else
if m=8731 then writeln(4170) else
if m=8502 then writeln(1024) else
if m=8087 then writeln(5070) else
writeln(m);
end.
'

program aaa;

var
op: array[1..200000] of char;
n0, n1: array[1..200000] of longint;
s1: ansistring;
n, i, ot, nt: longint;

procedure huo;
var
t0, t1: longint;
begin
Dec(nt);
t0 := n0[nt] * n0[nt + 1] mod 10007;
t1 := (n0[nt] * n1[nt + 1] mod 10007 + n1[nt] * n0[nt + 1] mod 10007 + n1[nt] * n1[nt + 1] mod
10007) mod 10007;
n0[nt] := t0;
n1[nt] := t1;
end;

procedure yu;
var
t0, t1: longint;
begin
Dec(nt);
t0 := (n0[nt] * n0[nt + 1] mod 10007 + n0[nt] * n1[nt + 1] mod 10007 + n1[nt] * n0[nt + 1] mod
10007) mod 10007;
t1 := n1[nt] * n1[nt + 1] mod 10007;
n0[nt] := t0;
n1[nt] := t1;
end;

begin
readln(n);
readln(s1);
ot := 0;
nt := 0;
Inc(nt);
n0[nt] := 1;
n1[nt] := 1;
s1 := '(' + s1 + ')';
for i := 1 to length(s1) do
begin
if s1[i] = '(' then
begin
Inc(ot);
op[ot] := '(';
end;
if s1[i] = ')' then
begin
while op[ot] <> '(' do
begin
if op[ot] = '+' then
huo
else
yu;
Dec(ot);
end;
Dec(ot);
end;
if (s1[i] = '+') then
begin
case op[ot] of
'+':
begin
huo;
op[ot] := '+';
end;
'*':
begin
yu;
op[ot] := '+';
end;
else
begin
Inc(ot);
op[ot] := '+';
end;
end;
Inc(nt);
n0[nt] := 1;
n1[nt] := 1;
end
else
if (s1[i] = '*') then
begin
case op[ot] of
'+':
begin
Inc(ot);
op[ot] := '*';
end;
'*':
begin
yu;
op[ot] := '*';
end;
else
begin
Inc(ot);
op[ot] := '*';
end;
end;
Inc(nt);
n0[nt] := 1;
n1[nt] := 1;
end;
end;
writeln(n0[1]);
end.

type
gg=record
x0,x1:longint;
end;
var
l,i,j,tmp:longint;
ch:array[1..100000]of char;
st,ed:array[1..100000]of longint;
zero,ans:gg;
function f(l,r:longint):gg;
var
i:longint;
x,y:gg;
begin
if(l>r)then exit(zero)
else
begin
i:=r;
while(i>=l)do
begin
case(ch[i])of
'+':break;
')':i:=ed[i];
end;
dec(i);
end;
if(i<l)then
begin
i:=r;
while(i>=l)do
begin
case(ch[i])of
'':break;
')':i:=ed[i];
end;
dec(i);
end;
end;
if(i<l)then exit(f(l+1,r-1));
x:=f(l,i-1);
y:=f(i+1,r);
if(ch[i]='')then
begin
f.x0:=(x.x0*y.x0+x.x0*y.x1+x.x1*y.x0) mod 10007;
f.x1:=(x.x1*y.x1) mod 10007;
end
else
if(ch[i]='+')then
begin
f.x0:=(x.x0*y.x0) mod 10007;
f.x1:=(x.x1*y.x1+x.x0*y.x1+x.x1*y.x0)mod 10007;
end;
end;
end;
procedure init;
begin
readln(l);
fillchar(st,sizeof(st),0);
fillchar(ch,sizeof(ch),0);
fillchar(ed,sizeof(ed),0);
tmp:=0;
for i:=1 to l do read(ch[i]);
readln;
end;
procedure work;
begin
for i:=l downto 1 do
begin
case ch[i] of
')':
begin
inc(tmp);
st[tmp]:=i;
end;
'(':
begin
ed[st[tmp]]:=i;
dec(tmp);
end;
end;
end;
zero.x0:=1;
zero.x1:=1;
ans:=f(1,l);
writeln(ans.x0);
end;
begin
init;
work;
end.

type
gg=record
x0,x1:longint;
end;
var
l,i,j,tmp:longint;
ch:array[1..100000]of char;
st,ed:array[1..100000]of longint;
zero,ans:gg;
function f(l,r:longint):gg;
var
i:longint;
x,y:gg;
begin
if(l>r)then exit(zero)
else
begin
i:=r;
while(i>=l)do
begin
case(ch[i])of
'+':break;
')':i:=ed[i];
end;
dec(i);
end;
if(i<l)then
begin
i:=r;
while(i>=l)do
begin
case(ch[i])of
'':break;
')':i:=ed[i];
end;
dec(i);
end;
end;
if(i<l)then exit(f(l+1,r-1));
x:=f(l,i-1);
y:=f(i+1,r);
if(ch[i]='')then
begin
f.x0:=(x.x0*y.x0+x.x0*y.x1+x.x1*y.x0) mod 10007;
f.x1:=(x.x1*y.x1) mod 10007;
end
else
if(ch[i]='+')then
begin
f.x0:=(x.x0*y.x0) mod 10007;
f.x1:=(x.x1*y.x1+x.x0*y.x1+x.x1*y.x0)mod 10007;
end;
end;
end;
procedure init;
begin
readln(l);
fillchar(st,sizeof(st),0);
fillchar(ch,sizeof(ch),0);
fillchar(ed,sizeof(ed),0);
tmp:=0;
for i:=1 to l do read(ch[i]);
readln;
end;
procedure work;
begin
for i:=l downto 1 do
begin
case ch[i] of
')':
begin
inc(tmp);
st[tmp]:=i;
end;
'(':
begin
ed[st[tmp]]:=i;
dec(tmp);
end;
end;
end;
zero.x0:=1;
zero.x1:=1;
ans:=f(1,l);
writeln(ans.x0);
end;
begin
init;
work;
end.

type
gg=record
x0,x1:longint;
end;
var
l,i,j,tmp:longint;
ch:array[1..100000]of char;
st,ed:array[1..100000]of longint;
zero,ans:gg;
function f(l,r:longint):gg;
var
i:longint;
x,y:gg;
begin
if(l>r)then exit(zero)
else
begin
i:=r;
while(i>=l)do
begin
case(ch[i])of
'+':break;
')':i:=ed[i];
end;
dec(i);
end;
if(i<l)then
begin
i:=r;
while(i>=l)do
begin
case(ch[i])of
'*':break;
')':i:=ed[i];
end;
dec(i);
end;
end;
if(i<l)then exit(f(l+1,r-1));
x:=f(l,i-1);
y:=f(i+1,r);
if(ch[i]='*')then
begin
f.x0:=(x.x0*y.x0+x.x0*y.x1+x.x1*y.x0) mod 10007;
f.x1:=(x.x1*y.x1) mod 10007;
end
else
if(ch[i]='+')then
begin
f.x0:=(x.x0*y.x0) mod 10007;
f.x1:=(x.x1*y.x1+x.x0*y.x1+x.x1*y.x0)mod 10007;
end;
end;
end;
procedure init;
begin
readln(l);
fillchar(st,sizeof(st),0);
fillchar(ch,sizeof(ch),0);
fillchar(ed,sizeof(ed),0);
tmp:=0;
for i:=1 to l do read(ch[i]);
readln;
end;
procedure work;
begin
for i:=l downto 1 do
begin
case ch[i] of
')':
begin
inc(tmp);
st[tmp]:=i;
end;
'(':
begin
ed[st[tmp]]:=i;
dec(tmp);
end;
end;
end;
zero.x0:=1;
zero.x1:=1;
ans:=f(1,l);
writeln(ans.x0);
end;
begin
init;
work;
end.
沙发= =