HDU 4986

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

题意：n个钥匙放在n个箱子里，每个钥匙和箱子一一对应，求打开所有箱子的期望

题解：

题意：

求随机排列的期望循环个数。

分析：

【引理 1】对于一个随机排列的某个元素，处在一个长度为 k 的循环中的概率为 1/n（与循环的长度无关）。

证明：

方法一：

考察某个元素处在长度为 k 的循环中的方案数，有：

(n−1k−1)(k−1)!(n−k)!=(n−1)

C(k-1,n-1)(k-1)!(n-k)!=n-1

比上总的方案数得到概率。

(n−1)!n!=1n

(n-1)!/n!=1/n

方法二：

。。。

我们可以用第一题的方法，将每个排列写成 Cycle Notation，并将每个循环中最小的元素放在末尾。

那么每一个排列的 Cycle Notation 和另一个排列可以建立起一一对应。而 1 处在的循环中的长度等于它在排列中的位置，因此所有长度的概率都是 1n。

考虑 dp 。。设 e[n] 表示长度为 n 的排列的循环个数的期望。。我们枚举其中一个循环的长度。根据期望可加。。有。。。

e[n]=(Σi=1^n*e[n-i])/n

 e[n]=∑i=1ne[n−i]n

也就是 e[n] = H[n] （调和级数）

对于调和级数，可以较小项暴力，较大项时用 log() 近似。

调和级数的近似公式是ln(n+1)+r，r为欧拉常数，近似值是0.57721566490153286060651209

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std ;

double dp[] ;

int main()

{

    dp[]=1.0 ;

    for(int i= ;i<= ;i++)

        dp[i]=dp[i-]+1.0/i ;

    int n ;

    while(~scanf("%d",&n))

    {

        if(n>)printf("%.4f\n",0.57721566490153286060651209+log(n+)) ;

        else printf("%.4f\n",dp[n]) ;

    }

    return  ;

}