HDU 2049 不容易系列之(4)——考新郎 题目 Problem Description 国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排; 然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板… 看来做新郎也不是容易的事情… 假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能. Input 输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。 Output 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。 Sample Input 2 2 2 3 2 Sample Output 1 3 分析一下 给我思路

<think>嗯，我现在要解决的是HDU 2049这道题，题目是关于“考新郎”的问题。让我仔细读一遍题目，确保理解正确。题目大意是说，有N对新婚夫妇，其中有M个新郎找错了新娘，问这种情况有多少种可能的组合。输入的第一行是测试实例的个数C，接下来C行每行给出N和M。输出每个实例的可能数目。 首先，我得明确问题的要求。题目需要计算的是在N个新郎中选出M个，这M个都找错了新娘的情况数目。这显然涉及到组合数学中的错位排列（也称为错排）问题。因为对于选中的M个新郎，每个人都必须不在自己的位置上，而剩下的N-M个新郎则必须正确找到新娘，所以那些未被选中的新郎的位置是正确的。 那问题可以分解为两个步骤： 1. 从N个新郎中选出M个，这M个人需要进行错排。 2. 剩下的N-M个新郎必须正确，即他们的排列方式是唯一的，也就是只有一种可能。 所以，总的情况数应该是组合数C(N, M)乘以M个元素的错排数D(M)。 接下来，我需要确定如何计算组合数和错排数。 组合数C(n, k)的公式是n!/(k!*(n−k)!）。这个部分应该没有问题，但需要注意n和k的范围。题目中的N和M最大是20，所以阶乘可能会比较大，但用长整型应该可以处理。 然后是错排数D(m)。错排数的递推公式我记得是D(n) = (n-1)*(D(n-1) + D(n-2))，初始条件是D(1)=0，D(2)=1。或者也可以用通项公式，比如D(n) = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n /n!)。不过对于编程来说，可能递推的方式更方便，尤其是当n比较小时，预处理错排数的数组会更高效。 那现在，我需要先计算组合数C(N,M)，然后乘以错排数D(M)。然后将这两个部分相乘得到结果。 比如，看样例输入： 第一个测试用例是2 2。即N=2，M=2。这时候，组合数是C(2,2)=1，错排数D(2)=1，所以结果是1*1=1。和样例输出一致。 第二个测试用例是3 2。N=3，M=2。组合数是C(3,2)=3。错排数D(2)=1，所以结果是3*1=3，符合样例输出。 这样，思路应该是正确的。现在需要思考如何实现这两个部分。 对于组合数的计算，由于n的范围是到20，可以考虑预先计算阶乘，然后用阶乘的数组来计算组合数。比如，预先计算fact[0]到fact[20]，其中fact[i]是i!的值。然后C(n,m)=fact[n]/(fact[m]*fact[n−m])。不过要注意数据类型的溢出问题，比如20!会非常大，用long long类型来存储可能比较安全。 对于错排数的计算，同样可以预先计算D[1]到D[20]。因为当M<=N<=20，所以最大的错排数是D(20)。递推方式的话： 初始化D[1]=0，D[2]=1。然后对于i>=3，D[i]=(i-1)*(D[i-1]+D[i-2])。 比如，D[3]=(3-1)*(D[2]+D[1])=2*(1+0)=2，这正确。因为三个元素的错排有两种情况。例如，元素1、2、3的正确排列是1-2-3，错排的话，可能的排列是2-3-1和3-1-2，共两种。 因此，正确的错排数可以通过递推得到。 现在，具体的实现步骤可能如下： 1. 预先生成阶乘数组fact，从0到20。 2. 预生成错排数数组D，从1到20。 3. 对于每个测试用例，输入N和M，计算C(N,M)*D[M]的值。 但需要注意的是，当M=1的时候，D[1]=0，所以这时候结果应该是C(N,1)*0=0。例如，当N=3，M=1时，选一个新郎让他错排，但错排数D[1]=0，所以总共有0种可能。但根据题目中的输入条件，M>1的情况是否存在？题目中的输入条件给出的是1<M<=N<=20。所以M最小是2吗？原题中输入的描述是“1<M<=N<=20”，所以M的取值是大于1，小于等于N的。那可能题目中的M的取值范围是M>=2？比如看样例输入中的第二个测试用例是3 2，M是2。所以错排数D[2]=1，所以没有问题。那当M=0或者M=1的时候，可能不在输入范围内，所以程序不需要处理这些情况。因此，在预生成错排数组时，D[1]虽然存在，但实际输入中不会有M=1的情况。 那现在，如何处理阶乘的计算？比如，阶乘数组的初始化： fact[0] = 1; fact[1] = 1; fact[2] = 2; ... 直到fact[20] = 20!。同样，可以用循环计算。 对于错排数组： d[1] = 0; d[2] = 1; for i from 3 to 20: d[i] = (i-1) * (d[i-1] + d[i-2]) 这些都可以预先计算好。 因此，在程序中，可以预先计算这两个数组，然后对于每个测试用例，直接计算组合数C(n,m) = fact[n]/(fact[m]*fact[n-m])，然后乘以d[m]，得到结果。 现在需要考虑的是，当计算组合数的时候，阶乘的数值是否溢出。比如，20!的值是2432902008176640000，这在C++中的long long类型是可以存储的，因为long long的范围是-9e18到9e18，而20!大约是2.4e18，所以没问题。而用Java的话，BigInteger可能会更安全，但题目中的N不超过20，所以用长整型应该足够。 因此，程序的大致流程是： 预处理fact数组和d数组。然后，对于每个测试用例，输入n和m，计算C(n,m)*d[m]，输出结果。 现在，测试一下样例： 比如第二个测试用例是3 2： fact[3] =6, fact[2]=2, fact[1]=1。C(3,2)=6/(2*1)=3。d[2]=1。3*1=3，正确。 另一个例子，比如n=4，m=2： 组合数是C(4,2)=6。d[2]=1。结果6*1=6。那是否合理？选2个人出来错排，他们的错排数是1，所以总共有6种可能？ 比如，假设这四个新郎是A、B、C、D，正确的新娘分别是a、b、c、d。选中的两个人比如A和B。他们必须都找错，那么可能的交换方式是A找b，B找a。这只有一种方式。所以对于选中的两个人来说，错排数是1。所以总共有C(4,2)*1=6种情况。确实如此。 那假设另一个例子，比如n=3，m=3。此时，组合数是1，错排数是D(3)=2。所以总共有2种可能。这与实际3个元素的错排数目相符。 综上，思路是正确的。 现在需要考虑的是如何编写代码，特别是预处理数组。 例如，在C++中，可以这样写： 预处理阶乘数组： long long fact[21]; fact[0] = 1; for(int i=1; i<=20; i++) fact[i] = fact[i-1] * i; 错排数组： long long d[21]; d[1] = 0; d[2] = 1; for(int i=3; i<=20; i++) d[i] = (i-1)*(d[i-1]+d[i-2]); 然后，对于每个测试用例，输入n和m： 计算组合数C(n,m) = fact[n]/(fact[m] * fact[n - m]); 然后结果就是C(n,m) * d[m]。 这样就能得到正确的结果。 需要注意的是，在C++中，当处理除法的时候，必须确保fact[m] * fact[n-m]的乘积能被fact[n]整除。由于组合数一定是整数，所以这里不会有问题。 例如，当n=3，m=2时： fact[3]=6, fact[2]=2, fact[1]=1. 6/(2*1)=3. 所以，这样的计算是正确的。 因此，这样的代码是正确的，应该能通过所有测试用例。 现在，再检查一下可能出现的边界情况。例如，当n=m的时候，即所有选中的新郎都错排。此时，结果应该是C(n,n)*d(n) =1*d(n)。比如，当n=2时，d(2)=1，结果正确。当n=3时，d(3)=2，结果2，正确。 另外，当m=0的情况？但题目中的输入条件m>1，所以不需要考虑。例如，输入中的m的最小值是2？ 根据题目描述，输入中的M的条件是1<M<=N<=20，所以M的最小可能值是2？ 例如，第一个测试用例是2 2，符合条件。那如果输入中有M=2的情况，那么没问题。 所以，现在代码的逻辑是正确的。 综上所述，解决这个问题的步骤是： 1. 计算组合数C(n, m)。 2. 计算错排数D(m)。 3. 将两者相乘，得到答案。 因此，程序实现的关键是预处理这两个数组，并且正确计算它们的乘积。</think>要解决HDU 2049“考新郎”问题，需分两步处理：**组合选择**和**错位排列**。以下是详细思路： --- ### **问题分析** 题目要求计算在N个新郎中选出M个并全部找错新娘的可能情况数。解决思路如下： 1. **组合选择**：从N个新郎中选出M个，组合数为$C(N, M)$。 2. **错位排列**：M个新郎全找错的排列数为错排数$D(M)$。 3. **总可能数**：将两者相乘，即$C(N, M) \times D(M)$。 --- ### **关键公式与预处理** 1. **组合数公式** 组合数$C(n, m) = \frac{n!}{m! \cdot (n-m)!}$。 预处理阶乘数组`fact[0..20]`，直接查表计算。 2. **错排数递推公式** 错排数满足递推关系： $$D(n) = (n-1) \cdot \left(D(n-1) + D(n-2)\right)$$ 初始条件： $$D(1) = 0,\quad D(2) = 1$$ 预处理错排数组`d[1..20]`。 --- ### **算法实现步骤** 1. **预处理阶乘数组** ```cpp long long fact[21] = {1}; // fact[0] = 1 for (int i = 1; i <= 20; i++) fact[i] = fact[i-1] * i; ``` 2. **预处理错排数组** ```cpp long long d[21] = {0, 0, 1}; // d[1]=0, d[2]=1 for (int i = 3; i <= 20; i++) d[i] = (i-1) * (d[i-1] + d[i-2]); ``` 3. **计算每个测试用例的结果** 输入N和M后，直接查表计算： $$结果 = C(N, M) \times D(M) = \frac{\text{fact}[N]}{\text{fact}[M] \cdot \text{fact}[N-M]} \times \text{d}[M]$$ --- ### **示例验证** 以样例输入`3 2`为例： 1. 组合数$C(3,2) = \frac{3!}{2! \cdot 1!} = 3$。 2. 错排数$D(2) = 1$。 3. 总可能数$3 \times 1 = 3$，与样例输出一致。 --- ### **代码实现（C++）** ```cpp #include <iostream> using namespace std; int main() { // 预处理阶乘和错排数 long long fact[21] = {1}; for (int i = 1; i <= 20; i++) fact[i] = fact[i-1] * i; long long d[21] = {0, 0, 1}; // d[0]未用，d[1]=0，d[2]=1 for (int i = 3; i <= 20; i++) d[i] = (i-1) * (d[i-1] + d[i-2]); int c; cin >> c; while (c--) { int n, m; cin >> n >> m; // 计算组合数C(n, m) = fact[n] / (fact[m] * fact[n-m]) long long cnm = fact[n] / (fact[m] * fact[n-m]); // 结果为组合数乘以错排数 cout << cnm * d[m] << endl; } return 0; } ``` --- ### **总结** 通过预处理阶乘和错排数，可快速计算每个测试用例的结果。时间复杂度为$O(1)$（预处理后查表），适用于题目中的输入范围。