Правильные подматрицы задачи

Ниже приведён один из возможных путей решения задачи на Python с учётом ограничений $n, m \le 300$.

Основная идея:

1. Подсчитать все «правильные» подматрицы высотой $\ge 2$ с помощью «инкрементального» прохода по строкам:

   • Фиксируем верхнюю границу подматрицы $r_1$.
   • По очереди расширяем нижнюю границу $r_2$ от $r_1$ до $n-1$. Таким образом рассматриваем все подматрицы, начинающиеся в строке $r_1$ и заканчивающиеся в строке $r_2$.
   • При добавлении каждой новой строки $r_2$ «инкрементально» обновляем для каждого столбца информацию:
     • какая буква встречается в «чёрных» клетках (цвет $(i+j) \bmod 2 = 1$) этого столбца, и вся ли она одинакова;
     • какая буква встречается в «белых» клетках (цвет $(i+j) \bmod 2 = 0$) этого столбца, и вся ли она одинакова.
   • Если в столбце $c$ при текущем наборе строк все «белые» клетки имеют ровно одну букву (не противоречат друг другу) и все «чёрные» клетки — ровно одну (другую) букву, то такой столбец считается «валидным».
   • Далее нужно найти, сколько непрерывных горизонтальных отрезков столбцов подряд имеют одну и ту же пару букв $(\text{letter}_0, \text{letter}_1)$ и при этом $\text{letter}_0 \neq \text{letter}_1$. Каждый такой непрерывный участок длины $L$ даёт вклад $\frac{L\,(L+1)}{2}$ в число подматриц (так как любой подотрезок внутри него порождает уникальную «правильную» подматрицу).

   Такой способ позволяет за $O(n^2 \cdot m)$ (с учётом аккуратной обработки) перебрать все прямоугольники высотой $\ge 2$.

2. Отдельно учесть «правильные» подматрицы высотой $1$.

   • Если подматрица состоит ровно из одной строки $r$, то её «шахматная» раскраска вдоль этой строки будет вида $(r + c)\bmod 2$.
   • Для отрезка столбцов $[c_1..c_2]$ (в одной фиксированной строке) «правильность» означает:
     1. Среди всех столбцов $c$ в этом отрезке, где $(r + c)\bmod 2 = 0$, буква в клетке одинакова (назовём её $A$).
     2. Среди столбцов, где $(r + c)\bmod 2 = 1$, буква в клетке одинакова (назовём её $B$).
     3. $A \neq B$.
     4. В отрезке действительно есть столбцы обоих цветов (иначе там будет либо только $A$, либо только $B$, что не даёт «двух различных букв» в шахматном узоре).
   • Чтобы эффективно посчитать количество таких отрезков в одной строке, можно использовать «скользящее окно» (two pointers) или похожую идею группировки. Главное – уметь быстро определять, что во всех «белых» позициях встречается не более одной буквы, во всех «чёрных» позициях — не более одной, и что эти буквы различны.
   • Для этого внутри одной строки заведём счётчики/частотные массивы (по 26 букв) отдельно для «белых» и для «чёрных» позиций. Будем двигать правую границу отрезка вперёд, а левую сдвигать при нарушении условия (например, появилось больше одной возможной буквы среди «белых» или среди «чёрных», или буквы у белых и чёрных совпали, или нет хотя бы одной позиции «белого» и одной «чёрного» цвета). Каждый раз, когда подотрезок $[s..e]$ стал валидным и его длина $\ge 2$, он даёт вклад в ответ.

Полный код, реализующий оба шага, может выглядеть довольно объёмно, поэтому приведём один из вариантов реализации, достаточно подробно прокомментированный.

