Mio visits ACGN Exhibition

One day, Mio visits an Animation Comic Game Novel (ACGN) Exhibition, and she would like to buy some presents for Ritsu.

We assure that the space of the exhibition is a n × m grid, called the grid A, and each cell in the grid represents a stall, only selling present 0 or 1. In other words, every cell of the n × m grid A is filled with 0 or 1.

Under the control policy for containing COVID−19, there are some restrictions on visiting route.

We define a SAFE PATH as a path from the top left cell (1,1), to the bottom right cell (n,m), and if you are in the cell (x,y), then you can only travel to the cells (x+1,y) or (x,y+1). Every visitor has to visit the exhibition through SAFE PATH, so does Mio.

The two paths are considered to be different if and only if at least one cell passed differs.Mio wonders how many different SAFE PATHs, which have some 0s and 1s, and the number of 0 is at least p, the number of 1 is at least q.

Since the answer may be too large, you only need to output the result modulo 998244353.

The first line contains four integers, n, m, p, q(1≤n,m≤500,0≤p,q≤10000).

Each of the next n lines contains m space separated integers $A_{i,j}$ (0≤ $A_{i,j}$ ≤1), denoting the number in the cell (i,j) of the grid A.

#include<bits/stdc++.h> #define ll long long using namespace std; const int mod=998244353; int f[2][505][1005]; int main(){ int n,m,p,q,x; cin>>n>>m>>p>>q; f[0][1][0]=1; for(int i=1;i<=n;i++){ int e=i&1; memset(f[e],0,sizeof f[e]); for(int j=1;j<=m;j++){ scanf("%d",&x); for(int k=n+m-1;~k;k--) if(x&&k) f[e][j][k]=(f[e^1][j][k-1]+f[e][j-1][k-1])%mod; else if(!x) f[e][j][k]=(f[e][j-1][k]+f[e^1][j][k])%mod; } } int ans=0; for(int i=q;i<=n+m-1-p;i++) ans=(ans+f[n&1][m][i])%mod; cout<<ans; }

详情