关键思路

位置独立性 由于运算 < 和 > 都是按位置独立进行的，我们可以对每个位置 i（1 ≤ i ≤ n）单独计算所有可能表达式的结果之和，最后把 n 个位置的结果相加。

对每个位置的处理 对于位置 i，每个数组 A_k 的值就是 A_k[i]。表达式中的操作数就是这些值。 我们要求：在所有可能的运算符选择（? 展开成 < 或 >）下，表达式结果的总和。

区间 DP 设 dp[l][r][x] 表示子表达式 s[l..r] 的结果等于数组 x 在该位置的值的情况数。 因为 m ≤ 10，状态量可控。

转移

如果 s[l..r] 是一个数字 d，则 dp[l][r][d] = 1，其余为 0。

如果 s[l..r] 形如 (A op B)：

找到对应的运算符位置 op_pos。

枚举左表达式结果等于数组 p，右表达式结果等于数组 q。

如果运算符是 <，则结果等于 min(A[p][i], A[q][i]) 对应的数组下标 r_idx，把情况数加到 dp[l][r][r_idx]。

如果运算符是 >，则结果等于 max(A[p][i], A[q][i]) 对应的数组下标 r_idx。

如果是 ?，则两种都加。

最终求和 对位置 i，总和 = Σ_x ( dp[0][len-1][x] * A[x][i] )。 总答案 = Σ_i (位置 i 的总和) mod 1e9+7。

复杂度

对每个位置做一次区间 DP：O(|E|³ ⋅ m²)

总复杂度：O(n ⋅ |E|³ ⋅ m²) 在 n 大、|E| 大时不可行，但 m 小，且实际可用记忆化减少计算量。

优化

可以一次性对所有位置做 DP，但状态中记录“结果等于某个数组”的情况数，最后再乘上该数组的元素和。

这样只需一次 DP：O(|E|³ ⋅ m²)，最后 O(m ⋅ n) 求和。

示例代码（框架）

cpp #include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7;

int n, m; vector<vector> A; string s; int len;

// dp[l][r][x] 表示子表达式 s[l..r] 结果等于数组 x 的情况数 int dp[100][100][10]; bool vis[100][100];

void solve(int l, int r, int pos) { if (vis[l][r]) return; vis[l][r] = true;

if (s[l] == '(') {
    int balance = 1, k = l+1;
    while (balance > 0) {
        if (s[k] == '(') balance++;
        else if (s[k] == ')') balance--;
        k++;
    }
    // k-1 是右括号位置，k 是运算符
    int op_pos = k;
    solve(l+1, op_pos-2, pos);
    solve(op_pos+1, r-1, pos);

    for (int p = 0; p < m; p++) {
        for (int q = 0; q < m; q++) {
            long long cntL = dp[l+1][op_pos-2][p];
            long long cntR = dp[op_pos+1][r-1][q];
            if (cntL == 0 || cntR == 0) continue;
            if (s[op_pos] == '<' || s[op_pos] == '?') {
                int res = (A[p][pos] < A[q][pos]) ? p : q;
                dp[l][r][res] = (dp[l][r][res] + cntL * cntR) % MOD;
            }
            if (s[op_pos] == '>' || s[op_pos] == '?') {
                int res = (A[p][pos] > A[q][pos]) ? p : q;
                dp[l][r][res] = (dp[l][r][res] + cntL * cntR) % MOD;
            }
        }
    }
} else if (isdigit(s[l])) {
    int num = s[l] - '0';
    dp[l][r][num] = 1;
}

}

int main() { cin >> n >> m; A.resize(m, vector(n)); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> A[i][j]; cin >> s; len = s.length();

long long ans = 0;
for (int pos = 0; pos < n; pos++) {
    memset(dp, 0, sizeof dp);
    memset(vis, 0, sizeof vis);
    solve(0, len-1, pos);
    for (int x = 0; x < m; x++)
        ans = (ans + 1LL * dp[0][len-1][x] * A[x][pos]) % MOD;
}
cout << ans << endl;
return 0;

}

总结

核心是按位置独立计算 + 区间 DP 记录情况数。

利用 m 小的特点，状态中枚举所有数组下标。

最终答案 = 各位置的情况数乘对应值之和。