python
def solve():
    import sys
    data = sys.stdin.read().strip().split()
    n, m = map(int, data[:2])
    # Далее идут n строк по m символов
    matrix = data[2:]
    
    # -----------------------------------------------------------------------------
    # Часть 1: считаем количество "правильных" подматриц высотой >= 2
    # -----------------------------------------------------------------------------
    #
    # Идея:
    # 1) Фиксируем r1 (верхняя строка).
    # 2) Для r2 от r1 до n-1 накапливаем информацию о каждом столбце:
    #    - col0Letter[c]: какой символ у "белых" ((i+c)%2 == 0) клеток данного столбца
    #      (если раньше все белые клетки были одинаковы, иначе -1 означает "невалидно",
    #      -2 означает "ещё не встречали белую клетку"? -- ниже упростим, инициализируем сразу
    #      при добавлении первой строки)
    #    - col1Letter[c]: аналогично для "чёрных" ((i+c)%2 == 1) клеток.
    # 3) Получив для каждого столбца c пару (col0Letter[c], col1Letter[c]) (если не -1),
    #    группируем подряд идущие столбцы с одинаковой парой (A, B), где A != B, A,B != -1.
    #    Пусть длина такого блока L, он даёт L*(L+1)//2 подматриц.
    #
    # Ограничение: смотрим только подматрицы, у которых количество строк (r2-r1+1) >= 2,
    # поскольку иначе один столбец не может содержать и "белые", и "чёрные" клетки.
    #
    
    answer_multirow = 0
    
    # col0Letter[c] и col1Letter[c] будем хранить как либо конкретный символ (char),
    # либо None, если уже столкнулись с противоречием в этом столбце для цвета.
    # Начальное значение тоже None, пока не заполним первой строкой.
    
    for r1 in range(n):
        # Инициализируем массивы
        col0Letter = [None]*m
        col1Letter = [None]*m
        
        # Будем наращивать нижнюю границу r2
        for r2 in range(r1, n):
            # Добавляем строку r2 к текущему "вертикальному" прямоугольнику
            h = r2 - r1 + 1  # высота текущего подпрямоугольника
            
            # Пройдемся по всем столбцам и обновим col0Letter[c], col1Letter[c]
            for c in range(m):
                if ((r2 + c) % 2) == 0:
                    # Это "белая" клетка по шахматному цвету
                    if col0Letter[c] is None:
                        # Ещё не было белой клетки в этом столбце (для текущего набора строк)
                        col0Letter[c] = matrix[r2][c]
                    else:
                        # Проверяем совпадение
                        if col0Letter[c] != matrix[r2][c]:
                            col0Letter[c] = None  # конфликт, инвалидируем
                else:
                    # "Чёрная" клетка
                    if col1Letter[c] is None:
                        col1Letter[c] = matrix[r2][c]
                    else:
                        if col1Letter[c] != matrix[r2][c]:
                            col1Letter[c] = None
            
            # Если высота = 1, столбец содержит клетки только одного цвета,
            # значит в таком столбце мы НЕ можем сразу же получить "белые+чёрные клетки".
            # Поэтому подматрицы высотой = 1 мы здесь не учитываем.
            # Считаем только если h >= 2:
            if h >= 2:
                # Теперь нужно за один проход по столбцам посчитать,
                # сколько подряд идущих имеют одинаковую пару (col0Letter, col1Letter),
                # причём обе буквы не None и отличаются друг от друга.
                current_pair = None
                current_len = 0
                
                for c in range(m):
                    A = col0Letter[c]
                    B = col1Letter[c]
                    # Проверим валидность
                    if A is None or B is None or A == B:
                        # Невалидная пара, обрываем текущую серию
                        if current_pair is not None:
                            # добавляем количество подотрезков
                            answer_multirow += current_len * (current_len + 1) // 2
                            current_pair = None
                            current_len = 0
                    else:
                        # Пара (A, B) валидна
                        if current_pair == (A, B):
                            current_len += 1
                        else:
                            # Закрываем предыдущую серию
                            if current_pair is not None:
                                answer_multirow += current_len * (current_len + 1) // 2
                            current_pair = (A, B)
                            current_len = 1
                
                # Закрыть последнюю серию
                if current_pair is not None:
                    answer_multirow += current_len * (current_len + 1) // 2
    
    # -----------------------------------------------------------------------------
    # Часть 2: считаем количество "правильных" подматриц высотой = 1
    # -----------------------------------------------------------------------------
    #
    # Если подматрица состоит из одной строки r и столбцов c1..c2,
    # то "шахматный" цвет клетки (r, c) есть (r+c) % 2.
    # Условие "правильности":
    #   - Все столбцы, где (r+c) % 2 = 0, имеют одну и ту же букву A.
    #   - Все столбцы, где (r+c) % 2 = 1, имеют одну и ту же букву B != A.
    #   - В подотрезке [c1..c2] есть хотя бы один c с цветом 0 и хотя бы один c с цветом 1.
    #   - Длина подотрезка >= 2 (иначе невозможно иметь и цвет0, и цвет1 в одной строке).
    #
    # Можно решить при помощи "скользящего окна" (двух указателей).
    
    def count_one_row_submatrices(row_string, row_index, m):
        res = 0
        
        # color0_freq[l] -- сколько раз буква l (0..25) встретилась на позициях, где цвет=0
        # color1_freq[l] -- где цвет=1
        color0_freq = [0]*26
        color1_freq = [0]*26
        
        # Число различных букв среди позиций цвета 0
        distinct0 = 0
        # Число различных букв среди позиций цвета 1
        distinct1 = 0
        
        # Сколько всего клеток цвета 0 в текущем окне [left..right]
        count0 = 0
        # Сколько всего клеток цвета 1
        count1 = 0
        
        left = 0
        
        for right in range(m):
            c = row_string[right]
            letter_id = ord(c) - ord('a')
            if ((row_index + right) % 2) == 0:
                # цвет 0
                count0 += 1
                color0_freq[letter_id] += 1
                if color0_freq[letter_id] == 1:
                    distinct0 += 1
            else:
                # цвет 1
                count1 += 1
                color1_freq[letter_id] += 1
                if color1_freq[letter_id] == 1:
                    distinct1 += 1
            
            # "Сжимаем" левую границу, пока подотрезок [left..right] не станет валидным
            # Критерии валидности:
            # 1) distinct0 <= 1
            # 2) distinct1 <= 1
            # 3) count0 > 0 и count1 > 0 (обе "краски" должны быть в отрезке)
            # 4) если distinct0 == 1 и distinct1 == 1, то единственные буквы не должны совпадать
            while True:
                # Проверяем, валиден ли текущий [left..right]
                if distinct0 <= 1 and distinct1 <= 1 and count0 > 0 and count1 > 0:
                    # Если ровно по 1 букве в каждом цвете, проверим различны ли они
                    if distinct0 == 1 and distinct1 == 1:
                        # Находим какие именно буквы
                        # (так как distinct0==1, среди color0_freq ровно одна буква > 0)
                        # (аналогично для color1_freq)
                        letter0 = -1
                        for i in range(26):
                            if color0_freq[i] > 0:
                                letter0 = i
                                break
                        letter1 = -1
                        for i in range(26):
                            if color1_freq[i] > 0:
                                letter1 = i
                                break
                        if letter0 == letter1:
                            # невалидно
                            pass
                        else:
                            # валидно, можно выходить из while
                            break
                    else:
                        # Если distinct0 == 0 или distinct1 == 0, или одна из них больше 1,
                        # либо нет обоих цветов - тоже невалидно
                        pass
                # Иначе невалидно - будем двигать left
                if left > right:
                    # Окно пустое, выходим
                    break
                # Убираем left-элемент
                c_left = row_string[left]
                letter_left = ord(c_left) - ord('a')
                if ((row_index + left) % 2) == 0:
                    # уходящая клетка была цвет0
                    count0 -= 1
                    color0_freq[letter_left] -= 1
                    if color0_freq[letter_left] == 0:
                        distinct0 -= 1
                else:
                    # цвет1
                    count1 -= 1
                    color1_freq[letter_left] -= 1
                    if color1_freq[letter_left] == 0:
                        distinct1 -= 1
                left += 1
            
            # Теперь [left..right], если он валиден, то все его подотрезки, заканчивающиеся в right
            # и начинающиеся от left..(right-1) тоже проверять. Нам нужны подотрезки длиной >= 2.
            length = right - left + 1
            if length >= 2:
                # Все подотрезки, заканчивающиеся в right, начинаются от индексов s, где s >= left
                # Так что количество таких подотрезков = length-1 (т.е. s = left..(right-1))
                # Но добавляем именно length - 1
                res += (length - 1)
        
        return res
    
    answer_singlerow = 0
    for r in range(n):
        answer_singlerow += count_one_row_submatrices(matrix[r], r, m)
    
    # Суммарный результат
    answer = answer_multirow + answer_singlerow
    print(answer)

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

