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

问题描述

问题分析

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#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)——考新郎