2051. Yes, Indeed...

时间限制 2000 ms   内存限制 256 MB

火已渐熄,而位不见王影

世界危在旦夕,为了拯救世界,你必须去传火。但在此之前,你必须依次点亮 $n$ 座营火。在每次行动中,如果你已经点燃了前 $i$ 座营火,你将尝试点燃第 $i + 1$ 座营火。但是很不幸的是,由于初火微弱,已经点燃的营火可能会熄灭。具体的,一座处于点燃状态的编号为 $i$ 的营火可能在两种情况下熄灭:

  1. 你刚选择了这座营火进行点燃,则它在被点燃后有 $p_i$ 的概率立即熄灭。
  2. 第 $i + 1$ 座营火刚刚因为你的本次行动熄灭(1、2两种情况引起的熄灭都算),则这座营火有 $p_i$ 的概率熄灭。

简单地说,可以认为你每次点燃一座营火后,你最近点燃的若干座营火可能会熄灭(可能为0座)。

请问要想点燃所有营火(在结算完每次行动后的熄灭后),你的期望行动次数是多少?由于答案可能很大,你只需要输出答案对 $10^9+7$ 取模的结果。
假设答案是 $\frac {p}{q}$ ( $p$ 与 $q$ 互质),你只需要输出 $p * (q$ 的逆元$)$,即 $\frac {p}{q} \equiv p * q ^ {m - 2} (mod \ m)$

灰烬大人,登上王座吧!

输入数据

本题包含多组数据。
第一行包含一个正整数 $T (1 \leq T \leq 4000) $,表示接下来有 $T$ 组测试点。

每组数据有三行:
第一行包含一个正整数 $n (2 \leq n \leq 2*10^5)$ ,表示营火的总数。
第二行包含n个正整数 $a_1, a_2...a_n (0 \leq a_i \leq 10^9)$
第三行包含n个正整数 $b_1, b_2...b_n (1 \leq b_i \leq 10^9)$
题目中所述 $p_i=a_i/b_i$ ,且保证 $(0 \leq p_i < 1)$

保证 $\sum n \leq 2*10^5$

输出数据

对于每组数据,输出一行,表示你的期望行动次数对 $10^9+7$ 取模的结果。

样例输入

复制
2
2
0 1
1 2
3
2 0 1
3 1 2 \n
 \n
 · \n
 · \n
 \n
 · · \n
 · · \n

样例输出

复制
3
6 \n
 \n

提交

请先 登录

© 2024 FAQs Contact About