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

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

题解：

题意：求随机排列的期望循环个数。分析：【引理 1】对于一个随机排列的某个元素，处在一个长度为 k 的循环中的概率为 1/n（与循环的长度无关）。证明：方法一：考察某个元素处在长度为 k 的循环中的方案数，有：

C(k-1,n-1)(k-1)!(n-k)!=n-1比上总的方案数得到概率。

(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] = H[n] （调和级数）对于调和级数，可以较小项暴力，较大项时用 log() 近似。

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

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std ;double dp[1000005] ;int main(){    dp[1]=1.0 ;    for(int i=2 ;i<=1000000 ;i++)        dp[i]=dp[i-1]+1.0/i ;    int n ;     while(~scanf("%d",&n))    {        if(n>1000000)printf("%.4f\n",0.57721566490153286060651209+log(n+1)) ;        else printf("%.4f\n",dp[n]) ;    }    return 0 ;}

View Code

HDU 4986