CF1623D Robot Cleaner Revisit

本题与 A 题有许多相似之处。不同之处在于本题引入了概率，并且约束条件也有所不同。 一个机器人清洁器被放置在一个由墙壁包围的矩形房间的地板上。地板由 $n$ 行 $m$ 列组成。地板的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $r$ 行第 $c$ 列的格子记作 $(r, c)$。机器人的初始位置为 $(r_b, c_b)$。 每一秒，机器人会移动 $dr$ 行和 $dc$ 列，即一秒后，机器人会从格子 $(r, c)$ 移动到 $(r + dr, c + dc)$。初始时 $dr = 1$，$dc = 1$。如果移动方向上遇到垂直墙壁（左墙或右墙），则在移动前 $dc$ 取反，即 $dc$ 变为 $-dc$。如果遇到水平墙壁（上墙或下墙），则在移动前 $dr$ 取反，即 $dr$ 变为 $-dr$。 每一秒（包括机器人开始移动前的那一刻），机器人会清洁其所在位置的同一行和同一列的所有格子。只有一个脏格子，位于 $(r_d, c_d)$。机器人的任务是清洁这个脏格子。 经过 A 题中的多次测试后，机器人现在坏了。它仍然按照上述方式清洁地板，但每一秒只有概率 $\frac{p}{100}$ 执行清洁操作，概率 $1 - \frac{p}{100}$ 不执行清洁操作。每一秒是否清洁是相互独立的。 给定地板的大小 $n$ 和 $m$，机器人的初始位置 $(r_b, c_b)$，脏格子的位置 $(r_d, c_d)$，以及清洁概率 $p$，求机器人完成任务所需的期望时间。 可以证明，答案可以表示为最简分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 是整数，且 $y \not\equiv 0 \pmod{10^9 + 7}$。输出等于 $x \cdot y^{-1} \bmod (10^9 + 7)$ 的整数。换句话说，输出一个整数 $a$，满足 $0 \le a < 10^9 + 7$ 且 $a \cdot y \equiv x \pmod{10^9 + 7}$。

每组测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10$）。接下来是每个测试用例的描述。 每个测试用例仅包含一行，包含 $n$、$m$、$r_b$、$c_b$、$r_d$、$c_d$ 和 $p$（$4 \le n \cdot m \le 10^5$，$n, m \ge 2$，$1 \le r_b, r_d \le n$，$1 \le c_b, c_d \le m$，$1 \le p \le 99$）——房间的大小、机器人的初始位置、脏格子的位置以及清洁的概率（百分比）。

对于每个测试用例，输出一个整数——机器人清洁脏格子的期望时间，结果对 $10^9 + 7$ 取模。

在第一个测试用例中，机器人每一秒都有机会清洁脏格子。利用[几何分布](https://en.wikipedia.org/wiki/Geometric_distribution)，可以得出清洁成功率为 $25\%$ 时，期望尝试次数为 $\frac{1}{0.25} = 4$。但由于机器人第一次有机会清洁是在开始移动前，所以答案是 $3$。  第一个样例的示意图。蓝色圆弧为机器人，红色星号为目标脏格子，紫色方块为机器人的初始位置。每一秒机器人有机会清洁一行一列，用黄色条纹表示。 在第二个测试用例中，棋盘大小和位置不同，但机器人每一秒仍有机会清洁脏格子，且清洁概率相同。因此答案与第一个样例相同。  第二个样例的示意图。 第三和第四个样例几乎相同，唯一的区别是脏格子和机器人的位置互换。但两种情况下的运动轨迹完全相同，因此结果也相同。 由 ChatGPT 4.1 翻译