题意：
简单来说就是给你一张二维的图只有0和1，然后你可以向下或者向右移动，要求最后到达(n,m)的方案数
思路：
首先通过01可以优化一维，在思考可以发现只需要两维就能进行滚动数组的优化，每次只更新两行，之前由于取mod不清楚一直wa，解决完之后，发现了我在实现滚动数组的时候，如果在当前位置为1时，我的更新是dp[i&1][j][k+1]=dp[(i-1)&1][j][k]+dp[i&1][j-1][k]，但是仔细一想就会发现，如果k=0时，dp[i&1][j][k]是不会更新的，所以还需要这里一点细节
#include<bits/stdc++.h> using namespace std; const int maxn=505; const int mod=998244353; long long dp[2][maxn][maxn*2]; int a[maxn][maxn]; int main() { int i,j,k; int n,m,p,q; cin>>n>>m>>p>>q; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>a[i][j]; } } dp[1][1][a[1][1]]=1; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(i==1&&j==1) continue; for(k=0;k<=1001;k++) { if(a[i][j]==1) { if(k==0) dp[i&1][j][k]=0; dp[i&1][j][k+1]=dp[(i-1)&1][j][k]%mod+dp[i&1][j-1][k]%mod; dp[i&1][j][k+1]%=mod; } else { dp[i&1][j][k]=dp[(i-1)&1][j][k]%mod+dp[i&1][j-1][k]; dp[i&1][j][k]%=mod; } } } } int cnt1=n+m-1; long long ans=0; for(k=q;k<=1000;k++) { if(cnt1-k>=p) { ans=ans+dp[n&1][m][k]%mod; ans%=mod; } } cout<<ans<<endl; return 0; }
