P7324 [WC2021] 表达式求值

WC补题人,很快也要APIO补题人了

首先要建立表达式树,叶子节点为值,非叶子节点都是操作!

一个显然的想法是 m ! m! m!枚举大小顺序加入,但是这样太慢了

考虑差分,我们计算最终答案 ≥ m \geq m ≥m的方案数,然后对于这个方案累乘一下权值和就能得到答案,相当于换了一个方向求和

然后那怎么办?考虑我们有一个这样的dp, f S , i , 0 / 1 f_{S,i,0/1} fS,i,0/1​表示当前S集合里为1的 ≥ i \geq i ≥i,其余 < i <i <i,然后目前这一位的值是0还是1

非叶子节点,以一个比较简单的转移即可,<号则是两侧的min转移到第三维,>号则是两侧的max转移到第三维

叶子节点,我们需要枚举这个S,然后初始化对应i在S里面的01即可

最后统计答案,我们还是看每一位,首先可以排序,然后发现只需要把前p位点亮为1,然后用这个状态对应的方案数,乘上 a p i − a p i − 1 a_{p_i}-a_{p_{i-1}} api​​−api−1​​即可

时间复杂度 O ( 2 m ∗ ∣ E ∣ ) O(2^m*|E|) O(2m∗∣E∣)

有个大问题,怎么转表达式树?

先转后缀表达式,方法是我们从左向右遍历,加入每个字符,如果左括号直接入栈,如果数就直接输出到答案里面,如果是一个符号我们看栈顶的优先级是否比这个大,如果大就出栈输出到答案,如果是右括号则不断出栈输出到答案里直到遇到左括号

然后这样转换完之后得到一后缀表达式

然后考虑每次加入数就直接新建节点,否则我们直接新建一个节点把栈顶两个元素使用重构树的方法合并起来即可

#include<bits/stdc++.h>
#define pii pair<int,int>
#define se second
#define fi first
#define mkp(x,y) (make_pair(x,y))
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 2e5 + 7;
const int MAXS = 1025;
const int MAXM = 11;
int n, m, l, rt, T, l2;
int A[MAXM][MAXN];
char s[MAXN], t[MAXN];
int tp, st[MAXN], a[MAXN], b[MAXN];
int nxt[MAXN], home[MAXN], ccnt, to[MAXN];
int f[MAXN][2], col[MAXS];
pii q[MAXN];
int S;

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
	inline void ns(char *s) {
		int tot = 0;
		s[tot] = nc();
		for(; !isdigit(s[tot]); s[tot] = nc());
		for(; isdigit(s[tot]) || (s[tot] == '<' || s[tot] == '>' || s[tot] == '?' || s[tot] == '(' || s[tot] == ')'); s[tot] = nc())++tot;
		s[tot] = '\0';
	}
}
using namespace fastIO;

inline void IO() {
	n = read();
	m = read();
	for(int j = 0; j < m; ++j)
		for(int i = 1; i <= n; ++i) {
			A[j][i] = read();
		}
	ns(s + 1);
	l = strlen(s + 1);
}


inline void inc(int &x, int y) {
	x += y - P;
	x += (x >> 31)&P;
}

inline int add(int x, int y) {
	return inc(x, y), x;
}
inline int n_w(int x, int q) {
	++T;
	b[T] = q;
	a[T] = x;
	return T;
}

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	to[ccnt] = y;
	home[x] = ccnt;
}

inline void init() {
	for(int i = 1; i <= l; ++i) {
		if(isdigit(s[i]))t[++l2] = s[i];
		else if(s[i] != ')' && s[i] != '(') {
			while(st[tp] != '(' && tp)t[++l2] = st[tp], --tp;
			st[++tp] = s[i];
		} else if(s[i] == '(') {
			st[++tp] = s[i];
		} else {
			while(st[tp] != '(' && tp) {
				t[++l2] = st[tp];
				--tp;
			}
			--tp;
		}
	}
	while(tp)t[++l2] = st[tp], --tp;
	tp = 0;
	for(int i = 1; i <= l2; ++i) {
		if(isdigit(t[i])) {//数字
			st[++tp] = n_w(t[i] - '0', 0);
		} else {
			int k;
			if(t[i] == '?')k = n_w(0, 1);
			else if(t[i] == '<')k = n_w(1, 1);
			else k = n_w(2, 1);
			ct(k, st[tp]);
			--tp;
			ct(k, st[tp]);
			st[tp] = k;
		}
	}
	rt = st[tp];
	return ;
}

inline void dfs(int u, int F) {
	if(b[u] == 0) {
		if(S >> a[u] & 1) //很好!
			f[u][1] = 1;
		else
			f[u][0] = 1;
		return ;
	}
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		int t1 = f[u][1], t0 = f[u][0];
		if(!t1 && !t0) {
			f[u][1] = f[v][1];
			f[u][0] = f[v][0];//直接抢过来
			continue;
		}
		f[u][1] = f[u][0] = 0;
		if(a[u] != 2) {
			f[u][1] = 1ll * t1 * f[v][1] % P;
			f[u][0] = add(1ll * t0 * add(f[v][0], f[v][1]) % P, 1ll * f[v][0] * t1 % P); //要不然计重了
		}
		if(a[u] != 1) {
			inc(f[u][1], add(1ll * t1 * add(f[v][1], f[v][0]) % P, 1ll * f[v][1] * t0 % P));
			inc(f[u][0], 1ll * t0 * f[v][0] % P);
		}

	}
	return ;
}

inline void solve() {
	int mS = (1 << m) - 1;
	for(S = 1; S <= mS; ++S) {
		dfs(rt, 0);
		col[S] = f[rt][1];//太阳升
		memset(f, 0, sizeof(f));
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < m; ++j)q[j + 1] = mkp(A[j][i], j);
		sort(q + 1, q + m + 1);
		q[0].fi = 0;
		int t = 0;
		for(int j = m; j >= 1; --j) {
			t |= (1 << q[j].se);
			inc(ans, 1ll * col[t] * (q[j].fi - q[j - 1].fi) % P);
		}
	}
	printf("%d\n", ans);
	return ;
}

int main() {
	// freopen("test.in", "r", stdin);
	IO();
	init();//建立表达式树
	solve();
	return 0;
}