记录编号	577865	评测结果	AAAAAAAAAAAAAAAA
题目名称	[NOIP 2022]种花	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	1.248 s
提交时间	2022-11-27 10:55:45	内存使用	4.08 MiB

#include "bits/stdc++.h"

using i64 = long long;

const i64 P = 998244353;

void solve() {
	i64 n, m, C, F;
	std::cin >> n >> m >> C >> F;
	
	std::vector<std::vector<i64>> a(n + 1);

	for (int i = 1; i <= n; ++ i) {
		std::string s;
		std::cin >> s;

		a[i] = std::vector<i64>(s.begin(), s.end());

		for (auto& x : a[i]) 
			x -= '0';
	}

	std::vector<std::vector<i64>> f(n + 1, std::vector<i64>(m + 1)), g(n + 1, std::vector<i64>(m + 1));

	for (int i = 0; i <= n; ++ i)
		f[i][m] = -1;
	for (int j = 0; j <= m; ++ j)
		g[0][j] = -1;

	for (int i = 1; i <= n; ++ i) {
		for (int j = m - 1; j >= 0; -- j) {
			if (a[i][j]) {
				f[i][j] = g[i][j] = -1;
			} else {
				(f[i][j] = f[i][j + 1] + 1) %= P,
				(g[i][j] = g[i - 1][j] + 1) %= P;
			}
		}
	}

	for (int i = 1; i <= n; ++ i) 
		for (int j = 0; j < m; ++ j) {
			if (a[i][j]) {
				f[i][j] = 0;
			} else {
				(f[i][j] += f[i - 1][j]) %= P;
			}
		}

	i64 resC = 0, resF = 0;
	std::vector<std::vector<i64>> c(n + 1, std::vector<i64>(m + 1));

	for (int i = 3; i <= n; ++ i) {
		for (int j = 0; j < m; ++ j) {
			if (a[i][j]) {
				c[i][j] = 0;
			} else {
				if (f[i][j] > 0 && f[i - 2][j] > 0 && g[i][j] > 0) {
					(c[i][j] = (f[i][j] - f[i - 1][j]) * (f[i - 2][j])) %= P;
					(resC += c[i][j]) %= P;
				}
			}
		}
	}

	for (int i = 3; i <= n; ++ i) 
		for (int j = 0; j < m; ++ j) {
			if (a[i][j]) {
				c[i][j] = 0;
			} else {
				(c[i][j] += c[i - 1][j]) %= P;
			}
		}

	for (int i = 3; i <= n; ++ i) 
		for (int j = 0; j < m; ++ j) 
			if (!a[i][j] && c[i - 1][j] && g[i][j] > 0) 
				(resF += c[i - 1][j]) %= P;

	std::cout << C * resC % P << ' ' << F * resF % P << ' ' << '\n';
}

int main() {
    freopen("noip2022_plant.in", "r", stdin);
    freopen("noip2022_plant.out", "w", stdout);

	int t, id;
	std::cin >> t >> id;

	while (t --) {
		solve();
	}
	return 0;
}