Hi everyone!

Thanks to K1o0n and Noobish_Monk for the round. This problem looks scary at first, but the final idea is short. I will explain it slowly, step by step, so even beginners can follow. If something is unclear, ask in the comments!

What does the problem ask?

We have a table of numbers with

$ rows and

$ columns. Pick any rectangle inside it (a "submatrix"). Let its height be

$, its width be

$, and the sum of its numbers be

$.

• If

$ is even, its price is

$. - If

$ is odd, its price is

$.

We need the total price of all rectangles, modulo

$. Also

$, so we need roughly an

$ solution.

Why is brute force too slow?

A table has about

$ rectangles. For

$ that is far too many. We need a smarter idea.

Let's try a tiny example first

Take one row with 3 numbers:

$. The rectangles are:

• length 1 (even sum of sizes):

$ - length 2 (odd):

$ - length 3 (even):

$

If you expand and add everything, almost all terms cancel and you get:

$

**The middle number

$ disappeared completely!** Only the 1st and 3rd numbers matter. This tells us that most of the stuff cancels out, and we just need to find what survives.

Step 1: Break

$ into pairs

$ means "sum of all numbers" times "sum of all numbers". So

$ is the sum of

$ over every pair of cells

$ inside the rectangle (the pair

$ and

$ both count, and

$ is allowed).

Now flip the viewpoint:

Instead of "for each rectangle, look at all pairs inside it", do "for each pair of cells, look at all rectangles that contain both".

So for each pair we only need the total of signs of all rectangles containing both cells. Call it

$. Then

$

Step 2: Rows and columns are independent

A rectangle is chosen by top row

$, bottom row

$, left column

$, right column

$. The sign is

$

because

$ and

$ (the

$s cancel in pairs and the minus signs don't change parity).

So the sign splits into a row part and a column part, and

$. We can handle rows alone, then columns alone.

Step 3: Solve the rows (columns are the same)

Let the two cells have rows with smaller value

$ and larger value

$. To contain both cells, the rectangle needs

$ and

$. So

$

These are sums like

$, where neighbours cancel:

• First part:

$ up to

$. If

$ is even, everything cancels and it's

$. If

$ is odd, one

$ is left, so it's

$. - Second part: sum from

$ to

$. If

$ and

$ have different parity, the count of terms is even and it cancels to

$. If they have the same parity, one term is left and it's

$.

Conclusion for rows: the pair contributes only if - the smaller row is odd, and - the larger row has the **same parity as

$**.

In that case

$. Columns work the same way with

$.

Multiplying:

$. This is a constant, so

$

That is why the code ends with: "if

$ is odd, negate the total".

Check with our example

$ (

$,

$): a pair is valid if the smaller column is odd and the larger column is odd. The valid column pairs are

$, which gives

$. ✓

Step 4: Add up the valid pairs fast

We still can't check all pairs (too slow), so we use prefix sums.

For a pair of cells, one of them is "up/left" and the other is "down/right" in terms of the roles of min and max. Depending on whether

$ or

$ holds the smaller row, and whether

$ or

$ holds the smaller column, there are exactly 4 cases:

(In cases 2 and 4 cell 1 is the "other" cell of the pair, so the ordered pair is counted from the other side. The "strict" versus "can touch" choices make sure no pair is counted twice when two cells share a row or column.)

For each cell in the table, we need:

"the sum of all good cells in the region down-right (or down-left) of me"

That is exactly what a 2D suffix sum gives in

$. We build two tables:

• S0: suffix sums going down-right over cells with row ≡ n and column ≡ m.
• S1: suffix sums going down-left over cells with row ≡ n and column odd.

Then for every cell with an odd row, we multiply its value by the right table lookup for each case and add it to total.

Complexity

• Time:

$ per test - Memory:

$

The sum of

$ over all tests is at most

$, so this runs comfortably

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        int W = m + 2;
        size_t sz = (size_t)(n + 2) * W;
        // id(i, j) = position of cell (i, j) in a flat array
        auto id = [&](int i, int j) { return (size_t)i * W + j; };
        vector<ll> A(sz, 0), S0(sz, 0), S1(sz, 0);

        // read the table, keep values in [0, MOD)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                ll x;
                scanf("%lld", &x);
                x %= MOD;
                if (x < 0) x += MOD;
                A[id(i, j)] = x;
            }

        // S0: suffix sums (down-right) over cells with row ≡ n, col ≡ m
        for (int i = n; i >= 1; i--)
            for (int j = m; j >= 1; j--) {
                ll v = ((i & 1) == (n & 1) && (j & 1) == (m & 1)) ? A[id(i, j)] : 0;
                S0[id(i, j)] = ((v + S0[id(i + 1, j)] + S0[id(i, j + 1)]
                                 - S0[id(i + 1, j + 1)]) % MOD + MOD) % MOD;
            }

        // S1: suffix sums (down-left) over cells with row ≡ n, col odd
        for (int i = n; i >= 1; i--)
            for (int j = 1; j <= m; j++) {
                ll v = ((i & 1) == (n & 1) && (j & 1)) ? A[id(i, j)] : 0;
                S1[id(i, j)] = ((v + S1[id(i + 1, j)] + S1[id(i, j - 1)]
                                 - S1[id(i + 1, j - 1)]) % MOD + MOD) % MOD;
            }

        ll total = 0;
        for (int i = 1; i <= n; i += 2) {      // smaller row must be odd
            for (int j = 1; j <= m; j++) {
                ll a = A[id(i, j)];
                if (j & 1) {                    // col odd
                    total = (total + a * S0[id(i, j)]) % MOD;         // case 1
                    total = (total + a * S0[id(i + 1, j + 1)]) % MOD; // case 2
                }
                if ((j & 1) == (m & 1)) {       // col ≡ m
                    total = (total + a * S1[id(i, j - 1)]) % MOD;     // case 3
                    total = (total + a * S1[id(i + 1, j)]) % MOD;     // case 4
                }
            }
        }
        // the constant sign (-1)^(n+m)
        if ((n + m) & 1) total = (MOD - total) % MOD;
        printf("%lld\n", total);
    }
    return 0;
}