题解

思路

秩为 $r$ 的 $n\times n$ 矩阵数量为

$$C_p(n,r)^2\cdot |GL(r,p)|,$$

其中 $C_p(n,r)$ 是高斯二项式，$GL(r,p)$ 是 $r$ 阶可逆矩阵的集合。

子任务 1

枚举矩阵的全部 $p^{n^2}$ 种填法，对每个矩阵在 $\mathbb F_p$ 上做高斯消元并统计秩。复杂度为 $O(p^{n^2}n^3)$。

子任务 2

直接使用

$$ans_r=\prod_{i=0}^{r-1}\frac{(p^n-p^i)^2}{p^r-p^i}.$$

对每个 $r$ 重新计算乘积，复杂度为 $O(k^2+k\log MOD)$，适用于 $k\le5000$。若某个 $p^r=1\pmod {MOD}$，则 $|GL(r,p)|$ 含零因子，从该秩起答案均为零。

子任务 3

利用相邻高斯二项式和可逆矩阵数量的比值，得到递推

$$ans_r=ans_{r-1}\cdot \frac{p^{r-1}(p^{n-r+1}-1)^2}{p^r-1}.$$

同时维护 $p^{r-1}$、$p^r$ 和 $p^{n-r+1}$。当 $r>n$ 时秩不可能达到；当 $p^r=1\pmod {MOD}$ 时，$|GL(r,p)|$ 被模数整除，并且更高阶的可逆矩阵数量仍含该因子，因此后缀答案全为零。

做法

从 $ans_0=1$ 开始依次计算。同步维护 $p^{r-1}$、$p^r$ 与递减指数的 $p^{n-r+1}$，用一次快速幂求 $(p^r-1)^{-1}$ 并代入递推式。若遇到 $r>n$ 或 $p^r=1$，直接把当前和后续答案置零。

正确性证明

先选择矩阵的像空间和核的补空间，分别产生两个高斯二项式因子；在两个固定的 $r$ 维空间之间选择可逆线性映射，产生 $|GL(r,p)|$，故计数公式正确。递推只是该公式相邻两项相除并约去公共因子，因此在分母非零时保持等价。分母首次为零时，可逆矩阵计数中已经出现模 $998244353$ 的零因子，所以当前及后续答案确为零。

复杂度

满分算法时间复杂度为 $O(k\log 998244353)$，空间复杂度为 $O(1)$；中档算法为 $O(k^2)$；小档为指数复杂度。