Назовём двоичную матрицу (матрицу, где каждое числ...

Ключ к задаче — понять, какие именно матрицы можно «обнулить» операциями переворота всех 4 ячеек любого блока 2×2.

1) Критерий «интересности»

Пусть у нас есть подматрица размера $h\times w$. Одна операция инвертирует ровно две клетки в каждой из двух строк и ровно две клетки в каждой из двух столбцов. Значит, чётность сумм по каждой строке и каждому столбцу не меняется. У нулевой матрицы все эти суммы чётные, следовательно:

Подматрица «интересна» тогда и только тогда, когда сумма в каждой её строке чётна и сумма в каждом её столбце чётна (по модулю 2).

Это верно и для вырожденных случаев $h=1$ или $w=1$: там операций 2×2 нет, и условие «все строки и столбцы чётные» эквивалентно «все элементы равны 0».

(Доказательство достаточности стандартно: из матрицы с чётными строками/столбцами можно последовательными 2×2-переворотами занулить клетки, двигаясь, например, слева направо и сверху вниз.)

---

2) Как быстро посчитать число «интересных» подматриц

Обозначим исходную матрицу как $a$ (элементы $0/1$), размеры $r\times c$.

Идея: фиксируем пару строк $(top,\,bot)$ и «схлопываем» между ними матрицу по вертикали до вектора паритетов столбцов — так мы проверяем столбцовую часть условия; внутри «хороших» отрезков столбцов (где паритет столбца чётный) посчитаем, у скольких подотрезков ещё и все строки дают чётную сумму.

Шаги

1. Переберём все пары строк $(top\le bot)$. Пусть высота блока $h=bot-top+1$.

2. Для каждой колонки $j$ посчитаем

$$P[j]=\bigoplus_{i=top}^{bot} a_{i,j}\quad(\text{XOR по вертикали}).$$

Столбец «подходит», если $P[j]=0$.

3. Разобьём столбцы на максимальные «хорошие» отрезки, где $P[j]=0$ подряд. На плохом столбце отрезок обрывается.

4. Внутри одного такого отрезка считаем подотрезки, где каждая из $h$ строк даёт чётную сумму.
   Для этого заведём вектор накопленных префиксных XOR по строкам

$$U = (u_{top},u_{top+1},\dots,u_{bot})\in \{0,1\}^h,$$

изначально нулевой в начале отрезка. Идём слева направо по столбцам отрезка, на каждом столбце $j$ делаем

$$U \mathrel{\oplus=} \big(a_{top,j},a_{top+1,j},\dots,a_{bot,j}\big).$$

Количество подотрезков с чётными суммами по всем строкам — это число пар позиций $(L,R)$ внутри отрезка, у которых префиксные векторы совпадают: $U(R)=U(L-1)$. Стандартно это считается счётчиком одинаковых $U$: держим хеш-таблицу частот встреченных $U$; на каждом шаге добавляем в ответ freq[U], затем инкрементируем freq[U]. Перед началом отрезка в таблице лежит только нулевой вектор с частотой 1.

5. Просуммировать ответы по всем отрезкам и всем парам строк.

Сложность

• Пары строк: $O(r^2)$.
• По каждой паре — один проход по $c$ столбцам с обновлением вектора длины $h$.
• При реализации $U$ как битсета/массива 64-битных слов: $O\!\left(r^2\cdot c \cdot \lceil h/64\rceil\right)$.
  На практике это быстро при $r$ до ~400–800 и $c$ до ~4000–10000. Для больших размеров можно:
  • делить по меньшей стороне (перебирать пары по более короткой размерности),
  • использовать рандомизированные 64-битные хеши строк, уменьшая константы.

---

3) Замечания по корректности и краям

• Случаи $h=1$ или $w=1$ автоматически корректно обрабатываются описанным алгоритмом: «хорошие» отрезки — это нули в единственной агрегированной строке/столбце, а условие по строкам/столбцам превращается в «все нули».
• Никаких дополнительных инвариантов, кроме чётностей по строкам и столбцам, нет — они и необходимы, и достаточны.

---

4) Короткий конспект решения

