CF2192F Fish Fight

在一个池塘中，有 $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

每个测试点包含若干组测试数据。第一行为测试用例数 $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$。

对于每组测试数据，输出一行一个整数，表示 Alice 获胜的概率对 $10^9+7$ 取模的结果。

在第一个测试点，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$。 由 ChatGPT 5 翻译