#P10690. 猫头鹰幸运之水
猫头鹰幸运之水
题目描述
有 种幸运事件与 个主线事件。每一步从当前可能发生的事件中等概率选一个,且本步只发生这个事件。每种幸运事件始终可以被选中,每个主线事件只能发生一次,发生后从候选集合中移除。
第 种幸运事件累计发生次数一旦超过 ,过程立即失败,此时无聊值为 。若没有失败,过程在全部主线事件发生后结束。此时无聊值等于连续发生幸运事件的最长段的长度。一段内可以包含不同种类的幸运事件。
求无聊值恰好为 的概率。按整个过程的原始概率计算,失败轨迹也属于概率空间。
输入格式
第一行三个正整数 。第二行 个正整数 。
输出格式
输出一行一个整数,表示所求概率对 取模的结果。若概率为分数 ,输出 。
样例 1
2 2 2
1 1
891203710
两种幸运事件必须分别发生一次且彼此连续。若它们都发生在第一个主线事件之前,有四种事件顺序,每种概率为 。若它们发生在两个主线事件之间,也有四种顺序,每种概率为 。总概率为 。
样例 2
1 2 2
2
453703707
样例 3
10 27 89
10 5 1 20 8 2 6 16 19 16
313780715
数据范围
,,,。
| 分值占比 | 附加限制 |
|---|---|
| 10% | |
| 20% | ,, |
| ,, | |
| 10% | |
| 40% | 无 |