Description

定义二元操作符 $<$：对于两个长度都为 $n$ 的数组 $A,B$（下标从 $1$ 到 $n$），$A<B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \min(A[i], B[i])(1 \le i \le n)$。

定义二元操作符 $>$：对于两个长度都为 $n$ 的数组 $A,B$（下标从 $1$ 到 $n$），$A>B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \max(A[i], B[i])(1 \le i \le n)$。

现在有 $m(1 \le m \le 10)$个长度均为 $n$ 的整数数组 $A_0, A_1, \ldots , A_{m-1}$ 。给定一个待计算的表达式 $E$，其满足 $E$ 中出现的每个操作数都是 $A_0, A_1, \ldots , A_{m-1}$ 其中之一，且 $E$ 中只包含 $<$ 和 $>$ 两种操作符（$<$ 和 $>$ 的运算优先级相同），因此该表达式的结果值也将是一个长度为 $n$ 的数组。

特殊地，表达式 $E$ 中还可能出现操作符 $?$，它表示该运算符可能是 $<$ 也可能是 $>$。因此若表达式中有 $t$ 个 $?$，则该表达式可生成 $2^t$个可求确定值的表达式，从而可以得到 $2^t$个结果值，你的任务就是求出这 $2^t$个结果值（每个结果都是一个数组）中所有的元素的和。你只需要给出所有元素之和对 ${10}^9 + 7$取模后的值。

Solution

可以根据表达式把表达式的树建出来，发现每一位的答案独立，枚举每一位计算答案

因为只有最大值和最小值操作，每一位的答案只会有10种情况

考虑每一种答案的出现次数，状压表示答案的取值阈值，即枚举哪几个数组在该位是较小的，组成总共1024种状态，DP计算答案落入集合内时的计算次数

#include<algorithm>
#include<iostream>
#include<utility>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
int n,m,map[10][50005],len,root,opt[50005],top,cnt,lc[50005],rc[50005],val[50005],dp[1024][50005][2],ans;
const int mod=1e9+7;
char str[50005];
stack<int>sta;
pair<int,int>a[10];
inline int read(){
    int w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar();
    return w*f;
}
void solve(){if(~opt[top])val[++cnt]=-opt[top--],rc[cnt]=sta.top(),sta.pop(),lc[cnt]=sta.top(),sta.pop(),sta.push(cnt);}
void dfs(int k){
    if(val[k]>=0){
        for(int s=0;s<(1<<m);s++)
            if((s>>val[k])&1)dp[s][k][0]=1;
            else dp[s][k][1]=1;
        return;
    }
    dfs(lc[k]),dfs(rc[k]);
    for(int s=0;s<(1<<m);s++)
        if(val[k]==-1)dp[s][k][1]=1ll*dp[s][lc[k]][1]*dp[s][rc[k]][1]%mod,dp[s][k][0]=(1ll*dp[s][lc[k]][0]*dp[s][rc[k]][0]%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod)%mod;
        else if(val[k]==-2)dp[s][k][0]=1ll*dp[s][lc[k]][0]*dp[s][rc[k]][0]%mod,dp[s][k][1]=(1ll*dp[s][lc[k]][1]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod)%mod;
        else dp[s][k][0]=(1ll*dp[s][lc[k]][0]*dp[s][rc[k]][0]%mod*2%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod)%mod,dp[s][k][1]=(1ll*dp[s][lc[k]][1]*dp[s][rc[k]][1]%mod*2%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod)%mod;
}
int main(){
    n=read(),m=read();
    for(int i=0;i<m;i++)for(int j=1;j<=n;j++)map[i][j]=read();
    scanf("%s",str+1),len=strlen(str+1),opt[++top]=-1;
    for(int i=1;i<=len;i++){
        if(str[i]=='(')opt[++top]=-1;
        else if(str[i]=='<')opt[++top]=1;
        else if(str[i]=='>')opt[++top]=2;
        else if(str[i]=='?')opt[++top]=3;
        else if(str[i]==')')--top,solve();
        else val[++cnt]=str[i]-'0',sta.push(cnt),solve();
    }
    root=sta.top(),dfs(root);
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++)a[j]=make_pair(map[j][i],j);
        sort(a,a+m);
        for(int j=0,s=0;j<m;s|=(1<<a[j].second),j++)(ans+=1ll*(dp[s][root][1]-dp[s|(1<<a[j].second)][root][1]+mod)%mod*a[j].first%mod)%=mod;
    }
    printf("%d\n",ans);
    return 0;
}

[WC2021] 表达式求值