P1002 [NOIP 2002 普及组] 过河卒 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库 —— 图也要存。

转录自洛谷 P1002，日期见页头。两边不一致时信原站。

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为「马拦过河卒」。

棋盘用坐标表示，A 点 (0, 0)、B 点 (n, m)，同样马的位置坐标是需要给出的。

棋盘示意：卒在 A(0,0)，目标 B(4,8)，马在 C(2,4)，八个控制点标为 P1~P8

现在要求你计算出卒从 A 点（不经过马的控制点）能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

数据规模与约定

对于 100% 的数据，1 ≤ n, m ≤ 20，0 ≤ 马的坐标 ≤ 20。

保证起点不是马的控制点。

【题目来源】NOIP 2002 普及组第四题。

输入输出样例

输入

6 6 3 3

输出

n = 6, m = 6，马在 (3, 3)。⚠ 这一组样例只挡得住本页两个错法里的一个，第 ⑤ 步会看到。

1和第 17 章那道题只差一个运算符

第 17 章的数字三角形问的是「最大和」，这道题问的是「有几条路」。把递归写出来，两者只差一个运算符：

    数字三角形： best(i,j) = a[i][j] + max( best(i+1,j), best(i+1,j+1) )
    过河卒：     walk(x,y) =            walk(x+1,y) + walk(x,y+1)

出口也只是换了个说法：走出棋盘或踩到控制点 → 0 条；走到 (n,m) → 1 条。

「求最优」换成「求方案数」，记忆化那三行一个字都不用改。

p1002Brute.cpp第一版：纯递归

// P1002 的**第一版**：纯递归，不记忆化。
//
// 题目：棋盘上 A(0,0) 到 B(n,m)，卒每步只能**向下**或**向右**。
//       马在 C(cx,cy)，**马所在的点和它一步能跳到的 8 个点**都不能走。问路径条数。
//
// 递归写出来几乎就是把题目念一遍：
//     f(x,y) = 从 (x,y) 出发走到 (n,m) 的路径条数
//            = f(x+1,y) + f(x,y+1)
//   出口：走出棋盘 → 0；踩到控制点 → 0；到 (n,m) → 1。
//
// ⇒ 和第 17 章那道数字三角形**只差一个运算符**：那里是 `max`，这里是 `+`。
//   「求最优」换成「求方案数」，记忆化那三行一个字都不用改。
//
// ⚠ 它**是对的**，只是跑不完：调用次数和路径条数同一个量级，
//   而顶格的答案是 1378 亿 —— 那不是「慢」，是跑不出来。
//   ⇒ 和第 17 章那道数字三角形一模一样：**加三行就好了**（p1002.cpp）。

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

static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static int n, m;
static bool bad[25][25];                    // 马的控制点（含马自己那一格）
static long long calls = 0;

static long long walk(int x, int y) {
    calls++;
    if (x > n || y > m || bad[x][y]) return 0;
    if (x == n && y == m) return 1;
    return walk(x + 1, y) + walk(x, y + 1);
}

