CF1525E Assimilation IV

Monocarp 正在玩一款名为“Assimilation IV”的游戏。在这款游戏中，他管理着一个庞大的帝国：建设城市并征服新的土地。 Monocarp 的帝国有 $n$ 座城市。为了征服新的土地，他计划在每座城市建造一座纪念碑。游戏是回合制的，由于 Monocarp 还是新手，他每回合恰好在一座城市建造一座纪念碑。 Monocarp 想要用已建成的纪念碑控制地图上的 $m$ 个点。对于每个点，他都知道它与每座城市之间的距离。纪念碑的作用如下：当在某座城市建造纪念碑时，该纪念碑会在建造的那一回合控制所有距离该城市不超过 $1$ 的点。下一个回合，该纪念碑能控制所有距离不超过 $2$ 的点，再下一个回合则是距离不超过 $3$ 的点，依此类推。Monocarp 将在 $n$ 个回合内建造 $n$ 座纪念碑，他的帝国将征服所有被至少一座纪念碑控制的点。 Monocarp 无法想出任何策略，因此每回合他会在所有尚未建造纪念碑的城市中随机选择一座城市建造纪念碑。Monocarp 想知道，在第 $n$ 回合结束时，他征服的点的期望数量是多少。请你帮他计算出被征服点的期望数量！

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 20$；$1 \le m \le 5 \cdot 10^4$），分别表示城市数量和点的数量。 接下来的 $n$ 行，每行包含 $m$ 个整数：第 $i$ 行第 $j$ 个整数 $d_{i, j}$（$1 \le d_{i, j} \le n + 1$）表示第 $i$ 座城市与第 $j$ 个点之间的距离。

可以证明，Monocarp 在第 $n$ 回合结束时征服点的期望数量可以表示为最简分数 $\frac{x}{y}$。请输出该分数对 $998\,244\,353$ 取模的结果，即 $x \cdot y^{-1} \bmod 998244353$，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \bmod 998244353 = 1$ 的数。

让我们来看一下纪念碑建造顺序的所有可能情况： - $[1, 2, 3]$： - 第一座城市控制所有距离不超过 $3$ 的点，即点 $1$ 和 $4$； - 第二座城市控制所有距离不超过 $2$ 的点，即点 $1$、$3$ 和 $5$； - 第三座城市控制所有距离不超过 $1$ 的点，即点 $1$。 总共控制了 $4$ 个点。 - $[1, 3, 2]$：第一座城市控制点 $1$ 和 $4$；第二座城市控制点 $1$ 和 $3$；第三座城市控制点 $1$。总共控制了 $3$ 个点。 - $[2, 1, 3]$：第一座城市控制点 $1$；第二座城市控制点 $1$、$3$ 和 $5$；第三座城市控制点 $1$。总共控制了 $3$ 个点。 - $[2, 3, 1]$：第一座城市控制点 $1$；第二座城市控制点 $1$、$3$ 和 $5$；第三座城市控制点 $1$。总共控制了 $3$ 个点。 - $[3, 1, 2]$：第一座城市控制点 $1$；第二座城市控制点 $1$ 和 $3$；第三座城市控制点 $1$ 和 $5$。总共控制了 $3$ 个点。 - $[3, 2, 1]$：第一座城市控制点 $1$；第二座城市控制点 $1$、$3$ 和 $5$；第三座城市控制点 $1$ 和 $5$。总共控制了 $3$ 个点。 期望被控制的点的数量为 $\frac{4 + 3 + 3 + 3 + 3 + 3}{6} = \frac{19}{6}$，即 $19 \cdot 6^{-1} \equiv 19 \cdot 166374059 \equiv 166374062 \pmod{998244353}$。 由 ChatGPT 4.1 翻译