CF1916H2.Matrix Rank (Hard Version)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

This is the hard version of the problem. The only differences between the two versions of this problem are the constraints on kk . You can make hacks only if all versions of the problem are solved.

You are given integers nn , pp and kk . pp is guaranteed to be a prime number.

For each rr from 00 to kk , find the number of n×nn \times n matrices AA of the field ^\dagger of integers modulo pp such that the rank ^\ddagger of AA is exactly rr . Since these values are big, you are only required to output them modulo 998244353998\,244\,353 .

^\dagger https://en.wikipedia.org/wiki/Field_(mathematics)

^\ddagger https://en.wikipedia.org/wiki/Rank_(linear_algebra)

输入格式

The first line of input contains three integers nn , pp and kk ( 1n10181 \leq n \leq 10^{18} , 2p<9982443532 \leq p < 998\,244\,353 , 0k51050 \leq k \leq 5 \cdot 10^5 ).

It is guaranteed that pp is a prime number.

输出格式

Output k+1k+1 integers, the answers for each rr from 00 to kk .

输入输出样例

  • 输入#1

    3 2 3

    输出#1

    1 49 294 168
  • 输入#2

    1 51549919 2

    输出#2

    1 51549918 0
首页