\[\text{省流：1.5h狂砍8分}
\]
T1 [ABC311F] Yet Another Grid Task
what？？
发现一个点染了黑色后它下面会将一个三角形染成黑色，画个图发现按列考虑比较好
设 \(f_{i,j}\) 表示第 \(i\) 列最高的黑色格子为第 \(j\) 行的，\(j=n+1\) 表示这一列全是白色。那么有转移
\[f_{i,j}=\sum_{k=j-1}^{n+1}{f_{i-1,k}}
\]
可以用后缀和优化做到 \(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;
}