前言
去年多测不清空导致即便 CCF 放过了我的 \(O(n^2 m)\) 的代码但依然挂成了 \(0pts\)。
当时看清空数组后能过 CCF 数据就没再管。
时隔 \(1\) 年，重做这道题写了 \(O(nm)\) 的正解，终于完成了当年的心愿。
\(O(n^2 m)\) 思路
想到计算方案的话可以维护两个数组 \(c1_{i,j}\) 表示 \(i,j\) 位置上向右的最多连续 \(0\) 的个数，\(c2_{i,j}\) 表示 \(i,j\) 位置上向下的最多连续 \(0\) 的个数。
考虑以每个点为 \(c\) 形的左上角的那个点的方案数。
那么当前点 \((i, j)\) 的方案就是：
\[\sum_{k = i + 2}^{i + c2[i][j]} c1[i][j] \times c1[k][j] \]当前行肯定不能算，下一行是 \(c\) 形中间的空行，所以从 \(i + 2\) 开始。
同样考虑以每个点为 \(f\) 形的左上角的点的方案数。
那么当前点 \((i, j)\) 的方案数就是：
\[\sum_{k = i + 2}^{i + c2[i][j]} c1[i][j] \times c1[k][j] \times (c2[i][j] - k) \]最后那一块就是 \(f\) 形下面的小尾巴的方案。
然后我们就得到了一个 \(O(n^2 m)\) 的解法。
\(o(nm)\) 解法
发现全是 \(0\) 的时候上面的解法会被卡飞，所以考虑优化。
发现再对 \(c1[i][j]\) 的每一列做一次前缀和，用 \(c3\) 表示 \(c1[1][j]+ \dots + c1[i][j]\)。
然后我们可以利用前缀和 \(o(1)\) 计算每一个点 \(c\) 形的方案。
同理对于 \(f\) 形，我们维护类似拐角形的方案数，然后每列做一次前缀和，也能做到 \(o(1)\) 计算每一个点的 \(f\) 形的方案数。
/*
* @Author: Aisaka_Taiga
* @Date: 2023-10-26 21:02:05
* @LastEditTime: 2023-10-26 22:22:57
* @LastEditors: Aisaka_Taiga
* @FilePath: \Desktop\P8865.cpp
* The heart is higher than the sky, and life is thinner than paper.
*/
#include <bits/stdc++.h>
#define int long long
#define P 998244353
#define N 1100
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x * f;
}
int n, m, c, f, a[N][N], c1[N][N], c2[N][N], c3[N][N], c5[N][N];
//c1每个点向右的零的个数，c2每个点向下的零的个数, c3每一列c2的前缀和，c5表示f形的下半部分当前点合法的数量。
//1h写了n^3的，80分
//1.5h终于把优化后的给写完了。
inline void qk()
{
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= m; j ++)
a[i][j] = c1[i][j] = c2[i][j] = c3[i][j] = c5[i][j] = 0;
return ;
}
inline void work()
{
qk();
int ans1 = 0, ans2 = 0;
n = read(), m = read(), c = read(), f = read();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
char cc;
cin >> cc;
a[i][j] = cc - '0';
}
}
for(int i = 1; i <= n; i ++)
{
int t = 0;
for(int j = m; j >= 1; j --)
{
if(a[i][j] == 0) t ++;
else t = 0;
c1[i][j] = (t == 0 ? 1 : t);
}
}
for(int i = 1; i <= m; i ++)
{
int t = 0;
for(int j = n; j >= 1; j --)
{
if(a[j][i] == 0) t ++;
else t = 0;
c2[j][i] = (t == 0 ? 1 : t);
}
}
for(int j = 1; j <= m; j ++)
for(int i = 1; i <= n; i ++)
c3[i][j] = (c3[i - 1][j] + c1[i][j] - 1) % P,
c5[i][j] = (c5[i - 1][j] + (c1[i][j] - 1) * (c2[i][j] - 1)) % P;
for(int i = 1; i <= n - 2; i ++)
{
for(int j = 1; j <= m - 1; j ++)
{
if(c2[i][j] < 3) continue;
ans1 = (ans1 + ((c1[i][j] - 1) * (c3[i + c2[i][j] - 1][j] - c3[i + 1][j])) % P) % P;
if(c2[i][j] < 4) continue;
ans2 = (ans2 + ((c1[i][j] - 1) * (c5[i + c2[i][j] - 1][j] - c5[i + 1][j])) % P) % P;
}
}
cout << ans1 * c << " " << ans2 * f << endl;
return ;
}
signed main()
{
int T = read(), iid = read();
while(T --) work();
return 0;
}