概要
AtCoder Problems様では6000以上という難易度がついています。180分10問という超速コンテストだったので上位層でもあまり解けていないからこうなったということでしょう（？）。
とはいえこの問題は奇抜な発想は必要とせず、自然な線形代数典型を積み重ねることで答にたどり着けます。
線形代数はほぼ任意の大学生が学ぶ分野ですので、復習も兼ねてお楽しみください。なお本記事では、階数を求めるパートを除き、解説pdfよりも良い計算量を実現しています。
線形代数の基礎は隅々までは解説しないです。たとえば「ベクトル空間」「部分空間」「線形写像」「基底」「次元」といった用語は仮定されます。線形代数を履修した経験のある方が、成り立つ命題を見て思い出したり、別の場所で復習できる程度のところまで解説しているつもりです。
基本的に任意の体でできる議論は $K$ のまま行い、数え上げの必要が生じた箇所についてのみ$K = \mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}$ に基づく立式をします。
以下、$K$ を体とし、$V = K^N$ とします（問題文の$N$）。また、各 $n$ に対して$V_n = K^{n}$ とします。便宜上こう定義しましたが、$V_n$については「$n$ 次元ベクトル空間のひとつ」という以上の認識は必要としません。
考察で経由する数え上げ物は、$a,b,c,\ldots$ の記号を当てています（センスない…）。基本的に、赤文字が数学概念の定義や約束事、青文字が数え上げ物の定義です。
解説
階数・階数標準形の復習
\[\mathrm{diag}(1,1,\ldots,1,0,0,\ldots,0)=\begin{pmatrix}E_{r}&O_{r,N-r}\\O_{N-r,r}&O_{N-r,N-r}\end{pmatrix}\] の形の行列を階数標準形といいます（$E$ は単位行列、$O$ は零行列）。
- 任意の行列 $C$ は、行基本変形・列基本変形の繰り返しで階数標準形にできる。
- そのときの $r$ は変形の仕方によらない。この $r$ を $\mathrm{rank}(C)$ と書き、 $C$ の階数（rank）と呼ぶ。
- $r$ は、$C$ の列ベクトルが生成するベクトル空間の次元と等しい。
- あるいは、$C$ の定める線形写像を $\varphi_C\colon V\longrightarrow V$ としたとき、$r$ は像の次元と等しい。像は $\varphi_C$ の値域で、$\mathrm{Im} \varphi_C$ あるいは $\varphi_C(V)$ などの表記があります。ここでは後者を採用していきます。
線形代数において多くの場合、行列は「数を長方形に並べたもの」と思うよりも、「列ベクトルを並べたもの」と思ったり「線形写像」と思う方が適切であることが多いです。
階数標準形への帰着
$C = AB$ となる行列 $(A,B)$ を数える問題でした。適当な正則行列（逆行列が存在するような行列）$P$ をとったとき、$C = AB \iff PC = PAB$ なので、$A$ を数える代わりに $PA$ を数えることで、「$PC = AB$ となる行列 $(A,B)$ を数える」問題に帰着されます。同様に正則行列 $Q$ もとって$BQ$を見ることで、「$PCQ = AB$ となる行列 $(A,B)$ を数える」問題にできます。「$C$ を $PCQ$ に置き換えても同じ答になる」ことが分かります。
- 行基本変形は、正則行列を左からかける操作
- 列基本変形は、正則行列を右からかける操作
（逆も成り立ちますが、ここでは必要ないです）であるので、「$C$ を基本変形しても 同じ答になる」問題であることが分かります。
任意の行列は基本変形により階数標準形にできるのでしたから、$C$ を階数標準形として問題が解ければよいことになります。結局、与えられた $C$ の成分はどうでもよくて、$C$ の階数のみが問題だということになります。同じ階数の $C$ に対して同じ答が付随するので、$C$ の階数を $r$ として、
- $\mathrm{rank}(AB) = r$ となる $(A,B)$ の個数 $a_{N,r}$
- $\mathrm{rank}(C) = r$ となる $C$ の個数 $b_{N,r}$
とすると、答は $\frac{a_{N,r}}{b_{N,r}}$ となることが分かります。
行列の積と線形写像
行列の積は、線形写像の合成です。$A,B$ に対応する線形写像 $\varphi_A,\varphi_B\colon V \longrightarrow V$ をとると、$\varphi_{C} = \varphi_A\circ \varphi_B$ となるのでした。
- $\varphi_A$ とか書いているけど、$A$ 倍写像 $v\mapsto Av$ です。
- $\varphi_A\circ \varphi_B$ は、$v\mapsto \varphi_A\bigl(\varphi_B(v)\bigr)$ という写像。「$\varphi_B$ でうつしたあと $\varphi_A$ でうつす」順であることに注意。本問だと困らないが。
- 上で述べた性質は $(AB)v = A(Bv)$ とも書けて、行列の結合法則の一部です。「結合法則から分かる性質」と考えてもよいですが、「行列の積は線形写像の合成なので、結合法則は自明である」という向きの理解の方が妥当であると思います。
$\mathrm{dim}_K(\varphi_A\circ \varphi_B)(V) = r$ という性質を観察する必要がありますが、各写像による像空間の次元変化を考えます。つまり、各 $n$ に対して
- $\mathrm{dim}_K \varphi_B(V) = n$ となる $B$ の個数 $b_{N,n}$ （上の記号 $b_{N,r}$ と整合性がある）
- 上の条件下で、$\mathrm{dim}_K(\varphi_A\circ \varphi_B)(V) = r$ となる $A$ の個数 $c_{N,n,r}$
を求めることにします。後者の数え上げが $B$ に依存していないことは次に説明されます。$a_{N,r} = \sum_{n}b_{N,n}c_{N,n,r}$ となるので、$b$ と $c$ の計算に帰着されました。
$c_{N,n,r}$ の言い換え
- $V$ の $r$ 次元部分空間の個数を、$d_{N,r}$ と書くことにします。
- $\mathrm{dim}_K(\varphi_A\circ \varphi_B)(V) = r$ となる $A$ の個数を知りたかったです。$(\varphi_A\circ \varphi_B)(V) = V_r$ となる $A$ の個数を $e_{N,n,r}$ とします。$r$ 次元部分空間は全て $V_r$ と同型なので、$c_{N,n,r} = d_{N,r}e_{N,n,r}$ が成り立ちます。
- $W = \varphi_B(V)$ とします。邪魔なので、$\varphi_A$ を単に $\varphi$ と書いていきます。$e_{N,n,r}$ は、 $\varphi(W) = V_r$ となる $\varphi\colon V\longrightarrow V$ の個数です。
- 任意の $W\longrightarrow V$ に対して その延長 $V\longrightarrow V$ がちょうど $|V|^{N-n}$ 個存在します（後述）。また $W$ は $V_n$ と同型です。したがって、全射線形写像 $\varphi\colon V_n\longrightarrow V_r$ の個数を $f_{n,r}$ とすると $e_{N,n,r} = f_{n,r} |V|^{N-n}$ が成り立ちます。
- まとめると、$c_{N,n,r} = d_{N,r}f_{n,r}|V|^{N-n}$ が成り立ちます。
- なお、$K = \mathbb{F}_2$ の状況であれば $|V| = 2^N$ です。
$W$ からの延長の個数を数える部分について補足します。$W$ の基底 $(w_1,\ldots,w_n)$ をとります。これは $V$ の基底 $(w_1,\ldots,w_N)$ に延長できます（線形独立性を保ったままベクトルを追加していく → 限界に達したときそれは基底）。$\varphi\colon V\longrightarrow V$ を定めることは、各 $i$ に対して $\varphi(w_i) \in V$ を1つずつ定めることと等価です。$1\leq i\leq n$ に対してこれらを定めている状態から始めると、選択肢が $|V|^{N-n}$ 通りあります。
より代数に詳しい人向け：補空間 $W’$ をとって $V = W\oplus W’$ とし、$\mathrm{Hom}_K(W\oplus W’,V)\cong \mathrm{Hom}_K(W,V)\times \mathrm{Hom}_K(W’,V)$ を見た。
$d_{N,r}$ の言い換え（$r$ 次元部分空間）
- $V=V_N$ の線形独立な $r$ ベクトルの順序対 $(v_1,\ldots,v_r)$ の個数を $g_{N,r}$ とおきます。
- 線形独立な $r$ 元を持ってくると、それらは $r$ 次元部分空間を生成します。 任意の $r$ 次元部分空間はこの方法で得られます。しかし、この方法だと同じ部分空間が何度も生成されます。重複を間引きましょう。
- 同じ部分空間 $r$ 次元部分空間$W$ を生成するベクトルの順序対はいくつあるでしょうか。$W\cong V_r$ ですからこれは既に記号を持っています。$g_{r,r}$です。
- よって、$d_{N,r} = \frac{g_{N,r}}{g_{r,r}}$ が分かります。
$g_{N,r}$ の計算（線形独立なベクトルの順序対）
言い換え・言い換えで対象物を整理することばかりやってきましたが、そろそろ答を出しにいきます。$g_{N,r}$ は1元ずつ順にとっていくという簡単な方法で計算することができます。
- $(v_1,\ldots,v_r,v_{r+1})$ が線形独立であることは、$(v_1,\ldots,v_r)$ が線形独立であり、かつ、$v_{r+1}$ が $v_1,\ldots,v_r$ の線形結合で書けないことと同値です。
- 後半部分は、$v_{r+1}\notin \mathrm{span}(v_1,\ldots,v_r)$ と同値です。（$\mathrm{span}(v_1,\ldots,v_r)$ は部分空間の生成。生成という単語が初耳の人は、$v_1,\ldots,v_r$ の線形結合全体と考えてください。）
- よって、線形独立な対 $(v_1,\ldots,v_r)$ を得ることは、各時点で $v_{r+1}\notin \mathrm{span}(v_1,\ldots,v_r)$ となる $v_{r+1}$ を選んでいくことと等価。
- $g_{N,r+1} = g_{N,r}\cdot (|V_N| – |V_r|)$が分かります。
$g_{N,0} = 1$なので、これで $g_{N,r}$ が計算できました。実装では上述の漸化式で扱えばよいですし、より公式らしくするなら $g_{N,r} = \prod_{i=0}^{r-1}(|V_N| – |V_i|)$ となります。$K = \mathbb{F}_2$ も思い出すと、$g_{N,r} = \prod_{i=0}^{r-1}(2^N-2^i)$ となります。
$f_{n,r}$ の言い換え（全射線形写像）
あれ、まだ言い換え物が残っていました。
- 一般に、$\varphi\colon V\longrightarrow V’$ を線形写像とします。このとき $\varphi$ で $0$ にうつる元全体 $\{v\in V\mid \varphi(v) = 0\}$ を $\varphi^{-1}(0)$ あるいは $\mathrm{Ker}(\varphi)$ などと書き、$\varphi$ の核（Kernel）といいます。
- 目標物は全射準同型 $\varphi\colon V_n\longrightarrow V_r$ の数え上げでしたが、$W = \mathrm{Ker}(\varphi)$ が一定のものをまとめて数えることにします。
- $V_n$ の部分空間 $W$ を任意にとります。$\mathrm{Ker}(\varphi) = W$ かつ $\varphi(V_n) = V_r$ となる 全射線形写像 $\varphi$ を定めるにはどうすればいいでしょうか。上で出てきたように、$W$ の基底 $(w_1,\ldots,w_m)$ を延長して $V_n$ の基底 $(w_1,\ldots,w_n)$ をひとつとります。
- まず $w_1,\ldots,w_m$ は $0$ にうつす必要があります。また、$w_{m+1},\ldots,w_n$ のうつり先は、$V_r$ の基底にうつす必要があります。実際、うつり先が線形従属だとすると $w_{m+1},\ldots,w_n$ のある線形結合が $0$ にうつることになり、$W = \mathrm{Ker}(\varphi)$ に矛盾します。また、全射線形写像を得るためには、これらのうつり先が $V_r$ を生成する必要があります。
- よって $W$ を固定したとき、$\varphi$ の構成と、$V_r$ の $(n-m)$ 元からなる基底の構成は等価です。$n-m\neq r$ ならばこれは不可能。$n-m = r$ ならば、これは $g_{r,r}$ 通りの方法があります。
- よって $W$ を動かすことで、$f_{n,r} = g_{r,r}\cdot d_{n,n-r}$ が成り立つと分かります。
より代数に詳しい人向け：全射線形写像 $V_n\longrightarrow V_r$ の構成を、準同型定理を利用して、部分空間 $W$ および同型 $V/W\cong V_r$ の構成に帰着しただけです。
$b_{N,n}$ の数え上げ（階数ごとの線形写像の個数）
最後に残しましたが、もう簡単です。
- $\varphi\colon V_N\longrightarrow V_N$ であって、像空間の次元が $n$ であるものを数えたい。
- 像空間 $W$ ごとに数える。
- $W$ を固定すると、$f_{N,n}$ 通り。$W$ の取り方が$d_{N,n}$ 通りある。
$b_{N,n} = d_{N,n} f_{N,n}$ となります。
実装向けまとめ
線形代数の勉強おつかれさまでした。結局、以下で答が出ます。
- $r = \mathrm{rank}(C)$ を計算する。rank は基本変形不変なので、基本変形で階数標準形にうつすことで、$O(N^3)$ で計算できる。
- $g_{N,r} = \prod_{i=0}^{r-1}(2^N-2^i)$
- $d_{N,r} = \frac{g_{N,r}}{g_{r,r}}$
- $f_{n,r} = g_{r,r}d_{n,n-r}$
- $b_{N,n} = d_{N,n} f_{N,n}$
- $c_{N,n,r} = d_{N,r}f_{n,r}2^{N(N-n)}$
- $a_{N,r} = \sum_{n=r}^{N}b_{N,n}c_{N,n,r}$
- $\mathrm{answer} = \frac{a_{N,r}}{b_{N,r}}$
結局、$O(1)$ で計算できる物を $O(N^2)$ 個ほど手に入れればよくて、階数を求めるところを除き $O(N^2)$ です（解説pdf から階数標準形を除き改善）。
類題？
競技プログラミングでは分からないですが、数学で上述の$d$, $g$ あたりは十分有名かと思います。他には
- $\mathrm{GL}(N,\mathbb{F}_q)$ の元の個数を求めよ
- $\mathrm{SL}(N,\mathbb{F}_q)$ の元の個数を求めよ
あたりが、ほとんど同じ考え方を使う類例かと思います。
ここで、体 $K$ に対して $\mathrm{GL}(N,K)$ は、$K$ の元を成分とする$N$次正則行列全体。 $\mathrm{SL}(N,K)$ は、$K$ の元を成分とする行列式が$1$の$N$次正則行列全体です。なお有限体の場合のみ書きますが、少し整数論もやると $\mathrm{SL}(N,\mathbb{Z}/m\mathbb{Z})$ の元を数え上げることなどもできます（中国剰余定理で素べきに帰着。素べきmodは素数modから持ち上げていく）。
答
$\mathrm{GL}(N)$ に関しては、上の解説で出てきた $b_{N,N}$ そのものである。$\mathrm{SL}(N)$ に関しては、$\mathrm{det}$ が $\mathrm{GL(N)}$ から $K^{\times}$ への全射準同型なので、$b_{N,N} / (|K|-1)$ である。
