P10888 [MX-S3-T4] "FeOI Round 1" Awake Farewell Bird (feat. Feryquitous)

Original link: 。 --- 

There are $n$ students (numbered $1 \sim n$) taking an exam with $m$ subjects (numbered $1 \sim m$). You are given that student $i$'s score in subject $j$ is $a_{i, j}$。 Now you want to rank these students. Since it is hard to compare the ability of two students whose scores do not form a partial order, you plan to set $m$ real numbers $p_{1 \sim m}$ (required to satisfy $\sum_{i = 1}^m p_i = 1$ and $p_i \ge 0$) as weights. Define student $i$'s weighted total score as $\sum_{j = 1}^m a_{i, j} \times p_j$. Then students are ranked in descending order of weighted total score, and students with equal weighted total score share the same rank。 Now all $m$ subject teachers have made requests to you. The teacher of subject $k$ wants your chosen $p$ to satisfy: - In the ranking result obtained by this $p$, there does not exist a pair of students $(x, y)$ ($x \ne y$) such that $x$ ranks higher (ties do not count), but $a_{x, k} < a_{y, k}$。 Because you want to distribute the weights as freely as possible, for each $k$ ($1 \le k \le m$), you need to compute **separately**: - What is the minimum value of $p_k$ such that **no matter how the other $\boldsymbol{p_i}$ are distributed**, the teacher of subject $k$'s requirement is always satisfied? Output the result modulo $998244353$。

**This problem contains multiple test cases within a single input file.** The first line contains an integer $T$ denoting the number of test cases。 For each test case, the format is: The first line contains two integers $n, m$。 Lines $2$ to $n + 1$ each contain $m$ integers. The integer in row $i + 1$, column $j$ denotes $a_{i, j}$。

For each test case, output $m$ lines, each containing a non-negative integer. The $i$-th line represents the result when $k = i$, i.e., the minimum value of $p_k$ modulo $998244353$。 That is, suppose the answer in lowest terms is $\frac{a}{b}$, where $a$ and $b$ are coprime. Output an integer $x$ such that $bx \equiv a \pmod{998244353}$ and $0 \le x < 998244353$。It can be proven that such an integer $x$ is unique。

**[Sample Explanation]** For the first test case, the answers before taking modulo are $\frac{1}{4}, \frac{3}{4}, \frac{1}{4}, \frac{1}{2}$ respectively。 For the second test case, the answers before taking modulo are $\frac{4}{5}, \frac{4}{5}$ respectively。 For the third test case, the answers before taking modulo are $0, 0, 0, 0$ respectively。 For the query with $k = 2$ in the first test case, suppose $p = [0.1, 0.75, 0.1, 0.05]$: - Student $1$'s weighted total score is $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$； - Student $2$'s weighted total score is $1 \times 0.1 + 3 \times 0.75 + 1 \times 0.1 + 2 \times 0.05 = 2.55$； - Student $3$'s weighted total score is $1 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 2 \times 0.05 = 2.1$； - Student $4$'s weighted total score is $4 \times 0.1 + 2 \times 0.75 + 4 \times 0.1 + 3 \times 0.05 = 2.45$； Then you rank the students (by descending weighted total score) as $[2, 4, 1, 3]$ (of course it can also be $[2, 1, 4, 3]$). Also, $a_{2, 2} = 3, a_{4, 2} = 2, a_{1, 2} = 2, a_{3, 2} = 2$, and there is no case where a lower-ranked student has a higher score in subject $2$。 It can be proven that when $p_2 \ge 0.75$, no matter how the other $p_i$ are distributed, the requirement can be satisfied; while when $p_2 < 0.75$, there must exist a distribution of the other $p_i$ that makes the requirement impossible to satisfy。 **[Constraints]** **This problem uses bundled tests.** Let $\sum nm$ be the sum of all $nm$ over all test cases within a single input file。 For $100\%$ of the testdata, $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$。 | Subtask ID | $n$ | $m$ | $\sum nm$ | Special Property | Score | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $\leq 10$ | $\leq 10$ | $\leq 100$ | None | $5$ | | $2$ | $\leq 100$ | $\leq 100$ | $\leq 10^4$ | None | $10$ | | $3$ | $\leq 5 \times 10^3$ | $\leq 5 \times 10^3$ | $\leq 10^4$ | None | $15$ | | $4$ | $\leq 100$ | $\le 10^5$ | $\le 2 \times 10^5$ | None | $20$ | | $5$ | $\le 10^5$ | $\leq 100$ | $\le 2 \times 10^5$ | None | $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$ | None | $20$ | Translated by ChatGPT 5