题解：P8788 [蓝桥杯 2022 国 A] 填空问题

guoshengyu1231 · 2025-05-15 20:06:42 · 题解

试题 A ：小蓝与钥匙

题目要求让 14 个孩子都分到自己的钥匙，另外 14 个孩子都不分到自己的钥匙，问一共有多少方案？ \\

首先我们要让这 28 个孩子中选择 14 个孩子分到自己的钥匙，显然方案数为 \operatorname{C}^{14}_{28}。但还有一个问题，那就是剩下 14 个孩子都必须不能分到自己的钥匙，这该怎么办呢？ \\

其实这个就是在排列组合中一个非常经典的问题——错排问题。至于怎么做，我们可以从递推的角度出发。 \\

现在我们设函数 \operatorname{f}(n) 用来求解 n 个数的错排问题的方案数。首先，对于第一个数，它可以坐到其余 n-1 个位置上。因为基本都差不多，那我们就以它做到了第 2 个位置上为例。 \\

如果第一个数坐到了第二个位置，那么第二个数它有以下两种方案：

坐到了第一个位置： \\ 此时便形成了一个闭环，如下图：因此第一种情况 \operatorname{f}(n)=\operatorname{f}(n-2)。
坐到了剩下 n-2 个位置中的一个： \\ 假设此时第 2 个数去了第 x 个位置，此时我们可以想象成是消除了第二个位置，让第一个数坐到第 x 个位置，这里可能有一些难理解，所以我还是给个图吧。此时问题就变成了 n-1 个数的错位排序，因此可得 \operatorname{f}(n)=\operatorname{f}(n-1)。最后总结公式可得错位排序的计算公式为 \operatorname{f}(n)=(n-1)(\operatorname{f}(n-1)+\operatorname{f}(n-2))。用程序模拟即可。 \\

最后两部分相乘，可得答案为 1286583532342313400。

这里我们需要引入一个概念——康托展开式，那到底什么是康托展开式呢？比如有一个以 n 个排列元素组成的全排列，然后给定一个全排列序列，求该序列是所有全排列序列中字典序第几的序列。这时候我们就可以用康托展开式进行求解，具体公式如下：

ans=a_n\times(n-1)!+a_n\times(n-1)!+\cdots+a_1\times0!

其中 a_i 为“当前元素”在“所有未出现的元素”中排在第 i 个（从 0 开始），并且 0\le a_i<i（1\le i\le n）。 \\

要想高效的算出一个排列的康托展开值，我们可以利用树状数组来求解。这里就不在过多赘述了，大家可以去看看这题：P5367 【模板】康托展开。最终答案显然就等于两个排列的康托展开值的差，答案为 106148357572143。