2018牛客多校01 A Monotonic Matrix

链接:https://www.nowcoder.com/acm/contest/139/A

求一个n*m的0、1、2矩阵(满足左上小于右下)的构造方案数。

方案数就等于这两条可以重合(不可相交)的分界线的种类数,如下图:

img

即:给定起点(n,0)、终点(0,m),只能向上和向右走,问有多少种走法,其实就是向右走m步向上走n步的组合数:
$$
C_{n+m}^m或C_{n+m}^n
$$
这里给出Lindström–Gessel–Viennot引理的应用:给一张无权有向无环图,给定n个起点和对应的n个终点,求n条不相交路径的方案数,引理给出结果为:

img

其中$a_{i}$表示路径i的起点,$b_{i}$表示路径i的终点。答案就是M的行列式的值。

对于本两条线的起点和终点不能重叠而且得和原方案等价(方案数等价即可),这就需要变换一下。把起终点向左上平移一下,将其中的一对起终点平移到$(n-1,-1)$和$(-1,m-1)$去,就有$e(a_1,b_1)=e(a_2,b_2)=C_{n+m}^n$,$e(a_1,b_2)=C_{n+m}^{n+1}$,$e(a_2,b_1)=C_{n+m}^{m+1}$那么针对本题的答案就是:
$$
{C_{n+m}^n}^2-C_{n+m}^{n+1}×C_{n+m}^{m+1}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const LL mod = 1e9+7;
const int maxn = 3010;
int n, m;
LL c[maxn][maxn];

void init() {
memset(c,0,sizeof(c));
c[0][0]=c[1][0]=c[1][1]=1;
for(int i = 2; i < maxn; i++) {
c[i][0] = c[i][i] = 1;
for(int j = 1; j < i; j++) {
c[i][j] = c[i-1][j] + c[i-1][j-1];
c[i][j] %= mod;
}
}
}

signed main() {
// freopen("in", "r", stdin);
init();
while(~scanf("%d%d",&n,&m)) {
LL ret = c[n+m][n]*c[n+m][n]; ret %= mod;
LL tmp = c[n+m][n+1]*c[n+m][m+1]; tmp %= mod;
ret -= tmp; ret += mod; ret %= mod;
printf("%lld\n", ret);
}
return 0;
}