题目大意

给定整数 $n$、$p$ 和 $k$，其中 $p$ 是质数。对于每个 $r = 0, 1, \dots, k$，计算在模 $p$ 的有限域 $\mathbb{F}_p$ 上，所有 $n \times n$ 矩阵中，秩恰好等于 $r$ 的矩阵个数。由于结果可能很大，要求输出对 $998244353$ 取模后的答案。

数据范围：$1 \le n \le 10^{18}$，$2 \le p < 998244353$，$0 \le k \le 5 \cdot 10^5$。

---

前置知识与公式推导

在大小为 $q$ 的有限域 $\mathbb{F}_q$ 上（本题中 $q = p$），秩为 $r$ 的 $n \times n$ 矩阵个数由以下著名公式给出：

$$N(n, r, q) = \left( \prod_{i=0}^{r-1} (q^n - q^i) \right)^2 \cdot \frac{1}{\prod_{i=0}^{r-1} (q^r - q^i)} $$

该公式可以进一步改写为递推形式，便于在 $O(k)$ 时间内求出所有 $r \le k$ 的答案。

我们记 $q = p \bmod MOD$，并令 $A_r = N(n, r, q) \bmod MOD$。则有：

• 当 $r = 0$ 时，只有全零矩阵满足条件，故 $A_0 = 1$。
• 当 $r > n$ 时，秩不可能超过 $n$，故 $A_r = 0$。
• 当 $1 \le r \le \min(n, k)$ 时，满足递推关系：

$$A_r = A_{r-1} \cdot q^{r-1} \cdot \frac{(q^{n-r+1} - 1)^2}{q^r - 1} \pmod{MOD} $$

推导要点：比较 $A_r$ 与 $A_{r-1}$ 的表达式中相同部分的比值，化简即得上述递推式。注意分母 $q^r - 1$ 在模意义下可逆，除非 $q^r \equiv 1 \pmod{MOD}$。本题中由于 $p < MOD$ 且 $MOD$ 是质数，可以证明在题目约束下分母恒不为零（除非 $q=1$ 但 $p\ge 2$ 且 $p<MOD$，$q$ 的阶通常大于 $k$），因此可直接求逆元。

---

算法实现细节

由于 $n$ 可达 $10^{18}$，而 $k$ 最多只有 $5\times 10^5$，我们需要在 $O(k)$ 或 $O(k \log MOD)$ 时间内完成计算。

关键步骤：

1. 预处理 $q$ 的幂次及其逆元
   计算 $q^0, q^1, \dots, q^k \pmod{MOD}$ 以及对应的逆元 $q^{-0}, q^{-1}, \dots, q^{-k}$。这一步只需一次线性递推，时间复杂度 $O(k)$。

2. 预处理 $(q^r - 1)^{-1}$
   对每个 $r = 1, 2, \dots, k$，计算 $c_r = (q^r - 1) \bmod MOD$，并用快速幂求其在模 $MOD$ 下的逆元。这一步复杂度 $O(k \log MOD)$，可接受。

3. 计算 $q^n \bmod MOD$
   使用快速幂在 $O(\log n)$ 时间内求出。

4. 递推计算 $A_r$
   递推式中的各项均可通过已预处理的数组 $O(1)$ 得到：

   • $a = q^{r-1}$
   • $term = q^n \cdot q^{-(r-1)} = q^{n-r+1} \pmod{MOD}$
   • $b = (term - 1) \bmod MOD$
   • 分母逆元 $inv\_c[r]$ 已预处理

   因此 $A_r = A_{r-1} \cdot a \cdot b \cdot b \cdot inv\_c[r] \pmod{MOD}$。注意乘法过程中每一步都立即取模，防止 long long 溢出。

5. 边界处理
   若 $r > n$，则直接令 $A_r = 0$。

---

复杂度分析

• 预处理 $O(k \log MOD)$，其中 $\log MOD \approx 30$。
• 递推 $O(k)$。
• 总时间复杂度 $O(k \log MOD + \log n)$，在 $k \le 5\times 10^5$ 时完全可行。
• 空间复杂度 $O(k)$。

---

AC 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MOD = 998244353;

// 快速幂：计算 a^b mod mod
ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, p;
    int k;
    cin >> n >> p >> k;
    
    ll q = p % MOD;
    ll max_r = min(n, (ll)k); // 秩超过n时答案必为0
    
    // 1. 预处理 q^0 ~ q^k mod MOD
    vector<ll> pow_q(k + 1);
    pow_q[0] = 1;
    for (int i = 1; i <= k; ++i) {
        pow_q[i] = pow_q[i-1] * q % MOD;
    }
    
    // 2. 预处理 q^{-0} ~ q^{-k} mod MOD
    ll inv_q = qpow(q, MOD - 2, MOD);
    vector<ll> inv_pow_q(k + 1);
    inv_pow_q[0] = 1;
    for (int i = 1; i <= k; ++i) {
        inv_pow_q[i] = inv_pow_q[i-1] * inv_q % MOD;
    }
    
    // 3. 预处理 (q^r - 1) 的逆元
    vector<ll> inv_c(k + 1);
    for (int r = 1; r <= k; ++r) {
        ll c = (pow_q[r] - 1 + MOD) % MOD;
        inv_c[r] = qpow(c, MOD - 2, MOD);
    }
    
    // 4. 计算 q^n mod MOD
    ll qn = qpow(q, n, MOD);
    
    // 5. 递推计算答案
    vector<ll> ans(k + 1);
    ans[0] = 1; // 秩0只有零矩阵
    for (int r = 1; r <= k; ++r) {
        if (r > max_r) {
            ans[r] = 0;
            continue;
        }
        ll a = pow_q[r-1];                     // q^{r-1}
        ll term = qn * inv_pow_q[r-1] % MOD;   // q^{n - r + 1}
        ll b = (term - 1 + MOD) % MOD;         // q^{n-r+1} - 1
        
        ans[r] = ans[r-1] * a % MOD;
        ans[r] = ans[r] * b % MOD * b % MOD;
        ans[r] = ans[r] * inv_c[r] % MOD;
    }
    
    // 6. 输出
    if (k >= 0) {
        printf("%lld", ans[0]);
        for (int i = 1; i <= k; ++i) {
            printf(" %lld", ans[i]);
        }
        printf("\n");
    }
    
    return 0;
}