Дан массив \(a\) длины \(n\) и массив \(b\) длины \(m\), оба состоящие из чисел \(0\) и \(1\). Рассмотрим матрицу \(c\) размера \(n \times m\), построенную по следующему правилу: \(c_{i, j} = a_i \cdot b_j\) (то есть \(a_i\), умноженное на \(b_j\)). Несложно заметить, что \(c\) также состоит только из нулей и единиц.
Сколько подпрямоугольников размера \(k\), состоящих только из единиц, есть в \(c\)?
Подпрямоугольник — это пересечение непрерывного подотрезка строк и непрерывного подотрезка столбцов матрицы. Рассмотрим четыре числа \(x_1, x_2, y_1, y_2\) (\(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le m\)), тогда подпрямоугольник \(c[x_1 \dots x_2][y_1 \dots y_2]\) — это пересечение строк \(x_1, x_1+1, x_1+2, \dots, x_2\) и столбцов \(y_1, y_1+1, y_1+2, \dots, y_2\).
Размер (площадь) подпрямоугольника — это количество элементов матрицы в нём.
Примечание
В первом примере матрица \(c\) такова:
В ней есть \(4\) подпрямоугольника размера \(2\), состоящих только из единиц:
Во втором примере матрица \(c\) такова:
