0%

Problem 626


Problem 626


Counting Binary Matrices

A binary matrix is a matrix consisting entirely of 0s and 1s. Consider the following transformations that can be performed on a binary matrix:

  • Swap any two rows
  • Swap any two columns
  • Flip all elements in a single row (1s become 0s, 0s become 1s)
  • Flip all elements in a single column

Two binary matrices $A$ and $B$ will be considered equivalent if there is a sequence of such transformations that when applied to $A$ yields $B$. For example, the following two matrices are equivalent:

$$A=\begin{pmatrix}
1 & 0 & 1 \
0 & 0 & 1 \
0 & 0 & 0
\end{pmatrix}\quad
B=\begin{pmatrix}
0 & 0 & 0 \
1 & 0 & 0 \
0 & 0 & 1
\end{pmatrix}$$

via the sequence of two transformations “Flip all elements in column 3” followed by “Swap rows 1 and 2”.

Define $c(n)$ to be the maximum number of $n\times n$ binary matrices that can be found such that no two are equivalent. For example, $c(3)=3$. You are also given that $c(5)=39$ and $c(8)=656108$.

Find $c(20)$, and give your answer modulo $1\ 001\ 001\ 011$.


01矩阵计数

01矩阵指的是只由0或1构成的矩阵。对于任意01矩阵,可以进行以下变形:

  • 交换任意两行
  • 交换任意两列
  • 翻转一行中所有元素(1变成0,0变成1)
  • 翻转一列中所有元素

现有两个01矩阵$A$和$B$,如果能够通过一系列上述变形能够将$A$变为$B$,则称$A$和$B$是 等价的。例如,如下的两个矩阵就是等价的:

$$A=\begin{pmatrix}
1 & 0 & 1 \
0 & 0 & 1 \
0 & 0 & 0
\end{pmatrix}\quad
B=\begin{pmatrix}
0 & 0 & 0 \
1 & 0 & 0 \
0 & 0 & 1
\end{pmatrix}$$

只需先翻转$A$中第三列的元素,然后交换第一行和第二行即可得到$B$。

在所有$n\times n$的01矩阵中,记两两互不等价的01矩阵数目最多为$c(n)$。例如,$c(3)=3$,$c(5)=39$,以及$c(8)=656108$。

求$c(20)$,并将你的答案对$1\ 001\ 001\ 011$取余。