1. 项目概述：从“放棋子”到错位排列的算法思维跃迁

最近在带学生刷信息学奥赛（信奥）题目时，又遇到了P3182 [HAOI2016] “放棋子”这道题。乍一看标题，很多刚接触的同学会下意识地往搜索、回溯或者棋盘类博弈的方向去想，但如果你真的去尝试用DFS枚举每个格子放不放棋子，那等待你的大概率是超时。这道题的精妙之处，恰恰在于它用一个非常生活化的场景——“放棋子”，包装了一个经典的组合数学问题：错位排列。这也是信奥题目的一大特点，它考察的往往不是蛮力，而是将实际问题抽象、转化为已知数学模型的能力。

简单来说，题目给你一个 N×N 的棋盘，但是每一行、每一列都有一个预设的障碍格。题目保证这些障碍格的位置非常“规矩”：任意两个障碍不在同一行，也不在同一列。现在要求你在剩下的格子里放置 N 个棋子，使得最终每行、每列都有且仅有一个棋子，并且任何一个棋子都不能放在障碍格上。问有多少种不同的放置方案。

举个例子，如果 N=2，障碍位置是 (1,1) 和 (2,2)。那么棋盘和障碍如下（X代表障碍）：

行1: X . 行2: . X

我们要放2个棋子，满足每行每列一个，且不放在X上。那么唯一的方案就是在(1,2)和(2,1)放棋子。所以方案数是1。

如果障碍是 (1,2) 和 (2,1)：

行1: . X 行2: X .

唯一的方案就是在(1,1)和(2,2)放棋子，方案数也是1。

你会发现，无论障碍具体在哪，只要它们满足“不同行不同列”的条件，这个棋盘放棋子的方案数，居然和障碍的具体位置无关！这就是本题的第一个关键洞察，也是通往“错位排列”的桥梁。我们今天的讨论，将不仅限于通过这道题，更会深入拆解如何用C++实现高精度计算的大数错位排列，分享从问题转化、公式推导到代码实现的完整心路历程和避坑指南。

2. 核心思路解析：为什么是错位排列？

理解这道题的核心，需要完成两步思维跳跃。

2.1 第一步：抽象与简化——障眼法的去除

题目最迷惑人的地方就是那个 N×N 的棋盘和具体的障碍位置。但条件“任意两个障碍不在同一行，任意两个障碍不在同一列”是突破口。这意味着，如果我们对棋盘的行和列进行适当的重新编号，总可以让这些障碍格恰好落在棋盘的主对角线上。

怎么理解呢？假设原始障碍在第 i 行的第a[i]列。由于障碍不同列，a[1]...a[N]实际上是 1 到 N 的一个排列。现在，我们进行一个“重映射”操作：

1. 保持行号不变。
2. 将列号进行一个置换：把原来第a[1]列重新编号为第1列，原来第a[2]列重新编号为第2列……以此类推。

经过这样的列重排后，新的棋盘上，第 i 行的障碍就必然在新的第 i 列上了，也就是落在了所有 (i, i) 的位置上，即主对角线。而列的重排只是一个“标签”的更换，并不会改变“每行每列放一个棋子且不放在障碍上”这个问题的方案总数。

关键提示：很多同学卡在第一步，就是总想模拟棋盘、标记障碍。实际上，在算法竞赛中，遇到这种“保证是排列”的条件，首先要想到的就是可以通过映射来标准化问题，这是降低思维复杂度的常用技巧。

经过这一步抽象，问题简化为：在一个 N×N 的棋盘上，主对角线的所有格子都是障碍。要在非对角线格子上放置 N 个棋子，满足每行每列有且仅有一个棋子。求方案数。

2.2 第二步：识别经典模型——错位排列的定义

简化后的问题描述，正是组合数学中“错位排列”的经典定义。

错位排列：对于 1, 2, …, N 这 N 个元素的一个排列，如果每个元素都不在其原始位置上，那么这个排列就是一个错位排列（Derangement）。

对应到我们的棋盘：

• “行号” i 可以看作元素 i。
• “列号” j 可以看作元素 i 被放置到的位置。
• “每行每列一个棋子”意味着行号和列号构成一个排列。
• “不能放在主对角线 (i, i) 上”意味着对于排列中的每个元素 i，其位置p[i]都不能等于 i。

