#P10690. 猫头鹰幸运之水

    ID: 9808 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-指数生成函数计数 DP概率 DP前缀和优化 DP滚动数组模逆元

猫头鹰幸运之水

题目描述

有 nn 种幸运事件与 mm 个主线事件。每一步从当前可能发生的事件中等概率选一个,且本步只发生这个事件。每种幸运事件始终可以被选中,每个主线事件只能发生一次,发生后从候选集合中移除。

第 ii 种幸运事件累计发生次数一旦超过 cic_i,过程立即失败,此时无聊值为 00。若没有失败,过程在全部主线事件发生后结束。此时无聊值等于连续发生幸运事件的最长段的长度。一段内可以包含不同种类的幸运事件。

求无聊值恰好为 kk 的概率。按整个过程的原始概率计算,失败轨迹也属于概率空间。

输入格式

第一行三个正整数 n,m,kn,m,k。第二行 nn 个正整数 c1,…,cnc_1,\ldots,c_n。

输出格式

输出一行一个整数,表示所求概率对 109+710^9+7 取模的结果。若概率为分数 a/ba/b,输出 a⋅b−1 mod (109+7)a\cdot b^{-1}\bmod(10^9+7)。

样例 1

2 2 2
1 1
891203710

两种幸运事件必须分别发生一次且彼此连续。若它们都发生在第一个主线事件之前,有四种事件顺序,每种概率为 1/1921/192。若它们发生在两个主线事件之间,也有四种顺序,每种概率为 1/1081/108。总概率为 25/43225/432。

样例 2

1 2 2
2
453703707

样例 3

10 27 89
10 5 1 20 8 2 6 16 19 16
313780715

数据范围

1≤n≤1001\le n\le100,1≤m≤10001\le m\le1000,1≤ci≤201\le c_i\le20,1≤k≤∑ici1\le k\le\sum_i c_i。

分值占比 附加限制
10% 1≤n,m,ci≤31\le n,m,c_i\le3
20% 1≤n≤201\le n\le20,1≤m≤41\le m\le4,1≤ci≤41\le c_i\le4
1≤n≤61\le n\le6,1≤m≤10001\le m\le1000,1≤ci≤201\le c_i\le20
10% k=∑icik=\sum_i c_i
40% 无

原 PDF 题面