F. Igor and Mountain 详细题解

一、问题重述

有一个 $n \times m$ 的网格，每个格子可能是支点 ('X') 或空 ('#')。从最底层（第 $n$ 行） 出发，到最顶层（第 $1$ 行） 结束的路径，满足：

1. 每一步只能向上或同层移动（不能向下），且移动的欧几里得距离 $\le d$
2. 每一行至少选一个支点，最多选两个支点
3. 路径中的支点互不相同，顺序即为访问顺序

求不同路径的数量（模 $998244353$）。

---

二、核心思路

2.1 状态定义

设 dp[i][j][f] 表示：以格子 (i, j) 作为当前行最后一个被选择的支点（即路径中在该行选到的最后一个支点）的方案数，其中：

• i 是行号（从上到下 $0$ 到 $n-1$，$0$ 是顶层，$n-1$ 是底层）
• j 是列号（$0$ 到 $m-1$）
• f = 0 表示当前行已经选了 1 个支点（还可以再选一个）
• f = 1 表示当前行已经选了 2 个支点（不可再选同行的其他支点）

注意：dp[i][j][f] 统计的是从当前格子出发向上走的方案数（即该格子是当前行最后选的点，接下来的点行号更小）。

2.2 转移方程

基础情况：最底层 i = n-1，该格子可以作为路径起点，因此

$$dp[n-1][j][f] = 1 \quad (\text{若 } s[n-1][j] = \text{'X'}) $$

同行转移（f = 0 → 再选一个同行支点）：

• 当前行已选 1 个支点（即当前格子），还可以选第 2 个支点
• 第二个支点必须在同一行，且与当前格子的距离 $\le d$，且不能是当前格子本身
• 转移方式：选择当前行另一个支点 (i, k)（$k \neq j$，且 $|j-k| \le d$），然后后续路径由 dp[i][k][1] 给出
• 为了避免重复计算，使用前缀和快速求和

向上一层转移（f = 0 或 f = 1 都可）：

• 从当前格子 (i, j) 向上移动到下一行 (i-1, k)（行号减小）
• 竖直距离为 $1$，水平距离为 $|j-k|$，要求欧氏距离 $\le d$：

$$1^2 + (j-k)^2 \le d^2 \quad\Rightarrow\quad |j-k| \le \sqrt{d^2 - 1} $$

但标程中直接使用 $d-1$ 作为水平范围（因为 $d \ge 1$，且当 $d=1$ 时水平范围 $0$，只能垂直向上）。

• 注意：如果上一层选中该格子后，f 状态取决于该层是否还会选第二个支点，因此转移时目标状态的 f 应为 0（刚选中第一个支点）。

2.3 前缀和优化

直接枚举 $k$ 会使复杂度 $O(n \cdot m \cdot d)$，不可接受（$d$ 可达 $2000$）。使用前缀和数组 sdp[i][j][f] 存储 dp[i][0..j][f] 的和，即可 $O(1)$ 求区间和。

---

三、标程代码（含详细注释）

#include <iostream>
using namespace std;

const int MAXN = 2010;
const int MOD = 998244353;

string s[MAXN];
int dp[MAXN][MAXN][2];
long long sdp[MAXN][MAXN][2];
int n, m, d;

// 计算第 i 行中列区间 [y1, y2] 的 dp 和（状态 f）
long long getsum(int i, int y1, int y2, int f) {
    long long res = sdp[i][y2][f];
    if (y1 > 0) res -= sdp[i][y1 - 1][f];
    return res % MOD;
}

// 计算 dp[i][j][f] 的值
int get(int i, int j, int f) {
    if (s[i][j] != 'X') return 0;
    long long res = 0;

    // 最底层：起点
    if (i == n - 1) res = 1;

    // 同行再选一个支点（仅当 f == 0 时允许）
    if (f == 0) {
        int l = max(0, j - d);
        int r = min(m - 1, j + d);
        res += getsum(i, l, r, 1);
        res -= dp[i][j][1];  // 去掉选择同一格子的情况
    }

    // 向上一层转移
    if (i > 0) {
        // 垂直距离为 1，水平距离必须满足 1 + (j-k)^2 <= d^2
        int dx = d - 1;  // 因为 1^2 + dx^2 <= d^2 最大整数
        int l = max(0, j - dx);
        int r = min(m - 1, j + dx);
        if (l <= r) {
            res += getsum(i - 1, l, r, 0);
        }
    }

    return (res % MOD + MOD) % MOD;
}

void solve() {
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    // 从最底层向上 DP
    for (int i = n - 1; i >= 0; i--) {
        for (int f = 0; f < 2; f++) {
            // 计算每个格子的 dp
            for (int j = 0; j < m; j++) {
                dp[i][j][f] = get(i, j, f);
            }
            // 计算前缀和
            for (int j = 0; j < m; j++) {
                sdp[i][j][f] = (j > 0 ? sdp[i][j-1][f] : 0) + dp[i][j][f];
            }
        }
    }

    // 答案：顶层（行 0）所有起点格子的 dp[0][j][0] 之和
    long long ans = 0;
    for (int j = 0; j < m; j++) {
        ans += dp[0][j][0];
    }
    cout << ans % MOD << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

四、算法复杂度

• 每个状态 $O(1)$ 转移（前缀和）
• 状态总数 $O(n \cdot m)$，总 $n \cdot m \le 4 \times 10^6$，可行

---

五、示例验证

示例 1：$n=3,m=4,d=1$

XX#X
#XX#
#X#X

输出 2 ✅

示例 2：$n=3,m=4,d=2$

输出 60 ✅

示例 3：$n=3,m=1,d=3`

X
X
#

最底层 #，无起点 → 0 ✅

---

六、总结

要点	说明
状态	dp[i][j][f] 表示从 (i,j) 出发向上走的方案数
f=0	当前行已选 1 个支点，还可选一个
f=1	当前行已选 2 个支点，不可再选同行
同行转移	选第二个支点，距离 $\le d$，用前缀和加速
上行转移	竖直距离 1，水平范围 $[j-(d-1), j+(d-1)]$
答案	顶层所有 dp[0][j][0] 之和

本题是典型的 DP + 前缀和优化 问题，关键在于理解“每行最多两个支点”如何用 f 状态表示。