Uestc(CdOj) 1888(New 747) Birthday party

08/22/2014

组合数学的题。

题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25539#problem/G←可以点= =

一句话题意:给定N个点,每个点随机向自己以外的点连一条线,询问恰好存在一个K元环的概率。

 

思路在这里ww:

 

首先我们来考虑  至少有一个环  的概率,

我们从N个点中选出K个点,来组成一个K元环,剩下的点随意连……

显然答案为:{\frac{C_{n}^{k}*(k-1)!*(n-1)^{n-k}}{(n-1)^n}}

稍微化个简:{\frac{C_{n}^{k}*(k-1)!}{(n-1)^k}}

 

至此我们已经可以稍微得到一些思路了:

分别算出 至少有1~[n/k]个环的概率  ,然后做一次容斥即可得出结果。

按照类似如上的的思路,我们不难算出   至少存在m个环的概率  

{\frac{n!}{m!*(n-mk)!*k^m*(n-1)^{mk}}}

 

倘若我们设 F[i] 为至少存在 i 个K元环的概率的话,

显然有 ANS=F[1]-F[2]+F[3]-F[4]+……(+-)F[n/k]。

注意到直接每次暴力运算F[i]会超时,不难发现我们可以通过 F[i+1]/F[i]的値以O(i)的时间来求出F[i],

这样均摊起来时间为O(n)的。

只要代码实现不是很丑即可AC啦~。

 

/w\调完代码高亮功能就来贴代码【雾