← 返回题目列表

Codeforces · 1916/H2

H2. 矩阵排名(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。该问题的两个版本之间的唯一区别是 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

给定整数 $$$n$$$、$$$p$$$ 和 $$$k$$$。 $$$p$$$ 保证是素数。

对于从$$$0$$$到$$$k$$$的每个$$$r$$$,求$$$n \times n$$$矩阵$$$A$$$的域$$$^\dagger$$$的整数模$$$p$$$的数量,使得$$$A$$$的排名$$$^\ddagger$$$恰好是$$$r$$$。由于这些值很大,因此您只需输出它们对 $$$998\,244\,353$$$ 取模即可。

$$$^\dagger$$$ https://en.wikipedia.org/wiki/Field_(数学)

$$$^\ddagger$$$ https://en.wikipedia.org/wiki/Rank_(线性代数)

输入

输入的第一行包含三个整数 $$$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$$$整数,从$$$0$$$到$$$k$$$的每个$$$r$$$的答案。

示例

输入 #1

3 2 3

输出 #1

1 49 294 168

输入 #2

1 51549919 2

输出 #2

1 51549918 0