A16771. Fish Fight
编程题
省选/NOI-
知识点
题目描述
在一个池塘中，有 $n$ 条鱼排成一排。对于每条鱼 $i$，其体型为 $a_i$，任何吃掉它的鱼体型将增加 $b_i$。
Alice 选择第 $x$ 条鱼，Bob 选择第 $y$ 条鱼。两人轮流操作，首先由 Alice 所选的鱼行动。每位玩家的操作回合中，其所选的鱼当前体型为 $p$。这条鱼会吃掉一条相邻且体型不超过自己的鱼 $q$。如果存在多条满足条件的鱼，则等概率地随机选一条吃掉。吃掉后体型增加被吃鱼的 $b_i$。
如果到了某条鱼回合开始时无法吃掉任意相邻的鱼，则该鱼被其相邻的鱼吞食（位于端点的鱼只会被唯一的邻居吃，内部的鱼会被任一邻居吃）。如果 Alice 的鱼被吃掉（无论是被 Bob 的鱼还是被其他邻居鱼吃掉），Alice 立即输掉。同理，Bob 的鱼被吃掉，Bob 立即输掉。
现已知 Alice 和 Bob 各自选择的鱼，计算 Alice 获胜的概率，对 $10^9+7$ 取模。
更正式地说，设 $M=10^9+7$。结果可表示为不可约分数 $\frac{p}{q}$，且 $q \not\equiv 0 \pmod M$。请输出 $p\,q^{-1} \bmod M$，即唯一满足 $0\le x<M$ 且 $xq\equiv p\pmod M$ 的整数 $x$。
Alice 选择第 $x$ 条鱼，Bob 选择第 $y$ 条鱼。两人轮流操作，首先由 Alice 所选的鱼行动。每位玩家的操作回合中，其所选的鱼当前体型为 $p$。这条鱼会吃掉一条相邻且体型不超过自己的鱼 $q$。如果存在多条满足条件的鱼，则等概率地随机选一条吃掉。吃掉后体型增加被吃鱼的 $b_i$。
如果到了某条鱼回合开始时无法吃掉任意相邻的鱼，则该鱼被其相邻的鱼吞食（位于端点的鱼只会被唯一的邻居吃，内部的鱼会被任一邻居吃）。如果 Alice 的鱼被吃掉（无论是被 Bob 的鱼还是被其他邻居鱼吃掉），Alice 立即输掉。同理，Bob 的鱼被吃掉，Bob 立即输掉。
现已知 Alice 和 Bob 各自选择的鱼，计算 Alice 获胜的概率，对 $10^9+7$ 取模。
更正式地说，设 $M=10^9+7$。结果可表示为不可约分数 $\frac{p}{q}$，且 $q \not\equiv 0 \pmod M$。请输出 $p\,q^{-1} \bmod M$，即唯一满足 $0\le x<M$ 且 $xq\equiv p\pmod M$ 的整数 $x$。
输入格式
每个测试点包含若干组测试数据。第一行为测试用例数 $t$（$1 \le t \le 500$）。
每组测试数据第一行为一个整数 $n$（$2 \le n \le 3000$），表示池塘中的鱼的数量。
第二行包含两个整数 $x$ 和 $y$（$1 \le x,y \le n$；$x \neq y$），表示 Alice 和 Bob 分别选择的鱼的编号。
第三行包含 $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$。
每组测试数据第一行为一个整数 $n$（$2 \le n \le 3000$），表示池塘中的鱼的数量。
第二行包含两个整数 $x$ 和 $y$（$1 \le x,y \le n$；$x \neq y$），表示 Alice 和 Bob 分别选择的鱼的编号。
第三行包含 $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$ 取模的结果。
输入输出样例
输入 #1
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
输出 #1
0 1 500000004 750000006 375000003 687500005
说明/提示
在第一个测试点，Alice 的鱼无法吃到任何相邻的鱼，所以 Alice 一定会输。
在第二个测试点，Alice 的鱼只有一个相邻的鱼，就是 Bob 的鱼，且 Alice 的鱼体型大于等于 Bob 的鱼体型，因此 Alice 必胜。
在第三个测试点，第一回合 Alice 选择的鱼可以吃掉两条相邻的鱼。
情况 1：吃掉第 3 条鱼（Bob 的鱼），Alice 获胜。
情况 2：吃掉第 1 条鱼。接下来 Alice 的鱼体型变为 $a_2 + b_1 = 4+0=4$。这样第二回合 Bob 的鱼会马上吃掉 Alice 的鱼，Alice 输。
两种情况发生的概率均为 $\frac{1}{2}$，所以 Alice 获胜的概率是 $0.5$。
在第四个测试点里，Alice 获胜的概率是 $0.75$。
在第二个测试点，Alice 的鱼只有一个相邻的鱼，就是 Bob 的鱼，且 Alice 的鱼体型大于等于 Bob 的鱼体型，因此 Alice 必胜。
在第三个测试点，第一回合 Alice 选择的鱼可以吃掉两条相邻的鱼。
情况 1：吃掉第 3 条鱼（Bob 的鱼），Alice 获胜。
情况 2：吃掉第 1 条鱼。接下来 Alice 的鱼体型变为 $a_2 + b_1 = 4+0=4$。这样第二回合 Bob 的鱼会马上吃掉 Alice 的鱼，Alice 输。
两种情况发生的概率均为 $\frac{1}{2}$，所以 Alice 获胜的概率是 $0.5$。
在第四个测试点里，Alice 获胜的概率是 $0.75$。