P10888 【MX-S3-T4】「FeOI Round 1」醒餞の鳥 (feat. Feryquitous)

原题链接：。 --- 

有 $n$ 个学生（编号为 $1 \sim n$）参加了一场有 $m$ 门学科（编号为 $1 \sim m$）的考试，现在你知道，学生 $i$ 的第 $j$ 门学科考试的成绩为 $a_{i, j}$。 现在你想要给这些学生排名。由于成绩不形成偏序关系的两个学生实力难以比较，所以你打算设置 $m$ 个实数 $p_{1 \sim m}$（要求满足 $\sum_{i = 1}^m p_i = 1$，且 $p_i \ge 0$）作为权值。定义学生 $i$ 的加权总分为 $\sum_{j = 1}^m a_{i, j} \times p_j$，则按照加权总分降序排名，加权总分相等的则排名并列。 现在这 $m$ 个学科的老师都向你提出了要求，第 $k$ 个学科的老师想让你所设置的 $p$ 满足： - 以这个 $p$ 得到的排名结果中，不存在一对学生 $(x, y)$（$x \ne y$），使得 $x$ 排名更靠前（并列不算），但是 $a_{x, k} < a_{y, k}$； 因为你想要尽量自由的分配权值，所以你需要对于每个 $k$（$1 \le k \le m$），都**分别**求出： - $p_k$ 至少要为多少，才能保证**无论如何分配其他 $\boldsymbol{p_i}$ 的权值，都能满足**第 $k$ 个学科的老师的要求？请输出答案对 $998244353$ 取模的结果。

无

无

**【样例解释】** 对于第一组数据，询问的答案取模之前分别为 $\frac{1}{4}, \frac{3}{4}, \frac{1}{4}, \frac{1}{2}$。 对于第二组数据，询问的答案取模之前分别为 $\frac{4}{5}, \frac{4}{5}$。 对于第三组数据，询问的答案取模之前分别为 $0, 0, 0, 0$。 对于第一组数据的 $k = 2$ 的询问，假设 $p = [0.1, 0.75, 0.1, 0.05]$： - 第 $1$ 个学生的加权总分是 $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$； - 第 $2$ 个学生的加权总分是 $1 \times 0.1 + 3 \times 0.75 + 1 \times 0.1 + 2 \times 0.05 = 2.55$； - 第 $3$ 个学生的加权总分是 $1 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 2 \times 0.05 = 2.1$； - 第 $4$ 个学生的加权总分是 $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$； 则你令按加权总分降序排名的学生编号为 $[2, 4, 1, 3]$（当然也可以令其为 $[2, 1, 4, 3]$），且 $a_{2, 2} = 3, a_{4, 2} = 2, a_{1, 2} = 2, a_{3, 2} = 2$，不存在排名更靠后但是第 $2$ 个学科成绩更高的情况。 可以证明，在 $p_2 \ge 0.75$ 的情况下，无论其他 $p_i$ 如何分布，都可以满足要求；而 $p_2 < 0.75$ 的情况下，一定存在一种其他 $p_i$ 的分布使得无法满足要求。 **【数据范围】** **本题开启捆绑测试。** 设 $\sum nm$ 为单个测试点内所有的 $nm$ 之和。 对于 $100\%$ 的数据，$1 \le T \le 5 \times 10^4$，$ 2 \le n, m \le 10^5$，$ \sum nm \le 2 \times 10^5$，$ 0 \le a_{i, j} \leq 10^8$。 | 子任务编号 | $n$ | $m$ | $\sum nm$ | 特殊性质 | 分数 | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $\leq 10$ | $\leq 10$ | $\leq 100$ | 无 | $5$ | | $2$ | $\leq 100$ | $\leq 100$ | $\leq 10^4$ | 无 | $10$ | | $3$ | $\leq 5 \times 10^3$ | $\leq 5 \times 10^3$ | $\leq 10^4$ | 无 | $15$ | | $4$ | $\leq 100$ | $\le 10^5$ | $\le 2 \times 10^5$ | 无 | $20$ | | $5$ | $\le 10^5$ | $\leq 100$ | $\le 2 \times 10^5$ | 无 | $10$ | | $6$ | $\le 10^5$ | $\le 10^5$ | $\le 2 \times 10^5$ | $a_{i, j} \in \{0, 1\}$ | $20$ | | $7$ | $\le 10^5$ | $\le 10^5$ | $\le 2 \times 10^5$ | 无 | $20$ |