首先我们知道各行独立，因此只需要对所有 \(B\) 求解 \(aB \equiv a \pmod q\)。这相当于是以 \(1\) 为特征值的一个特征子空间，即 \(1\)-特征子空间。
假设我们已经有 \(n-d\) 维作为这个子空间，则剩下的方案数应该是 \(\{d,n\}_q = (q^n-q^{n-d})(q^n-q^{n-d+1})\dots(q^n-q^{n-1})\)。但这只是钦定，我们需要进行一个子空间反演。根据 EI 的教导，我们只需要列出 q-EGF \(\sum_k \frac{f_k x^k}{(q; q)_k}\) 并商 \(\zeta(x) = \sum_k \frac{x^k}{(q; q)_k}\)。
记
\[ \begin{aligned} G(x) &= \sum_k \frac{\{k, n\}_q x^k}{(q; q)_k} \\ &= \sum_k x^k \frac{(q^n-q^{n-k})\cdots(q^n-q^{n-1})}{(1-q)\cdots(1-q^k)} \end{aligned} \]
有
\[ G(x)-G(qx) = q^n xG(x) - q^{n-1} x G(q^{-1} x) \]
设 \(F(x) = G(x) \zeta^{-1}(x)\)。注意到 \(\zeta^{-1}(qx) = \zeta^{-1}(x) (1-x)^{-1}, \zeta^{-1}(q^{-1}x) = \zeta^{-1}(x) (1-q^{-1}x)\)，就有
\[ \begin{aligned} (1- q^n x) G(x)\zeta^{-1}(x) - G(qx)\zeta^{-1}(x) + q^{n-1} x G(q^{-1} x) \zeta^{-1}(x) &= 0 \\ (1- q^n x) F(x) - (1-x) F(qx) + q^{n-1}x(1-q^{-1} x)^{-1} F(q^{-1} x) &= 0 \\ (1-q^n x)(1-q^{-1} x) F(x) - (1-x)(1-q^{-1} x) F(qx) + q^{n-1}x F(q^{-1}x) &= 0 \end{aligned} \]
可得递推式
\[ f_k = (q^{-1}+q^n-q^{k-1}-q^{k-2}-q^{n-k}) f_{k-1} + (q^{k-3}-q^{n-1}) (1-q^{k-1}) f_{k-2} \]