Crosses

Observation 1: switch from half-sizes to actual rectangle sizes

Each of the two centered rectangles has odd side lengths: $X_1=2a+1,\quad Y_1=2b+1,\quad X_2=2c+1,\quad Y_2=2d+1.$

So a cross is the union of two axis-aligned odd-by-odd rectangles with the same center.

That already implies a cute fact:

• every such union has odd area,
• therefore if $s$ is even, the answer is immediately $0$.

Free pruning. We take those.

Observation 2: for a fixed shape, centers are easy to count

Let $R=\max(X_1,X_2),\qquad T=\max(Y_1,Y_2).$ These are the outer height and outer width of the union.

To fit the whole cross on the grid, the center must stay far enough from every border. The number of valid rows for the center is $n-R+1,$ and similarly the number of valid columns is $m-T+1.$ So every ordered pair of rectangle sizes with outer dimensions $(R,T)$ contributes $(n-R+1)(m-T+1)$ placements.

So the real task is:

For every odd $R\le n$ and odd $T\le m$, count how many ordered pairs of rectangles have outer dimensions exactly $(R,T)$ and union area $s$.

That’s the whole game.

Observation 3: only two structural cases exist

Fix odd $R,T$.

There are only two possibilities.

Case A: one rectangle is already the full $R\times T$

Then the union area is simply $RT.$ The other rectangle can be any odd sub-rectangle: $P\le R,\quad Q\le T,\quad P,Q\text{ odd}.$

How many choices?

• number of odd $P\le R$ is $\frac{R+1}{2}$,
• number of odd $Q\le T$ is $\frac{T+1}{2}$.

So the number of possible second rectangles is $\frac{R+1}{2}\cdot\frac{T+1}{2}.$

Since the pair is ordered, the full $R\times T$ rectangle can be either the first or the second one, so multiply by $2$. But if both rectangles are $R\times T$, that ordered pair was counted twice and should only count once.

Therefore, when $s=RT$, the number of ordered pairs is $2\cdot \frac{R+1}{2}\cdot \frac{T+1}{2}-1.$

Case B: neither rectangle is the full $R\times T$

Then one rectangle must provide the maximum height, and the other must provide the maximum width. So the pair looks like $R\times Q\quad\text{and}\quad P\times T,$ where $P<R,\qquad Q<T,$ and all four numbers are odd.

Their union area is $RQ+PT-PQ.$ A nicer form is $RQ+PT-PQ = RT-(R-P)(T-Q).$

Now the trick: since $R,P,T,Q$ are odd, both differences are even. Write $R-P=2u,\qquad T-Q=2v,$ with $1\le u\le \frac{R-1}{2},\qquad 1\le v\le \frac{T-1}{2}.$ Then $s = RT-4uv.$ So for fixed $R,T$, the crossing case reduces to counting factor pairs of $K=\frac{RT-s}{4}.$

If $K$ is not a positive integer, there is no crossing contribution. If it is, we count ordered pairs $(u,v)$ such that

\quad 1\le u\le \frac{R-1}{2}, \quad 1\le v\le \frac{T-1}{2}.$$ Each such $(u,v)$ determines exactly one pair $(P,Q)$, and then there are exactly **2** ordered rectangle pairs: - first is $R\times Q$, second is $P\times T$, - or vice versa. So the crossing contribution is $$2\times \#\{(u,v): uv=K,\ u\le \tfrac{R-1}{2},\ v\le \tfrac{T-1}{2}\}.$$ ## Final algorithm Enumerate all odd $$R=1,3,5,\dots\le n,$$ $$T=1,3,5,\dots\le m.$$ For each pair: 1. let $$W=(n-R+1)(m-T+1);$$ 2. if $$RT=s,$$ add $$W\left(2\cdot \frac{R+1}{2}\cdot \frac{T+1}{2}-1\right);$$ 3. else if $$RT>s$$ and $$RT-s\equiv 0\pmod 4,$$ let $$K=\frac{RT-s}{4};$$ count ordered divisor pairs $(u,v)$ of $K$ satisfying the bounds, and add $$W\cdot 2\cdot \text{count}.$$ That’s it. No DP, no black magic, no pretending $250^4$ is acceptable. ## Why it’s correct We partition all ordered rectangle pairs with outer dimensions $(R,T)$ into exactly two disjoint sets: - one rectangle equals $R\times T$, - or neither does, in which case the maxima come from different rectangles. These are exhaustive and disjoint. - In the first set, union area is exactly $RT$, and the counting formula above is exact. - In the second set, every pair is uniquely represented by $u=(R-P)/2$ and $v=(T-Q)/2$, hence by a factorization of $K=(RT-s)/4$, and vice versa. Then multiplying by the number of valid centers $W$ counts all sextuples $$(a,b,c,d,x_0,y_0)$$ exactly once. So the algorithm is correct. ## Complexity There are at most about $250$ odd values of $R$ and $250$ odd values of $T$, so about $$250\cdot 250 = 62500$$ pairs. For each pair, divisor enumeration costs $$O(\sqrt{K})\le O(\sqrt{nm})\le O(500).$$ In practice it’s much smaller, since here $K\le 62500$. So the total complexity is roughly $$O\left(\frac{n}{2}\cdot \frac{m}{2}\cdot \sqrt{nm}\right),$$ which is easily fast enough for $n,m\le 500$. Memory usage is $$O(1).$$ Clean, brute-forcey in the good way, and very Codeforces-2100-core.