“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part2（D——数学公式+分数取模）

D.扔硬币（数学公式+分数取模）

题意：

有n枚硬币，已知至少有m枚硬币是反面，求恰好有k枚硬币是正面的概率。

对于结果是p/q，输出分数取模1e9+7后的结果。

思路：

首先很容易可以知道，当m+k>n时，题目中描述的情况是不存在的，直接输出0即可。

接下来考虑其他合法的情况：问题是在至少m枚硬币是反面的前提下，恰好有k枚硬币是正面的概率。

假设事件A是至少m枚硬币是反面，事件B是恰好有k枚硬币是正面，所以答案就是
$ $P（B|A）=P（AB）/P(A)$ $

因为P（AB）和P(A)的分母都是总事件，所以就可以约掉，问题就可以转化为方案数了（应该是高中知识，比赛时没想到）

分子即A和B同时成立的方案数就是相当于n枚硬币里恰好有k枚硬币是正面，为C（n,k）;

分母即A单独成立的方案数不是很好求，因为题目要求的是至少m枚硬币是反面，我们可以用总的方案数减去不合法的情况C，C就是有x枚硬币是反面而且x<m的所有情况，总的方案数是2^n。

关于组合数的求解可看：传送门

最后的一步就是如何处理p/q%mod，这就是相当于p*q的逆元%mod；

代码：（拼音变量哈哈哈）

参考博客：