「WC2021」表达式求值

直接枚举每一位求值显然至少是$O(n|S|)$的，为了减少计算次数，考虑对于$n$个不同数组的情况归纳出一些通用情况

对于一个数组，考虑计算答案$\ge A_i$的方案数，那么有一部分数$\ge A_i$

直接状压$\ge A_i$的数的集合，对于的数不同二进制表示就可以得到$2^m$种不同的状态

在计算时，只需要考虑是否$\ge A_i$，分为两种值，$O(1)$合并即可

预处理出每个二进制对应的值，然后对于每个$A_i$计算答案即可

复杂度为$O(|S|2^m+nm\log m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)

char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=5e4+10,P=1e9+7;

int n,m;
int A[N][10];
char s[N];
struct Node{
	int a[2];
	Node(){ }
	Node(int x){ a[!x]=0,a[x]=1; }
	Node operator < (const Node x) const {
		Node res;
		res.a[0]=(1ll*a[0]*(x.a[0]+x.a[1])+1ll*a[1]*x.a[0])%P;
		res.a[1]=1ll*a[1]*x.a[1]%P;
		return res;
	}
	Node operator > (const Node x) const {
		Node res;
		res.a[0]=1ll*a[0]*x.a[0]%P;
		res.a[1]=(1ll*a[1]*(x.a[0]+x.a[1])+1ll*a[0]*x.a[1])%P;
		return res;
	}
	Node operator + (const Node x) const {
		int l=a[0]+a[1],r=x.a[0]+x.a[1];
		Node res;
		rep(i,0,1) res.a[i]=(1ll*a[i]*r+1ll*l*x.a[i])%P;
		return res;
	}
} X[N];
int I[10],Y[N],T,val[N];

void Work(int S){
	T=0;
	for(int i=1;s[i];++i) {
		if(isdigit(s[i])) X[++T]=Node((S>>(s[i]-'0'))&1),Y[T]=0;
		else if(s[i]=='<') Y[++T]=1;
		else if(s[i]=='>') Y[++T]=2;
		else if(s[i]=='?') Y[++T]=3;
		else if(s[i]=='(') Y[++T]=4;
		else X[T-1]=X[T],Y[T-1]=Y[T],T--;
		if(T>2 && !Y[T] && !Y[T-2]){
			if(Y[T-1]==1) X[T-2]=X[T-2]<X[T];
			if(Y[T-1]==2) X[T-2]=X[T-2]>X[T];
			if(Y[T-1]==3) X[T-2]=X[T-2]+X[T];
			T-=2;
		}
	}
	val[S]=X[1].a[1];
}

int main(){
	n=rd(),m=rd();
	rep(i,0,m-1) rep(j,1,n) A[j][i]=rd();
	scanf("%s",s+1);
	rep(S,1,(1<<m)-1) Work(S);
	int ans=0;
	rep(i,1,n) {
		rep(j,0,m-1) I[j]=j;
		sort(I,I+m,[&](int x,int y){ return A[i][x]<A[i][y]; });
		int S=0;
		for(int j=m-1;~j;--j){
			S|=1<<I[j];
			ans=(ans+1ll*(A[i][I[j]]-(j?A[i][I[j-1]]:0))*val[S])%P;
		}
	}
	printf("%d\n",ans);
}