P6784: 种花（plant）

---

【题目描述】

【题目描述】
小 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 取模的结果即可，具体输出结果请看输出格式部分。
【输入格式】
从文件 plant.in 中读入数据。
第一行包含两个整数 T, id，分别表示数据组数和测试点编号。如果数据为样例则保证 id = 0。
接下来一共 T 组数据，在每组数据中：
第一行包含四个整数 n, m, c, f，其中 n, m 分别表示花园的行数、列数，对于 c, f的含义见输出格式部分。
接下来 n 行，每行包含一个长度为 m 且仅包含 0 和 1 的字符串，其中第 i 个串的 第 j 个字符表示 ai,j，即花园里的第 i 行第 j 列是不是一个土坑。
【输出格式】
输出到文件 plant.out 中。
设花园中 C‐ 形和 F‐ 形的种花方案分别有 VC 和 VF 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 (c × VC) mod 998244353,(f ×VF ) mod 998244353 ，其中 a mod P 表示 a 对 P 取模后的结果。
【样例 1 输入】
1 0
4 3 1 1
001
010
000
000
【样例 1 输出】
4 2
【样例 1 解释】
四个 C‐ 形种花方案为：
**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***
其中 * 表示在这个位置种花。注意 C 的两横可以不一样长。
类似的，两个 F‐ 形种花方案为：
**1 **1
*10 *10
**0 ***
*00 *00
【样例 2】
见选手目录下的 plant/plant2.in 与 plant/plant2.ans。
【样例 3】
见选手目录下的 plant/plant3.in 与 plant/plant3.ans。  
【数据范围】
对于所有数据，保证：1 ≤ T ≤ 5，1 ≤ n, m ≤ 10^3，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
6					B	6
7	≤10	≤10			无	10
8	≤20	≤20				6
9	≤30	≤30
10	≤50	≤50				8
11	≤100	≤100				10
12	≤200	≤200				6
13	≤300	≤300
14	≤500	≤500				8
15	≤1000	≤1000		0		6
16				1		14

 
特殊性质 A: ∀1 ≤ i ≤ n, 1 ≤ j ≤ ⌊m/3⌋, ai,3j = 1。
特殊性质 B：∀1 ≤ i ≤ ⌊n/4⌋, 1 ≤ j ≤m, a4i,j= 1。

题目类型~

NOIP2022 

咻咻~

提交答案 状态 返回