int main(int argc, char** argv) {
    int cx, cy;
    if (!(cin >> n >> m >> cx >> cy)) return 0;
    if (cx >= 0 && cx <= n && cy >= 0 && cy <= m) bad[cx][cy] = true;   // ⚠ 马自己那一格也算
    for (int t = 0; t < 8; t++) {
        int x = cx + DX[t], y = cy + DY[t];
        if (x >= 0 && x <= n && y >= 0 && y <= m) bad[x][y] = true;
    }
    cout << walk(0, 0) << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

它慢到什么程度：调用次数就是路径条数的量级

马放在棋盘外（一格都不挡），n = m 一档一档往上加：

`n = m`	4	8	12	16
记忆化	49	161	337	577
纯递归	363	71 499	15 392 887	3 465 051 659
倍数	7×	444×	45 676×	600 万×

而题面顶格是 n = m = 20。⇒ 和第 17 章一样：加三行就好了。

p1002.cpp★ 这一版就能 AC

// P1002 过河卒 —— 记忆化搜索（★ 这一版就能 AC）
//
// 题目：棋盘上 A(0,0) 到 B(n,m)，卒每步只能**向下**或**向右**。
//       马在 C(cx,cy)，**马所在的点和它一步能跳到的 8 个点**都不能走。问路径条数。
//
// 递归写出来几乎就是把题目念一遍：
//     f(x,y) = 从 (x,y) 出发走到 (n,m) 的路径条数
//            = f(x+1,y) + f(x,y+1)
//   出口：走出棋盘 → 0；踩到控制点 → 0；到 (n,m) → 1。
//
// ⇒ 和第 17 章那道数字三角形**只差一个运算符**：那里是 `max`，这里是 `+`。
//   「求最优」换成「求方案数」，记忆化那三行一个字都不用改。
//
// ★★★ 而这道题真正会挂人的，不是搜索，是**一行类型声明**：
//   没有马挡路时答案就是 `C(n+m, n)`，顶格 `C(40,20) = 137846528820` ——
//   **比 int 的上限大 64 倍**。用 `int` 存就是 WA，而且是那种「样例全过」的 WA。
//   ⇒ 页面第 ③ 步把「哪些输入会溢出」441 个马位一个一个数完了。

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

static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static int n, m;
static bool bad[25][25];                    // 马的控制点（含马自己那一格）
static long long f[25][25];                 // ★ long long，不是 int
static bool vis[25][25];
static long long calls = 0;

static long long walk(int x, int y) {
    calls++;
    if (x > n || y > m || bad[x][y]) return 0;
    if (x == n && y == m) return 1;
    if (vis[x][y]) return f[x][y];
    long long res = walk(x + 1, y) + walk(x, y + 1);
    vis[x][y] = true;
    f[x][y] = res;
    return res;
}

int main(int argc, char** argv) {
    int cx, cy;
    if (!(cin >> n >> m >> cx >> cy)) return 0;
    if (cx >= 0 && cx <= n && cy >= 0 && cy <= m) bad[cx][cy] = true;   // ⚠ 马自己那一格也算
    for (int t = 0; t < 8; t++) {
        int x = cx + DX[t], y = cy + DY[t];
        if (x >= 0 && x <= n && y >= 0 && y <= m) bad[x][y] = true;
    }
    cout << walk(0, 0) << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

2★★★ 这道题真正会挂人的，是一行类型声明

没有马挡路时，答案就是从 (0,0) 走到 (n,m) 的组合数 C(n+m, n)。顶格：

    C(40, 20) = 137 846 528 820
    int 上限  =   2 147 483 647
                 ------------------
    比值      = 64.2 倍

用 int 存就是 WA。 而且是最难受的那种 WA：样例照过。

p1002Int.cpp错法一：用 int

// P1002 的**错法一**：和 p1002.cpp 一模一样，只把 `long long` 换成了 `int`。
//
// 题目：棋盘上 A(0,0) 到 B(n,m)，卒每步只能**向下**或**向右**。
//       马在 C(cx,cy)，**马所在的点和它一步能跳到的 8 个点**都不能走。问路径条数。
//
// ★★★ 这是这道题最出名的坑，而它是一道**三十秒的算术题**：
//   没有马挡路时答案就是 `C(n+m, n)`，顶格 `C(40, 20) = 137846528820` ——
//   **是 int 上限 2147483647 的 64.2 倍**。
//
// ⚠ 它最难缠的地方是**样例全过**（样例答案是 6），而且**随机对拍也很难抓**：
//   要溢出得同时满足两件事 —— `n + m` 够大、**而且马没把路挡死**。
//   页面第 ③ 步把顶格那 441 个马位一个一个数完了，第 ④ 步量了随机对拍的抓获率。

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

static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static int n, m;
static bool bad[25][25];                    // 马的控制点（含马自己那一格）
static int f[25][25];                       // ★ 错在这里
static bool vis[25][25];
static long long calls = 0;

static int walk(int x, int y) {
    calls++;
    if (x > n || y > m || bad[x][y]) return 0;
    if (x == n && y == m) return 1;
    if (vis[x][y]) return f[x][y];
    int res = walk(x + 1, y) + walk(x, y + 1);   // ★ 这一加就溢出了
    vis[x][y] = true;
    f[x][y] = res;
    return res;
}

int main(int argc, char** argv) {
    int cx, cy;
    if (!(cin >> n >> m >> cx >> cy)) return 0;
    if (cx >= 0 && cx <= n && cy >= 0 && cy <= m) bad[cx][cy] = true;   // ⚠ 马自己那一格也算
    for (int t = 0; t < 8; t++) {
        int x = cx + DX[t], y = cy + DY[t];
        if (x >= 0 && x <= n && y >= 0 && y <= m) bad[x][y] = true;
    }
    cout << walk(0, 0) << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3★★★ 「要不要 long long」是一道能算出精确分界的算术题

不用猜，也不用靠对拍撞。这道题的输入空间小到可以整个数完：

先看顶格。 n = m = 20，马的位置有 21 × 21 = 441 种，一个一个跑：

顶格 `n = m = 20` 的 441 个马位	个数
题面排除的（马控制了起点）	3
答案溢出 `int`	433
答案是 0（马把终点或起点周围堵死了）	5
最大答案	137 846 521 561

⇒ 顶格时几乎必然溢出（433 / 438 = 98.9%）。

再看整个输入空间。 400 组 (n, m)，每组把 441 个马位都试一遍取最大答案：


最大可能答案超过 `int` 的 `(n, m)` 组数	24 / 400 = 6%
其中最小的 `n + m`	34（那一组的最大答案 2 175 838 789）

★★★ 而随机对拍，300 轮只抓到 12 次

生成器（各 300 轮）	`int` 版被抓
照题面随机（`n, m ∈ [1,20]`，马随机）	12 / 300 = 4%
顶格档（`n = m = 20`，只随机马位）	298 / 300

算出来是 6%，实测是 4% —— 两条路对上了（实测略低，因为还得马不挡路）。

⇒ 这一条值得记住：输入空间小的时候，「算一遍」比「对拍」又快又充分。 算一遍花的是几十毫秒，而且直接给出精确的分界线 n + m ≥ 34；对拍跑 300 轮抓 12 次，只能告诉你「好像有问题」。 ★ 这是第 11 章 P1908 那条的正面版本：那道题是「对拍查不出溢出」缺主语，这道题是连主语都能算出来 —— 而顺手写的「照题面随机」生成器正好落在最不容易触发的那一头。

4⚠ 顺带一条：`n` 和 `m` 是坐标不是格数

A 是 (0,0)、B 是 (n,m)，所以棋盘上一共有 (n+1) × (m+1) 个点。数组要开到 21 × 21（这一页统一开了 25 × 25），开成 20 × 20 就是越界。

★ 而马的坐标范围题面单独给了：0 ≤ 马的坐标 ≤ 20 —— 它可以落在棋盘外 （比如 n = m = 4 而马在 (20, 20)），那时它一格都不挡。第 ① 步那张调用次数表用的就是这种输入。

5错法二：8 个跳点都标了，唯独忘了马自己站的那一格

题面原话：「该马所在的点和所有跳跃一步可达的点称为对方马的控制点。」 —— 是 9 个点，不是 8 个。而顺手写循环时只会想到那八个方向。

p1002Self.cpp错法二：忘标马自己

// P1002 的**错法二**：8 个跳点都标了，**唯独忘了马自己站的那一格**。
//
// 题目：棋盘上 A(0,0) 到 B(n,m)，卒每步只能**向下**或**向右**。
//       马在 C(cx,cy)，**马所在的点和它一步能跳到的 8 个点**都不能走。问路径条数。
//
// 题面原话：「该马所在的点**和**所有跳跃一步可达的点称为对方马的控制点。」
//   —— 是 9 个点，不是 8 个。而顺手写循环时只会想到那八个方向。
//
// ★ 页面第 ⑤ 步量了它有多好抓：官方样例就挡住了吗？答案在那儿。

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

static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static int n, m;
static bool bad[25][25];                    // 马的控制点（含马自己那一格）
static long long f[25][25];                 // ★ long long，不是 int
static bool vis[25][25];
static long long calls = 0;

static long long walk(int x, int y) {
    calls++;
    if (x > n || y > m || bad[x][y]) return 0;
    if (x == n && y == m) return 1;
    if (vis[x][y]) return f[x][y];
    long long res = walk(x + 1, y) + walk(x, y + 1);
    vis[x][y] = true;
    f[x][y] = res;
    return res;
}

int main(int argc, char** argv) {
    int cx, cy;
    if (!(cin >> n >> m >> cx >> cy)) return 0;
    // ★ 错在这里：少了「马自己那一格也是控制点」这一句
    for (int t = 0; t < 8; t++) {
        int x = cx + DX[t], y = cy + DY[t];
        if (x >= 0 && x <= n && y >= 0 && y <= m) bad[x][y] = true;
    }
    cout << walk(0, 0) << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 这一个官方样例挡住了 —— 而上一个没挡住

	正确答案	输出
用 `int`	6	6 ← 放过去了
忘标马自己那一格	6	10 ← 挡住了

同一组样例，一个错法过、一个错法挂。 ⇒ 又一次：「官方样例挡不挡得住」是一个一个试出来的事 （同一轮的 P1518 是两个都挡住，P1074 是样例 ① 放过了一个）。

对拍上它比 int 那个好抓得多：

生成器（各 300 轮）	忘标马自己被抓	其中正解就是 0 的轮数
照题面随机	86 / 300	15
顶格档	298 / 300	2

⚠ 注意第三列：照题面随机时有 15 轮正解本来就是 0（马把路堵死了），那些轮两版一起输出 0 —— 对拍记「通过」而验的是零。这是第 14 章 P1746 那条的又一次现场，只是这道题上比例不高。

6度量程序和生成器

上面每一张表 —— 顶格那 441 个马位、400 组 (n,m) 的边界、两个错法的抓获率、还有那张调用次数表 —— 都是这一份跑出来的，并且逐条写进了 scripts/check-viz.mjs。

p1002Count.cpp度量程序

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

// P1002 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1002Count`      人看的版本
// `./p1002Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① 官方样例：四个版本各输出什么；
//   ② ★★★ 顶格 n = m = 20：**441 个马位一个一个数完**（bug 空间数得完就别抽样）——
//      多少个位置会让答案溢出 int、多少个位置答案是 0（终点被挡死）、最大答案是多少；
//   ③ ★★★ 溢出的边界：对 400 组 (n, m) 各取「最大可能答案」，多少组超过 int、
//      最小的那个 n + m 是几 —— ⇒ 「要不要 long long」是一道能算出精确分界的算术题；
//   ④ 两个错法在两档生成器上的抓获率（照题面随机 ／ 顶格）；
//   ⑤ 纯递归 vs 记忆化的调用次数。

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

static bool CSV = false;
static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};
static const long long INT_TOP = 2147483647LL;

static int n, m;
static bool bad[25][25];
static long long f[25][25];
static bool vis[25][25];
static long long calls;

/** self = false 时故意漏掉「马自己那一格」（错法二） */
static void mark(int cx, int cy, bool self) {
    memset(bad, 0, sizeof bad);
    if (self && cx >= 0 && cx <= n && cy >= 0 && cy <= m) bad[cx][cy] = true;
    for (int t = 0; t < 8; t++) {
        int x = cx + DX[t], y = cy + DY[t];
        if (x >= 0 && x <= n && y >= 0 && y <= m) bad[x][y] = true;
    }
}

static long long walk(int x, int y, bool memo) {
    calls++;
    if (x > n || y > m || bad[x][y]) return 0;
    if (x == n && y == m) return 1;
    if (memo && vis[x][y]) return f[x][y];
    long long res = walk(x + 1, y, memo) + walk(x, y + 1, memo);
    if (memo) { vis[x][y] = true; f[x][y] = res; }
    return res;
}

static long long solve(int N, int M, int cx, int cy, bool self = true, bool memo = true) {
    n = N; m = M;
    mark(cx, cy, self);
    memset(vis, 0, sizeof vis);
    calls = 0;
    return walk(0, 0, memo);
}

/** 用 int 重算一遍（错法一）：把每一步的加法都截断成 32 位 */
static int fi[25][25];
static bool visi[25][25];
static int walkInt(int x, int y) {
    if (x > n || y > m || bad[x][y]) return 0;
    if (x == n && y == m) return 1;
    if (visi[x][y]) return fi[x][y];
    int res = walkInt(x + 1, y) + walkInt(x, y + 1);
    visi[x][y] = true;
    fi[x][y] = res;
    return res;
}
static int solveInt(int N, int M, int cx, int cy) {
    n = N; m = M;
    mark(cx, cy, true);
    memset(visi, 0, sizeof visi);
    return walkInt(0, 0);
}

static bool controlsOrigin(int cx, int cy) {
    if (cx == 0 && cy == 0) return true;
    for (int t = 0; t < 8; t++) if (cx + DX[t] == 0 && cy + DY[t] == 0) return true;
    return false;
}

/** 和 p1002Gen.cpp 逐字一致 */
static void gen(int seed, int mode, int& N, int& M, int& cx, int& cy) {
    mt19937 rng((unsigned)seed * 2654435761u + 19u);
    if (mode == 1) { N = M = 20; }
    else { N = (int)(rng() % 20) + 1; M = (int)(rng() % 20) + 1; }
    do { cx = (int)(rng() % 21); cy = (int)(rng() % 21); } while (controlsOrigin(cx, cy));
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");

    /* ① 官方样例 6 6 3 3 */
    {
        long long ok = solve(6, 6, 3, 3);
        long long self = solve(6, 6, 3, 3, false);
        long long brute = solve(6, 6, 3, 3, true, false);
        long long bi = solveInt(6, 6, 3, 3);
        if (!CSV) printf("① 官方样例 6 6 3 3：正解 %lld｜int 版 %lld｜忘标马自己 %lld｜纯递归 %lld\n",
                         ok, bi, self, brute);
        row("sample", {ok, bi, self, brute});
    }

    /* ② ★★★ 顶格 n = m = 20：441 个马位，一个一个数完 */
    {
        int over = 0, zero = 0, illegal = 0;
        long long mx = 0;
        for (int cx = 0; cx <= 20; cx++)
            for (int cy = 0; cy <= 20; cy++) {
                if (controlsOrigin(cx, cy)) { illegal++; continue; }   // 题面保证不会出现
                long long r = solve(20, 20, cx, cy);
                if (r > INT_TOP) over++;
                if (r == 0) zero++;
                mx = max(mx, r);
            }
        if (!CSV) printf("\n② 顶格 n = m = 20，441 个马位全数完：\n"
                         "   题面排除的（马控制起点）%d 个｜答案溢出 int 的 %d 个｜答案是 0 的 %d 个｜最大答案 %lld\n",
                         illegal, over, zero, mx);
        row("full20", {illegal, over, zero, mx});
    }

    /* ③ ★★★ 溢出的边界：每组 (n,m) 的「最大可能答案」 */
    {
        int overPairs = 0, minSum = 999;
        long long mnOver = LLONG_MAX;
        for (int N = 1; N <= 20; N++)
            for (int M = 1; M <= 20; M++) {
                long long best = 0;
                for (int cx = 0; cx <= 20 && best <= INT_TOP; cx++)
                    for (int cy = 0; cy <= 20 && best <= INT_TOP; cy++) {
                        if (controlsOrigin(cx, cy)) continue;
                        best = max(best, solve(N, M, cx, cy));
                    }
                if (best > INT_TOP) {
                    overPairs++;
                    if (N + M < minSum) { minSum = N + M; mnOver = best; }
                }
            }
        if (!CSV) printf("\n③ 400 组 (n, m) 里，最大可能答案超过 int 的有 %d 组；"
                         "最小的那个 n + m 是 %d（那一组的最大答案 %lld）\n", overPairs, minSum, mnOver);
        row("bound", {overPairs, minSum, mnOver});
    }

    /* ④ 两个错法在两档生成器上的抓获率 */
    {
        if (!CSV) printf("\n④ 两个错法各被抓多少（每档 300 轮）\n");
        vector<long long> out;
        for (int mode : {0, 1}) {
            int bi = 0, bs = 0, zero = 0;
            for (int s = 1; s <= 300; s++) {
                int N, M, cx, cy;
                gen(s, mode, N, M, cx, cy);
                long long ok = solve(N, M, cx, cy);
                if (ok == 0) zero++;
                if (solveInt(N, M, cx, cy) != ok) bi++;
                if (solve(N, M, cx, cy, false) != ok) bs++;
            }
            out.push_back(bi); out.push_back(bs); out.push_back(zero);
            if (!CSV) printf("  %s：int 版被抓 %d / 300｜忘标马自己被抓 %d / 300"
                             "（其中正解就是 0 的有 %d 轮）\n",
                             mode ? "顶格档  " : "照题面随机", bi, bs, zero);
        }
        row("catch", out);
    }

    /* ⑤ 纯递归 vs 记忆化的调用次数 */
    {
        // ⚠ 草稿里马放在 (2,2)，结果它把 (0,1) 和 (1,0) 一起挡了 —— 起点直接被封死，
        //   四档答案全是 0、调用 3 次。⇒ **马放哪儿要先想一下**，不然量的是个空壳。
        //   这里放到 (20,20)：n = m ≤ 16 时它落在棋盘外，一格都不挡。
        if (!CSV) printf("\n⑤ 纯递归 vs 记忆化的调用次数（马放在棋盘外的 (20,20)，一格不挡）\n");
        vector<long long> out;
        for (int k : {4, 8, 12, 16}) {
            solve(k, k, 20, 20, true, true);
            long long cm = calls;
            solve(k, k, 20, 20, true, false);
            long long cb = calls;
            out.push_back(cm); out.push_back(cb);
            if (!CSV) printf("  n = m = %2d：记忆化 %lld 次，纯递归 %lld 次（%.0f 倍）\n",
                             k, cm, cb, cb * 1.0 / cm);
        }
        row("calls", out);
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1002Gen.cpp数据生成器

// P1002 对拍生成器：`./p1002Gen <seed> [模式]`
//   模式 0（默认）**照题面随机**：n, m ∈ [1,20]，马坐标 ∈ [0,20]（保证起点不是控制点）
//   模式 1 ★ **顶格档**：n = m = 20，只随机马的位置
//
// ★★★ 两档必须都跑，而这一页的主线就在它们的差别上：
//   这道题最出名的坑是**答案要开 long long**（顶格 `C(40,20) = 137846528820`，
//   是 int 上限的 64.2 倍）。可**照题面随机**很难抓到它 ——
//   要溢出得同时满足两件事：`n + m` 够大，**而且马没把路挡死**。
//   页面第 ③ ④ 步把这两个条件分别量了一遍。
//
// ⚠ 题面保证「起点不是马的控制点」，所以这里造出来的马位也要满足这一条，
//   否则造的是**非法输入**，两版一起输出 0，对拍验的是零。

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

static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

/** (cx,cy) 的马会不会控制到 (0,0) */
static bool controlsOrigin(int cx, int cy) {
    if (cx == 0 && cy == 0) return true;
    for (int t = 0; t < 8; t++) if (cx + DX[t] == 0 && cy + DY[t] == 0) return true;
    return false;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937 rng(seed * 2654435761u + 19u);

    int n, m;
    if (mode == 1) { n = m = 20; }
    else { n = (int)(rng() % 20) + 1; m = (int)(rng() % 20) + 1; }

    int cx, cy;
    do { cx = (int)(rng() % 21); cy = (int)(rng() % 21); } while (controlsOrigin(cx, cy));
    printf("%d %d %d %d\n", n, m, cx, cy);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠ 写这个度量程序时踩的一脚：马放哪儿要先想一下

第 ① 步那张「纯递归 vs 记忆化」的表，草稿里马固定放在 (2, 2) —— 结果它把 (0,1) 和 (1,0) 一起挡了，卒从起点一步都迈不出去。于是四档答案全是 0、调用次数全是 3，那张表量的是一个空壳，而它看起来完全正常（没有报错、数字也整整齐齐）。

⇒ 改成把马放到棋盘外的 (20,20)（n = m ≤ 16 时一格不挡）才量到真东西。 造对照数据之前，先确认它没有把要观察的现象本身消掉。

7一页纸


关键的一步	和第 17 章数字三角形只差一个运算符：`max` 换成 `+`
哪一版能 AC	`p1002.cpp`（记忆化＋ `long long`）
最容易挂的一行	`int` 存答案 —— 顶格 `C(40,20) = 137846528820`，是 int 上限的 64.2 倍
第二容易挂的一行	控制点是 9 个不是 8 个（马自己那一格也算）
这一页的主线	「要不要 long long」能算出精确分界：`n + m ≥ 34`，400 组里只有 24 组（6%）； ⇒ 输入空间小的时候，算一遍比对拍又快又充分（对拍 300 轮只抓到 12 次）
顶格有多险	`n = m = 20` 的 441 个马位里，433 个会溢出 int（98.9%）

洛谷 P1002 [NOIP 2002 普及组] 过河卒

0题目原文（本地存了一份）

输入

输出

1和第 17 章那道题只差一个运算符

2★★★ 这道题真正会挂人的，是一行类型声明

3★★★ 「要不要 long long」是一道能算出精确分界的算术题

4⚠ 顺带一条：`n` 和 `m` 是坐标不是格数

5错法二：8 个跳点都标了，唯独忘了马自己站的那一格

6度量程序和生成器

7一页纸