P8865 [NOIP2022] Planting Flowers

Xiao C decides to plant a pattern of the letters $\texttt{CCF}$ in his garden, so he wants to know how many planting schemes there are for the letters $\texttt C$ and $\texttt F$ respectively. Unfortunately, there are some pits in the garden where flowers cannot be planted, so he hopes you can help solve this problem. The garden can be viewed as a grid with $n \times m$ positions, with rows numbered $1$ to $n$ from top to bottom, and columns numbered $1$ to $m$ from left to right. Each position may be a pit or not. Use $a_{i,j} = 1$ to indicate that there is a pit at row $i$, column $j$, and use $a_{i,j} = 0$ otherwise. A planting scheme is called $\texttt{C-}$ shaped if there exist $x_1, x_2 \in [1, n]$ and $y_0, y_1, y_2 \in [1, m]$, satisfying $x_1 + 1 < x_2$ and $y_0 < y_1, y_2 \leq m$, such that the segments from columns $y_0$ to $y_1$ on row $x_1$, from columns $y_0$ to $y_2$ on row $x_2$, and from rows $x_1$ to $x_2$ on column $y_0$ are all not pits, and flowers are planted only on these positions. A planting scheme is called $\texttt{F-}$ shaped if there exist $x_1, x_2, x_3 \in [1, n]$ and $y_0, y_1, y_2 \in [1, m]$, satisfying $x_1 + 1 < x_2 < x_3$ and $y_0 < y_1, y_2 \leq m$, such that the segments from columns $y_0$ to $y_1$ on row $x_1$, from columns $y_0$ to $y_2$ on row $x_2$, and from rows $x_1$ to $x_3$ on column $y_0$ are all not pits, and flowers are planted only on these positions. Examples of $\texttt{C-}$ shaped and $\texttt{F-}$ shaped planting schemes are shown in the explanation of Sample 1. Now Xiao C wants to know, given $n$, $m$, and the values $\{a_{i,j}\}$ indicating whether each position is a pit, how many possible $\texttt{C-}$ shaped and $\texttt{F-}$ shaped planting schemes there are, respectively. Since the answer may be very large, you only need to output the result modulo $998244353$. See the output format section for details.

The first line contains two integers $T, id$, denoting the number of test cases and the test point ID, respectively. If the input is a sample, it is guaranteed that $id = 0$. Then there are $T$ test cases. In each test case: - The first line contains four integers $n, m, c, f$, where $n$ and $m$ denote the number of rows and columns of the garden, respectively. The meanings of $c$ and $f$ are described in the output format section. - The next $n$ lines each contain a string of length $m$ consisting only of $0$ and $1$. The $j$-th character of the $i$-th string denotes $a_{i,j}$, i.e., whether the cell at row $i$, column $j$ in the garden is a pit.

Let the numbers of $\texttt{C-}$ shaped and $\texttt{F-}$ shaped planting schemes in the garden be $V_C$ and $V_F$, respectively. For each test case, output one line with two non-negative integers separated by a space, representing $(c \times V_C) \bmod 998244353$ and $(f \times V_F ) \bmod 998244353$, respectively, where $a \bmod P$ denotes $a$ modulo $P$.

【Explanation of Sample 1】 The four $\texttt{C-}$ shaped planting schemes are: ```plain **1 **1 **1 **1 *10 *10 *10 *10 **0 *** *00 *00 000 000 **0 *** ``` Here $\texttt*$ denotes planting a flower at that position. Note that the two horizontal strokes of $\texttt C$ do not need to have the same length. Similarly, the two $\texttt{F-}$ shaped planting schemes are: ```plain **1 **1 *10 *10 **0 *** *00 *00 ``` 【Sample 2】 See the attachments $\texttt{plant/plant2.in}$ and $\texttt{plant/plant2.ans}$. 【Sample 3】 See the attachments $\texttt{plant/plant3.in}$ and $\texttt{plant/plant3.ans}$. 【Constraints】 For all test cases, it is guaranteed that $1 \leq T \leq 5$, $1 \leq n, m \leq 10^3$, $0 \leq c, f \leq 1$, and $a_{i,j} \in \{0, 1\}$. | Test point ID | $n$ | $m$ | $c=$ | $f=$ | Special property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 1000$ | $\leq 1000$ | $0$ | $0$ | None | $1$ | | $2$ | $=3$ | $=2$ | $1$ | $1$ | None | $2$ | | $3$ | $=4$ | $=2$ | $1$ | $1$ | None | $3$ | | $4$ | $\leq 1000$ | $=2$ | $1$ | $1$ | None | $4$ | | $5$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | A | $4$ | | $6$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | B | $6$ | | $7$ | $\leq 10$ | $\leq 10$ | $1$ | $1$ | None | $10$ | | $8$ | $\leq 20$ | $\leq 20$ | $1$ | $1$ | None | $6$ | | $9$ | $\leq 30$ | $\leq 30$ | $1$ | $1$ | None | $6$ | | $10$ | $\leq 50$ | $\leq 50$ | $1$ | $1$ | None | $8$ | | $11$ | $\leq 100$ | $\leq 100$ | $1$ | $1$ | None | $10$ | | $12$ | $\leq 200$ | $\leq 200$ | $1$ | $1$ | None | $6$ | | $13$ | $\leq 300$ | $\leq 300$ | $1$ | $1$ | None | $6$ | | $14$ | $\leq 500$ | $\leq 500$ | $1$ | $1$ | None | $8$ | | $15$ | $\leq 1000$ | $\leq 1000$ | $1$ | $0$ | None | $6$ | | $16$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | None | $14$ | Special property A: $\forall 1 \leq i \leq n, 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloor$, $a_{i, 3 j} = 1$. Special property B: $\forall 1 \leq i \leq \left\lfloor \frac{n}{4} \right\rfloor, 1 \leq j \leq m$, $a_{4 i, j} = 1$. Translated by ChatGPT 5