Codeforces Round 510 (Div. 2) |
---|
Закончено |
У Васи есть волшебная матрица $$$a$$$ размера $$$n \times m$$$. Строки матрицы нумеруются от $$$1$$$ до $$$n$$$ сверху вниз, столбцы матрицы нумеруются от $$$1$$$ до $$$m$$$ слева направо. Обозначим как $$$a_{ij}$$$ элемент, находящийся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца.
Также у Васи есть фишка. Изначально фишка находится на пересечении $$$r$$$-й строки и $$$c$$$-го столбца (то есть в ячейке со значением $$$a_{rc}$$$). Вася выполняет следующую процедуру до тех пор, пока это возможно: среди всех ячеек матрицы, в которых значение меньше, чем в ячейке, содержащей сейчас фишку, Вася случайно и равновероятно выбирает одну ячейку и перемещает свою фишку туда.
После перемещения фишки Вася прибавляет к своим очкам квадрат евклидового расстояния между этими ячейками (то есть между ячейкой, в которой сейчас находится фишка, и ячейкой, в которой фишка находилась до перемещения). Процедура заканчивается, когда нет ни одной ячейки матрицы, в которой значение меньше, чем в ячейке, содержащей сейчас фишку.
Евклидово расстояние между ячейками матрицы $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$ равно $$$\sqrt{(i_1-i_2)^2 + (j_1-j_2)^2}$$$.
Определите математическое ожидание очков, которые наберет Вася.
Можно показать, что ответ может быть выражен как $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ — взаимно простые целые числа, а $$$Q \not\equiv 0~(mod ~ 998244353)$$$. Выведите значение $$$P \cdot Q^{-1}$$$ по модулю $$$998244353$$$.
В первой строке содержатся два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 1\,000)$$$ — количество строк и столбцов в матрице $$$a$$$.
Следующие $$$n$$$ строк содержат описание матрицы $$$a$$$. В $$$i$$$-й строке задано $$$m$$$ целых чисел $$$a_{i1}, a_{i2}, \dots, a_{im} ~ (0 \le a_{ij} \le 10^9)$$$.
Следующая строка содержит два целых числа $$$r$$$ и $$$c$$$ $$$(1 \le r \le n, 1 \le c \le m)$$$ — номер строки и номер столбца, в которых изначально находится фишка.
Выведите математическое ожидание набранных Васей очков в формате, описанном в условии.
1 4
1 1 2 1
1 3
2
2 3
1 5 7
2 3 1
1 2
665496238
В первом тестовом примере Вася сможет переместить фишку ровно один раз. Математическое ожидание набранных очков будет равно $$$\frac{1^2 + 2^2+ 1^2}{3} = 2$$$.
Название |
---|