2023.9.27测试

T1 [ABC311F] Yet Another Grid Task

what？？

发现一个点染了黑色后它下面会将一个三角形染成黑色，画个图发现按列考虑比较好

设 \(f_{i,j}\) 表示第 \(i\) 列最高的黑色格子为第 \(j\) 行的，\(j=n+1\) 表示这一列全是白色。那么有转移

可以用后缀和优化做到 \(O(n^2)\)。注意对于一列来说，\(j\) 必须大于等于最高的那个给定的黑色格子，所以 \(f_{i,top_i+1}\sim f_{n+1}=0\)

#include<bits/stdc++.h>
using namespace std;

const int N=2010,MOD=998244353;

int n,m,top[N],f[N][N],ans;
char s[N][N];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		scanf("%s",s[i]+1);
	
	for(int j=1; j<=m; j++)
	{
		top[j]=n+1;
		for(int i=1; i<=n; i++)
		{
			if(s[i][j]=='#')
			{
				top[j]=i;
				break;
			}
		}
	} 
	
	f[0][n+1]=1;
	for(int i=1; i<=m; i++)
	{
		int tmp=f[i-1][n+1];
		for(int j=n+1; j>=1; j--)
		{
			(tmp+=f[i-1][j-1])%=MOD;
			f[i][j]=tmp;
		}
		for(int j=top[i]+1; j<=n+1; j++)
			f[i][j]=0;
	}
	
	for(int i=1; i<=top[m]; i++)
		(ans+=f[m][i])%=MOD;
	
	printf("%d",ans);

	return 0;
}