题目描述
小 C 决定在他的花园里种出 \(\texttt{CCF}\) 字样的图案，因此他想知道 \(\texttt C\) 和 \(\texttt F\) 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。
花园可以看作有 \(n\times m\) 个位置的网格图，从上到下分别为第 \(1\) 到第 \(n\) 行，从左到右分别为第 \(1\) 列到第 \(m\) 列，其中每个位置有可能是土坑，也有可能不是，可以用 \(a_{i,j} = 1\) 表示第 \(i\) 行第 \(j\) 列这个位置有土坑，否则用 \(a_{i,j} = 0\) 表示这个位置没土坑。
一种种花方案被称为 \(\texttt{C-}\) 形的，如果存在 \(x_1, x_2 \in [1, n]\)，以及 \(y_0, y_1, y_2 \in [1, m]\)，满足 \(x_1 + 1 < x_2\)，并且 \(y_0 < y_1, y_2 \leq m\)，使得第 \(x_1\) 行的第 \(y_0\) 到第 \(y_1\) 列、第 \(x_2\) 行的第 \(y_0\) 到第 \(y_2\) 列以及第 \(y_0\) 列的第 \(x_1\) 到第 \(x_2\) 行都不为土坑，且只在上述这些位置上种花。
一种种花方案被称为 \(\texttt{F-}\) 形的，如果存在 \(x_1, x_2, x_3 \in [1, n]\)，以及 \(y_0, y_1, y_2 \in [1, m]\)，满足 \(x_1 + 1 < x_2 < x_3\)，并且 \(y_0 < y_1, y_2 \leq m\)，使得第 \(x_1\) 行的第 \(y_0\) 到第 \(y_1\) 列、第 \(x_2\) 行的第 \(y_0\) 到第 \(y_2\) 列以及第 \(y_0\) 列的第 \(x_1\) 到第 \(x_3\) 行都不为土坑，且只在上述这些位置上种花。
样例一解释中给出了 \(\texttt{C-}\) 形和 \(\texttt{F-}\) 形种花方案的图案示例。
现在小 C 想知道，给定 \(n, m\) 以及表示每个位置是否为土坑的值 \(\{a_{i,j}\}\)，\(\texttt{C-}\) 形和 \(\texttt{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\) 列是不是一个土坑。
输出格式
设花园中 \(\texttt{C-}\) 形和 \(\texttt{F-}\) 形的种花方案分别有 \(V_C\) 和 \(V_F\) 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 \((c \times V_C) \bmod 998244353\)，\((f \times V_F ) \bmod 998244353\) ，其中 \(a \bmod P\) 表示 \(a\) 对 \(P\) 取模后的结果。
样例 #1
样例输入 #1
1 0
4 3 1 1
001
010
000
000
样例输出 #1
4 2
提示
【样例 1 解释】
四个 \(\texttt{C-}\) 形种花方案为：
**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***
其中 \(\texttt*\) 表示在这个位置种花。注意 \(\texttt C\) 的两横可以不一样长。
类似的，两个 \(\texttt{F-}\) 形种花方案为：
**1 **1
*10 *10
**0 ***
*00 *00
【样例 2】
见附件下的 \(\texttt{plant/plant2.in}\) 与 \(\texttt{plant/plant2.ans}\)。
【样例 3】
见附件下的 \(\texttt{plant/plant3.in}\) 与 \(\texttt{plant/plant3.ans}\)。
【数据范围】
对于所有数据，保证：\(1 \leq T \leq 5\)，\(1 \leq n, m \leq 10^3\)，\(0 \leq c, f \leq 1\)，\(a_{i,j} \in \{0, 1\}\)。
| 测试点编号 | \(n\) | \(m\) | \(c=\) | \(f=\) | 特殊性质 | 测试点分值 |
|---|---|---|---|---|---|---|
| \(1\) | \(\leq 1000\) | \(\leq 1000\) | \(0\) | \(0\) | 无 | \(1\) |
| \(2\) | \(=3\) | \(=2\) | \(1\) | \(1\) | 无 | \(2\) |
| \(3\) | \(=4\) | \(=2\) | \(1\) | \(1\) | 无 | \(3\) |
| \(4\) | \(\leq 1000\) | \(=2\) | \(1\) | \(1\) | 无 | \(4\) |
| \(5\) | \(\leq 1000\) | \(\leq 1000\) | \(1\) | \(1\) | A | \(4\) |
| \(6\) | \(\leq 1000\) | \(\leq 1000\) | \(1\) | \(1\) | B | \(6\) |
| \(7\) | \(\leq 10\) | \(\leq 10\) | \(1\) | \(1\) | 无 | \(10\) |
| \(8\) | \(\leq 20\) | \(\leq 20\) | \(1\) | \(1\) | 无 | \(6\) |
| \(9\) | \(\leq 30\) | \(\leq 30\) | \(1\) | \(1\) | 无 | \(6\) |
| \(10\) | \(\leq 50\) | \(\leq 50\) | \(1\) | \(1\) | 无 | \(8\) |
| \(11\) | \(\leq 100\) | \(\leq 100\) | \(1\) | \(1\) | 无 | \(10\) |
| \(12\) | \(\leq 200\) | \(\leq 200\) | \(1\) | \(1\) | 无 | \(6\) |
| \(13\) | \(\leq 300\) | \(\leq 300\) | \(1\) | \(1\) | 无 | \(6\) |
| \(14\) | \(\leq 500\) | \(\leq 500\) | \(1\) | \(1\) | 无 | \(8\) |
| \(15\) | \(\leq 1000\) | \(\leq 1000\) | \(1\) | \(0\) | 无 | \(6\) |
| \(16\) | \(\leq 1000\) | \(\leq 1000\) | \(1\) | \(1\) | 无 | \(14\) |
特殊性质 A：\(\forall 1 \leq i \leq n, 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloor\)，\(a_{i, 3 j} = 1\)；
特殊性质 B：\(\forall 1 \leq i \leq \left\lfloor \frac{n}{4} \right\rfloor, 1 \leq j \leq m\)，\(a_{4 i, j} = 1\)；
题解
这个题是独立做出来的绿题，非常开心
我们来看C的方案，观察样例就知道，对于C的两个顶点，我们需要知道每个顶点右面有几个零，如果知道这点，我们只需要使用乘法原理即可
对于（i，j）这个格子，我们怎么统计他右面有几个零？
刚开始我的方法是暴力维护，暴力维护的时间复杂度太高，我一直T的原因就在这里，后面我进行了修改，倒序枚举，从第m列开始，如果这个格子的数字是0，那么xh[i][j]=xh[i][j+1]+1，否则xh[i][j]=0，当然，我们也需要统计向上有多少个？方法是同样的。
那么我们怎么找C的方案数？我们发现在竖的方向上，至少存在3个连续的0，同时他们右面有多个0，我们是可以有C方案的，可以暴力统计，但是我发现，这个可以递推，用lst[i][j]记录在连续的0里面，目前匹配的数量是多少？如果当然(i,j)连续0的数量符合条件，那么前lst[i-2][j]是符合条件的，也就是说，和(i-2,j)匹配的，一定和他匹配，同时需要加上(i-2,j) 的向右数量，否则，匹配数量为0，同时更新lst[i][j],如何更新lst[i][j]呢？lst[i][j]默认等于lst[i-1][j]，如果他自己也能匹配，加上自己向右的数量即可
经过上述过程，记录到pp[i][j]表示前面有多少个匹配数量，直接和0的数量相乘即可，那么C的问题就解决了
C的问题解决了之后，F的问题也就好解决了，因为F正好是C加上1个0，这个想法也是我偶然想到的，不得不说，这题出的实在是妙，我们记录C方案的前缀和即可
反思
对于我来说，最难的部分是对于(i,j)找匹配的问题，之前我一直认为(i,j)的匹配就是(i-1,j)的匹配加上(i-2,j)的向右个数，
代码实现
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m,c,ff,id,t;
char s[maxn][maxn];
int xh[maxn][maxn],f[maxn][maxn],xs[maxn][maxn],pp[maxn][maxn],lst[maxn][maxn],sum[maxn][maxn];
long long ansc,ansf;
int main(){
//freopen("plant4.in","r",stdin);
scanf("%d%d",&t,&id);
for(int ss=1;ss<=t;ss++){
scanf("%d%d%d%d",&n,&m,&c,&ff);
memset(xh,0,sizeof xh);
memset(xs,0,sizeof xs);
memset(f,0,sizeof f);
memset(lst,0,sizeof lst);
memset(pp,0,sizeof pp);
memset(sum,0,sizeof sum);
ansc=ansf=0;
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
if(s[i][m]=='0') xh[i][m]=1;
else xh[i][m]=0;
for(int j=m-1;j>=1;j--)
if(s[i][j]=='0'){
xh[i][j]=xh[i][j+1]+1;
xs[i][j]=xs[i-1][j]+1;
}
else{
xh[i][j]=0;
xs[i][j]=0;
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++)
// cout<<xs[i][j]<<" ";
// cout<<endl;
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='0'){
if(xs[i][j]>=3){
if(xh[i][j]>=2) pp[i][j]=lst[i-2][j];
else pp[i][j]=0;
}
if(xh[i][j]>=2) lst[i][j]=lst[i-1][j]+xh[i][j]-1;
else lst[i][j]=lst[i-1][j];
}else{
lst[i][j]=0;
}
}
}
for(int i=3;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='0'&&xh[i][j]>=2&&xs[i][j]>=3){
f[i][j]=(xh[i][j]-1)*pp[i][j]%998244353;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(s[i][j]=='0') {
ansf=(ansf+sum[i-1][j])%998244353;
sum[i][j]=(sum[i-1][j]+f[i][j])%998244353;
}
else sum[i][j]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ansc=(ansc+f[i][j])%998244353;
ansc=ansc*c%998244353;
ansf=ansf*ff%998244353;
printf("%lld %lld\n",ansc,ansf);
}
}
/**
1 7
10 10 1 1
0000000000
0000000100
0000100000
0000000000
0000000000
0000000000
0000000001
0000000000
0010000001
0000000000
*/