题解

#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
;
}