3927. T1-[NOIP2022] 种花(flower)
时间限制：1000 MS 内存限制：256 MB
题目描述
小 $ C $ 决定在他的花园里种出 $ CCF $ 字样的图案，因此他想知道 `C` 和 `F` 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。 花园可以看作有 $ n×m $ 个位置的网格图，从上到下分别为第 $ 1 $ 到第 $ n $ 行，从左到右分别为第 $ 1 $ 列到第 $ m $ 列，其中每个位置有可能是土坑，也有可能不是，可以用 $ a_{i,j}=1 $ 表示第 $ i $ 行第 $ j $ 列这个位置有土坑，否则用 $ a_{i,j}=0 $ 表示这个位置没土坑。 一种种花方案被称为 `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 $ 行都不为土坑，且只在上述这些位置上种花。 一种种花方案被称为 `F` 形的，如果存在 $ x_1,x_2,x_3∈[1,n] $ ，以及 $ y_0,y_1,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 $ 行都不为土坑，且只在上述这些位置上种花。 样例一解释中给出了 `C` 形和 `F` 形种花方案的图案示例。 现在小 $ C $ 想知道，给定 $ n,m $ 以及表示每个位置是否为土坑的值 $ \{a_{i,j}\} $ ，`C` 形和 `F` 形种花方案分别有多少种可能？ 由于答案可能非常之大，你只需要输出其对 $ 998244353 $ 取模的结果即可，具体输出结果请看输出格式部分。 #### 输入格式 第一行包含两个整数 $ T,i_d $ ，分别表示数据组数和测试点编号。如果数据为样例则保证 $ i_d=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 $ 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 $ mod998244353 $ , $ (f×VF)mod998244353 $ ，其中 $ a\ mod\ P $ 表示 $ a $ 对 $ P $ 取模后的结果。 #### 数据范围 对于所有数据，保证： $ 1≤T≤5 $ ， $ 1≤n,m≤10^3 $ ， $ 0≤ c,f ≤1 $ ， $ a_{i,j}∈{0,1} $ 。  特殊性质 $ A $ : $ ∀1≤i≤n,1≤j≤⌊\frac{m}{3}⌋,a_{i,3j}=1 $ 。 特殊性质 $ B $ : $ ∀1≤i≤⌊\frac{n}{4}⌋,1≤j≤m,a_{4i,j}=1 $ 。 #### 输入样例： ``` 1 0 4 3 1 1 001 010 000 000 ``` #### 输出样例： ``` 4 2 ``` #### 样例解释 四个 `C` 形种花方案为： ``` **1 **1 **1 **1 *10 *10 *10 *10 **0 *** *00 *00 000 000 **0 *** ``` 其中 `*` 表示在这个位置种花。 注意 `C` 的两横可以不一样长。 类似的，两个 `F` 形种花方案为： ``` **1 **1 *10 *10 **0 *** *00 *00 ``` | | | --- |