2101: [USACO 2026 First Contest, Platinum] Problem 3. Pluses and Minuses
题目描述
Farmer John once painted a rectangular grid on the ground of his pasture. In each cell, he painted either a or a (representing and , 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 and (inclusive).
As an example, consider the row . It does not satisfy the condition, since the subsegment has sum .
However, the row 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.
输入
The first line contains , , and (, ), meaning that the grid has dimensions and Farmer John remembers the values of different cells in the grid.
Then following lines each contain a character followed by two integers and (), meaning that the value at the th row and th column of the grid is . It is guaranteed that no ordered pair appears more than once within a single test.
Additionally, it is guaranteed that neither the sum of nor the sum of over all tests exceeds , and that the sum of over all tests does not exceed .
输出
样例输入
2
1 3 3
+ 1 3
+ 1 1
- 1 2
1 3 3
+ 1 1
+ 1 3
+ 1 2样例输出
1
0提示
SAMPLE INPUT:
1
2 2 0
SAMPLE OUTPUT:
7
Here are the seven grids:
++
++
++
+-
++
-+
+-
++
+-
-+
-+
++
-+
+-
SCORING:
- Inputs 3-4: for all tests
- Inputs 5-6: for all tests
- Inputs 7-11:
- Inputs 12-14:
- Inputs 15-22: No additional constraints.