Official

Ex - make 1 Editorial by Nyaan

今回の問題は簡単にいうと、基底の線形結合に関する条件がついたベクトルの集合を数え上げる問題です。
このような問題では、 \(q^n - q^m\) のような少し扱いづらい式の積や和が登場しがちです。実はこの \(q^n-q^m\) を \(m\) を動かして積を取った数は q-二項係数 (ガウスの二項係数) という名前の付いた数の定数倍になり、いくつかの便利な事実が知られています。
今回は q-二項係数に関連する話を簡単にまとめました。

q-類似

\(q \to 1\) を取ると元のものに一致するように \(q\) を導入することを q-類似 と呼びます。
例えば、自然数 \(n\) の q-類似 \(\lbrack \mathbf{n} \rbrack_q\) は次のように定義されます。

\[\lbrack \mathbf{n} \rbrack_q := 1 + q + \dots + q^{n-1} = \frac{1-q^n}{1-q}\]

同様に、階乗や二項係数の q-類似は次のようになり、これらは q-階乗 や q-二項係数 と呼ばれています。

\[\lbrack \mathbf{n} \rbrack_q ! := \prod_{m=1}^n \lbrack \mathbf{m} \rbrack_q\]

\[\binom{\mathbf{n}}{\mathbf{r}}_q := \frac{\lbrack \mathbf{n} \rbrack_q !}{\lbrack \mathbf{r} \rbrack_q !\lbrack \mathbf{n-r} \rbrack_q !}\]

部分空間の数え上げ(典型)

q-二項係数は実はベクトル空間上の数え上げと関わりがある値です。代表例として部分空間の数え上げを考えます。

\(q\) を素数とする。\(V\) を \(\mathbb{F}_q\) 上の \(n\) 次元ベクトル空間とする。このとき、\(V\) の \(r\) 次元部分空間の個数は \(\binom{\mathbf{n}}{\mathbf{r}}_q\) である。

いくつかの証明を紹介します。(これらの証明を押さえておけば q-二項係数絡みの基本的な問題はだいたい対処できると思います)

以下では求める答えである (\(\mathbb{F}_q\) 上の\(n\) 次元ベクトル空間の \(r\) 次元部分空間の個数) を便宜上 \(a_{n, r}\) と置きます。また、下付きの \(q\) は適宜省略します。

証明 1

ベクトルからなる \(r\) 要素の列であって、それらが \(n\) 次元ベクトル空間の \(r\) 次元部分空間の基底をなすものの個数を \(f(n,r)\) とします。
\(f(n, r)\) について、明らかに

\[a_{n, r} \times f(r, r) = f(n, r)\]

が成り立つので、\(a_{n,r}\) は \(\frac{f(n,r)}{f(r,r)}\) と一致します。よって \(f(n, r)\) が計算できればよいです。

\(f(n,r)\) は空の列に今まで選んだベクトルからなる空間と独立なベクトルを \(1\) 本ずつ追加していく操作の通り数に言い換えられます。追加する通り数は、\(1\) 本目は \(q^n - 1\) 通り, \(2\) 本目は \(q^n - q\) 通り, \(\dots\), \(r\) 本目は \(q^n - q^{r-1}\) 通りです。よって

\[f(n,r) = (q^n - 1) (q^n - q) \dots (q^n - q^{r-1})\]

となります。そして、\(n\) 次元ベクトル空間の \(r\) 次元部分空間の通り数は、いくらかの式変形により

\[\frac{f(n,r)}{f(r,r)} = \frac{[\mathbf{n}]!}{[\mathbf{n-r}]![\mathbf{r}]!} = \binom{\mathbf{n}}{\mathbf{r}}\]

になることが確認できます。

証明 2

基底に 1 対 1 対応するベクトル列を定めて、それを数え上げる方針で解きます。
\(\mathbb{F}_q\) ベクトル \(v\) に対して \(\mathrm{top}(v)\) を \(v_i \neq 0\) であるような最大の \(i\) として定めます。(そのような \(i\) が無い場合は \(\mathrm{top}(v) = -1\) )

このとき、\(n\) 次元ベクトル空間の \(r\) 次元部分空間は次の条件を満たす \(r\) 個のベクトル \(b_1, \dots, b_r\) と1 対 1 対応します。

  • \(0 \leq \mathrm{top}(b_1) \lt \dots \lt \mathrm{top}(b_r) \leq n-1\)
  • \(b_i\) の \(\mathrm{top}(b_i)\) 番目の要素は \(1\) である。
  • すべての整数の組 \((i, j)\) \((1 \leq i \lt j \leq r)\) について \(b_j\) の \(\mathrm{top}(b_i)\) 番目の要素は \(0\) である。

このように正規化されたベクトル列の個数を数え上げる問題を考えると、\(a_{n, r}\) について以下の漸化式が成り立つことがわかります。

\[a_{n, r} = q^{n-r} a_{n-1, r-1} + a_{n-1, r}\]

ところで、 q-二項係数について次の式が成り立ちます。

\[\binom{\mathbf{n}}{\mathbf{r}} = q^{n-r} \binom{\mathbf{n-1}}{\mathbf{r-1}} + \binom{\mathbf{n-1}}{\mathbf{r}} \]

