P13633 [NWRRC 2021] First to Solve

著名的 Forcedeltas 编程竞赛有 $n$ 名参赛者，$m$ 道题目，比赛持续 $k$ 分钟。 对于每位参赛者 $i$ 和每道题目 $j$，已知一个整数 $a_{i, j}$。如果 $a_{i, j} = 0$，表示参赛者 $i$ 无法解出题目 $j$。否则，表示参赛者 $i$ 恰好需要 $a_{i, j}$ 分钟解出题目 $j$。 所有参赛者都遵循相同的策略。具体来说，每位参赛者会列出所有自己能解出的题目，将该列表等概率随机打乱，然后按顺序依次解题，直到列表结束或比赛结束。 例如，若参赛者 $i$ 打乱后的题目列表为 $j_1, j_2, \ldots$，则他会在第 $a_{i, j_1}$ 分钟解出题目 $j_1$，在第 $a_{i, j_1} + a_{i, j_2}$ 分钟解出题目 $j_2$，以此类推。注意，不能在第 $k+1$ 分钟或更晚解出题目。 我们说参赛者 $i$ 获得题目 $j$ 的“最先解出”奖（First to Solve award），当且仅当没有其他参赛者比他更早解出题目 $j$。特别地，多个参赛者可以同时获得同一道题的该奖项。 请计算每位参赛者期望获得的奖项数，答案对 $998\,244\,353$ 取模（具体见输出格式）。

第一行包含三个整数 $n$、$m$ 和 $k$，分别表示参赛者人数、题目数量和比赛时长（$1 \le n \le 500$；$1 \le m \le 26$；$1 \le k \le 300$）。 接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$（$0 \le a_{i, j} \le k$）。其中第 $j$ 个整数表示参赛者 $i$ 解题 $j$ 所需的分钟数，若为 $0$ 则表示无法解出该题。

输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 位参赛者期望获得的奖项数，对 $998\,244\,353$ 取模。 形式化地，设 $M = 998\,244\,353$。可以证明，期望奖项数可表示为不可约分数 $\frac{p}{q}$，其中 $p$、$q$ 为整数且 $q \not\equiv 0 \pmod{M}$。请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

在样例测试中，第 $1$ 位参赛者总能获得题目 $1$ 的奖项，第 $2$ 位参赛者总能获得题目 $2$ 的奖项，第 $3$ 位参赛者期望获得的奖项数为 $\frac{3}{4}$，第 $4$ 位参赛者无法获得任何奖项，第 $5$ 位参赛者期望获得的奖项数为 $\frac{1}{2}$。 由 ChatGPT 4.1 翻译