← 返回题目列表

Codeforces · 2192/F

F. 鱼斗

中文机器翻译题面 查看原题

在一个池塘里,$$$n$$$ 条鱼排成一排。对于每条鱼 $$$i$$$,其大小为 $$$a_i$$$,任何吃掉它的鱼都会增长 $$$b_i$$$。

Alice 挑鱼 $$$x$$$,Bob 挑鱼 $$$y$$$。他们轮流从爱丽丝的鱼开始。在每个玩家的回合中,让他们的鱼的大小为 $$$p$$$。该鱼将吃掉大小为 $$$q$$$ 且满足 $$$p \geq q$$$ 的相邻鱼。如果存在不止一条这样的鱼,它会在其中均匀随机选择。吃东西会增加其体积 吃过 鱼的$$$b_i$$$。

如果在回合开始时,一条鱼不能吃掉任何相邻的鱼,它就会被其邻居吃掉(端点处的鱼有一个邻居;内部的鱼有两个)。如果爱丽丝的鱼被吃掉了(要么被鲍勃的鱼吃掉,要么被她邻近的鱼吃掉),她立即就输了。同样,如果鲍勃的鱼被吃掉(无论是被爱丽丝的鱼还是被他邻近的鱼吃掉),他就会立即失败。

给定 Alice 和 Bob 选择的鱼,计算 Alice 获胜的概率,以 $$$10^9+7$$$ 为模。

更正式地说,令$$$M=10^9+7$$$。答案可以写成不可约分数 $$$\frac{p}{q}$$$ 其中 $$$q \not\equiv 0 \pmod M$$$。输出$$$p \, q^{-1} \bmod M$$$,唯一整数$$$x$$$,其中$$$0 \le x \lt M$$$ 和$$$x q \equiv p \pmod M$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — 池塘中鱼的数量。

第二行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x,y \le n$$$; $$$x \neq y$$$)。

第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

第四行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,输出一个整数,即 Alice 获胜的概率以 $$$10^9 + 7$$$ 为模。

示例

输入
复制

6
2
1 2
1 2
1 1
2
1 2
2 1
1 1
3
2 3
1 4 4
0 1 1
5
4 2
2 6 5 5 3
1 2 1 3 2
7
3 5
1 1 1 1 1 1 1
0 0 0 0 0 0 1
10
8 3
2 5 9 3 8 4 5 6 2 7
1 3 5 2 7 3 4 2 2 3

输出
复制

0
1
500000004
750000006
375000003
687500005

注意

在第一个测试用例中,爱丽丝的鱼不能吃任何相邻的鱼,因此爱丽丝总是输。

在第二个测试用例中,Alice 的鱼只有一条相邻的鱼,即 Bob 的鱼,由于 Alice 的鱼大小大于或等于 Bob 的鱼大小,Alice 总是获胜。

在第三个测试用例中,在第一个回合中,爱丽丝的鱼可以吃掉相邻的鱼。

案例$$$1$$$:它吃鱼$$$3$$$(鲍勃的鱼)。爱丽丝赢了。

案例$$$2$$$:它吃鱼$$$1$$$。 Alice 的鱼的新大小将为 $$$a_2 + b_1 = 4 + 0 = 4$$$。这会导致鲍勃的鱼在第二回合总是吃掉爱丽丝的鱼。爱丽丝输了。

两种情况的可能性相同,因此 Alice 获胜的概率为 $$$0.5$$$

在第四个测试用例中,Alice 获胜的概率为 $$$0.75$$$