#P18877. [2026多校联测]花海
[2026多校联测]花海
花海
题目背景
天空仍灿烂 它爱着大海
情歌被打败 爱已不存在
题目描述
果果前段时间刚刚认识了一些花,她想采一些花做一片花海。
由于果果还小,她只认识 种花,每种花的花瓣数量为 。注意,由于每种花的区别不止在于花瓣数量,所以可能会存在不同种类的花 相同。
果果一共采了 朵花,她知道第 朵花每天会掉落 瓣花瓣,即每 天掉落一瓣花瓣。那么每朵花都终有一天会凋零。果果感到非常伤心,于是她只想知道恰好一半的花凋零是什么时候,即第 朵凋零的花的时间。注意时间可以不是整数。为了简化题目,保证 是奇数。
但是果果突然发现,她不记得她采摘的 朵花分别有多少花瓣了。她只能认为每朵花都有 的概率有 瓣花瓣。她也转为让你求恰好一半的花凋零的时间的期望。答案对 取模。
输入格式
第一行两个正整数 ,表示花的种数和采摘的花的数量。
第二行 个正整数,表示每种花的花瓣数量。
第三行 个正整数,表示每朵花的每天掉落的花瓣数。
输出格式
输出一行一个整数,表示时间的期望对 取模的结果。
输入输出样例 #1
2 3
4 5
1 2 3
250000004
输入输出样例 #2
3 3
4 5 6
1 2 3
500000006
输入输出样例 #3
5 5
4 5 6 10 2
1 2 3 2 4
434986672
说明/提示
【样例解释】
对于第一个样例,三朵花每天分别凋零 瓣,考虑三朵花分别的花瓣数量:
- : 的时候,三朵花剩余的瓣数分别为 ,恰好有两朵花凋谢。
- : 的时候,三朵花剩余的瓣数分别为 ,恰好有两朵花凋谢。
- : 的时候,三朵花剩余的瓣数分别为 ,恰好有两朵花凋谢。
- , , , , 的时候同理,恰好有两朵花凋谢的时间分别为 , , , , 。
综上,期望时间为 $\frac{2 + 2 + 2.5 + 2.5 + 2 + 2 + 2.5 + 2.5}{8} = \frac{9}{4}$,输出 。
【更多样例】
见附加样例。
三个样例分别对应测试点 的数据范围及性质。
【数据范围】
对于 的数据,保证 ,且 是奇数,。
| 测试点编号 | 特殊性质 | |
|---|---|---|
| 无 | ||
| 无 |