以此题解纪念我那寄了的NOIP

这道题拿到手，最先该想到的就是计数问题 既然要我们计数，暴力是肯定过不去的 那我们就来找一下规律 c和f的合法很简单，c只需要有两行合法的横并且之间相隔一行即可，f则更简单了，简而言之在c下面加一竖就是f，所以找到了c就等同于找到了f 那么我们如何找c？ 我一开始的思路是输入时把每一个左下角的点标记上，然后求这些点所在的横行以及列的前缀和，求出c 然鹅我很快发现这样写不仅我的代码跟shi一样臭长还会Tle 所以我去观（jie）摩（jian）了一下洛谷上其他大佬的思路 然后我发现，我在预处理前缀和时只需要找到每一行中合法的横就行了！然后求方案数时只需要把这一行和上上一行的横一块算就可以了（具体公式待会再说） 预处理代码如下：

for(int i=1;i<=n;i++)
		{
			for(int j=m-1;j>=1;j--)
			{
				if(map1[i][j]=='1') f[i][j]=-1;//如果不能种，那么这点赋值为-1，下一个点如果有就+1=0，下下个点如果有就是+1=1，就正常了
				else if(map1[i][j+1]=='0') f[i][j]=f[i][j+1]+1;//能种的话就求前缀和
//注意！这里一定不能写成else！因为如果是else的话map1数组是字符，是有换行符存在的!只能是else if！
			}
		}

前缀和处理完之后，我们来说如何计算 计数无非就两个原理，一个是乘法原理，一个是加法原理 很容易想到这题是乘法原理 因为设下边一行是b，上上一行每多x，方案增加xb okc有了那么f就跟着出来了 代码实现： 我们按列的顺序枚举 c1，f1分别是这一点上上行之前的方案数 根据乘法原理我们只需要让当前的方案加上其他两行的方案数*当前点的前缀和即可（不要忘记取模！因为数据可能特特特特大，不每一步都取模容易寄） c有了的话f就有了（看注释） 计算代码如下：(1ll是强制转换成longlongint）

for(int j=1;j<m;j++)
		{
			int c1=0,f1=0;
			for(int i=1;i<=n;i++)
			{
				if(f[i][j]==-1)
				{
				 	c1=0;f1=0;
					continue ;
				}
				ansc=ansc%mod+(1ll*f[i][j]*(c1%mod))%mod;
				ansf=(ansf%mod+f1%mod)%mod;
				f1=(f1+(1ll*f[i][j]*(c1%mod))%mod)%mod;//这就是上一次计算的f值，每多1就加上之前的方案数就行
				c1+=max(0,f[i-1][j]);//(如果这点不能种我设的初值是-1，所以要用max去取0)
			}
		}

总代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long ansc,ansf,C,F;
char map1[1005][1005];
int f[1005][1005];
int n,m,t,id;
int main()
{
	scanf("%d%d",&t,&id);
	while(t--)
	{
		memset(f,0,sizeof f);
		scanf("%d%d%d%d",&n,&m,&C,&F);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>map1[i][j];
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=m-1;j>=1;j--)
			{
				if(map1[i][j]=='1') f[i][j]=-1;
				else if(map1[i][j+1]=='0') f[i][j]=f[i][j+1]+1;
			}
		}
		for(int j=1;j<m;j++)
		{
			int c1=0,f1=0;
			for(int i=1;i<=n;i++)
			{
				if(f[i][j]==-1)
				{
				 	c1=0;f1=0;
					continue ;
				}
				ansc=ansc%mod+(1ll*f[i][j]*(c1%mod))%mod;
				ansf=(ansf%mod+f1%mod)%mod;
				f1=(f1+(1ll*f[i][j]*(c1%mod))%mod)%mod;
				c1+=max(0,f[i-1][j]);
			}
		}
		cout<<(C*ansc)%mod<<' '<<(F*ansf)%mod<<endl;
		ansc=ansf=0;
	}
	return 0;
}