Editorial - AtCoder Beginner Contest 278

Contest Duration: 2022-11-19 21:00:00+0900 - 2022-11-19 22:40:00+0900 (local time) (100 minutes) Back to Home

Official

Ex - make 1 Editorial by en_translator

Simply put, this problem asks to count the number of matrices subject to constraints about the linear combinations of bases.
In such problem, we often need to handle the sums and products of somewhat cumbersome expressions like \(q^n - q^m\). In fact, the product of \(q^n-q^m\) over varying \(q\) equals the q-binomial coefficients (or Gaussian binomial coefficients) multiplied by a constant factor, and several useful facts are known.
In this article we overview some facts related to the q-binomial coefficients.

q-analog

q-analog is a procedure of introducing \(q\) so that \(q \to 1\) yields the original value.
For example, the q-analog of a natural number \(n\), \(\lbrack \mathbf{n} \rbrack_q\), is defined as follows:

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

Similarly, the q-analog of factorials and binomial coefficients are expressed as follows, which are called q-factorials and q-binomial coefficients:

\[\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 !}.\]

Counting subspaces (typical)

As a matter of fact, the q-binomial coefficients have something to do with combinatorics in a vector space. As a representative example, consider how to count the number of subspaces.

Let \(q\) be a prime and \(V\) be \(n\)-dimensional vector space on \(\mathbb{F}_q\). Then, the number of \(r\)-dimensional subspaces of \(V\) is \(\binom{\mathbf{n}}{\mathbf{r}}_q\).

We introduce some of the proofs. (Once you grasped these proofs, you should be able to handle most of the basic problems related to q-binomial coefficients.)

For convenience, let us denote by \(a_{n, r}\) the number of \(r\)-dimensional subspaces of a \(n\)-dimensional vector space on \(\mathbb{F}_q\). Also, we sometimes omit the subscript \(q\).

Proof 1

Let \(f(n,r)\) be the number of sequences of \(r\) vectors that form a bases set of \(r\)-dimensional subspace of a \(n\)-dimensional vector space.
For \(f(n, r)\), obviously we have

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

so \(a_{n,r}\) coincides with \(\frac{f(n,r)}{f(r,r)}\). Thus, it is sufficient to find \(f(n, r)\).

\(f(n,r)\) is equal to the number of ways to append, to an initially empty list, vectors that are independent of the space spanned by the vectors chosen so far. There are \((q^n-1)\) choices for the first vector, \((q^n - q)\) for the second, \(\dots\), and \((q^n - q^{r-1})\) for the \(r\)-th. Therefore,

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

With some deformations, we can assert that the number of \(r\)-dimensional subspaces of a \(n\)-dimensional vector space is

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

Proof 2

We solve it by defining a vector sequence that corresponds to bases one-to-one, and counting the sequences.
For a vector \(v\) on \(\mathbb{F}_q\), let us define \(\mathrm{top}(v)\) to be the largest \(i\) such that \(v_i \neq 0\). (If there is no such \(i\), let \(\mathrm{top}(v) = -1\).)

Then, the \(r\)-dimensional subspace of a \(n\)-dimensional vector space corresponds one-to-one to \(r\) vectors \(b_1, \dots, b_r\) such that:

\(0 \leq \mathrm{top}(b_1) \lt \dots \lt \mathrm{top}(b_r) \leq n-1\);
the \(\mathrm{top}(b_i)\)-th element of \(b_i\) is \(1\);
for all integer pairs \((i, j)\) \((1 \leq i \lt j \leq r)\), the \(\mathrm{top}(b_i)\)-th element of \(b_j\) is \(0\).

Once we boil it down to counting such normalized sequences of vectors, we find the following recurrence relations of \(a_{n, r}\):

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

By the way, we have the following equality about the q-binomial coefficients:

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

Therefore, the conjecture can be proved inductively.

Proof 3

We may exploit generating functions. We can express the number of normalized sequences of vectors mentioned in Proof 2 in terms of generating functions as

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

all that left to evaluate this.
Let \(b_{n,r} = a_{n,r} q^{r(r-1)/2}\) and \(f_n(x) =\sum_{r} b_{n,r} x^r = \prod_{i=1}^{n} (q^i x + 1)\), then

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

and comparing the \(r\)-th coefficients yields

\[ \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} \]

Together with \(b_{n,0} = 1\), we have

\[ \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} \]

from which we can assert that \(a_{n,r} = \binom{\mathbf{n}}{\mathbf{r}}_q\).

In competitive programming, the key of the q-binomial coefficients is that, just like the ordinary binomial coefficients, we can also evaluate \(\binom{\mathbf{n}}{\mathbf{r}}\) in an \(\mathrm{O}(1)\) time if we precalculate \(\lbrack \mathbf{n} \rbrack_q !\) and their inverses.
We enumerated some exercises in the end of this article. Some of them as well as this problem requires an optimization based on this fact.

Solution

The desired answer is

(good sequences of length \(N\)), subtracted by
(good sequences of length \(N-1\)) \(\times (2^B - N + 1)\).

Since we can evaluate both 1 and 2 if we can count “the number of not good sequences of length \(N\),” so we rephrase in this way.

We apply a rather unorthodox inclusion-exclusion principle. Let

\(F(s) :=\) (the number of not good sequences \(A\) obtained by \(s\) operations in the Problem Statement);
\(G(s) := \) (the number of not good sequences \(A\) obtained by repeatedly choosing one of \([0, 2^B)\) and pushing it to \(A\) \(s\) times).

We have the following relation between \(F(\ast)\) and \(G(\ast)\):

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

and conversely

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

Since we can enumerate \({s \brack 1}, \dots, {s \brack s}\) in a total of \(\mathrm{O}(N \log N)\) time, it is sufficient to enumerate \(G(1), G(2), \dots, G(N)\) to solve this problem.

Now let us consider how to find \(G(s)\). Let \(G(s, r)\) be the number of objects for \(G(s)\) such that the rank of \(A\) is \(r\) when regarded as \((S \times B)\)-matrix on \(\mathbb{F}_2\). In the similar way as the observation in the “counting subspace” chapter, we notice

\[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.\]

Therefore

\[ \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} \]

so we can enumerate \(G(1), G(2), \dots, G(N)\) in a total of \(\mathrm{O}(N \log N + B)\) using convolution.
Hence, the problem can be solved in a total of \(\mathrm{O}(N \log N + B)\) time, which is fast enough.