Blog·Tanky WooABOUTRSS

HDOJ 2048 神、上帝以及老天爷

27 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2048

这里用到了错排公式。

代码:

 // Author: Tanky Woo
// HDOJ: 2048
#include 
using namespace std;
__int64 fib[22];
__int64 pala[22];
int nCases;
int main()
{
    pala[1] = 0;
    pala[2] = 1;
    fib[1] = 1;
    fib[2] = 2;
    for(int i = 3; i < 22; ++i)
    {
        pala[i] = (i-1)*(pala[i-1]+pala[i-2]);
        fib[i] = fib[i-1]*i;
    }
    scanf("%d", &nCases;);
    int n;
    while(nCases--)
    {
        scanf("%d", &n;);
        printf("%.2lf%%\n", ((double)pala[n])/fib[n]*100.0);
    }
    return 0;
}

===================================================

错排公式:

pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?   这个问题推广一下,就是错排问题: n个有序的元素应有n!种不同的排列。如若一个排列式的所有的元素都不在原来的位置上,则称这个排列为错排。   下面用递推的方法推导错排公式:   当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.   第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;   第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;   综上得到   M(n)=(n-1)[M(n-2)+M(n-1)]   特殊地,M(1)=0,M(2)=1