牛客网第一场 A Monotonic Matrix

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

Count the number of n x m matrices A satisfying the following condition modulo (10⁹+7).
* A_{i, j} ∈ {0, 1, 2} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.
* A_{i, j} ≤ A_{i + 1, j} for all 1 ≤ i < n, 1 ≤ j ≤ m.
* A_{i, j} ≤ A_{i, 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 ≤ n, m ≤ 10

* The number of test cases does not exceed 10

⁵

考虑 0101 和 1212 的分界线，用 (n,0)(n,0) 到 (0,m)(0,m) 的两条不相交（可重合）路径，平移其中一条变成 (n−1,−1)(n−1,−1) 到 (−1,m−1)(−1,m−1) 变成起点 (n,0)(n,0) 和 (n−1,−1)(n−1,−1)，终点 (0,m)(0,m) 和 (−1,m−1)(−1,m−1) 的严格不相交路径，套 Lindstrom-Gessel-Viennot lemma 定理。

lgv公式;

#include <iostream>

#include<stdio.h>

#define ll long long

#define mod 1000000007

using namespace std;

ll inv[];

ll jiecheng[];

ll pow (ll a,ll b)

{

    ll ans=;

    while(b>)

    {

        if(b%==)

        {

            ans=ans*a;

            ans=ans%mod;

        }

        b=b/;

        a=(a*a)%mod;

    }

    return ans;

}

int main()

{

    jiecheng[]=;

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

    {

        jiecheng[i]=jiecheng[i-]*i;

        jiecheng[i]=jiecheng[i]%mod;

    }

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

    {

        inv[i]=pow(jiecheng[i],mod-);

    }

   int n,m;

   while(~scanf("%d%d",&n,&m))

   {

      ll p;

      p=(jiecheng[n+m]*inv[n])%mod*inv[m]%mod;

      p=p*p%mod;

      ll q,w;

      q= (jiecheng[n+m]*inv[n+])%mod*inv[m-]%mod;

      w=(jiecheng[n+m]*inv[n-])%mod*inv[m+]%mod;

      q=q*w%mod;

      cout<<(p+mod-q)%mod<<endl;

    }

    return ;

}

巴特西

牛客网第一场 A Monotonic Matrix

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

备注:

最新文章

热门文章