Solution. CF1916H2 Matrix Rank (Hard Version)
Description
给定 $n,p,k$，对于每个 $r\in[0,k]$，求出 $\mathbb{F}_p$ 上有多少个秩为 $r$ 的 $n\times n$ 矩阵。
答案对 $998244353$ 取模。
$n\le 5\times 10^{18},k\le 5\times 10^5,0\le p<998244353$
Solution
我基本没学过线性代数，如下做法参考 CF 上 JeanBombeur 的 comment，推导过程可能不严谨。
一个 $n\times n$ 矩阵的秩为 $r$ 也就意味着这个矩阵的所有行向量张成了 $\mathbb F_p^n$ 上的一个 $r$ 维子空间，我们首先对这个子空间计数，考虑确定这个子空间的基。
基由 $r$ 个线性无关的 $n$ 维向量构成。首先确定第一个向量。$\mathbb F_p$ 上的 $n$ 维向量共有 $p^n$ 个，基中向量不能为零向量，所以选取第一个向量的方式共有 $p^n-1$ 种。第二个向量类似，但不能是第一个向量的若干倍，所以共有 $p^n-p$ 中选法。接下来以此类推，后面的向量不能是前面已经选取的向量的线性组合，所以选取 $r$ 个向量的方案数为 $(p^n-p^0)(p^n-p^1)\cdots(p^n-p^{r-1})$。
但是注意基不同却不意味着子空间不同。一个 $r$ 维子空间的基的个数等于选取 $r$ 个线性无关的 $r$ 维向量的方案数，根据上文的分析，这个值等于 $(p^r-p^0)(p^r-p^1)\cdots(p^r-p^{r-1})$。
所以，$\mathbb F_p^n$ 上的 $r$ 维子空间的个数为 $\dfrac{(p^n-p^0)(p^n-p^1)\cdots(p^n-p^{r-1})}{(p^r-p^0)(p^r-p^1)\cdots(p^r-p^{r-1})}$。
接下来，我们要在这个 $r$ 维子空间内选取 $n$ 个向量，并且这 $n$ 个向量仍然张成一个 $r$ 维子空间。这等价于选取一个 $n\times r$ 的矩阵，满足其秩为 $r$，从行秩的角度考虑就是刚才的问题，这个方案数并不好计算，但如果从列秩考虑（矩阵的秩=行秩=列秩，这是线性代数中的结论，也有很多经典的证法），问题就变为了选取 $r$ 个 $n$ 维向量，且这 $r$ 个向量张成一个 $r$ 维子空间的方案数，这显然要求 $r$ 个向量线性无关，方案数在上文已经计算过了。
综上，$\mathbb F_p$ 上秩为 $r$ 的 $n\times n$ 矩阵的个数为 $\dfrac{((p^n-p^0)(p^n-p^1)\cdots(p^n-p^{r-1}))^2}{(p^r-p^0)(p^r-p^1)\cdots(p^r-p^{r-1})}$。
这个分式的上下两部分均可以递推计算，总复杂度视具体实现为 $O(k)$ 或 $O(k\log k)$。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
