cf1525e.md

提示 1： 考虑直接暴力的复杂度如何？（有 $n!$ 种排列和 $m$ 个位置，每个位置需要 $\mathcal{O}(n)$ 的时间判断，总复杂度为 $\mathcal{O}(nmn!)$）

提示 2： 上述复杂度应该优化掉哪一个维度？因为各个城市之间相互的影响作用不好刻画，$m$ 部分难以优化。于是 $m$ 是不可避免的。

提示 3： 由于复杂度中 $m$ 是不可避免的，因此可以依次考虑每一个城市，同时，由于期望具有可加性，期望等于每个城市被点亮的概率相加的结果。

提示 4： 被点亮的情况很多，但是不被点亮的情况很容易刻画，考虑计算不被点亮的概率。

欸，看提示喔。

根据提示，我们考虑将期望拆分为概率之和，并反向计算不被点亮的概率。而这只需要计算在所有 $n!$ 种排列中，有多少种无法点亮某个城市。

一个城市不被点亮有何要求呢？

第 $0$ 秒点亮的灯与城市的距离大于 $n$，第 $1$ 秒点亮的灯与城市的距离大于 $n-1$，第 $2$ 秒点亮的灯与城市的距离大于 $n-2$，……，第 $n-1$ 秒点亮的灯与城市的距离大于 $1$ 。

这些条件是越来越弱的，因此从前往后考虑。假设距离为 $d$ 的灯有 $c_d$ 盏。

我们先看第 $0$ 秒点亮的灯，其只能选取距离是 $n+1$ 的，我们可以从中任取，有 $c_{n+1}$ 种方案；

第 $1$ 秒点亮的灯，其可以选取距离是 $n / n+1$ 的，我们可以从中任取，但不能跟前面的重复，因此有 $c_n+c_{n+1}-1$ 种方案；

第 $2$ 秒点亮的灯，其可以选取距离是 $n-1 / n / n+1$ 的，我们可以从中任取，但不能跟前面的重复，因此有 $c_{n-1}+c_n+c_{n+1}-2$ 种方案；

……

使用上述逻辑，每一次的方案使用乘法原理相乘，即可得到所有方案数，进而计算得到概率。其相邻两项只相差了 $c_k-1$ ，因此可以实现 $\mathcal{O}(1)$ 更新。

当然，中间有可能出现没灯可选的情况，此时直接退出循环即可（也可以不退出，因为更新的答案已经是 $0$ 了）。

将上述计算的概率加总即可，时间复杂度为 $\mathcal{O}(nm)$ .

具体代码如下（只包含中间处理部分）——

def main():
    n, m = MII()
    dist = [LII() for _ in range(n)]

    mod = 998244353
    cnt = [0] * n

    inv = 1
    for i in range(1, n + 1):
        inv *= i
        inv %= mod
    inv = pow(inv, -1, mod)

    ans = 0
    for i in range(m):
        for j in range(n):
            if dist[j][i] >= 2:
                cnt[dist[j][i] - 2] += 1
        
        cur = 1
        cur_cnt = 0
        for j in range(n - 1, -1, -1):
            cur_cnt += cnt[j]
            cur *= cur_cnt
            cur %= mod
            cur_cnt -= 1
        
        for j in range(n):
            cnt[j] = 0
        
        ans = (ans + 1 - cur * inv) % mod

    print(ans)