Задача 626
Подсчет двоичных матриц

Двоичная матрица - это матрица, состоящая исключительно из нулей и единиц. Рассмотрим следующие преобразования, которые можно выполнить над двоичной матрицей:

  • Поменять местами любые два ряда
  • Поменять местами любые два столбца
  • Обратить все элементы одного ряда (1 становятся 0, а 0 становятся 1)
  • Обратить все элементы одного столбца

Две бинарные матрицы $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}$

через последовательность из двух преобразований "Обратить все элементы столбца 3" и "Поменять местами ряды 1 и 2".

Определим $c(n)$ как максимальное количество двоичных матриц $n\times n$, из которых никакие две не эквивалентны. Например, $c(3)=3$. Вам также дано, что $c(5)=39$ и $c(8)=656108$.

Найдите $c(20)$ и дайте остаток от деления полученного числа на $1\,001\,001\,011$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net