题目描述
小 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 取模后的结果。
1 0
4 3 1 1
001
010
000
000
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≤103,0≤c,f≤1,ai,j∈{0,1}。
测试点编号 |
n |
m |
c= |
f= |
特殊性质 |
测试点分值 |
1 |
≤1000 |
0 |
无 |
1 |
2 |
=3 |
=2 |
1 |
1 |
2 |
3 |
=4 |
3 |
4 |
≤1000 |
4 |
5 |
≤1000 |
A |
6 |
B |
6 |
7 |
≤10 |
无 |
10 |
8 |
≤20 |
6 |
9 |
≤30 |
10 |
≤50 |
8 |
11 |
≤100 |
10 |
12 |
≤200 |
6 |
13 |
≤300 |
14 |
≤500 |
8 |
15 |
≤1000 |
0 |
6 |
16 |
1 |
14 |
特殊性质 A:∀1≤i≤n,1≤j≤⌊3m⌋,ai,3j=1;
特殊性质 B:∀1≤i≤⌊4n⌋,1≤j≤m,a4i,j=1;