所以，放置棋子的每一种方案，本质上就是求 {1, 2, ..., N} 的一个错位排列。方案数就是 N 个元素的错位排列数，通常记为!N或D(N)。

因此，P3182这道题的核心，就是计算 N 的错位排列数 D(N)。输入一个 N，输出 D(N)。障碍的具体位置输入，仅仅是为了验证题目条件（事实上，在本题中读入障碍位置后可以直接忽略它们）。

3. 错位排列的计算：从递推公式到高精度实现

知道了是求 D(N)，下一步就是如何计算。对于信奥竞赛，N 可以很大（本题中 N ≤ 200），D(N) 会是一个远超long long范围的巨大整数，因此我们必须自己实现高精度运算。

3.1 错位排列的递推公式

错位排列数有一个优美的递推公式，这是实现的基础：

D(1) = 0（1个元素不可能不在自己位置上）D(2) = 1（只有 [2, 1] 一种）对于 n ≥ 2， D(n) = (n-1) * [ D(n-1) + D(n-2) ]

公式的直观理解（非常重要）： 考虑第 n 个元素（也就是最大号的那个），它不能放在位置 n。我们看看它能放在哪里，以及放完之后其他元素怎么办。

1. 第 n 个元素有 (n-1) 个其他位置可以放（位置 1 到 n-1）。
2. 假设第 n 个元素放在了位置 k（k 从 1 到 n-1）。现在我们需要放置剩下的 n-1 个元素。
3. 这时，元素 k 被“挤”出来了。它有两个去处：
   • 情况A：元素 k 放到位置 n。那么剩下的 n-2 个元素（排除了 n 和 k），就构成了一个规模为 n-2 的子问题，方案数是 D(n-2)。
   • 情况B：元素 k 不放到位置 n。那么，位置 n 现在被占了（被元素 k 视为不可用的位置），而元素 k 也不能回自己的位置（位置 k 已经被元素 n 占了）。对于剩下的 n-1 个元素（包括 k）和 n-1 个位置（除了位置 k），问题等价于这 n-1 个元素都各自有一个“禁止位”（元素 i 不能放位置 i），且禁止位构成一个排列。这就是一个规模为 n-1 的错位排列问题，方案数是 D(n-1)。
4. 由于第 n 个元素有 (n-1) 种选择（k 有 n-1 种可能），而对于每一种 k，后续都有 (D(n-1) + D(n-2)) 种方案。因此总公式为 D(n) = (n-1) * (D(n-1) + D(n-2))。

这个理解过程比死记硬背公式更重要，它体现了组合计数中“分类讨论”和“子问题化”的核心思想。

3.2 高精度计算的设计与实现

N 最大为 200，D(200) 是一个超过 300 位的天文数字。C++ 标准库没有原生的大整数类型，我们需要用数组或字符串来模拟。

3.2.1 高精度结构体设计

