---

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
$$ \mathbf{A} = \begin{pmatrix} 1 & 0 & 1\\0 & 0 & 0\\1 & 0 & 1\end{pmatrix} \quad
\mathbf{B} = \begin{pmatrix} 0 & 0 & 0\\0 & 0 & 0\\1 & 1 & 1\end{pmatrix} $$
$\mathbf{A}$ has complexity $2$ because the set of rows and columns is ${000,101}$.

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

For $0 \le k \le 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$矩阵
$$ \mathbf{A} = \begin{pmatrix} 1 & 0 & 1\\0 & 0 & 0\\1 & 0 & 1\end{pmatrix} \quad
\mathbf{B} = \begin{pmatrix} 0 & 0 & 0\\0 & 0 & 0\\1 & 1 & 1\end{pmatrix} $$
$\mathbf{A}$的复杂度为$2$，因为它不同的行与列构成的集合为${000,101}$。

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

对于$0 \le k \le 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)$。

---