排列组合( Lindström–Gessel–Viennot lemma 定理)

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

Monotonic Matrix

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

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 2
2 2
1000 1000

输出
复制

6
20
540949876

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

题意：

求有多少n*m的矩阵满足：

1.每个数都是0或1或2

2.a(i,j)<=a(i+1,j)

3.a(i,j)<=a(i,j+1)

题解： $C(n+m,n)*C(n+m,n)-C(n+m,n-1)*C(n+m,n+1)$

链接：https://blog.csdn.net/black_miracle/article/details/81128169

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MAX 2005

const ll mod=1e9+;

ll C[MAX][MAX];

void c()

{

    for(int i=;i<MAX;i++)

    {

        C[i][]=;

        for(int j=;j<=i;j++)

            C[i][j]=(C[i-][j-]+C[i-][j])%mod;

    }

}

int main()

{

    c();

    int n,m;

    while(cin>>n>>m)

    {

      cout<<((C[n+m][n]*C[n+m][n])%mod-(C[n+m][n-]*C[n+m][n+])%mod+mod)%mod<<endl; //加+mod是为了防止出现负数

    }

}

该题是一个定理来着，具体看这个链接：https://blog.csdn.net/qq_25576697/article/details/81138213

巴特西

排列组合( Lindström–Gessel–Viennot lemma 定理)

最新文章

热门文章