• Лемма: матрица обнуляема 2×2-переворотами ⇔ все её строки и столбцы имеют чётную сумму.
• Подсчёт: для каждой пары строк соберите «хорошие» колонны (с нулевым вертикальным XOR), разбейте на отрезки, внутри отрезка считайте подотрезки, где префиксный вектор XOR по строкам совпадает на концах (частоты одинаковых векторов).

Если хотите, набросаю эталонный код (C++/PyPy) с битсетами/хешами под ваши ограничения входа.

ниже — быстрое решение на Python за $O(r^2\cdot c)$ с надёжным (детерминированным) хешированием по строкам. Идея: фиксируем пару строк $(top,bot)$; по каждому столбцу ведём

• col_par[j] — чётность столбца на этом вертикальном отрезке;
• col_hash[j] — XOR из 64-битных хешей тех строк в этом столбце, где стоит 1.

Далее разбиваем столбцы на максимальные отрезки, где col_par==0; внутри каждого считаем число подотрезков с чётными суммами по всем строкам через «одинаковые префиксные XOR» (счётчик частот).

python
from collections import defaultdict
import random

def count_interesting_submatrices(a):
    """
    a: список списков из 0/1, размер r x c
    возвращает количество «интересных» подматриц
    """
    r = len(a)
    if r == 0:
        return 0
    c = len(a[0])

    # детерминированные 64-битные "хэши" для строк
    rnd = random.Random(0)
    row_hash = [rnd.getrandbits(64) for _ in range(r)]

    ans = 0

    # фиксируем верхнюю строку
    for top in range(r):
        # при наращивании bot поддерживаем по каждому столбцу:
        col_par = [0] * c          # паритет по вертикали на [top..bot]
        col_hash = [0] * c         # XOR хэшей тех строк, где в столбце стоит 1

        # наращиваем нижнюю строку
        for bot in range(top, r):
            rb = row_hash[bot]
            row_b = a[bot]

            # обновляем вертикальные агрегаты по всем столбцам
            for j in range(c):
                if row_b[j]:
                    col_par[j] ^= 1
                    col_hash[j] ^= rb

            # теперь идём по столбцам, выделяя «хорошие» сегменты col_par==0
            j = 0
            while j < c:
                # пропускаем «плохие» столбцы
                while j < c and col_par[j] != 0:
                    j += 1
                if j >= c:
                    break
                # старт хорошего сегмента
                start = j
                while j < c and col_par[j] == 0:
                    j += 1
                end = j  # [start, end)

                # внутри сегмента считаем подотрезки с чётными суммами по всем строкам
                pref = 0
                freq = defaultdict(int)
                freq[0] = 1
                for k in range(start, end):
                    pref ^= col_hash[k]
                    ans += freq[pref]
                    freq[pref] += 1

    return ans


# ---- Пример использования ----
if __name__ == "__main__":
    # Пример: считывание из stdin формата:
    # r c
    # r строк по c чисел 0/1 (без пробелов или через пробелы — оба варианта поддержим)
    import sys
    data = sys.stdin.read().strip().split()
    if data:
        it = iter(data)
        r = int(next(it))
        c = int(next(it))
        a = []
        for _ in range(r):
            row = []
            # поддержка строк вида '0101' или '0 1 0 1'
            peek = next(it)
            if len(peek) == c and set(peek) <= {"0", "1"}:
                row = [int(ch) for ch in peek]
            else:
                # первый токен — уже число, добираем ещё c-1
                row.append(int(peek))
                for _ in range(c - 1):
                    row.append(int(next(it)))
            a.append(row)
        print(count_interesting_submatrices(a))

Что делает код

• Для каждой пары строк $(top,bot)$ поддерживает по столбцам:
  • col_par[j] = XOR_{i=top..bot} a[i][j] — фильтруем только отрезки столбцов с чётной суммой.
  • col_hash[j] = XOR_{i=top..bot, a[i][j]=1} row_hash[i] — «вектор паритетов строк» в сжатом виде.
• Внутри каждого «хорошего» сегмента (где col_par==0) считаем число подотрезков, у которых префиксные XOR по col_hash совпадают — стандартный приём «сколько пар одинаковых префиксов», дающий подматрицы с чётной суммой в каждой строке.
• Итог — сумма по всем парам строк и сегментам.