У Казака Вуса есть поле с размерами \(n \times m\), которое состоит из «0» и «1». Он строит из этого поля бесконечное поле. Это он делает так:
- Берет текущее поле и находит для него новое инвертированное поле. Другими словами, в новом поле будет «1» там, где был «0», а «0» там, где был «1».
- К начальному полю приписывает справа инвертированное поле.
- К начальному полю приписывает снизу инвертированное поле.
- К начальному полю приписывает справа снизу начальное поле.
- Повторяет все это.
Например, если начальное поле было таким:
\(\begin{matrix} 1 & 0 & \\ 1 & 1 & \\ \end{matrix}\) После первой итерации оно станет таким:
\(\begin{matrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{matrix}\) После второй итерации оно станет таким:
\(\begin{matrix} 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0& 0 & 0 & 0 & 1 & 1 \\ \end{matrix}\) И так далее...
Пронумеруем строки сверху вниз от \(1\) до бесконечности, а столбцы слева направо от \(1\) до бесконечности. Назовем подматрицей \((x_1, y_1, x_2, y_2)\) все числа, которые имеют координаты \((x, y)\), такие что \(x_1 \leq x \leq x_2\) и \(y_1 \leq y \leq y_2\).
Казаку иногда нужно находить сумму всех чисел на подматрицах. Так как он очень занят сейчас, помогите ему найти ответы!