蓝桥杯2022国赛A组 小蓝与钥匙(排列组合、错排、递推)

蓝桥杯2022国赛A组

I. 小蓝与钥匙

$ans=C_{28}^{14} \cdot D[14]$

其中，$C_{28}^{14}$表示从$28$个人中，选出$14$个匹配的。$D[14]$表示剩余$14$个人没有人选到自己对应的钥匙，即规模为$14$的错排。

错排的递推公式：$D[n] = (n - 1)(D[n - 2] + D[n - 1])$，其中$D[1] = 0$，$D[2] = 1$.

推导：

假如有n封信，任何一封信都需要错位，错排方案数是D(n)；

1. 分步计数原理：使用分步计数原理，统计第一封信的排列方法，然后再讨论其余信的排列方法数； (1) 第一步：首先找出一封信a出来，这封信不能排在其本身位置，只能放在其余n−1个位置上，因此有n−1种排法； (2) 第二步：现在讨论其余除a之外的其余信的位置的错排问题；
2. 分类计数原理 假设第一封信a占据了b的位置，那么此时b放在哪个信封分两种情况：b放在a位置，或b不放在a位置； (1) 第一类：第一种情况是放在a位置，此时 b放在a位置，剩下n−2封信进行错排，方案数是D(n−2)； (2) 第二类：第二种情况是b没有去a的位置，即a的位置一定放的是非b，这样，除了b之外的所有位置都有且仅有一个不能放的元素，这种情况下相当于除a之外的其它元素的错排问题，即n−1个元素的错排问题,方案数是D(n−1)； (3) 加法法则：汇总上述分类计数原理，使用加法法则，计算结果是D(n−1) + D(n−2)
3. 乘法法则：汇总上述分步计数原理，使用乘法法则，计算结果是： $D[n] = (n - 1)(D[n - 2] + D[n - 1])$

#include <iostream>
using namespace std;

typedef long long LL;
LL wrarr[20];	// 错排递推数组 

int main(){ 
	wrarr[1] = 0, wrarr[2] = 1;
	for(int i = 3; i <= 14; i ++) wrarr[i] = (i - 1) * (wrarr[i - 2] + wrarr[i - 1]);
	
	LL res = 1;
	int div = 1;
	for(int i = 15; i <= 28; i ++){
		res = res * i;
		while(res % div == 0 && div <= 14){
			res = res / div;
			div ++;
		}
	}
	
	res = res * wrarr[14];
	
	cout << res;
	return 0;
}