牛客网暑期acm训练赛讲解视频,牛客网暑期acm训练赛

链接：https://www.nowcoder.com/acm/contest/139/A
来源：牛客网
 

Count the number of n x m matrices A satisfying the following condition modulo (109+7).
* Ai, j ∈ {0, 1, 2} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai + 1, j for all 1 ≤ i < n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai, j + 1 for all 1 ≤ i ≤ n, 1 ≤ j < m.

输入描述: The input consists of several test cases and is terminated by end-of-file.Each test case contains two integers n and m. 输出描述: For each test case, print an integer which denotes the result.

示例1

输入

复制

1 22 21000 1000 输出

复制

620540949876 备注:  

* 1 ≤ n, m ≤ 103
* The number of test cases does not exceed 105.

题意：

　　给一个n*m的矩阵赋值（0，1，2）。使得每个数都不小于它左面和上面的数。

题解：

　　构建0和1的轮廓线。对于单独的轮廓线，共需要往上走n步，往右走m步。有C(n+m,n)种方式。两个轮廓线的总情况是C(n+m,n)*C(n+m,n)种方式。但是还要去重掉相交的情况。

　　假设将0轮廓线向左上平移一个单位，那么此时两个轮廓线既不能相交也不能重合。

　　假设0轮廓线是从A到B，1轮廓线是从C到D。那么相交的情况可以理解成从A到D，从C到B。情况数是C(n+m,n-1)*C(n+m,m-1)

　　总答案就是C(n+m,n)*C(n+m,n)-C(n+m,n-1)*C(n+m,m-1)

//Sinhaeng Hhjian#include<stdio.h>#include<string.h>#include<map>#include<vector>#include<algorithm>using namespace std;typedef long long ll;const int maxn=1e6+5;const int mod=1e9+7;int n, m, C[2004][2004];int main(){ C[1][0] = C[1][1] = 1; for(int i=2;i<2004;i++){ C[i][0]=1; for(int j=1;j<2004;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } while(~scanf("%d%d", &n, &m)) printf("%dn", ((1ll*C[n+m][n]*C[n+m][n])%mod-(1ll*C[n+m][n-1]*C[n+m][m-1])%mod+mod)%mod); return 0;}