这是 TLE code

其中 $sum_{i,j}$ 表示第 $i$ 行从右往左遇见第一个 $1$ 之前 $0$ 个数

$s$ 数组代表从下往上

#include<bits/stdc++.h>
#define N 1005
#define ll long long
using namespace std;
const int mod=998244353;
int g,id;
int n,m,c,f;
char a[N][N];
int sum[N][N],s[N][N];
int sc,sf;
int main() 
{
//	freopen("plant3.in","r",stdin);
	scanf("%d%d",&g,&id);
	while(g--)
	{
		memset(sum,0,sizeof(sum));
		memset(s,0,sizeof(s));
		scanf("%d%d%d%d",&n,&m,&c,&f);
		sc=sf=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[i][j],a[i][j]-='0';
		for(int i=1;i<=n;i++)
			for(int j=m;j>=1;j--)
				if(!a[i][j]) sum[i][j]=sum[i][j+1]+1;
				else sum[i][j]=0;
		for(int j=1;j<=m;j++)
			for(int i=n;i>=1;i--)
				if(!a[i][j])s[i][j]=s[i+1][j]+1;
				else s[i][j]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				if(a[i][j]||a[i+1][j]) continue;
				for(int k=i+2;k<=n;k++)
				{
					if(a[k][j]) break;
					sc=(sc+1ll*(sum[i][j]-1)*(sum[k][j]-1)%mod)%mod;
					sf=sf+(sum[i][j]-1)*(sum[k][j]-1)%mod*(s[k][j]-1)%mod,sf%=mod;
				}
			}
		printf("%d %d\n",sc*c,f*sf);
	}
	return 0;
}

对代码进行优化 得到的 WA 代码

#include<bits/stdc++.h>
#define N 1005
#define int long long
using namespace std;
const int mod=998244353;
int g,id;
int n,m,c,f;
char a[N][N];
int sum[N][N],s[N][N];
int gc[N][N],gf[N][N],lst[N][N];
int sc,sf;
signed main() 
{
	scanf("%d%d",&g,&id);
	while(g--)
	{
		memset(sum,0,sizeof(sum));
		memset(s,0,sizeof(s));
		memset(gc,0,sizeof(gc));
		memset(gf,0,sizeof(gf));
		memset(lst,0,sizeof(lst));
		scanf("%d%d%d%d",&n,&m,&c,&f);
		sc=sf=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[i][j],a[i][j]-='0';
		for(int i=1;i<=n;i++)
			for(int j=m;j>=1;j--)
				if(!a[i][j]) sum[i][j]=sum[i][j+1]+1;
				else sum[i][j]=0;
		for(int i=1;i<=m;i++)
			lst[n+1][i]=n+1;
		for(int j=1;j<=m;j++)
			for(int i=n;i>=1;i--)
			{
				if(!a[i][j])lst[i][j]=lst[i+1][j],s[i][j]=s[i+1][j]+1;
				else s[i][j]=0,lst[i][j]=i;
				gc[i][j]=gc[i+1][j]+sum[i][j]-1,gc[i][j]%=mod;
				gf[i][j]=gf[i+1][j]+1ll*(sum[i][j]-1)*(s[i][j]-1)%mod,gf[i][j]%=mod;
			}
		for(int i=1;i<=n-2;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(a[i][j]||a[i+1][j]) continue;
				sc=sc+1ll*(sum[i][j]-1)*(gc[i+2][j]-gc[lst[i][j]][j]+mod)%mod;
				sf=sf+1ll*(sum[i][j]-1)*(gf[i+2][j]-gf[lst[i][j]][j]+mod)%mod;
			}
		}
		printf("%d %d\n",sc*c,f*sf);
	}
	return 0;
}