Поиск правильных подматриц

Ниже приведён один из возможных вариантов решения задачи на языке Python без использования каких-либо «подсказок контекста».

Идея решения (кратко):

1. Матрица называется «правильной», если в ней ровно две разные буквы и они расположены в шахматном порядке.

   • Под «шахматным порядком» понимается, что все клетки одной чётности (по сумме индексов строки и столбца) содержат одну и ту же букву, а все клетки другой чётности — вторую букву.
   • Причём эти две буквы должны отличаться (т.,е. ровно две различные буквы).

2. Чтобы посчитать количество таких подматриц, можно перебрать все пары различных букв $(a_1, a_2)$. Для каждой пары проверяются два варианта раскладки по чётностям:

   • чётные клетки содержат $a_1$, нечётные — $a_2$;
   • чётные клетки содержат $a_2$, нечётные — $a_1$.

3. Для фиксированной пары букв и фиксированного распределения «(чётность $\to$ буква)» мы строим вспомогательную бинарную матрицу $X$ размера $n \times m$, где

   $$X[i][j] = \begin{cases} 1, & \text{если условие на букву/чётность в (i,j) выполняется},\\ 0, & \text{иначе}. \end{cases}$$

   Тогда любая подматрица исходной матрицы будет «шахматной» с нужной парой букв в точности тогда, когда в этой подматрице все элементы $X$ равны 1 (то есть подматрица в $X$ целиком состоит из единиц).

4. Задача сводится к тому, чтобы в бинарной матрице $X$ подсчитать количество подматриц, состоящих только из единиц.

5. Подсчёт количества подматриц из единиц в $X$ можно сделать за $O(n \times m)$ при помощи «гистограммного» метода (иногда его называют методом поиска максимального прямоугольника в бинарной матрице, но мы его дорабатываем, чтобы считать все прямоугольники, а не только максимально возможный):

   • Идём по строкам сверху вниз.

   • Для каждой строки $r$ поддерживаем массив height[j] (для $j=0..m-1$), где height[j] равен количеству подряд идущих единиц по вертикали «над» $(r,j)$ (включая текущую строку $r$).

   • Для текущей строки хотим узнать, сколько прямоугольников целиком из единиц «заканчиваются» на этой строке (т.,е. имеют нижнюю границу в строке $r$).

   • Если мы рассмотрим массив height как гистограмму, то количество всех прямоугольников в гистограмме (которые могут закончиться на этой высоте) можно найти, зная для каждой позиции $j$ «длину» расширения влево и вправо, в пределах которой height[...] >= height[j].

     • Пусть left[j] — индекс самой левой колонки, где высота меньше height[j],
       а right[j] — индекс за самой правой колонкой, где высота меньше height[j].
       Тогда количество способов выбрать левую и правую границу прямоугольника, который включает колонку $j$ и имеет высоту $\ge height[j]$, равно $$(j - \text{left}[j]) \;\times\; (\text{right}[j] - j).$$
     • По вертикали мы можем выбрать любую из height[j] строк наверх (то есть $height[j]$ вариантов), потому что все они подряд имеют высоту не меньше height[j].
     • Значит, вклад от колонки $j$ к общему числу прямоугольников равен $$height[j] \;\times\; (j - \text{left}[j]) \;\times\; (\text{right}[j] - j).$$

   • Суммируя по всем $j$ для данной строки $r$, получаем число прямоугольников, заканчивающихся на $r$. Далее добавляем этот результат к общему счётчику.

6. Повторяем такие подсчёты для каждой пары букв $(a_1, a_2)$ и двух вариантов распределений по чётностям. Все результаты суммируем.

7. Выдаём итоговую сумму.

Решение

