← 返回题目列表

Codeforces · 1525/E

E. 同化IV

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

Monocarp 正在玩游戏“同化 IV”。在这款游戏中,他管理着一个伟大的帝国:建造城市并征服新的土地。

Monocarp 的帝国拥有 $$$n$$$ 个城市。为了征服新的土地,他计划在每个城市建造一座纪念碑。该游戏是回合制的,由于 Monocarp 仍然是业余爱好者,因此他每回合只建造一个纪念碑。

Monocarp 在地图上有 $$$m$$$ 个点,他想使用建造的纪念碑来控制。对于每个点,他都知道它与每个城市之间的距离。纪念碑的工作方式如下:当在某个城市建造时,纪念碑控制距离该城市最多 $$$1$$$ 的所有点。下一回合,纪念碑控制距离最多 $$$2$$$ 的所有点,之后的回合 - 距离最多 $$$3$$$,依此类推。 Monocarp 将在 $$$n$$$ 回合中建造 $$$n$$$ 纪念碑,他的帝国将征服至少一个纪念碑控制的所有点。

Monocarp无法想出任何策略,因此在每个回合中他会从所有剩余城市(没有纪念碑的城市)中随机选择一个城市作为纪念碑。 Monocarp 想知道在第 $$$n$$$ 回合结束时他将征服多少个点(其中 $$$m$$$)。帮助他计算预计的征服点数!

输入

第一行包含两个整数 $$$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$$$,i。 e.值 $$$x \cdot y^{-1} \bmod 998244353$$$ 其中 $$$y^{-1}$$$ 是 $$$y \cdot y^{-1} \bmod 998244353 = 1$$$ 的数字。

示例

输入 #1

3 5
1 4 4 3 4
1 4 1 4 2
1 4 4 4 3

输出 #1

166374062

注意

让我们看看将建造纪念碑的城市的所有可能顺序:

- $$$[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$$$ 积分。