hdu 4336 Card Collector (2012多校 #4) (容斥原理模板题)

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

题意:有n种卡片,买一包干脆面得到第i种卡片的概率是p[i],每包干脆面最多有一张卡片,问收集齐所有卡片要买的干脆面的包数的数学期望。

思路:容斥模板题。1.0/p[i]就是拿到某张卡片需要买的包数的数学期望

注意体会这种具体应用容斥的模拟方法,把1<<n转化成二进制来模拟有1个元素的集合,有2个元素的集合…有n个元素的集合。
核心代码:

 

20160305update:前几天有道题没写递归形式tle掉了。。。所以来学习一下容斥原理的递归形式。

以及这道题用递归的形式写了一遍。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz