记录编号	581717	评测结果	AAAAAAAAAAAAAAAA
题目名称	3811.[NOIP 2022]种花	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.891 s
提交时间	2023-08-10 20:09:38	内存使用	34.58 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 1100,mod = 998244353;
int T,id,n,m,C,F;
long long r[N][N],c[N][N],f[N][N],ansc,ansf;
bool v[N][N];
char ch;
void first(){
    ansc = ansf = 0;
	memset(r,0,sizeof(r));
	memset(v,0,sizeof(v));
	memset(c,0,sizeof(c));
	memset(f,0,sizeof(f));
}
void init(){
	scanf("%d%d%d%d",&n,&m,&C,&F);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin>>ch;
			v[i][j] = (ch == '1');
		}
	}
}
int main(){
	freopen("plant.in","r",stdin);
	freopen("plant.out","w",stdout);
	scanf("%d%d",&T,&id);
	while(T--){
		first();
		init();
		for(int i = 1;i <= n;i++){
			r[i][m+1] = -1;
			for(int j = m;j >= 1;j--){
				if(!v[i][j])r[i][j] = r[i][j+1]+1;
				else r[i][j] = -1;
			}
		}
		for(int j = 1;j <= m;j++){
			for(int i = n;i >= 1;i--){
				if(!v[i][j])c[i][j] = (r[i][j] + c[i+1][j]) % mod;
			}
		}
		for(int j = 1;j <= m;j++){
			int k = 0;
			for(int i = n,k = n;i >= 1;i--){
				if(!v[i][j])f[i][j] = ((r[i][j] * (k-i)) % mod + f[i+1][j]) % mod;
				else k = i-1;
			}
		}
		for(int i = 1;i <= n-2;i++){
			for(int j = 1;j <= m;j++){
				if(!v[i+1][j] && !v[i][j]){
					ansc = (ansc + (r[i][j] * c[i+2][j]) % mod) % mod;
					ansf = (ansf + (r[i][j] * f[i+2][j]) % mod) % mod;
				}
			}
		}
		printf("%lld %lld\n",ansc*C,ansf*F);
	}
	
	return 0;
	
}