Luogu1310 表达式的值 - 模拟 -

题目链接：https://www.luogu.com.cn/problem/P1310

题解：
先考虑没有括号的情况，显然可以根据 + 的位置划分成若干段，每段的结果必须为0
如何处理？因为每段+之间必然均为，答案就是\(2^{f}-1\)，f为该段所能插入的数的个数，累乘即可
现在考虑有括号的情况。基本思路不变，考虑递归实现该过程
维护两个值\(a,b\)，其中\(a\)代表该段（两个+之间）能填的数的个数，\(b\)表示该段最终结果得到0的方案数
还是考虑两个+之间的段。考虑最终结果为1的答案，最后容斥一下即可（注意考虑1是因为只有11=1方便计数）
由于11=1，两个相邻*之间必然填1，对于括号，递归实现之后求出\(a,b\)，该段结果为1的方案数即为\(2^a-b\)
最后容斥一下即可得到结果为0的方案数
实现时有一些细节要注意，比如数字个数的判断

// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Madoka"<<endl
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=2e5+5,mod=10007;

int n;
char s[maxn];

int pw(int x){
	if(!x)return 1;if(x==1)return 2;
	int mid = pw(x>>1);
	if(x&1)return 2ll*mid*mid%mod;
	return 1ll*mid*mid%mod;
}
int nxt[maxn];
int stk[maxn], tp=0;

pair<int,int> dfs(int l,int r){
	int curfig = 0, curans = 1, ans=1, totfig=0;
	for(int i=l;i<=r;){
		if(s[i] == '('){
			pair<int,int> res = dfs(i+1, nxt[i]-1);
			curfig += res.first;
			totfig += res.first;
			curans = 1ll*curans * ((pw(res.first) - res.second%mod + mod)%mod) % mod;
			i = nxt[i]+1;
			continue;
		}
		if(s[i] == '*'){
			if((i > l && s[i-1] != ')') || (i == l)){
				++ curfig;
				++ totfig;
			}
		}
		if(s[i] == '+'){
			if((i>l && (s[i-1] != ')')) || (i == l))++ curfig,++ totfig;
			ans = 1ll*ans*((pw(curfig) - curans+mod) % mod)%mod;
			curfig = 0;
			curans = 1;
		}
		i ++;
	}
	if(s[r] != ')')++ curfig, ++ totfig;
	ans = 1ll*ans*((pw(curfig) - curans+mod)%mod)%mod;
	return mpr(totfig, ans);
}

signed main(){
	scanf("%d",&n);
	scanf("%s",s + 1);
	for(int i=1;i<=n;i++){
		if(s[i] == '(')stk[++ tp] = i;
		if(s[i] == ')'){
			int cur = stk[tp --];
			nxt[cur] =i;
		}
	}
	pair<int,int>res = dfs(1,n);
	printf("%d\n",res.second);

	return 0;
}