1. 从一道排列计数题说起Good Permutations 的挑战最近在 Codeforces 和 daimayuan 这类在线评测平台上排列相关的计数问题热度一直不减。这类题目往往披着“简单定义”的外衣实则考察选手对组合数学、动态规划乃至数论等知识的综合运用能力。今天要聊的这道“Good Permutations”#851就是一个典型的例子。题目描述通常很简洁对于一个长度为 n 的排列 p如果对于所有满足 1 ≤ i j ≤ n 的整数对 (i, j)都有|p_i - p_j| ≠ |i - j|成立那么这个排列就被称为“好的”。我们的任务就是计算长度为 n 的“好排列”的数量。初看之下这个条件|p_i - p_j| ≠ |i - j|似乎只是在说排列中任意两个位置上的数值之差不能等于这两个位置下标之差。但如果你尝试手动枚举 n3,4 的情况很快就会发现问题没那么简单。n3 时排列 [1,2,3] 显然不满足例如 i1,j2有 |1-2| |1-2|。实际上n3 时一个“好排列”都没有。到了 n4情况开始复杂需要仔细排查。这种题目直接吸引了两类人一是正在备战算法竞赛需要刷题巩固思维的同学二是对组合数学有浓厚兴趣喜欢探究数字间隐秘规律的爱好者。它不像纯粹的动态规划题有明确的“状态”定义也不像图论题有清晰的模型它更像一个需要你从混乱中寻找秩序的智力游戏。这道题的核心难点在于约束条件是全局性的、成对出现的。它不像“错排问题”那样有一个经典的递推公式可以直接套用。|p_i - p_j| ≠ |i - j|这个条件等价于禁止排列中出现“距离相等”的对。换句话说在排列中任何两个元素它们的值之差不能等于它们的索引之差。这让人联想到国际象棋中“皇后”的攻击方式皇后可以沿对角线攻击而这里一个位于位置 i、值为 p_i 的元素它“攻击”的正是那些满足p_j - p_j i - j或p_j - p_j j - i的其他位置 j。所以“好排列”问题在组合数学里有一个更响亮的名字——N皇后问题的一个变种或者更准确地说是“不允许皇后沿对角线互相攻击”的排列计数问题的简化版因为这里只关心是否在同一条对角线上而不区分方向。理解了这个模型我们就知道不能硬来了。n 稍微大一点比如 n10排列总数是 10! 3,628,800虽然可以暴力枚举但再大就无能为力了。题目通常要求 n 可以达到 10 甚至更大在取模意义下计算这就需要我们寻找更聪明的数学方法或高效的算法策略。接下来我们就一步步拆解这个问题看看如何从最基础的暴力搜索过渡到利用对称性和约束条件进行剪枝并探讨其背后的数学本质。2. 问题转化从排列约束到“非攻击皇后”模型要系统解决这个问题第一步是彻底理解并转化约束条件。给定排列 p[1..n]条件为对所有 i j有|p_i - p_j| ≠ |i - j|。我们把这个绝对值等式拆开它其实包含两种情况p_i - p_j i - jp_i - i p_j - jp_j - p_i i - jp_i i p_j j(将负号移项并整理可得)这揭示了问题的关键两个位置 (i, p_i) 和 (j, p_j) 冲突即不满足“好”的条件当且仅当它们的“差值”p_i - i相等或者它们的“和值”p_i i相等。这是一个非常重要的洞察。它允许我们将排列中的每个元素 i位置为 i值为 p_i映射到两个关键的属性值上主对角线标识d1 p_i - i。在棋盘模型中这对应从左上到右下方向的对角线编号。所有d1值相同的元素位于同一条“主对角线”上。副对角线标识d2 p_i i。这对应从右上到左下方向的对角线编号。所有d2值相同的元素位于同一条“副对角线”上。那么“好排列”的条件就可以重新表述为在这个排列中任何两个不同的元素它们的d1值不能相同同时它们的d2值也不能相同。换句话说映射i - (d1, d2)必须是一个双射即每个d1值和每个d2值在 1 到 n 的这 n 个元素中至多只能出现一次。但这可能吗让我们看看d1和d2的取值范围。对于d1 p_i - i因为 1 ≤ p_i ≤ n, 1 ≤ i ≤ n所以d1的范围是[1-n, n-1]即-(n-1)到(n-1)总共2n-1个可能值。对于d2 p_i i范围是[2, 2n]总共也是2n-1个可能值。我们需要将 n 个元素分配到这些“对角线”上并且保证分配时每个元素占据一个唯一的(d1, d2)对。所有被占据的d1值必须互不相同。所有被占据的d2值必须互不相同。这立刻让我们联想到另一个经典的组合问题在 n x n 的棋盘上放置 n 个互不攻击的皇后。皇后的攻击范围是同行、同列、同对角线。而这里“同行”冲突自然避免因为排列 p 本身就是一个双射每个值只出现一次相当于每列只有一个皇后“同列”冲突也自然避免每个位置 i 只放一个值相当于每行只有一个皇后。剩下的约束就是两条对角线不能重复而这正是 N皇后问题的核心约束因此“Good Permutations”问题完全等价于经典的 N皇后问题。计算长度为 n 的“好排列”的数量就是计算在 n x n 棋盘上放置 n 个互不攻击的皇后的方案数。这是一个众所周知的、计算复杂度非常高的问题。对于 n1 到 n10经典解的数量序列是1, 0, 0, 2, 10, 4, 40, 92, 352, 724... 你可以验证n1 时排列 [1] 是好的n2,3 时无解n4 时有 2 个解对应两个皇后放置方案每个方案对应一个排列。注意这里有一个细微但至关重要的点。在严格的 N皇后问题中解的数量通常指“本质不同的解”的数量即考虑旋转和对称性。但在“Good Permutations”问题中每一个不同的皇后放置布局直接对应一个不同的排列 p通过读取每一行皇后所在的列号。因此我们计算的是所有可能的排列而不是去重后的本质解。对于 n8经典结果是 92 个所有解而不是 12 个本质解。理解了问题的等价性我们的策略就清晰了求解 N皇后问题的所有可行布局并计数。对于算法竞赛n 的范围决定了我们采用何种方法。3. 算法策略选择回溯、位运算与数学特性既然问题归结为 N皇后那么算法选择就取决于 n 的上限。在 daimayuan 或 Codeforces 的题目中n 的范围是关键信息。假设 n 最大在 15 左右这是一个常见的挑战上限我们可以采用深度优先搜索DFS回溯法并利用位运算进行极致优化。如果 n 更大比如达到 20可能需要更高级的算法如启发式搜索或舞蹈链 DLX或者题目可能只需要输出对某个大质数取模的结果并暗示存在某种递推或容斥原理公式尽管 N皇后问题没有已知的简单闭式解。3.1 基础回溯与剪枝最直观的方法是回溯法。我们一行一行对应位置 i 从 1 到 n地放置皇后。在第 i 行我们需要选择一个列号 col对应 p_i 的值使得这个 col 满足没有被之前的行占用列冲突。其主对角线d1 col - i没有被占用。其副对角线d2 col i没有被占用。我们可以用三个布尔数组来记录列、主对角线、副对角线的占用情况。cols[col]: 表示第 col 列是否被占用。diag1[d1]: 表示主对角线d1 col - i是否被占用。注意 d1 的范围是[-(n-1), n-1]编程时通常加上偏移量n使其索引非负即index col - i n。diag2[d2]: 表示副对角线d2 col i是否被占用。d2 的范围是[2, 2n]索引可以从 2 开始。一个朴素的 DFS 回溯框架如下伪代码def backtrack(row, n, cols, diag1, diag2, count): if row n: count[0] 1 return for col in range(1, n1): d1 col - row d2 col row if not cols[col] and not diag1[d1] and not diag2[d2]: cols[col] diag1[d1] diag2[d2] True backtrack(row1, n, cols, diag1, diag2, count) cols[col] diag1[d1] diag2[d2] False这个方法可以解决 n 约在 12 以内的问题。当 n13 或更大时搜索空间爆炸需要优化。3.2 位运算优化回溯这是竞赛中解决 N皇后问题n 15的标准高效方法。其核心思想是用整数的二进制位来表示列和对角线的占用状态利用位运算快速枚举可放置的位置。我们定义三个整数cols_mask: 一个 n 位的二进制数1表示该列已被占用。diag1_mask: 表示当前行有哪些主对角线位置被之前的皇后攻击到。diag2_mask: 表示当前行有哪些副对角线位置被之前的皇后攻击到。关键技巧在于当我们在第row行放置皇后时所有被攻击的位置是cols_mask | diag1_mask | diag2_mask。那么可用的位置就是其取反后只保留低 n 位的部分available_pos (~(cols_mask | diag1_mask | diag2_mask)) ((1 n) - 1)。然后我们不断取出available_pos中的最低位1进行尝试def dfs(row, cols, diag1, diag2, n): if row n: return 1 count 0 # 当前行所有被攻击的位置 forbidden cols | diag1 | diag2 # 可用的位置二进制位为1表示可放 available ((1 n) - 1) (~forbidden) while available: # 取出最低位的1 pos available -available # 尝试放置在这个位置 count dfs(row 1, cols | pos, (diag1 | pos) 1, (diag2 | pos) 1, n) # 移除这个位置继续尝试下一个 available available - 1 return count这里diag1和diag2的更新需要解释在下一行主对角线的攻击线会向左移动一位对应 1副对角线的攻击线会向右移动一位对应 1。这是因为对角线是相对于当前行而言的。位运算回溯将每次选择从遍历 n 列优化为只遍历真正可用的几个位置并且状态转移是常数时间的位操作效率极高。用这种方法在普通计算机上可以在几秒内算出 n15 的所有解约 2.2e9 种状态中的可行解实际计算很快。3.3 利用对称性进一步剪枝对于 N皇后问题棋盘具有旋转和反射对称性。虽然“Good Permutations”要求计数所有排列但我们在搜索时可以利用对称性减少计算量。例如第一行皇后可以只放在前一半的列中因为放在后半部分列的解可以通过水平反射得到我们在计数时乘以相应的倍数即可但要注意中心列的特殊处理。这通常能将搜索空间减少近一半。然而在算法竞赛的时限内对于 n15位运算回溯已经足够。如果题目中 n 更大比如 n20位运算回溯也可能超时这时就需要考虑舞蹈链Dancing Links, DLX算法它用精确覆盖算法来求解是已知求解 N皇后问题最高效的通用算法之一可以处理 n 约在 20-25 左右。实操心得在实现位运算回溯时最容易出错的地方是对角线的移位操作和二进制位的索引对应关系。我个人的习惯是将皇后的位置pos视为一个只有一位是 1 的二进制数其1所在的位置从右往左数第几位就代表列号从0开始计数。这样cols | pos就表示占用了该列。对于对角线一定要画图理解假设当前在第row行放在col列那么它影响的主对角线在下一行row1会延伸到col-1列如果存在所以是左移一位副对角线会延伸到col1列所以是右移一位。务必用 n4 的小例子手动模拟一遍确保移位方向正确。4. 从暴力到打表竞赛中的实战策略在在线评测OJ的实战中面对“Good Permutations”这类题目我们需要根据输入范围灵活制定策略。情况一n 很小例如 n ≤ 10这是最简单的情况。我们甚至可以在本地预先计算出所有 n 对应的答案然后硬编码到程序中直接根据输入的 n 输出答案。这就是所谓的“打表Precomputation/Table”。例如我们通过位运算回溯程序计算出 n 从 1 到 10 的答案序列为[1, 0, 0, 2, 10, 4, 40, 92, 352, 724]。那么提交的代码可能就是ans [1, 0, 0, 2, 10, 4, 40, 92, 352, 724] n int(input()) print(ans[n-1] if n len(ans) else 0)这种方法时间复杂度是 O(1)绝对安全。但前提是题目给出的 n 上限就在我们打表的范围内。情况二n 中等例如 n ≤ 15且需要在线计算如果题目 n 上限是 15并且要求在线计算可能需要对结果取模那么我们就需要在代码中实现优化后的回溯算法通常是位运算版。这里有一个重要细节结果可能非常大。n15 时解的数量是 2279184还在 32 位整数范围内。但 n 再大数量会急剧增长题目很可能会要求输出结果对某个大质数如 1e97取模的值。这时我们在 DFS 的回溯过程中每次找到一个解就执行count (count 1) % MOD即可。情况三n 更大例如 n 15这在单纯的排列计数题中较少见因为结果数量会爆炸式增长输出都成问题。如果出现题目极有可能不是让我们计算精确解而是寻找某种规律或者转化为判断是否存在解对于某些特殊的 n。另一种可能是题目经过了改编约束条件可能发生了微妙变化使得问题不再是严格的 N皇后。这时就需要重新审题。对于原汁原味的“Good Permutations”即 N皇后当 n 很大时没有已知的多项式时间算法。目前已知的结果是通过分布式计算或高度优化的算法得到的。例如n27 的解的数量是一个巨大的数字。在竞赛中这种范围通常意味着题目本身可能允许打表或者 n 的上限被故意设置得让回溯法无法通过从而逼迫选手去寻找数学规律或更巧妙的解法——但就 N皇后而言除了搜索没有更巧妙的通用公式。踩坑记录我曾经在一次比赛中遇到一个类似题目n 上限是 12我直接写了回溯并提交结果超时。检查后发现我虽然用了回溯但剪枝不够彻底并且每次递归都复制了整个棋盘状态。后来改用位运算状态用整数传递速度立刻提升了几十倍。另一个坑点是对角线的数组大小。主对角线索引col - row n的范围是[0, 2n-2]数组需要开2*n大小。如果只开了n大小当 n 较大时会发生数组越界导致程序出现未定义行为可能在本该找到解的时候提前退出或计数错误。这种 bug 非常隐蔽建议统一将数组大小设为2*n5以留有余地。5. 测试验证与扩展思考无论采用哪种算法验证都是必不可少的。对于小 n我们可以用最笨的暴力枚举生成所有排列并检查条件来验证我们的回溯或位运算算法是否正确。例如用 Python 的itertools.permutations生成所有排列然后检查条件n8 都可以快速验证。验证代码框架如下import itertools def is_good_perm(p): n len(p) for i in range(n): for j in range(i1, n): if abs(p[i] - p[j]) abs(i - j): return False return True def brute_force(n): count 0 for perm in itertools.permutations(range(1, n1)): if is_good_perm(perm): count 1 return count # 测试 n1 到 8 for n in range(1, 9): print(fn{n}: brute_force{brute_force(n)})将输出结果与我们优化算法的结果对比确保一致。扩展思考模运算下的计数如果题目要求结果对 M 取模而 M 不是质数甚至可能和 n! 有公因数这时直接计数取模没问题。但如果我们想用组合数学或容斥原理来推导公式尽管很难就需要考虑模逆元等概念。“至少有一对冲突”的排列数这是“好排列”的反面。可以用容斥原理计算但公式非常复杂因为冲突的条件共享同一条对角线不是独立的。随机生成“好排列”这是一个更有挑战性的问题。由于解的数量相对总排列数非常少直接随机生成再检验效率极低。需要采用启发式算法如回溯加随机选择、或模拟退火等。与图论的联系我们可以构造一个冲突图顶点是所有的排列位置赋值(i, value)如果两个赋值冲突即导致 |value_i - value_j| |i - j|则连一条边。那么“好排列”就对应这个图中的一个大小为 n 的独立集且每个 i 和每个 value 恰好出现一次。这将其转化为一个图上的精确覆盖问题这也是舞蹈链DLX算法可以应用的原因。最后虽然“Good Permutations”最终指向了经典的 N皇后问题但思考过程本身非常有价值。它展示了如何将一个抽象的排列约束转化为直观的几何棋盘模型如何通过等式变形抓住问题本质以及如何根据数据范围选择合适的算法策略暴力、回溯、位运算、打表。在算法竞赛中这种“转化与建模”的能力往往比熟记某个具体算法的模板更为重要。下次遇到类似的排列约束问题不妨先试试看能不能把它映射到某个熟悉的组合结构或图模型上。