Задача №114744. Латинский квадрат
Крис любит решать разные головоломки. Недавно он узнал про судоку, идея которых основана на латинских квадратах. Таблица размера \(k \times k\) называется латинским квадратом , если количество различных элементов в таблице равно \(k\), и ни в одной строке и ни в одном столбце нет двух одинаковых элементов.
Например,
| A | B |
| B | A |
| S | P | R |
| R | S | P |
| P | R | S |
| Q |
| A | B | C |
| C | C | A |
| C | A | B |
| A | B | C |
| D | C | A |
| C | A | B |
| A | B | C |
| C | A | B |
Крис хочет сделать новую головоломку на основе латинских квадратов. Однако, у него есть только старая заготовка, которая является таблицей размера \(n \times m\). Крис хочет вырезать из заготовки одну сплошную часть, которая будет являться латинским квадратом. Сколькими способами он может это сделать? Два способа считаются разными, если есть клетка таблицы-заготовки, которая принадлежит вырезаемой части в одном случае и не принадлежит в другом.
В первой строке даны два целых числа \(n\) и \(m\) — размеры заготовки (\(1 \le n, m \le 2\,000\)).
В следующих \(n\) строках даны строки \(s_i\) — описание заготовки. Каждая строка \(s_i\) состоит из \(2 \cdot m\) символов с ASCII-кодами от \(33\) до \(126\). В клетке заготовки на пересечении \(i\)-й строки и \(j\)-го столбца находится пара символов \(s_{i, 2 \cdot j - 1}\) и \(s_{i, 2 \cdot j}\) (\(1 \le i \le n\), \(1 \le j \le m\)). Элементы в двух клетках заготовки равны, если упорядоченные пары символов в этих клетках равны. За подробным пояснением входных данных смотрите замечания.
Выведите одно целое число — количество способов вырезать из заготовки латинский квадрат.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||
| Группа | Баллы | \(n, m\) | Необх. группы | Комментарий} |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 9 | \(n, m \le 20\) | 0 | |
| 2 | 10 | \(n, m \le 100\) | 0, 1 | |
| 3 | 25 | \(n, m \le 500\) | 0, 1, 2 | |
| 4 | 26 | – | – | В каждой строке и каждом столбце все элементы различны. |
| 5 | 30 | – | 0, 1, 2, 3, 4 | Offline-проверка. |
4 5 AABBAAAACC BBAABBCCAA AABBCCAABB BBCCAABBCC
26
5 10
!"#$%&'()*+,-./01234
56789:;<=>?@ABCDEFGH
IJKLMNOPQRSTUVWXYZ[\
]^_`abcdefghijklmnop
qrstuvwxyz{|}~!"#$%&50