Problem 782

Distinct Rows and Columns

The complexity of an $n \times n$ binary matrix is the number of distinct rows and columns.

For example, consider the $3 \times 3$ matrices
$A = (\begin{matrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}) B = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})$
$A$ has complexity $2$ because the set of rows and columns is $000, 101$ .

$B$ has complexity $3$ because the set of rows and columns is $000, 001, 111$ .

For $0 \leq k \leq n^{2}$ , let $c (n, k)$ be the minimum complexity of an $n \times n$ binary matrix with exactly $k$ ones.

Let
$C (n) = \sum_{k = 0}^{n^{2}} c (n, k)$
For example, $C (2) = c (2, 0) + c (2, 1) + c (2, 2) + c (2, 3) + c (2, 4) = 1 + 2 + 2 + 2 + 1 = 8$ .

You are given $C (5) = 64$ , $C (10) = 274$ and $C (20) = 1150$ .

Find $C (10^{4})$ .

不同的行与列

对于一个 $n \times n$ 的 $01$ 矩阵，其复杂度等于其不同的行与列的数量。

例如，考虑如下的 $3 \times 3$ 矩阵
$A = (\begin{matrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}) B = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})$
$A$ 的复杂度为 $2$ ，因为它不同的行与列构成的集合为 $000, 101$ 。

$B$ 的复杂度为 $3$ ，因为它不同的行与列构成的集合为 $000, 001, 111$ 。

对于 $0 \leq k \leq n^{2}$ ，记 $c (n, k)$ 为 $n \times n$ 的 $01$ 矩阵中，包含恰好 $k$ 个 $1$ 的此类矩阵的最小复杂度。

记
$C (n) = \sum_{k = 0}^{n^{2}} c (n, k)$
例如， $C (2) = c (2, 0) + c (2, 1) + c (2, 2) + c (2, 3) + c (2, 4) = 1 + 2 + 2 + 2 + 1 = 8$ 。

已知 $C (5) = 64$ ， $C (10) = 274$ ， $C (20) = 1150$ 。

求 $C (10^{4})$ 。