| Codeforces Round 763 (Div. 2) |
|---|
| Закончено |
Условие задачи имеет много общего с задачей 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$$$.
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
3 3 15 15 332103349 99224487
В первом примере у робота есть возможности очистить грязную клетку каждую секунду. Используя геометрическое распределение, мы можем вычислить, что при вероятности успеха $$$25\%$$$ ожидаемое количество попыток очистить грязную клетку равно $$$\frac 1 {0.25} = 4$$$. Но так как первая попытка очистки выполняется до первого движения робота, то ответ равен $$$3$$$.
Иллюстрация к первому примеру. Робот обозначен голубой дугой. Красной звездой обозначена грязная клетка. Каждую секунду робот с некоторое вероятностью может очистить строку и столбец, что показано желтыми линиями. Во втором примере размеры доски и позиции другие, но робот все еще имеет возможность очистить строку и столбец каждую секунду с той же вероятность. Поэтому ответ такой же, как и в первом примере.
Иллюстрация ко второму примеру. Третий и четвертый примеры почти одинаковые. Единственное отличие — позиции робота и грязной клетки поменяны местами. Однако движения в этих двух примерах одинаковые, поэтому результат тоже одинаковый.