python
def solve():
    import sys
    data = sys.stdin.read().strip().split()
    # Первая строка: n, m
    n, m = map(int, data[:2])
    # Далее n строк по m символов
    matrix = data[2:]
    
    # Преобразуем матрицу в список строк (или можно список списков)
    # Здесь matrix уже список из n строк, каждая длиной m
    # Убедимся, что действительно строк n, каждая по m символов:
    assert len(matrix) == n
    for row in matrix:
        assert len(row) == m
    
    # Буквы, которые могут встречаться
    letters = 'abcdefghijklmnopqrstuvwxyz'
    
    # Чтобы быстрее проверять, какая буква в какой ячейке,
    # можно сделать словарь {буква -> индекс}, но ниже
    # просто воспользуемся сравнением символов напрямую.
    
    # Функция подсчёта числа подпрямоугольников, состоящих только из 1 в бинарной матрице X
    def count_submatrices_of_ones(X):
        """
        X - список списков из 0/1, размер n x m
        Возвращает число всех подпрямоугольников, в которых все элементы == 1.
        """
        n_loc = len(X)
        m_loc = len(X[0])
        
        # height[j] = сколько подряд единиц по вертикали над (i,j) (включая текущую строку)
        height = [0]*m_loc
        
        total_rectangles = 0
        
        for i in range(n_loc):
            # Обновим высоты:
            for j in range(m_loc):
                if X[i][j] == 1:
                    height[j] += 1
                else:
                    height[j] = 0
            
            # Найдём для каждого j: left[j] - ближайший слева столбец с высотой меньше height[j]
            # Используем монотонный стек
            left = [-1]*m_loc
            stack = []
            for j in range(m_loc):
                while stack and height[stack[-1]] >= height[j]:
                    stack.pop()
                left[j] = stack[-1] if stack else -1
                stack.append(j)
            
            # Найдём для каждого j: right[j] - ближайший справа столбец с высотой меньше height[j]
            right = [m_loc]*m_loc
            stack = []
            for j in range(m_loc-1, -1, -1):
                while stack and height[stack[-1]] >= height[j]:
                    stack.pop()
                right[j] = stack[-1] if stack else m_loc
                stack.append(j)
            
            # Теперь считаем вклад в общее число прямоугольников
            for j in range(m_loc):
                h = height[j]
                # Кол-во способов выбрать колонки, включающие j,
                # при условии, что высота >= h:
                width_count = (j - left[j]) * (right[j] - j)
                # По вертикали можно выбрать любую из h строк (высота)
                total_rectangles += h * width_count
        
        return total_rectangles
    
    # Главная часть: перебор всех пар букв
    from itertools import combinations
    
    # Для удобства сделаем функцию, создающую матрицу X (0/1) под конкретную «раскладку»
    # a0, a1 - две различные буквы,
    # parity0 = True означает: на клетках с чётной суммой (i+j) ставим a0, с нечётной - a1
    # Возвращает X (n x m) из 0 и 1, где 1 - если в (i,j) нужная буква, иначе 0.
    def build_binary_matrix(a0, a1, parity0=True):
        X = [[0]*m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                # p = (i+j) % 2
                p = (i + j) & 1
                # Если parity0=True, то p=0 -> a0, p=1 -> a1
                # Если parity0=False, то p=0 -> a1, p=1 -> a0
                if parity0:
                    need = a0 if p == 0 else a1
                else:
                    need = a1 if p == 0 else a0
                if matrix[i][j] == need:
                    X[i][j] = 1
                else:
                    X[i][j] = 0
        return X
    
    answer = 0
    
    # Перебираем все пары различных букв (комбинации из 26 возможных латинских)
    # Но будем учитывать только те буквы, которые реально встречаются в матрице,
    # чтобы не тратить время на лишнее. Для этого найдём множество всех букв в матрице.
    used_letters = set()
    for row in matrix:
        used_letters.update(row)
    used_letters = sorted(list(used_letters))
    
    # Теперь берём все пары из used_letters
    for a0, a1 in combinations(used_letters, 2):
        # 1) Раскладка: чётные -> a0, нечётные -> a1
        X = build_binary_matrix(a0, a1, parity0=True)
        answer += count_submatrices_of_ones(X)
        
        # 2) Раскладка: чётные -> a1, нечётные -> a0
        X = build_binary_matrix(a0, a1, parity0=False)
        answer += count_submatrices_of_ones(X)
    
    print(answer)

Пояснения к коду

1. Чтение входных данных:

   • Первые два числа $`n`, `m`$ — размеры матрицы.
   • Далее считываем $n$ строк по $m$ символов.

2. Подготовка к перебору пар:

   • Собираем множество всех букв, реально встречающихся в исходной матрице, чтобы не перебирать впустую пары из 26 латинских букв, которые не встречаются совсем.

3. Для каждой пары букв $(a_0, a_1)$ строим две бинарные матрицы:

   • В одной чётные позиции $(i+j)\%2=0$ заполняются буквой $a_0$, а нечётные — $a_1$.
   • В другой — наоборот ($a_0\leftrightarrow a_1$).
     В местах, где буква совпадает с требуемой, ставим 1, иначе 0.

4. Функция count_submatrices_of_ones(X) подсчитывает количество подпрямоугольников из одних единиц в бинарной матрице $X$ за $O(n \times m)$.

   • Идём по строкам, накапливаем «высоты» подряд идущих единиц в массиве height[j].
   • Для каждой строки используя стек, вычисляем, как далеко можно «расширять» прямоугольник влево и вправо для каждой высоты height[j].
   • Вычисляем вклад в общее количество подпрямоугольников.

5. Суммируем результаты по всем парам букв и двум вариантам раскладки. Выводим итоговую сумму.

Данный алгоритм корректен, поскольку:

• Любая «правильная» подматрица для некоторой пары букв $(a_0, a_1)$ обязательно отразится в одной из двух бинарных матриц (с соответствующим распределением по чётностям) как область, где все значения равны 1.
• Мы корректно считаем все подпрямоугольники из 1 в бинарных матрицах.
• Пары букв $(a_0, a_1)$ перебираются без повторений, и каждая «шахматная» подматрица в исходной задаче будет учтена ровно один раз в подходящем варианте.

При необходимости можно оптимизировать детали ввода-вывода, но в целом идея решения остаётся такой же.