rt。

$r$ 数组存的是每个点右边最多可以扩展多远且中间都可以种花；$d$ 数组存的是往下的。

提交记录链接

// Problem: P8865 [NOIP2022] 种花
// URL: https://www.luogu.com.cn/problem/P8865
// Start Time: 2023-10-16 20:10:41
// 
// Powered by CP Editor (https://cpeditor.org)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<cmath>
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define int long long
#define _IOBUF_SIZE 1u<<22
using namespace std;
class _istream{
	private:
		char inbuf[_IOBUF_SIZE],*inputp1,*inputp2;FILE*in;
		template<class T>void _read(T&n){n=0;bool f=false;char ch=get();for(;ch!='-'&&!isdigit(ch);ch=get());if(ch=='-'){f=true;ch=get();}for(;isdigit(ch);ch=get()){n=n*10+(ch^'0');}if(f)n=~n+1;}
		long double _read_float(){long double n=0,w=1;bool f=false,f2=false;char ch=get();for(;ch!='-'&&ch!='.'&&!isdigit(ch);ch=get());if(ch=='-'){f=true;ch=get();}else if(ch=='.'){f2=true;ch=get();}for(;isdigit(ch)||ch=='.';ch=get()){if(ch=='.'){f2=true;continue;}if(f2)w*=10;n=n*10+(ch^'0');}if(f)n=-n;return n/w;}
	public:
		_istream(const char*_in=""){inputp1=inputp2=inbuf;in=(_in[0]?fopen(_in,"r"):stdin);}~_istream(){if(in!=stdin)fclose(in);}
		inline char get(){if(inputp1==inputp2){inputp2=inbuf+fread((inputp1=inbuf),1,sizeof(inbuf),in);if(inputp2==inputp1)return EOF;}return*(inputp1++);}
		inline bool eof(){if(inputp1==inputp2){inputp2=inbuf+fread((inputp1=inbuf),1,sizeof(inbuf),in);if(inputp2==inputp1)return true;}return false;}
		template<typename Tp>inline _istream&operator>>(Tp&n){_read(n);return*this;}
		inline _istream&operator>>(float&n){n=_read_float();return*this;}
		inline _istream&operator>>(double&n){n=_read_float();return*this;}
		inline _istream&operator>>(long double&n){n=_read_float();return*this;}
		inline _istream&operator>>(bool&b){int i;(*this)>>i;b=(bool)i;return*this;}
		inline _istream&operator>>(char&ch){while(isspace(ch=get()));return*this;}
		inline _istream&operator>>(char*p){while(!isspace(*p=get()))++p;*p=0;return*this;}
		inline _istream&operator>>(string&s){char ch;s.clear();while(isspace(ch=get()));s.push_back(ch);while(!isspace(ch=get()))s.push_back(ch);return*this;}
};
class _ostream{
	const static int MAX_HEAD_SIZE=1005;const static int MAX_END_SIZE=35;
	private:
		char outbuf[_IOBUF_SIZE],*outputp1,*outputend;FILE*out;int precision=-1;
		inline void out_flush(){fwrite(outbuf,1,static_cast<size_t>(outputp1-outbuf),out);outputp1=outbuf;}
		template<class T>void _write(const T&n){if(n<0){put('-');_write(~n+1);return;}if(n>9)_write(n/10);put('0'^(n%10));}
		inline void _write_lf(long double n){if(n<0)put('-'),n=-n;static long double x;static char array[MAX_HEAD_SIZE+1+MAX_END_SIZE],*out=array+MAX_END_SIZE;static int top=0,end=0;x=floor(n);while(x>0&&top<MAX_HEAD_SIZE){out[++top]=fmod(x,10);x=(x-out[top])/10;}while(out[top]==0&&top>0)--top;n-=floor(n);while(n>1e-30&&end>-MAX_END_SIZE){n*=10;out[--end]=(int)floor(n);n-=out[end];}if(precision!=-1){if(end>-precision-1)end=-precision-1;while(end<-precision-1)out[end++]=0;if(out[end]>4)++out[end+1];out[end]=0;++end;int idx;for(idx=end;out[idx]==10&&idx!=-1;++idx){out[idx]=0;++out[idx+1];}if(out[-1]==10){out[-1]=0;++out[1];}for(idx=1;out[idx]==10;++idx){out[idx]=0;++out[idx+1];}if(idx>top)top=idx;}if(top==0)top=1;for(;top;--top){put('0'^out[top]);out[top]=0;}if(end!=0||precision!=-1){put('.');for(int i=-1;i>=end;--i){put('0'^out[i]);out[i]=0;}end=0;}}
	public:
		_ostream(const char*_out=""){outputend=(outputp1=outbuf)+sizeof(outbuf);out=(_out[0]?fopen(_out,"w"):stdout);}~_ostream(){out_flush();if(out!=stdout)fclose(out);}
		inline void put(char ch){*(outputp1++)=ch;if(outputp1==outputend)out_flush();}
		template<typename Tp>inline _ostream&operator<<(Tp n){_write(n);return*this;}
		inline void setprecision(int n){precision=n;}
		inline _ostream&operator<<(float n){_write_lf(n);return*this;}
		inline _ostream&operator<<(double n){_write_lf(n);return*this;}
		inline _ostream&operator<<(long double n){_write_lf(n);return*this;}
		inline _ostream&operator<<(bool b){(*this)<<(int)b;return*this;}
		inline _ostream&operator<<(char ch){put(ch);return*this;}
		inline _ostream&operator<<(const char*p){while(*p)put(*p++);return*this;}
		inline _ostream&operator<<(string s){(*this)<<s.data();return*this;}
};
_istream fin("");_ostream fout("");
#define cin fin
#define cout fout
#define endl '\n'
#define inf 0x3f3f3f3f
#define inff 0x3f3f3f3f3f3f3f3f
#define mod 998244353
#define mod2 1000000007
#define PROBLEM_NAME "paint"
#define vint vector<int>
const int maxn=1e3+2;
int n,m,c,f,r[maxn][maxn],d[maxn][maxn],sum[maxn][maxn];
bool a[maxn][maxn];
inline int C(){
	for(int i=1;i<=n;++i){
		int cur=0;
		for(int j=m;j>=1;--j){
			if(a[i][j]) cur=-1;
			else r[i][j]=cur;
			++cur;
		}
	}
	int ret=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i][j]) sum[i][j]=0;
			else sum[i][j]=sum[i-1][j]+r[i][j];
		}
	}
	for(int i=3;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!a[i-1][j]) ret=(ret+sum[i-2][j]*r[i][j])%mod;
		}
	}
	return ret;
}
inline int F(){
	for(int i=1;i<=n;++i){
		int cur=0;
		for(int j=m;j>=1;--j){
			if(a[i][j]) cur=-1;
			else r[i][j]=cur;
			++cur;
		}
	}
	for(int j=1;j<=m;++j){
		int cur=0;
		for(int i=n;i>=1;--i){
			if(a[i][j]) cur=-1;
			else d[i][j]=cur;
			++cur;
		}
	}
	int ret=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i][j]) sum[i][j]=0;
			else sum[i][j]=sum[i-1][j]+r[i][j];
		}
	}
	for(int i=3;i<n;++i){
		for(int j=1;j<=m;++j){//往上 往右 往下
			if(!a[i-1][j]) ret=(ret+sum[i-2][j]*r[i][j]*d[i][j])%mod;
		}
	}
	return ret;
}
inline void solve(){
	cin>>n>>m>>c>>f;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			char ch;
			cin>>ch;
			if(ch=='1') a[i][j]=1;
		}
	}
	cout<<c*C()<<' '<<f*F()<<endl;
}
signed main(){
	// file(PROBLEM_NAME);
	int t=1,id;
	cin>>t>>id;
	while(t--) solve();
	return 0;
}