我习惯用一个结构体来封装高精度整数，这样操作起来更清晰。这里采用“万进制”来存储，即数组的每一个元素存储数字的4位十进制位。这比十进制存储（一位占一个数组元素）计算效率更高，比二进制存储又更便于输入输出。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; struct BigInt { int data[500]; // 每个元素存储4位数字，500*4足以容纳D(200) int len; // 当前使用的数组长度 // 构造函数，初始化为0 BigInt() { memset(data, 0, sizeof(data)); len = 1; } // 设置为一个普通整数 void set(int x) { memset(data, 0, sizeof(data)); len = 0; do { data[len++] = x % 10000; x /= 10000; } while (x > 0); } // 高精度加法 BigInt operator + (const BigInt& b) const { BigInt res; res.len = max(len, b.len); int carry = 0; for (int i = 0; i < res.len; i++) { int sum = data[i] + b.data[i] + carry; res.data[i] = sum % 10000; carry = sum / 10000; } if (carry > 0) { res.data[res.len++] = carry; } return res; } // 高精度乘法（高精度 * 整数） BigInt operator * (int b) const { BigInt res; res.len = len; long long carry = 0; // 注意用long long防止中间溢出 for (int i = 0; i < len; i++) { long long product = (long long)data[i] * b + carry; res.data[i] = product % 10000; carry = product / 10000; } while (carry > 0) { res.data[res.len++] = carry % 10000; carry /= 10000; } return res; } // 输出函数 void print() { printf("%d", data[len - 1]); // 最高位直接输出，不含前导0 for (int i = len - 2; i >= 0; i--) { printf("%04d", data[i]); // 中间位需要补足4位 } printf("\n"); } };

实操心得：为什么选择万进制？十进制存储（一位一存）实现最简单，但乘法、加法运算次数多，效率低。万进制是效率与实现复杂度的一个很好平衡。10000作为基数，两个万进制数相乘不会超过int范围（10000*10000=1e8），方便处理。同时，输出时要注意除最高位外，每一位都要用%04d补足4位，否则会丢失前导零导致错误。

3.2.2 主算法逻辑

有了高精度类，主算法就非常简洁了，就是递推公式的直接实现。

int main() { int N; cin >> N; // 读入障碍位置，根据前文分析，其具体位置不影响结果，但需要读入以消耗输入 int temp; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> temp; } } // 错位排列递推初始化 if (N == 1) { cout << 0 << endl; return 0; } BigInt d1, d2, dn; // d1代表D(n-2), d2代表D(n-1), dn代表D(n) d1.set(0); // D(1) = 0 d2.set(1); // D(2) = 1 for (int n = 3; n <= N; n++) { // D(n) = (n-1) * [ D(n-1) + D(n-2) ] dn = (d1 + d2) * (n - 1); // 滚动更新，为下一次迭代准备 d1 = d2; d2 = dn; } // 注意：当N=2时，循环不会执行，d2就是结果 if (N == 2) { d2.print(); } else { dn.print(); } return 0; }

注意事项：边界条件与滚动数组

1. N=1 和 N=2 需要特判，这是递推的起点。
2. 使用d1,d2,dn三个变量滚动递推，避免了开一个大数组D[201]来存储所有中间结果，节省了内存。这在N很大时是一个好习惯。
3. 递推从 n=3 开始。如果 N<3，要记得直接输出初始值。

4. 代码实现的深度优化与细节打磨

上面的代码已经可以AC这道题了。但在实际竞赛和教学中，我们还可以从健壮性、可读性和性能上做更多思考。

4.1 输入处理的陷阱

题目输入格式是先读 N，然后是一个 N×N 的 01 矩阵。很多同学会尝试去解析这个矩阵，找出障碍位置，甚至想验证“障碍是否在不同行不同列”。这完全是浪费时间，并且可能引入错误。

// 低效且易错的写法 vector<int> barrier(N); for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ cin >> temp; if(temp == 1) barrier[i] = j; // 记录障碍位置 } } // 然后可能还想验证一下barrier数组是否是个排列...

正确的做法是直接忽略矩阵内容，只读入，不存储。因为我们已经从数学上证明了结果与障碍具体位置无关。这能节省大量内存和CPU时间。

// 高效且正确的写法 int trash; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> trash; // 读入并丢弃 } }

4.2 高精度乘法的进一步优化

我们实现的高精度乘法是O(n)的（n是位数）。当 N=200 时，D(N) 的位数大约在 375 位左右（万进制下约94个单元），乘以一个不超过200的整数，这个复杂度完全可接受。但如果问题规模更大，可以考虑更高效的算法（如FFT乘法），不过对于信奥本题，无需过度优化。

一个小的优化点是，在operator* (int b)中，我使用了long long类型的carry和product。这是因为data[i] * b的最大值是 9999 * 199，大约 2e6，加上进位也不会超过 1e10，在long long范围内是安全的。这是实现高精度乘法时一个非常容易忽略的溢出点。

4.3 完整、鲁棒的最终代码

将以上所有点结合起来，并添加适当的注释，得到一份工业级的参考代码：

#include <iostream> #include <cstring> #include <algorithm> using namespace std; // 万进制高精度整数类 struct BigInt { static const int BASE = 10000; // 万进制基 static const int WIDTH = 4; // 每个单元宽度 int data[500]; // 存储单元，500*4位足够应对N<=200 int len; // 当前长度 // 构造函数与初始化 BigInt() { memset(data, 0, sizeof(data)); len = 1; } BigInt(int num) { *this = num; } // 赋值运算符（从int） BigInt& operator=(int num) { memset(data, 0, sizeof(data)); len = 0; do { data[len++] = num % BASE; num /= BASE; } while (num > 0); return *this; } // 高精度加法 BigInt operator+(const BigInt& b) const { BigInt res; res.len = max(len, b.len); int carry = 0; for (int i = 0; i < res.len; i++) { int sum = data[i] + b.data[i] + carry; res.data[i] = sum % BASE; carry = sum / BASE; } if (carry) { res.data[res.len++] = carry; } return res; } // 高精度乘法（高精度 * 小整数） BigInt operator*(int b) const { BigInt res; res.len = len; long long carry = 0; // 防止中间结果溢出 for (int i = 0; i < len; i++) { long long product = (long long)data[i] * b + carry; res.data[i] = product % BASE; carry = product / BASE; } while (carry) { res.data[res.len++] = carry % BASE; carry /= BASE; } return res; } // 输出 void print() const { printf("%d", data[len - 1]); for (int i = len - 2; i >= 0; i--) { printf("%04d", data[i]); // 注意：四位数字，不足补零 } putchar('\n'); } }; int main() { int N; scanf("%d", &N); // 读入并忽略障碍矩阵 int trash; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &trash); } } // 处理边界情况 if (N == 1) { puts("0"); return 0; } if (N == 2) { puts("1"); return 0; } // 初始化递推：d1 = D(1), d2 = D(2) BigInt d1 = 0; // D(1) BigInt d2 = 1; // D(2) BigInt dn; // 当前D(n) // 递推计算 D(n) = (n-1) * [ D(n-1) + D(n-2) ] for (int n = 3; n <= N; n++) { dn = (d1 + d2) * (n - 1); // 滚动更新 d1 = d2; d2 = dn; } // 输出结果 dn.print(); return 0; }

5. 常见问题与调试心得

在教授和实现这道题的过程中，我遇到了学生们几个高频错误点，这里集中记录一下。

问题一：结果输出为0，或者明显偏小。

• 排查点1：高精度输出函数。这是最常见的错误。万进制输出时，除了最高位，其他位必须用%04d格式化输出。如果用了%d，那么像 123 这个单元（代表0123）会被输出成“123”，导致数字错误。例如，数字1000000在万进制下存储为[0, 1]（低位在前）。正确输出应为1 000000，如果第二位用%d输出，就成了1 0，结果变成10。
• 排查点2：递推初始值。确认D(1)=0,D(2)=1。有人会记成D(0)=1（空排列算一种），但本题从N=1开始。
• 排查点3：乘法溢出。检查operator*中的carry和product是否使用了足够大的类型（如long long）。

问题二：运行超时。

• 原因：几乎不可能。N最大200，递推200次，每次是高精度加法和一次乘以小整数（O(位数)）。位数在400以内，计算量极小。如果超时，99%是陷入了对障碍矩阵的无用处理，比如试图用DFS在棋盘上搜索方案。
• 解决：回归问题本质，直接计算错位排列数。

问题三：答案部分正确，部分错误。

• 排查：可能是滚动更新逻辑写反了。确保是d1 = d2; d2 = dn;，即用d1和d2分别表示D(n-2)和D(n-1)。错误的更新顺序会导致递推关系错乱。
• 验证：可以写一个小的测试程序，计算前10个错位排列数，与已知序列 [0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961] 进行比对。

问题四：如何处理N=0的情况？

• 分析：题目明确 N≥1。从组合数学定义上，D(0) 通常定义为 1（空排列满足“没有元素在自己位置上”）。但本题不需要考虑。

调试技巧：

1. 单元测试高精度类：单独测试你的BigInt结构体，用一些小数字验证加法、乘法、输出是否正确。
2. 小数据打表：用你的程序计算 N=1 到 10 的结果，与标准答案手工对比。这是验证算法逻辑最直接的方法。
3. 简化问题测试：可以先写一个用long long计算小N错位排列的程序（注意N>20就会溢出），用它来验证你的高精度递推逻辑是否正确。

最后，这道P3182“放棋子”就像信奥路上的一个经典路标，它提醒我们，面对复杂场景，第一步永远是抽象和转化。识别出背后的错位排列模型，问题就从一道复杂的搜索题变成了一道纯粹的组合数学递推题。而高精度运算，则是实现这个数学结论的必要工具。掌握这种“化归”的思想，比多刷十道题更有价值。在后续遇到类似“禁止配对”、“混乱的排序”等问题时，错位排列的递推公式和这种高精度实现方式，将会是你武器库中一件非常称手的兵器。