NOIP '22 P1 - Flower Planting

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Little C decided to plant the pattern of CCF in his garden, so he wanted to know how many flowering schemes there are for the two letters C and F; He wants you to help him with this problem.

A garden can be viewed as a grid map with n \times m locations, which are the 1st to nth rows from top to bottom, and the 1st to mth columns from left to right, where each location may be mud or not. Specifically, a_{i,j} = 1 indicates that there is mud at the position of row i and column j, and a_{i,j} = 0 indicates that there is no mud at this position.

A planting scheme is called C-shaped, if there exist x_1, x_2 \in [1,n], and y_0, y_1, y_2 \in [1,m], such that x_1+1 < x_2, and y_0 < y_1, y_2 \le m, so that the y_0th to y_1th column of the x_1th row, the y_0th to y_2th column of the x_2th row, and the x_1th to x_2th row of the y_0th column are not mud, and flowers are only planted in these positions.

A planting scheme is called 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 \le m, so that the y_0 to y_1 column of the x_1 row, the y_0 to y_2 column of the x_2 row, and the x_1 to x_3 row of the y_0 column are not mud, and flowers are only planted in these positions.

Sample 1 gives examples of C-shape and F-shape planting schemes.

Now little C wants to know, given n, m and the value \{a_{i, j}\} indicating whether each position is mud, how many possibilities are there for C-shaped and F-shaped flowering schemes? Since the answer may be very large, you only need to output the result modulo 998\,244\,353. Please refer to the output format section for specific output results.

Input Specification

The first line contains two integers T, \mathit{id}, which respectively represent the number of data sets and the number of test points. All sample data have \mathit{id} = 0.

Next, there are T sets of data, in each set of data:

The first line contains four integers n, m, c, f, where n, m represent the number of rows and columns of the garden respectively, and see the output format section for the meaning of c, f.

The next n lines, each line contains a string of length m and only contains 0 and 1, where the jth character of the ith string represents a_{i, j}, that is, is the jth column of the ith row in the garden mud.

Output Specification

For each set of data, if there are V_C and V_F C-shaped and F-shaped flower planting schemes in the garden respectively, you need to output two non-negative integers separated by a space, (c \times V_C) \bmod 998\,244\,353, and (f \times V_F) \bmod 998\,244\,353, where a \bmod P represents the result of taking the remainder of a divided by P.

Sample Input 1

1 0
4 3 1 1
001
010
000
000

Sample Output 1

4 2

Explanation of Sample 1

The four C-typed plans are:

**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***

Where * means to plant flowers at this position. Note that the two bars of C can be of different lengths.

Similarly, the two F-shape planting schemes are:

**1 **1
*10 *10
**0 ***
*00 *00

Additional Samples

Additional sample cases can be found here.

Constraints

For all data, it is guaranteed that 1 \le T \le 5, 1 \le n, m \le 10^3, 0 \le c, f \le 1, a_{i, j} \in \{0, 1\}.

CasenmcfSpecial PropertyPoints
1\leq 1000\leq 100000none1
2=3=2112
3=43
4\leq 10004
5\leq 1000\forall 1 \leq i \leq n, 1 \leq j \leq \lfloor \frac{m}{3} \rfloor, a_{i, 3j} = 14
6\forall 1 \leq i \leq \lfloor \frac{n}{4} \rfloor, 1 \leq j \leq m, a_{4i, j} = 16
7\leq 10\leq 10none10
8\leq 20\leq 206
9\leq 30\leq 306
10\leq 50\leq 508
11\leq 100\leq 10010
12\leq 200\leq 2006
13\leq 300\leq 3006
14\leq 500\leq 5008
15\leq 1\,000\leq 1\,00006
16114

Comments

There are no comments at the moment.