2018 牛客多校第一場A（不知名定理）

題目

題意：一個矩陣由012三個數字組成，這個矩陣從左到右，從上到下，都是不遞減的。

思路：

考慮 01 和 12 的分界線

是 (n, 0) 到 (0, m) 的兩條不相交(可重合)路徑

平移其中一條變成 (n-1, -1) 到 (-1, m-1)

變成起點 (n, 0) 和 (n-1, -1)，終點 (0, m) 和 (-1, m-1) 的嚴格不相交路徑 套 Lindström–Gessel–Viennot lemma

答案是Cn+m,n2 -Cn+m,m-1Cn+m,n-1

可以用楊輝三角求組合數

代碼：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[2050][2050];
const int ll mod=1e9+7;
void init()
{
    dp[0][1]=dp[1][1]=1;
    for(int i=2;i<=2002;i++)
    {
        dp[0][i]=dp[i][i]=1;
        for(int j=1;j<i;j++)
        {
            dp[j][i]=(dp[j][i-1]+dp[j-1][i-1])%mod;
        }
    }
}
int main()
{
    init();
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        ll ans=(dp[n][m+n]*dp[n][m+n]%mod+mod-dp[n-1][n+m]*dp[m-1][n+m]%mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}