3811. [NOIP 2022]种花

【题目描述】

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

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

一种种花方案被称为 $\rm C‐形$ 的，如果存在 $x_1,\ x_2\ ∈\ [1, n]$，以及 $y_0,\ y_1,\ y_2\ ∈\ [1,\ m]$，满足 $x_1\ +\ 1\ <\ x_2$，并且 $y_0\ <\ y_1,\ y_2\ ≤\ m$，使得第 $x_1$ 行的第 $y_0$ 到第 $y_1$ 列、第 $x_2$ 行的第 $y_0$ 到第 $y_2$ 列以及第 $y_0$ 列的第 $x_1$ 到第 $x_2$ 行都不为土坑，且只在上述这些位置上种花。

一种种花方案被称为 $\rm F‐形$ 的，如果存在 $x_1,\ x_2,\ x_3\ ∈\ [1, n]$，以及 $y_0,\ y1,\ y_2\ ∈\ [1,\ m]$，满足 $x_1\ +\ 1\ <\ x_2\ <\ x_3$，并且 $y_0\ <\ y_1,\ y_2\ ≤\ m$，使得第 $x_1$ 行的第 $y_0$ 到第 $y_1$ 列、第 $x_2$ 行的第 $y_0$ 到第 $y_2$ 列以及第 $y_0$ 列的第 $x_1$ 到第 $x_3$ 行都不为土坑，且只在上述这些位置上种花。

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

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

【输入格式】

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

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

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

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

【输出格式】

设花园中 $C‐$ 形和 $F‐$ 形的种花方案分别有 $V_C$ 和 $V_F$ 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 $(c × V_C)\bmod \ 998244353,(f\ ×\ V_F )\bmod\ 998244353$ ，其中 $a\bmod\ 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/3输入输出】

点击下载样例2/3 

【数据规模与约定】

【来源】

$CCF\ NOIP2022$