#P18877. [2026多校联测]花海

[2026多校联测]花海

花海

题目背景

天空仍灿烂 它爱着大海

情歌被打败 爱已不存在

题目描述

果果前段时间刚刚认识了一些花,她想采一些花做一片花海。

由于果果还小,她只认识 nn 种花,每种花的花瓣数量为 aia_i。注意,由于每种花的区别不止在于花瓣数量,所以可能会存在不同种类的花 aia_i 相同。

果果一共采了 mm 朵花,她知道第 ii 朵花每天会掉落 did_i 瓣花瓣,即每 1di\frac{1}{d_i} 天掉落一瓣花瓣。那么每朵花都终有一天会凋零。果果感到非常伤心,于是她只想知道恰好一半的花凋零是什么时候,即第 m+12\frac{m+1}{2} 朵凋零的花的时间。注意时间可以不是整数。为了简化题目,保证 mm 是奇数。

但是果果突然发现,她不记得她采摘的 mm 朵花分别有多少花瓣了。她只能认为每朵花都有 1n\frac{1}{n} 的概率有 aia_i 瓣花瓣。她也转为让你求恰好一半的花凋零的时间的期望。答案对 109+710^9+7 取模。

输入格式

第一行两个正整数 n,mn,m,表示花的种数和采摘的花的数量。

第二行 nn 个正整数,表示每种花的花瓣数量。

第三行 mm 个正整数,表示每朵花的每天掉落的花瓣数。

输出格式

输出一行一个整数,表示时间的期望对 109+710^9+7 取模的结果。

输入输出样例 #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

说明/提示

【样例解释】

对于第一个样例,三朵花每天分别凋零 1,2,31, 2, 3 瓣,考虑三朵花分别的花瓣数量:

  • 4,4,44, 4, 4:t=2t=2 的时候,三朵花剩余的瓣数分别为 2,0,02, 0, 0,恰好有两朵花凋谢。
  • 4,4,54, 4, 5:t=2t=2 的时候,三朵花剩余的瓣数分别为 2,0,02, 0, 0,恰好有两朵花凋谢。
  • 4,5,44, 5, 4:t=2.5t=2.5 的时候,三朵花剩余的瓣数分别为 1.5,0,01.5, 0, 0,恰好有两朵花凋谢。
  • (4,5,5)(4, 5, 5), (5,4,4)(5, 4, 4), (5,4,5)(5, 4, 5), (5,5,4)(5, 5, 4), (5,5,5)(5, 5, 5) 的时候同理,恰好有两朵花凋谢的时间分别为 t=2.5t=2.5, t=2t=2, t=2t=2, t=2.5t=2.5, t=2.5t=2.5。

综上,期望时间为 $\frac{2 + 2 + 2.5 + 2.5 + 2 + 2 + 2.5 + 2.5}{8} = \frac{9}{4}$,输出 9⋅4−1 mod (109+7)=2500000049 \cdot 4^{-1} \bmod (10^9+7) = 250000004。

【更多样例】

见附加样例。

三个样例分别对应测试点 6,13,166,13,16 的数据范围及性质。

【数据范围】

对于 100%100\% 的数据,保证 1≤n,m≤5001\le n,m\le 500,且 mm 是奇数,1≤ai,di≤1091\le a_i,d_i\le 10^9。

测试点编号 n,mn,m 特殊性质
1∼21\sim 2 ≤6\le 6 无
3∼53\sim 5 ≤10\le 10
6∼126\sim 12 ≤100\le 100
13∼1513\sim 15 ≤500\le 500 di=1d_i=1
16∼2016\sim 20 无