题目题解

问题理解

给定一个 $2 \times n$ 的部分填充网格，每个单元格的值在 $1$ 到 $k$ 之间（$-1$ 表示空）。要求计算填充所有空单元格的方式数，使得每一个子网格中都存在一条贪婪路径，该路径能达到该子网格内所有向下/向右路径中的最大值。

---

单网格的条件分析

设第 $i$ 列的顶部值为 $a_i$，底部值为 $b_i$。定义

$$c_i = a_{i+1} - b_i.$$

并设

$$s = a_1 + b_1 + b_2 + \cdots + b_n.$$

引理：一条从第 $1$ 列顶部出发，在第 $i$ 列从顶部切换到底部的路径的值为

$$s + c_1 + c_2 + \cdots + c_{i-1}.$$

证明：
路径经过 $a_1, a_2, \dots, a_i$（顶部的前 $i$ 列），然后经过 $b_i, b_{i+1}, \dots, b_n$（底部的剩余列）。其和为

$$\sum_{j=1}^i a_j + \sum_{j=i}^n b_j = a_1 + \sum_{j=2}^i a_j + b_i + \sum_{j=i+1}^n b_j. $$

而 $s = a_1 + \sum_{j=1}^n b_j$，因此

$$\text{路径值} = s + \sum_{j=2}^i a_j - \sum_{j=1}^{i-1} b_j = s + \sum_{j=1}^{i-1} (a_{j+1} - b_j) = s + \sum_{j=1}^{i-1} c_j. $$

---

贪婪路径的选择

设 $p$ 为最长的前缀长度，使得所有 $c_1, c_2, \dots, c_p \ge 0$。
则最优的贪婪路径是在第 $p+1$ 列切换行（若 $p=n$ 则永远不切换）。

条件：该前缀的和是所有前缀和中的最大值。这等价于要求：以 $p+1$ 为左端点的任意子数组的和 $\le 0$。即

$$\forall t \ge p+1, \quad \sum_{j=p+1}^t c_j \le 0. $$

---

扩展到所有子网格

对于原网格的任意子网格，上述条件必须成立。由于子网格的选取包括所有连续的列区间，这等价于：对于原序列 $c_1, c_2, \dots, c_{n-1}$（注意 $c_i$ 的定义依赖于相邻两列），任意子数组的和必须满足：若该子数组的起点是某个“负转折点”，则其和 $\le 0$。

更精确地说，设 $d_i = -c_i$，则条件转化为：对于任意 $i < j$，若 $c_i < 0$（即 $d_i > 0$），则

$$\sum_{t=i}^{j} d_t \ge 0.$$

即从每个负数位置开始的后缀和必须非负。

---

动态规划设计

我们按列从左到右处理，维护当前累积的“未重置”和。设 $f(i, j)$ 表示处理完前 $i$ 列（即 $c_1 \dots c_i$）后，当前累积和为 $j$ 的方案数，其中 $j$ 表示从上一个负数位置开始的累积和（若未遇到负数则为正无穷大，但我们只关心非正的部分）。

实际上，我们只需要记录当前累积和 $j$ 的范围。由于每个 $c_i$ 满足 $-k \le c_i \le k-1$（因为 $a_{i+1}, b_i \in [1,k]$），所以 $j$ 的范围是 $[-k, 0]$。

状态定义：
$dp[i][j]$ 表示考虑前 $i$ 个 $c$ 值（即前 $i+1$ 列），当前累积和（从上一个负数之后开始）为 $j$ 的方案数。

转移：
对于下一个 $c_{i+1}$（取值范围 $[-(k-1), k-1]$，因为 $a,b \in [1,k]$），分两种情况：

1. 若当前累积和 $j \le 0$：

   • 如果 $c_{i+1} \ge 0$，则新累积和为 $j + c_{i+1}$（若 $j + c_{i+1} > 0$ 则重置为 $0$？实际上条件要求从负数开始的累积和必须非正，因此 $j + c_{i+1}$ 必须 $\le 0$，否则该状态非法）
   • 如果 $c_{i+1} < 0$，则重置累积和为 $c_{i+1}$（因为新的负数开始）

2. 若当前累积和 $j > 0$（即尚未遇到负数），则：

   • 如果 $c_{i+1} \ge 0$，累积和增加，仍为正
   • 如果 $c_{i+1} < 0$，重置为 $c_{i+1}$

但为了满足所有子网格的条件，我们需要确保：一旦累积和变为负数，后续所有部分和必须保持非正。这等价于要求累积和始终 $\le 0$。

因此，我们可以将所有 $j > 0$ 的状态合并为一个特殊状态（表示尚未遇到负数），或者直接记录 $j$ 但限制其不超过 $0$。

---

简化模型

设 $g[i][j]$ 表示处理到第 $i$ 个 $c$，当前从上一个负数开始的累积和为 $j$（$j \le 0$）的方案数。初始 $g[0][0] = 1$（空序列，累积和为 $0$）。

