poj 1322 chocolate (指数型母函数 )

http://poj.org/problem?id=1322
题意:

 

 

思路:别看n,m很大。。。但是想一下。。m显然不可能大于c(如果大于c,那么根据抽屉原理,至少存在一种巧克力大于一个,然而大于一个就会被取走…矛盾)   这样概率为0.m也不可能大于n,因为最好的情况就是取出的巧克力都放在了桌子上,如果总共取的还不到n个,又怎么可能剩下m(m>n)个呢。此外,还需要n,m奇偶性相同,否则设n-m=2K+1 ,说明如果要剩余m个,那么就要减少2k+1个,但是巧克力是两个两个减少的,减少的个数一定是偶数,因此矛盾。所以n,m奇偶性相同。

 

接下来可以用概率dp做,由于n比较大,滚动一下应该可以… 然后看到别人的题解里写到当n>1000的时候已经趋向平衡(达到了要求的精度)… 这道题dp写起来的确容易,也不是很难想。

不过作为dp废宁愿选择数学方法,指数型母函数。

 

分析可知,取过偶数次的巧克力消失,只有取过奇数次的巧克力会留在桌子上。

那么要剩余m个巧克力,也就是有m种巧克力取了奇数次,剩下的c-m种巧克力取了偶数次。

对应的的生成函数(母函数)分别是(e^x-e(-x))/2和(e^x+e(-x))/2  (推倒类似)hdu2065红色病毒解题报告

总事件个数为c^n

根据古典概型,所求概率为 (Gn*n!*C[c][m])/(c^n)  其中Gn*n!为生成函数,C[c][m]是因为不确定c种巧克力中的哪m种取了奇数个。

现在的问题就成了求Gn中x^n的系数。。我就是因为这个卡了两天这道题。。。

 

其实模拟就好,复杂度O(c^2)而已。。主要是好久没写二项式定理。。。有点忘了(手动智力-2)

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz