Table Splits
Time limit3sMemory limit256 MB
Count the choices of two interior row cuts and two interior column cuts for which the sum of the five corner parts of the resulting 3x3 split is even.
- Level
Medium7 of 10
- Topics
- Prefix sum, Combinatorics, Math, Implementation
- Solved
- No attempts yet
Problem
Consider a numeric table A[1..n, 1..m] filled with zeros and ones. Any four integers (r1, r2, c1, c2) with 1 ≤ r1 < r2 < n and 1 ≤ c1 < c2 < m define a split of the table into nine parts, as shown in the figure.
Let sum(A**i) be the sum of the numbers in part A**i. Let S = sum(A1) + sum(A3) + sum(A5) + sum(A7) + sum(A9). Your task is to determine, for a given table A, the number of splits for which S is even.
For example, the table
0101
0101
0100
has three splits. For (r1=1, r2=2, c1=1, c2=2) and (r1=1, r2=2, c1=1, c2=3), the sum of the numbers in the odd-numbered parts is two, which is even. For (r1=1, r2=2, c1=2, c2=3), the sum is three, which is odd. Thus two splits qualify.
Input
The first line contains two integers n and m (3 ≤ n, m ≤ 3000). Each of the following n lines contains m characters, which describe a row of the table A.
Output
Print the number of quadruples (r1, r2, c1, c2) such that:
- 1 ≤ r1 < r2 < n;
- 1 ≤ c1 < c2 < m;
- the sum of the numbers in the odd-numbered parts of the table A is even.