现在做到的两道有关于错排的题目有：
2048：http://acm.hdu.edu.cn/showproblem.php?pid=2048
神、上帝以及老天爷
做这道题刚开始没有什么头绪，后来上网查了一下才发现原来有一个错排公式，也就是元素都不在对应原来位置的方法数。公式为：f(n) = (n-1) [f(n-2) + f(n-1)]
推导过程为：
第一步：假如一共有n个元素，那么如果把第n个元素放在某一个位置k，一共有n-1种方法；
第二步：放编号为k的元素有两种情况：(1)如果把它放到位置n，那么除了n和k元素外的n-2个元素一共有f(n-2)种方法。(2)如果不把它放到位置n，那么对于剩下的n-1个元素有f(n-1)种方法。
综上所述，错排公式为:f(n) = (n-1) f(n-2) + (n-1)f(n-1)=(n-1) [f(n-2) + f(n-1)]
有了错排公式，这道题就很容易解决了，总的排列方法数有n的阶乘个，而全部错排的方法数有 (n-1) [f(n-2) + f(n-1)]个，最后直接把错排方法数除以总的排列数，然后注意输出格式就可以了。
解题代码如下：
#include<stdio.h>
int main()
{
int m;
scanf("%d",&m);
while(m--)
{
long long a[100],sum=1;
int i,j,n;
scanf("%d",&n);
a[1]=0;
a[2]=1;
if(n>2)
{
for(i=3;i<=n;i++)
{
a[i]=(i-1)*((a[i-1]+a[i-2]));
}
}
for(i=1;i<=n;i++)
{
sum=sum*i;
}
printf("%.2lf%%\n",(double)a[n]/sum*100);
}
return 0;
}
还有道题目：http://acm.hdu.edu.cn/showproblem.php?pid=2049
不容易系列之(4)——考新郎
这道题和上面类似，也用到错排公式，不同的是他不一定需要把全部实例错排，在给出总共m对夫妇后要求指定其中n个新郎找错新娘的方法数。解题思路是先用数学的排列组合知识求出从n对夫妇中随机挑出的(m-n)个新郎和新娘配对成功的方法数，即,然后求n个新郎没有和新娘配对成功的方法数，即a[i]=(i-1)*((a[i-1]+a[i-2]))，最后两个数相乘便可以得到结果。
解题代码如下:
#include<stdio.h>
int main()
{
int k;
scanf("%d",&k);
while(k--)
{
long long a[25];
long long sum1=1,sum2=1,p,i;
int m,n;
scanf("%d%d",&m,&n);
a[1]=0;
a[2]=1;
if(n>2)
{
for(i=3;i<=n;i++)
{
a[i]=(i-1)*((a[i-1]+a[i-2]));
}
}
if(m==n)
{
printf("%lld\n",a[n]);
}
else
{
p=m;
for(i=1;i<=m-n;i++)
{
sum1=sum1*p;
p=p-1;
}
for(i=1;i<=m-n;i++)
{
sum2=sum2*i;
}
printf("%lld\n",sum1/sum2*a[n]);
}
}
return 0;
}
通过这道题除了学习了重要的错排公式之外，还要注意在写这种题时要把变量类型设置为long long型，以免数值太大超过int的范围！
