RT

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353ll
int p[1001][1001],q[1001][1001];
int t,n,m,i,j,l,k,s,c,f,tmp;
bool a[1001][1001];
signed main()
{
	scanf("%lld%lld",&t,&n);
	while(t--)
	{
		scanf("%lld%lld%lld%lld",&n,&m,&c,&f);
		k=s=0; 
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++) scanf("%1d",&a[i][j]);
		for(i=1;i<=n;i++)
			for(j=m;j;j--) p[i][j]=(a[i][j] ? 0:p[i][j+1]+1);
		if(c)
		{
			for(j=1;j<=m;j++)
				for(i=1;i<n-1;i++)
					for(l=i+1;l<=n;l++)
					{
						if(a[i][j]||a[l][j])break;
						if(l>i+1)k=(k+(p[i][j]-1)*(p[l][j]-1))%mod;
					}
		}
		if(f)
		{
			for(j=1;j<=m;j++)
				for(i=n;i;i--) q[i][j]=(a[i][j] ? 0:q[i+1][j]+1);
			for(j=1;j<=m;j++)
				for(i=1;i<n-2;i++)
				{
					for(l=i+1;l<n;l++)
					{
						tmp=0;
						if(a[i][j]||a[l][j])break;
						if(l>i+1)tmp=(tmp+(p[i][j]-1)*(p[l][j]-1))%mod,tmp=tmp*(q[l][j]-1)%mod;
						s=(s+tmp)%mod;
					}
				}	
		}
		printf("%lld %lld\n",k,s);
	}
	return 0;
}

CQ NOIP取消了，自己在家模拟。

大意是枚举每个C,F的左竖边，然后用前缀和计算每条线段的贡献

但是这是O(n^3)，求大佬优化

如果优化不了，给出一种我看得懂的正解也行

看着几乎整个机房都AC掉了T1，真的很痛苦/kk