← 返回题目列表

Codeforces · 1042/E

E. 瓦夏和魔法矩阵

中文机器翻译题面 查看原题

Vasya 拥有一个大小为 $$$n \times m$$$ 的魔法矩阵 $$$a$$$。矩阵的行从上到下编号为$$$1$$$到$$$n$$$,列从左到右编号为$$$1$$$到$$$m$$$。令 $$$a_{ij}$$$ 为第 $$$i$$$ 行和第 $$$j$$$ 列的交集中的元素。

Vasya 也有一个芯片。最初,芯片位于第 $$$r$$$ 行和第 $$$c$$$ 列的交集处(即在元素 $$$a_{rc}$$$ 中)。 Vasya 尽可能长时间地执行以下过程:在矩阵中所有值小于包含筹码的元素的值的元素中,Vasya 随机等概率地选择一个元素,并将其筹码移至该元素。

移动筹码后,他将这些元素之间(即筹码现在所在的元素与筹码被移动的元素之间)之间的欧几里得距离的平方添加到他的分数中。当没有元素的值小于其中包含芯片的元素的值时,该过程结束。

坐标为 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 的矩阵元素之间的欧氏距离等于 $$$\sqrt{(i_1-i_2)^2 + (j_1-j_2)^2}$$$。

计算 Vasya 最终得分的期望值。

可以证明,答案可以表示为$$$\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)$$$ — 芯片现在所在的行索引和列索引。

输出

按照问题陈述中描述的格式打印 Vasya 最终分数的期望值。

示例

输入 #1

1 4
1 1 2 1
1 3

输出 #1

2

输入 #2

2 3
1 5 7
2 3 1
1 2

输出 #2

665496238

注意

在第一个示例中,Vasya 将移动他的筹码一次。最终分数的期望值等于$$$\frac{1^2 + 2^2+ 1^2}{3} = 2$$$。