GitBook

这里写图片描述 这里写图片描述 这里写图片描述

这一题也是卡了好久 原先以为是简单的排列组合 但现在看这其实是一个错排问题

与普通的错排不同的在于这里新郎与新郎是不同的 所以有哪一些谁选对(哪一些谁选错)也是不同的 所以计算可能时也要把这个考虑进去

这里使用了一个数组保存错排数据 另一个数组保存阶乘数据 以此来节约时间

#include<stdio.h>
int main() {
	long long a[21]= {0,0,1};
	long long b[21]= {1};
	for(int i=3; i<21; i++) {
		a[i]=(i-1)*(a[i-1]+a[i-2]);
	}
	for(int i=1; i<21; i++) {
		b[i]=i*b[i-1];
	}
	int T;
	scanf("%d",&T);
	while(T--) {
		int n,m;
		scanf("%d %d",&n,&m);
		printf("%lld\n",b[n]/b[n-m]/b[m]*a[m]);
	}
	return 0;
}

题目地址:【杭电】[2049]不容易系列之(4)——考新郎