1. Подсчёт для высоты $\ge 2$:

   • Для каждой пары строк $(r_1, r_2)$ последовательно «наращиваем» информацию о столбцах.
   • В массиве col0Letter[c] храним текущую букву для «белых» клеток (цвет 0) в столбце $c$ или None, если либо буква ещё не определена, либо уже был конфликт. Аналогично col1Letter[c] для «чёрных» (цвет 1).
   • Каждый раз, когда добавляем новую строку $r_2$, проходим по всем столбцам и обновляем эти значения (проверяем, совпадает ли новая буква с уже хранящейся).
   • Затем одним проходом по столбцам считаем длины подряд идущих одинаковых пар $(\text{letter}_0,\text{letter}_1)$. Каждая такая непрерывная группа длины $L$ даёт $L \times (L+1)/2$ подпрямоугольников по горизонтали.

2. Подсчёт для высоты $=1$:

   • В одной фиксированной строке $r$ просматриваем все подотрезки столбцов $[c_1..c_2]$.
   • Цвет клетки определяется $(r+c)\bmod 2$. Нужно, чтобы все клетки цвета 0 в этом отрезке имели одну букву, все клетки цвета 1 — одну (другую) букву, и чтобы в отрезке был хотя бы один столбец цвета 0 и хотя бы один столбец цвета 1.
   • Реализуем через технику «скользящего окна»: ведём частотные массивы для букв «белых» позиций и «чёрных» позиций.
   • Двигаем правую границу right, постепенно добавляя столбцы. Если в окне нарушаются условия (например, среди «белых» больше одной возможной буквы), то двигаем левую границу left, убирая лишние столбцы, пока окно снова не станет «валидным».
   • Для каждого right (после «сжатия» левой границы) количество подотрезков, заканчивающихся на right и длиной $\ge2$, равно $\max(0, \text{(текущее\_окно\_размер)} - 1)$.

В сумме оба подхода дают искомое число всех «правильных» подматриц.

• Сложность для высоты $\ge2$: $O(n^2 \cdot m)$.
• Сложность для высоты $=1$: $O(n \cdot m)$ (при аккуратной реализации скользящего окна фактически $O(n \cdot m)$).

Итого при $n, m \le 300$ код может работать на грани, но при достаточно оптимизированном Python (или PyPy) обычно укладывается в разумные ограничения.

Итог: вышеуказанный скрипт читает входные данные в формате задачи, выводит одно число — количество «правильных» подматриц. В примерах:

• Если подать:

  text
  2 2
  ab
  ba

  Должно получиться 5.
• Если подать:

  text
  2 2
  aa
  aa

  Должно получиться 0.