求在有限域 $F_p$ ($p$ 为质数)下大小为 $n$ 秩为 $k$ 的方阵个数.
考虑dp,不妨记 $f_{i,j}$ 表示考虑前 $i$ 行,秩为 $j$ 的方案数.
则转移较为显然.
$f_{i,j} = (p^n-p^{j-1})f_{i-1,j-1} + p^jf_{i,j-1}.$
也就是枚举新的这一行是否可以被之前的线性无关行线性组合出来.
考虑优化,不妨设$F_k(x)=\sum_{i=0}^{\infty}f_{i+k,k}$.
考察转移的形式,我们会发现$F_k(x)$的系数是$\prod_{i=0}^{k-1}(p^n-p^i)$的倍数(因为每次使秩增加的转移都会乘上这个东西,或者也可以归纳证明),这启发我们设$G_k(x)=F_k(x)\prod_{i=0}^{k-1}\frac1{(p^n-p^i)}$.
则由转移式可得$G_k(x)=G_{k-1}(x)+p^kxG_k(x)$.
也就是说$G_k(x)=\prod_{i=0}^{k}\frac1{1-p^ix}$.
所以所求即为$\prod_{i=0}^{k}\frac1{1-p^ix}[x^{n-k}]\prod_{i=0}^{k-1}(p^n-p^i)$.
假设 $n$,$k$ 同级,直接分治ntt不难做到$O(n\log^2n)$,稍加思考也不难得到一个 $O(n\log n)$ 的做法.