The concept and application of Cartland number

Concept

$C_n^{2n}-C_{n-1}^{2n}=\frac{C_n^{2n}}{n+1}$

Application 1

Background

Their thinking

take 01 The sequence is placed in the coordinate system , The starting point is set at the origin . if 0 To the right ,1 To go up , So in any prefix 0 No less than 1 The number of is transformed into , Any point on the path , The abscissa is greater than or equal to the ordinate . The problem is the number of such legal paths .

The following figure , From (0,0) Go to the (n,n) The path of , The green line and below indicate legal , It is illegal to touch the red line .

It can be seen from the picture that , Any illegal path （ Such as black path ）, All correspond to one from (0,0) Go to the (n−1,n+1) A path for （ Such as gray path ）. And any one (0,0) Go to the (n−1,n+1) The path of , It also corresponds to one from (0,0) Go to the (n,n) Illegal path .

The answer is shown in the figure , The Cartland number .

Template code

// Background ：AcWing 889
#include<iostream>
using namespace std;
const int N=100010,mod=1e9+7;
typedef long long LL;
int a,b,n;
int qmi(int a,int b,int p)
{
    
    int res=1;
    while(b)
    {
    
        if(b&1) res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b=b>>1;
    }
    return res;
}
int main()
{
    
    scanf("%d",&n);
    a=2*n,b=n;
    int res=1;
    for(int i=a;i>a-b;i--) res=(LL)res*i%mod;
    for(int i=1;i<=b;i++) res=(LL)res*qmi(i,mod-2,mod)%mod;
    // Convert division to modular inverse of multiplication 
    res=(LL)res*qmi(n+1,mod-2,mod)%mod;
    printf("%d",res);
    return 0;
}