Farmer John once painted a rectangular grid on the ground of his pasture. In
each cell, he painted either a \(+\) or a \(−\) (representing \(+1\) and \(−1\),
respectively).

Over time, the paint faded, and Farmer John now remembers the values of only
some cells. However, Farmer John does remember one important fact about the
original painting:

In every row and every column, the sum of the values in any contiguous
subsegment was always between \(−1\) and \(2\) (inclusive).

As an example, consider the row \(\texttt{+ - - +}\). It does not satisfy the
condition, since the subsegment \(\texttt{+ [ - - ] +}\) has sum \(-2\).

However, the row \(\texttt{- + + -}\) does satisfy the condition.

[ - ] + + -    sum = -1
[ - + ] + -    sum = 0
[ - + + ] -    sum = +1
[ - + + - ]    sum = 0
- [ + ] + -    sum = +1
- [ + + ] -    sum = +2
- [ + + - ]    sum = +1
- + [ + ] -    sum = +1
- + [ + - ]    sum = 0
- + + [ - ]    sum = -1

Count the number of different grids consistent with Farmer John's memory.

Problem credits: Alex Chen

SCORING

• Inputs 3-4: \(\min(R,C)=1\) for all tests
• Inputs 5-6: \(R,C\le 10\) for all tests
• Inputs 7-11: \(\sum \max(R,C)^2 \le 10^6\)
• Inputs 12-14: \(\sum RC \le 10^6\)
• Inputs 15-22: No additional constraints.

Problem credits: Alex Chen

The first line contains \(T\) (\(1\le T\le 100\)), the number of independent tests.
Each test is specified as follows:

The first line contains \(R\), \(C\), and \(X\) (\(1\le R,C\le 5\cdot 10^5\),
\(0\le X\le \min(10^5,RC)\)), meaning that the grid has dimensions \(R\times C\) and
Farmer John remembers the values of \(X\) different cells in the grid.

Then following \(X\) lines each contain a character \(v\in \{+, -\}\) followed by
two integers \(r\) and \(c\) (\(1\le r\le R, 1\le c\le C\)), meaning that the value at
the \(r\)th row and \(c\)th column of the grid is \(v\). It is guaranteed that no
ordered pair \((r,c)\) appears more than once within a single test.

Additionally, it is guaranteed that neither the sum of \(R\) nor the sum of \(C\)
over all tests exceeds \(10^6\), and that the sum of \(X\) over all tests does not
exceed \(2\cdot 10^5\).

For each test, output the number of grids on a separate line.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Platinum