目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
Problem - 1525E - Codeforces
二、解题报告
1、思路分析
看数据量盲猜O(nm)解法先
然后看题，考虑暴力做法：
n!种排列，然后判断每个point是否能被点亮
这样可以计算出所有点亮数目的方案，总可能是n!，那么按照数学期望计算公式就能算了
我们看时间复杂度，m个point，每个point最坏枚举n个位置来判断能否被点亮，这样时间复杂度就是O(n! * n * m)
我们考虑优化，至少要把阶乘拿掉，不然没法AC
我们考虑本题数学期望还等于每个位置被点亮的概率之和
<=> (1 - 每个位置不被点亮的概率)之和
那么我们能否快速计算每个位置不被点亮的方案数呢？
考虑turn1~turnn的覆盖范围为n~1
那么对于point j，在turni只能选择与自己距离大于n - i + 1的的城市
那么我们枚举point，O(n)预处理距离为1~n-1和距离大于n的城市数目，后缀和就是距离大于i的城市数目
我们枚举turn1~turnn，便枚举边记录后缀和prei，第1个位置的可选方案数pren，第2个位置方案数是pren + pren-1 - 1（减一是为了不跟前面重复）……
然后我们就能在O(nm)内计算出结果
数学思维还是很重要的嘿
2、复杂度
时间复杂度： O(nm) 空间复杂度：O(nm)
3、代码详解
import sys
import math
sys.stdin = open('in.txt', 'r')
# input = lambda: sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x) + '\n')
mod = 998244353
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
inv = 1
for i in range(1, n + 1):
inv = inv * i % mod
inv = pow(inv, mod - 2, mod)
ret = 0
for i in range(m):
cnt = [0] * (n + 2)
for j in range(n):
cnt[min(g[j][i], n + 1)] += 1
s = 0
cur = 1
for j in range(n + 1, 1, -1):
s += cnt[j]
cur = cur * s % mod
s -= 1
ret = (ret + 1 - cur * inv) % mod
write(ret)