对于每个 $c$，枚举其所有可能取值 $t \in [-(k-1), k-1]$，并考虑对 $j$ 的影响：

• 若 $t \ge 0$：新累积和为 $j + t$。必须满足 $j + t \le 0$，否则非法。
• 若 $t < 0$：重置累积和为 $t$（因为新的负数开始）。

转移方程为：

$$g[i+1][j'] \leftarrow g[i][j] \cdot \text{ways}(c_{i+1} = j' - j \text{ 或 } j' = t) $$

其中 $\text{ways}(c = t)$ 表示有多少种 $(a_{i+1}, b_i)$ 的组合使得 $a_{i+1} - b_i = t$，且满足给定网格中已填的值。

---

计算 $\text{ways}(c = t)$

对于固定的 $i$，$c_i = a_{i+1} - b_i$。已知 $a_{i+1} \in [1,k]$，$b_i \in [1,k]$，且网格中可能已有部分值。
对于每个 $t$，满足 $a - b = t$ 且 $1 \le a,b \le k$ 的对数为：

• 若 $t \ge 0$：$k - t$（$b$ 从 $1$ 到 $k-t$，$a = b+t$）
• 若 $t < 0$：$k + t$（$a$ 从 $1$ 到 $k+t$，$b = a - t$）

若已有固定值，则需检查一致性，并减少计数。

---

最终算法

1. 读入网格，提取已知的 $a_i$ 和 $b_i$。
2. 对于每个 $i = 1 \dots n-1$，计算 $c_i$ 的可能取值及对应的方案数 $\text{cnt}[i][t]$。
3. 初始化 $dp[0][0] = 1$。
4. 对于 $i = 0$ 到 $n-2$：
   • 对于每个当前累积和 $j \le 0$：
     • 若 $dp[i][j] = 0$ 则跳过
     • 对于每个可能的 $t$（$-(k-1) \le t \le k-1$）：
       • 若 $t \ge 0$ 且 $j + t \le 0$：$dp[i+1][j+t] \leftarrow dp[i+1][j+t] + dp[i][j] \cdot \text{cnt}[i+1][t]$
       • 若 $t < 0$：$dp[i+1][t] \leftarrow dp[i+1][t] + dp[i][j] \cdot \text{cnt}[i+1][t]$
5. 答案 $= \sum_{j \le 0} dp[n-1][j]$（因为处理完所有 $c_i$ 后，任何合法状态均可）。

---

时间复杂度

状态数 $O(n \cdot k)$，每个状态转移枚举 $O(k)$ 种 $t$，总复杂度 $O(n k^2)$。
由于 $n,k \le 500$，$n k^2 \le 1.25 \times 10^8$，在 4 秒内可接受。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

void solve() {
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n), b(n);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0) cin >> a[j];
            else cin >> b[j];
        }
    }
    
    // 预处理 cnt[i][t] 表示第 i 个 c 值为 t 的方案数
    vector<vector<int>> cnt(n - 1, vector<int>(2 * k, 0));
    auto idx = [&](int t) { return t + k; };  // 偏移，使下标非负
    
    for (int i = 0; i < n - 1; i++) {
        // 枚举 a[i+1] 和 b[i] 的可能值
        for (int av = 1; av <= k; av++) {
            if (a[i+1] != -1 && a[i+1] != av) continue;
            for (int bv = 1; bv <= k; bv++) {
                if (b[i] != -1 && b[i] != bv) continue;
                int t = av - bv;
                cnt[i][idx(t)]++;
            }
        }
    }
    
    // DP
    vector<vector<int>> dp(n, vector<int>(2 * k, 0));
    dp[0][idx(0)] = 1;  // 初始累积和为 0
    
    for (int i = 0; i < n - 1; i++) {
        vector<vector<int>> ndp(n, vector<int>(2 * k, 0));
        for (int j = -k; j <= 0; j++) {
            int cur = dp[i][idx(j)];
            if (cur == 0) continue;
            for (int t = -(k-1); t <= k-1; t++) {
                int ways = cnt[i][idx(t)];
                if (ways == 0) continue;
                if (t >= 0) {
                    if (j + t <= 0) {
                        ndp[i+1][idx(j + t)] = (ndp[i+1][idx(j + t)] + 1LL * cur * ways) % MOD;
                    }
                } else {
                    ndp[i+1][idx(t)] = (ndp[i+1][idx(t)] + 1LL * cur * ways) % MOD;
                }
            }
        }
        dp = ndp;
    }
    
    int ans = 0;
    for (int j = -k; j <= 0; j++) {
        ans = (ans + dp[n-1][idx(j)]) % MOD;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

总结

本题的核心是将网格条件转化为对序列 $c_i = a_{i+1} - b_i$ 的约束，要求从每个负数位置开始的后续部分和非正。通过动态规划维护当前累积和，并利用预处理的 $c_i$ 取值计数，可以在 $O(n k^2)$ 时间内求解。