弱省互测#0 t1
T1
2023-09-27 14:22:21 时间
题意
给一个\(N \times M\)的01网格,1不能走,从起点\((1, 1)\)走到\((N, M)\),每次只能向下或向右走一格,问两条不相交的路径的方案数。(n, m<=1000)
分析
先考虑一条,再考虑去掉相交的情况。
题解
令\(d(a, b, c, d)\)表示从\((a, b)\)走到\((c, d)\)一条路径的方案数,则可以简单得到答案:
\[Ans = d(2, 1, n, m-1) + d(1, 2, n-1, m) - T
\]
我们来考虑任意两条相交路径。
令\(p\)表示这些交点最下最右的点。那么我们将后面那一段路径换一下,也就是原来我往下,现在我往右,原来往右,现在往下。
发现其实这就是\(d(2, 1, n-1, m) + d(1, 2, n, m-1)\)
于是我们减掉后者即可。
#include <bits/stdc++.h>
using namespace std;
const int mo=1e9+7;
int n, m;
char s[2005][2005];
int d[2][2005][2005];
int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) {
scanf("%s", s[i]+1);
}
d[0][1][1]=d[1][1][1]=1;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
if(s[i][j]!='1') {
if(j!=1) {
d[1][i][j]=d[1][i-1][j]+d[1][i][j-1];
if(d[1][i][j]>=mo) {
d[1][i][j]-=mo;
}
}
if(i!=1) {
d[0][i][j]=d[0][i-1][j]+d[0][i][j-1];
if(d[0][i][j]>=mo) {
d[0][i][j]-=mo;
}
}
}
}
}
printf("%lld\n", (1ll*d[0][n][m-1]*d[1][n-1][m]%mo-1ll*d[0][n-1][m]*d[1][n][m-1]%mo+mo)%mo);
return 0;
}
相关文章
- 【2014NOIP普及组】T1. 珠心算测验 试题解析
- 【2008NOIP普及组】T1. ISBN号码 试题解析
- 【2001NOIP普及组】T1.数的计数 试题解析
- 【2000NOIP普及组】T1. 计算器的改良 试题解析
- 答题卡 / T1(模拟)
- 【DG特长生2010 T1】【SSL 1969】最小的数
- 【DG特长生2020 T1】数学题
- 【DG特长生2016 T1】【luogu P1151】【SSL 2640】子数整数
- [2018.08.08 T1] 签到题
- [2018.09.08 T1] 炉石
- [2018.10.11 T1] 锻造
- [2018.10.10 T1] 餐馆
- [2018.03.14 T1] 矩阵(matrix)
- [2018.08.09 T1] 数学题
- [2018.03.13 T1] 比赛(contest)