2018牛客多校01 A Monotonic Matrix

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

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

方案数就等于这两条可以重合（不可相交）的分界线的种类数，如下图：

即：给定起点(n,0)、终点(0,m)，只能向上和向右走，问有多少种走法，其实就是向右走m步向上走n步的组合数：

$$C_{n+m}^m或C_{n+m}^n$$
这里给出Lindström–Gessel–Viennot引理的应用：给一张无权有向无环图，给定n个起点和对应的n个终点，求n条不相交路径的方案数，引理给出结果为：

其中$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}$$

复制

#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;
}