- 2021 江西省赛A
题目链接：https://ac.nowcoder.com/acm/contest/21592/A
题意：给出一个布尔矩阵（每个位置的值非零即一）
然后问给定p和q，问从（1,1）=》（n,m）的所有路径中至少通过p次0&&q次1的路径的数量
const int md = 998244353; int a[507][507]; ll dp[507][1007]; int main() { int n = read,m = read,p = read,q = read; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) a[i][j] = read; } dp[1][!a[1][1]] = 1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(i != 1 || j != 1) if(a[i][j] == 1) { for(int k=i+j-1; k>=0; k--) dp[j][k] = (dp[j][k] + dp[j-1][k]) % md; } else { for(int k=i+j-1; k>=1; k--) dp[j][k] = (dp[j][k-1] + dp[j-1][k-1]) % md; dp[j][0] = 0; } } } ll ans = 0; for(int i=p; i<=n+m-1-q; i++) ans = (ans + dp[m][i]) % md; cout << ans << endl; return 0; }
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-动态规划22-括号生成8282 人正在系统学习中