よって、命題は帰納的に証明できます。

証明 3

母関数を利用して求めることもできます。 証明 2 に登場する正規化されたベクトルの個数を母関数で記述すると

\[a_{n, r} = q^{-r(r+1)/2} [x^r]\prod_{i=1}^{n} (q^i x + 1)\]

になるので、これを求めればよいです。
\(b_{n,r} = a_{n,r} q^{r(r-1)/2}, f_n(x) =\sum_{r} b_{n,r} x^r = \prod_{i=1}^{n} (q^i x + 1)\) と置きます。すると

\[f_n(x) (q^{n+1} x + 1) = f_n (qx) (qx + 1)\]

が成り立ち、両辺の \(r\) 次の係数を見ると

\[ \begin{aligned} &q^{n+1} b_{n,r-1} + b_{n,r} = q^r (b_{n,r-1} + b_{n,r})\\ &\to b_{n,r} = \frac{q^r - q^{n+1}}{1-q^r}a_{n,r-1} \end{aligned} \]

を得られます。\(b_{n,0} = 1\) とあわせて

\[ \begin{aligned} b_{n,r} &= \frac{(q^1 - q^{n+1}) \dots (q^r - q^{n+1})}{(1-q^1) \dots (1-q^r)}\\ &= q^{r(r+1)/2}\frac{(1 - q^n) \dots (1 - q^{n+1} - r)}{(1-q^1) \dots (1-q^r)}\\ &=q^{r(r+1)/2} \binom{\mathbf{n}}{\mathbf{r}} \end{aligned} \]

となり、ここから \(a_{n,r} = \binom{\mathbf{n}}{\mathbf{r}}_q\) が確認できます。

さて、競技プログラミングにおける q-二項係数のポイントとしては、q-二項係数も通常の二項係数と同様に、\(\lbrack \mathbf{n} \rbrack_q !\) およびその逆元を前計算すれば \(\binom{\mathbf{n}}{\mathbf{r}}\) が \(\mathrm{O}(1)\) で求まるという点が挙げられます。
末尾に出題例を何問か挙げましたが、出題例の一部、および今回の問題はこの点を利用して高速化することを要求しています。

解法

求めたい答えは

  1. (長さ \(N\) の良い数列) から
  2. (長さ \(N-1\) の良い数列) \(\times (2^B - N + 1)\) を 引いたもの

です。1, 2 はともに「長さ \(N\) の良い数列 でない 数列の個数」が求まればただちに計算できるので、これを求める問題に言い換えて考えます。

少し変則的な包除原理を利用します。

  • \(F(s) :=\) (問題文の操作を \(s\) 回やった時に得られる、良い数列でない \(A\) の個数)

  • \(G(s) := \) (\([0, 2^B)\) から 1 つ選んで \(A\) に push するのを \(s\) 回繰り返したときに得られる、良い数列でない \(A\) の個数)

と置きます。\(F(\ast)\) と \(G(\ast)\) の関係を考えると

\[G(s) = \sum_{t=0}^s {s \brace t} F(t)\]

になり、反転して

\[F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brack t} G(t)\]

となります。\({s \brack 1}, \dots, {s \brack s}\) は \(\mathrm{O}(N \log N)\) で列挙できるので、 \(G(1), G(2), \dots, G(N)\) を列挙すればこの問題を解くことができます。

\(G(s)\) を求める問題を考えます。\(G(s)\) の数え上げの対象である \(A\) のうち、\(A\) を \(S \times B\) の \(\mathbb{F}_2\) 係数行列とみなしたときの rank が \(r\) である場合の答えを \(G(s, r)\) とすると、「部分空間の数え上げ」の章における考察を応用すれば

\[G(s, r) = 2^{\frac{r(r+1)}{2}} \frac{\lbrack \mathbf{B-1} \rbrack_2 !}{\lbrack \mathbf{B-1-r} \rbrack_2 !} \binom{\mathbf{s}}{\mathbf{r}}_2\]

であるとわかります。よって

\[ \begin{aligned} G(s) &= \sum_{r=0}^s G(s, r) \\ &=\sum_{r=0}^s 2^{\frac{r(r+1)}{2}} \frac{\lbrack \mathbf{B-1} \rbrack!}{\lbrack \mathbf{B-1-r} \rbrack!} \binom{\mathbf{s}}{\mathbf{r}} \\ &=\lbrack \mathbf{B-1} \rbrack! \lbrack \mathbf{s} \rbrack ! \sum_{r=0}^s \left( \frac{2^{\frac{r(r+1)}{2}} }{ \lbrack \mathbf{B-1-r} \rbrack! \lbrack \mathbf{r} \rbrack!}\right) \left(\frac{1}{\lbrack \mathbf{s-r} \rbrack!}\right) \end{aligned} \]

になり、上式を利用すると \(G(1), G(2), \dots, G(N)\) は畳み込みで \(\mathrm{O}(N \log N + B)\) で列挙できます。
以上よりこの問題を全体で \(\mathrm{O}(N \log N + B)\) で解くことができて、これは十分高速です。

関連問題

q-二項係数を利用して解ける問題を (想定解・非想定解を問わず) 以下にまとめました。

(ネタバレ防止用に畳んでいます)

posted:
last update: