这个问题的表述和问题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)$$$,找到机器人完成工作的预期时间。
可以证明,答案可以表示为不可约分数 $$$\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$$$ 为模。
示例
输入 #1
6 2 2 1 1 2 1 25 3 3 1 2 2 2 25 10 10 1 1 10 10 75 10 10 10 10 1 1 75 5 5 1 3 2 2 10 97 98 3 5 41 43 50
输出 #1
3 3 15 15 332103349 99224487
注意
在第一个测试用例中,机器人每秒都有机会清洁脏单元。利用几何分布,我们可以发现,在成功率为$$$25\%$$$的情况下,清除脏单元的预期尝试次数为$$$\frac 1 {0.25} = 4$$$。但因为机器人第一次有机会清洁单元是在机器人开始移动之前,所以答案是 $$$3$$$。
第一个示例的插图。蓝色弧线是机器人。红星是目标污垢细胞。紫色方块是机器人的初始位置。机器人每秒都有机会清洁一行和一列,以黄色条纹表示。
在第二个测试用例中,板子尺寸和位置不同,但机器人仍然有机会每秒清洁脏单元,并且具有相同的清洁概率。因此答案与第一个例子相同。
第二个示例的插图。
第三种情况和第四种情况几乎是一样的。唯一的区别是脏单元和机器人的位置交换了。但两种情况下的运动是相同的,因此结果相同。