AI Finds Nothing Here — Deon Nicholas

Problem

Given integers $n, m, r, c$ $(1 \leq r \leq n \leq 10^9,\ 1 \leq c \leq m \leq 10^9)$ .

An $n \times m$ binary matrix of $0$ 's and $1$ 's is valid if every contiguous submatrix of size $r \times c$ has a total xor of $0$ .

How many valid binary matrices are there? (Modulo $998244353$ .)

Initial Observations

Binary.
Xor's.
Construction.
Everything seems "fixed" once you've chosen some cells.
Greed?
Fix $r \cdot c - 1$ cells?

IdeaFix some cells freely, the rest are forcedAC

Pretty quickly I figured you might be able to set a few cells freely as either $0$ or $1$ , which would force other cells to a single value (the only choice that makes the xor equal $0$ ). Then, with a sweep of sorts, you might be able to find them all.

Key Observation

Look at the top-left $r \times c$ submatrix. If you arbitrarily select all $r \cdot c$ cells except one — say the bottom-right cell $(r, c)$ — then the value of that cell is forced: there is exactly one choice that makes the xor of the submatrix $0$ .

Key Observation

Once the top-left $r \times c$ submatrix is fixed, slide the window one step to the right (or down). Most of the cells inside are already decided — only the newly entered column (or row) is undecided. Choose all of its cells freely except the bottom-right one, which the xor rule forces. Repeat until the window reaches the edge, in both directions.

Draw a Picture

At this point, it's easier to look at an example of what happens as you slide. Here's a $5 \times 6$ matrix ( $n = 5$ , $m = 6$ ) with a $2 \times 3$ window ( $r = 2$ , $c = 3$ ).

Legend:   ·  free choice (0 or 1)      x  forced by the xor rule
          .  not yet decided          +--+  the current window
 
Step 1 — the top-left 2x3 window: pick 5 cells freely, the 6th is forced
 
    +----------+
    | ·  ·  ·  | .  .  .
    | ·  ·  x  | .  .  .
    +----------+
      .  .  .    .  .  .
      .  .  .    .  .  .
      .  .  .    .  .  .
 
Step 2 — slide right one: only the entering column is new; its bottom
cell is forced, the rest chosen freely
 
       +----------+
     · | ·  ·  ·  | .  .
     · | ·  x  x  | .  .
       +----------+
      .  .  .  .    .  .
 
Step 3 — after sliding across the whole top: a row of x's emerges
 
      ·  ·  ·  ·  ·  ·
      ·  ·  x  x  x  x
      .  .  .  .  .  .
 
Step 4 — same idea sliding down from the top-left: a column of x's
 
      ·  ·  ·  ·  ·  ·
      ·  ·  x  x  x  x
      ·  ·  x  .  .  .
      ·  ·  x  .  .  .
      ·  ·  x  .  .  .
 
Step 5 — slide into the remaining region (bottom-right corner of each
window placement is always the only unknown): everything else is forced
 
      ·  ·  ·  ·  ·  ·
      ·  ·  x  x  x  x
      ·  ·  x  x  x  x
      ·  ·  x  x  x  x
      ·  ·  x  x  x  x

After doing this, you'll see the top rows and left columns were chosen arbitrarily, and the x's fill in the rest: every remaining window placement has its bottom-right corner as the only unknown cell, so sliding the window over the whole matrix forces everything else.

Key Observation

In the end, every cell at position $(i, j)$ with $i \geq r$ and $j \geq c$ is forced — an $(n - r + 1) \times (m - c + 1)$ rectangle of forced cells anchored at the bottom-right corner. All other cells (the top $r - 1$ rows and the left $c - 1$ columns) can be chosen freely.

Write It Out

The formula becomes clear from here: $2$ choices for every free cell, exactly one choice for every forced cell.

\begin{aligned} \text{ALL} &= n \cdot m \\ \text{FORCED} &= (n - r + 1)(m - c + 1) \\ \text{FREE} &= \text{ALL} - \text{FORCED} \\ \text{CHOICES} &= 2^{\text{FREE}} = 2^{\,n m \,-\, (n - r + 1)(m - c + 1)} \end{aligned}

Since $n$ and $m$ can be up to $10^9$ (so the exponent can be around $10^{18}$ ), and everything is modulo $998244353$ , you cannot exponentiate naively.

Draw from Experience

You can compute $a^b \bmod p$ in $O(\log b)$ time with fast exponentiation (repeated squaring).

Algorithm

PRIME = 998244353
 
def pow2(e):                    # 2^e mod PRIME by repeated squaring
    res, base = 1, 2
    while e:
        if e % 2: res = res * base % PRIME
        base = base * base % PRIME
        e //= 2
    return res
 
def solve(n, m, r, c):
    total  = n * m                        # 64-bit: up to ~10^18
    forced = (n - r + 1) * (m - c + 1)
    free   = total - forced
    return pow2(free)

Generate and Test

The first idea I had turned out to be the right one, so I started from it and checked that it worked, which led us here.

Examine Examples

The sliding observation felt relatively obvious to me, but getting it exactly right meant checking a few low-hanging examples (including the sample test cases), along with drawing it out and writing out the formula.

Review

The answer is $2^{\,nm - (n-r+1)(m-c+1)} \bmod 998244353$ , computed with fast exponentiation in $O(\log(nm))$ . The path:

One cell per window is forced. In the top-left $r \times c$ window, choose all cells but one freely — the last is forced by the xor rule. [1]
Slide the window. Each step right or down introduces one new column or row: all of it is free except the bottom-right cell of the window, which is forced. Sweeping the window over the whole matrix decides every cell. [2]
The forced region is a rectangle. Exactly the cells $(i, j)$ with $i \geq r$ and $j \geq c$ are forced — $(n-r+1)(m-c+1)$ of them; the rest are free. [3]
Count the choices: $2$ per free cell, so $2^{\,nm - (n-r+1)(m-c+1)}$ — with the exponent up to $\sim 10^{18}$ , computed by repeated squaring modulo $998244353$ .

References

Problem-solving techniques used:

Generate and Test

The problem was straightforward enough that the first idea turned out to be correct; I mostly spent the time verifying the exact mechanics to reach the final formula.

Draw a Picture

This problem became relatively easy once I drew out exactly what happens as the rectangle slides — key to seeing that the block from $(r, c)$ to $(n, m)$ is completely forced and everything else is free.

Examine Examples

The small test cases were good for getting a feel for it all.

Write It Out

Getting the formula exactly right was a matter of just writing it down cleanly.

Draw from Experience

Fast exponentiation is a standard technique that should be in any competitive programmer's "book of code."

Learning points:

I've hit a lot of problems needing fast exponentiation lately as I've been getting back into competitive programming — and I'm rusty enough that I couldn't code it cleanly from memory without a couple of tiny bugs. Adding it to my "book of code"; it really should just be standard.

Topics:

Math / counting / combinatorics
Binary representation / XOR
Constructive algorithms / proof by construction
Sweep / sliding window
Fast exponentiation