NOIP 2022 T1 种花

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define int unsigned long long
#define mod 998244353
int t,id,n,m,c,f,G[2000][2000];
int presum[2000][2000];//右缀和
int downsum[2000][2000];//下缀和
int downpresum[2000][2000];//下右缀和
pair<int,int> V(){
	int sumc=0,sumf=0;//C的方案数，F的方案数
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(G[i][j]==1)continue;//如果这个点能走，那就走
			bool flag=0;
			if(G[i][j+1]==0&&G[i][j]==0&&G[i+1][j]==0&&G[i+2][j]==0&&i+2<=n){
				flag=1;
			}
			else{
				flag=0;
			}
			if(flag){
				int sum2=presum[i][j+1];//第一行的长度
				sumc+=(downpresum[i+2][j]*sum2);//加上从i+2的位置起，下右的前缀和，也就是下面的右缀和的缀和。
			}
			
			flag=0;
			if(G[i][j+1]==0&&G[i][j]==0&&G[i+1][j]==0&&G[i+2][j]==0&&G[i+3][j]==0&&i+3<=n){
				flag=1;
			}
			else{
				flag=0;
			}
			if(flag){
				int sum1=presum[i][j+1];
				sumf+=((downpresum[i+2][j]-downpresum[i+downsum[i][j]-1][j])*sum1*(downsum[i][j]-3));
			}
		}
	}
	return make_pair(sumc,sumf);//返回一个二元组
}
signed main(){
	scanf("%d%d",&t,&id);
	while(t--){
		memset(presum,0,sizeof(presum));
		memset(G,0,sizeof(G));
		memset(downsum,0,sizeof(downsum));
		memset(downpresum,0,sizeof(downpresum));
		scanf("%d%d%d%d",&n,&m,&c,&f);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char ch=getchar();
				while(!isdigit(ch))ch=getchar();
				G[i][j]=(ch=='1');
			}
		}
		for(int i=n;i>=1;i--){
			for(int j=m;j>=1;j--){
				presum[i][j]=(G[i][j]==0?1+presum[i][j+1]:0);
				downsum[i][j]=(G[i][j]==0?1+downsum[i+1][j]:0);
				downpresum[i][j]=(G[i][j]==0&&G[i+1][j]==0?downpresum[i+1][j]+presum[i][j+1]:0);
			}
		}
		pair<int,int> par = V();
		printf("%llu %llu\n",(c*par.first)%mod,(f*par.second)%mod);//就是这个出问题了，第一个llu出问题了，样例三正确答案应该是114，但是这里输出109。
	}
	return 0;
}

但是答案却：

测试点信息：

但是在我没有优化我的代码之前，确是80分：

没有优化前的代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define int unsigned int
#define mod 998244353
int t,id,n,m,c,f,G[2000][2000];
int presum[2000][2000];
int downsum[2000][2000]; 
pair<int,int> V(){
	int sumc=0,sumf=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(G[i][j]==1)continue;
			bool flag=0;
			if(G[i][j+1]==0&&G[i][j]==0&&G[i+1][j]==0&&G[i+2][j]==0&&i+2<=n){
				flag=1;
			}
			else{
				flag=0;
			}
			if(flag){
				int sum2=presum[i][j+1];
				for(int x=i;x<=n&&G[x][j]!=1;x++){
					if(x<=i+1)continue;
					int sum1=presum[x][j+1];
					sumc+=(sum1*sum2);
				}
			}
			
			flag=0;
			if(G[i][j+1]==0&&G[i][j]==0&&G[i+1][j]==0&&G[i+2][j]==0&&G[i+3][j]==0&&i+3<=n){
				flag=1;
			}
			else{
				flag=0;
			}
			if(flag){
				int sum1=presum[i][j+1];
				for(int x=i;x<=n&&G[x][j]!=1;x++){
					if(x<=i+2){
						continue;
					}
					for(int xx=i+2;xx<x;xx++){
						int sum2=presum[xx][j+1];
						sumf+=(sum1*sum2);
					}
				}
			}
		}
	}
	return make_pair(sumc,sumf);
}
signed main(){
	scanf("%d%d",&t,&id);
	while(t--){
		memset(presum,0,sizeof(presum));
		memset(G,0,sizeof(G));
		scanf("%d%d%d%d",&n,&m,&c,&f);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char ch=getchar();
				while(!isdigit(ch))ch=getchar();
				G[i][j]=(ch=='1');
			}
		}
		for(int i=n;i>=1;i--){
			for(int j=m;j>=1;j--){
				presum[i][j]=(G[i][j]==0?1+presum[i][j+1]:0);
//				donwsum[i][j]=(G[i][j]==0?1+downsum[i+1][j]:0);
			}
		}
		pair<int,int> par = V();
		printf("%u %u\n",(c*par.first)%mod,(f*par.second)%mod);
	}
	return 0;
}

求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！求调！