# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* pols_agyi_pols

*mexomerf*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Given N and M, both even, define F(K) to be the minimum possible sum of \sum_{i=1}^N R_i + \sum_{i=1}^M C_i across all N\times M boolean grids containing exactly K ones.

R_i denotes the bitwise XOR of the i-th row, and C_i denotes the bitwise XOR of the i-th column.

Find \displaystyle\sum_{K=1}^{NM} F(K).

# EXPLANATION:

First, we of course need to figure out what F(K) actually is.

If K is a multiple of 4, we always have F(K) = 0.

This is because the N\times M grid can be tiled with 2\times 2 subgrids (since N and M are both even), and taking some \frac{K}{4} of these subgrids will give us K ones while also ensuring that every row and every column has an even number of ones; hence each R_i and C_i will be 0.

This observation also tells us that it might be helpful to look at values of K modulo 4, so we do exactly that.

- If K = 4x, F(K) = 0 as noted above.
- If K = 4x+1, F(K) = 2.

We can place 4x ones using the above strategy, which leaves us with a single extra.

Anywhere it’s placed, that row and column will have an odd number of ones; giving a sum of 2.- It’s further not hard to see that 2 is optimal, because having an odd number of ones in total means some row and some column must contain an odd number of ones.

- Similarly, if K = 4x+3, we have F(K) = 2 again.

Place 4x ones in 2\times 2 blocks, then choose any 2\times 2 block and fill in three of its slots. This leaves one row and one column with an odd number of ones.

That only leaves the K = 4x+2 case.

For this, observe that we certainly have F(K) \leq 2 - using the same strategy as above, we can fill in 4x cells using 2\times 2 subgrids, then fill in two adjacent cells in another subgrid.

However, we can sometimes do better!

When N = 2 or M = 2, we don’t really have enough space for more fancy arrangements.

In these cases, indeed F(K) = 2 when K is 2 modulo 4.

## Proof

Without loss of generality, let N = 2.

If every column contains either 0 or 2 ones, the number of ones in the first and second row must be equal.

But there are 4x+2 ones in total, meaning 2x+1 in each row (which is odd).

So, R_1 + R_2 = 2 while all the C_i are 0.

On the other hand, if some column contains exactly one 1, there must be at least one more column containing exactly one 1 (since the total number of ones is even).

In this case, the value of the grid is at least 2.

So, when N = 2, we have F(K) = 2 when K = 4x+2.

M = 2 is similar, just flip the dimensions.

Now, suppose N, M\geq 4.

If K = 2, then the best we can do is place both ones in the same row or column; giving F(2) = 2.

Similarly, if K = N\cdot M - 2, the best we can do is remove two ones from the same row/column, giving a value of 2 again.

In every other case, we in fact have F(K) = 0.

## How?

For this, it’s helpful to look at the case N = M = 4.

Observe that for K = 6 and K = 10, we have the following arrangements:

```
1100
0110
1010
0000
```

```
1111
1100
1010
1001
```

These ensure that every row and column has an even number of ones.

Now, for an arbitrary N, M, K (where N, M \geq 4 and 2 \lt K \lt N\cdot M - 2), do the following:

- If K = 6 or K = 10, use the above strategies to obtain a value of 0.

We’re now left with K \gt 10. - Keep the top-left 4\times 4 grid aside for now.

The remainder of the grid can be tiled using \frac{NM}{4} - 4 subgrids of size 2\times 2. - Repeatedly keep filling in these 2\times 2 grids till you need to place 10 ones.

Then, place these 10 ones in the top-left 4\times 4 grid in the above pattern.

Finally, we need to actually sum this up across all K.

However, since every value is either 0 or 2, that’s actually quite simple.

- If N = 2 or M = 2, we have F(K) = 0 when K is a multiple of 4, and F(K) = 2 otherwise.

Summing this up across all K gives \displaystyle 2\cdot \frac{3NM}{4} = \frac{3NM}{2} - If N, M \geq 4, we have F(K) = 2 for every odd K, and K = 2 and N\cdot M - 2.

That gives us a value of \displaystyle 2\cdot\frac{NM}{2} + 4 = NM + 4.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, m = map(int, input().split())
if n == 2 or m == 2:
print((3*n*m)//2)
else:
print(n*m + 4)
```