首页 > 代码库 > HDU 4986

HDU 4986

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

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

题解:

题意:求随机排列的期望循环个数。分析:【引理 1】对于一个随机排列的某个元素,处在一个长度为 k 的循环中的概率为 1/n(与循环的长度无关)。证明:方法一:考察某个元素处在长度为 k 的循环中的方案数,有:
(n1k1)(k1)!(nk)!=(n1)
C(k-1,n-1)(k-1)!(n-k)!=n-1比上总的方案数得到概率。
(n1)!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[ni]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