题目来源：Problem - 2049
思路分析：
假设有n个新郎，m个新郎选错，m个人错选有F(m)种情况
首先，先考虑n个人错排的情况（分为两种情况），推导出递归公式：
（1）假设原先有n-1个新郎已经完成了错排，总共有F(n-1)种情况，这时再来一个新郎，要想完成全都错排，就得将自己的新娘与别人的新娘交换，这就有（n-1）种可能性，这时便有(n-1)*F(n-1)种情况
（2）假设原先的n-1个新郎没有完成全部错排，要想实现全都错排，只有一种情况：n-2个新郎已经完成了错排，这就有F(n-2)种情况，那个选对自己新娘的新郎要与最后来的第n个新郎交换，而这个选对自己新娘的新郎可以是n-1个新郎中的任何一个，所以有（n-1）种可能性，这时便有(n-1)*F(n-2)种情况
综上，n个人错排的递归公式为
其次，有n个新郎，m个新郎选错，这就有C（n，m）种情况
实现代码：
import java.util.Scanner;
public class Test_2049 {
public static void main (String args[]) {
Scanner in = new Scanner(System.in);
int c = in.nextInt();
long []num = new long[21];
num[2] = 1;
num[3] = 2;
for(int i=4;i<num.length;i++) {
num[i] = (i-1) * (num[i-1] + num[i-2]);
}
while(c -- != 0) {
int n = in.nextInt();
int m = in.nextInt();
if(n == m)
System.out.println(num[m]);
else {
long top = 1;
long bottom = 1;
for(int i=n;i>m;i--) {
top *= i;
}
for(int i=1;i<=(n-m);i++) {
bottom *= i;
}
System.out.println(num[m] * top / bottom);
}
}
}
}
提示：
一般来说，递归产生数据比较大，最好定义类型时，定义为long、double这些范围比较大的类型。
