CF1916H2 Matrix Rank (Hard Version)

这是该问题的困难版本。两种版本的唯一区别在于 $k$ 的约束条件。只有在解决了所有版本的问题后，才能进行 Hack。 给定整数 $n$、$p$ 和 $k$。保证 $p$ 是一个质数。 对于每个 $r$ 从 $0$ 到 $k$，求在模 $p$ 的整数域 $^\dagger$ 上，秩 $^\ddagger$ 恰好为 $r$ 的 $n \times n$ 矩阵 $A$ 的个数。由于这些值可能很大，你只需要输出它们对 $998\,244\,353$ 取模的结果。 $^\dagger$ [https://en.wikipedia.org/wiki/Field\_(mathematics)](https://en.wikipedia.org/wiki/Field_(mathematics)) $^\ddagger$ [https://en.wikipedia.org/wiki/Rank\_(linear\_algebra)](https://en.wikipedia.org/wiki/Rank_(linear_algebra))

输入的第一行包含三个整数 $n$、$p$ 和 $k$（$1 \leq n \leq 10^{18}$，$2 \leq p < 998\,244\,353$，$0 \leq k \leq 5 \cdot 10^5$）。 保证 $p$ 是一个质数。

输出 $k+1$ 个整数，依次表示每个 $r$ 从 $0$ 到 $k$ 的答案。

由 ChatGPT 4.1 翻译