「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)\)
#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);
}