HDOJ2049不容易系列之(4)——考新郎

错排问题。

递推公式D(n)=(n-1)*(D(n-1)+D(n-2));

这题的核心问题是错排。答案就是乘个组合数就完事了。

记一下错排：

d[1]=0;d[2]=1;

假设n个xl刚开始都和xn正确匹配，xl n号开始错选了xn k号，这里选法有n-1种情况。

然后1：xl k号选了xn n号，这时候其他的n-2项开始错排为d（n-2）；

2：xl k号选了除这2个号的其他号，xl k号不能选n号，这时候就剩下n-1个位置错排了为d（n-1）；

最终推出公式。