UOJ Logo Universal Online Judge

UOJ

好评差评[+10]

#777. 【NOIP2022】种花

附件下载 统计

小 C 决定在他的花园里种出 CCF 字样的图案，因此他想知道 C 和 F 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。

花园可以看作有 n×m 个位置的网格图，从上到下分别为第 1 到第 n 行，从左到右分别为第 1 列到第 m 列，其中每个位置有可能是土坑，也有可能不是，可以用 ai,j=1 表示第 i 行第 j 列这个位置有土坑，否则用 ai,j=0 表示这个位置没土坑。

一种种花方案被称为 C- 形的，如果存在 x1,x2∈[1,n]，以及 y0,y1,y2∈[1,m]，满足 x1+1<x2，并且 y0<y1,y2≤m，使得第 x1 行的第 y0 到第 y1 列、第 x2 行的第 y0 到第 y2 列以及第 y0 列的第 x1 到第 x2 行都不为土坑，且只在上述这些位置上种花。

一种种花方案被称为 F- 形的，如果存在 x1,x2,x3∈[1,n]，以及 y0,y1,y2∈[1,m]，满足 x1+1<x2<x3，并且 y0<y1,y2≤m，使得第 x1 行的第 y0 到第 y1 列、第 x2 行的第 y0 到第 y2 列以及第 y0 列的第 x1 到第 x3 行都不为土坑，且只在上述这些位置上种花。

样例一解释中给出了 C- 形和 F- 形种花方案的图案示例。

现在小 C 想知道，给定 n,m 以及表示每个位置是否为土坑的值 {ai,j}，C- 形和 F- 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 998244353 取模的结果即可，具体输出结果请看输出格式部分。

输入格式

第一行包含两个整数 T,id，分别表示数据组数和测试点编号。如果数据为样例则保证 id=0。

接下来一共 T 组数据，在每组数据中：

第一行包含四个整数 n,m,c,f，其中 n,m 分别表示花园的行数、列数，对于 c,f 的含义见输出格式部分。

接下来 n 行，每行包含一个长度为 m 且仅包含 0 和 1 的字符串，其中第 i 个串的第 j 个字符表示 ai,j，即花园里的第 i 行第 j 列是不是一个土坑。

输出格式

设花园中 C- 形和 F- 形的种花方案分别有 VC 和 VF 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 (c×VC)mod998244353，(f×VF)mod998244353 ，其中 amodP 表示 a 对 P 取模后的结果。

样例一

input

1 0
4 3 1 1
001
010
000
000

output

4 2

explanation

四个 C- 形种花方案为：

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

其中 * 表示在这个位置种花。注意 C 的两横可以不一样长。

类似的，两个 F- 形种花方案为：

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

样例二

见下发文件中的 ex_plant2.in 与 ex_plant2.ans。

样例三

见下发文件中的 ex_plant3.in 与 ex_plant3.ans。

子任务

对于所有数据，保证：1≤T≤5，1≤n,m≤103，0≤c,f≤1，ai,j∈{0,1}。

测试点编号 n m c= f= 特殊性质 测试点分值
1 ≤1000 ≤1000 0 0 无 1
2 =3 =2 1 1 2
3 =4 3
4 ≤1000 4
5 ≤1000 A 4
6 B 6
7 ≤10 ≤10 无 10
8 ≤20 ≤20 6
9 ≤30 ≤30 6
10 ≤50 ≤50 8
11 ≤100 ≤100 10
12 ≤200 ≤200 6
13 ≤300 ≤300 6
14 ≤500 ≤500 8
15 ≤1000 ≤1000 0 6
16 1 14

特殊性质 A：∀1≤i≤n，1≤j≤⌊m3⌋，ai,3j=1；

特殊性质 B：∀1≤i≤⌊n4⌋，1≤j≤m，a4i,j=1。

时间限制：1s

空间限制：512MB

Server time: 2025-03-25 11:57:16