AcWing 889. 01 sequence satisfying the condition (Cartland number)

Topic linking

https://www.acwing.com/problem/content/891/

Ideas

Because there is n individual 1 and n individual 0, Then we can finally reach the point (n,n), It's hard for us to think positively , So we can see in the middle 1 The quantity ratio of 0 In many cases , For this method, we can turn it into a plane diagram ,1 It means taking a step to the right ,0 It means taking a step up , Then the opposite of what we are asking for now is to go through $y=x+1$ The number of schemes for this line , We can do to this line (n,n) A symmetric graph of the is (n-1,n+1), We will find that the number of schemes in this position is ：$C_{2n}^{n-1}$, For walking to (n,n) The number of all schemes is :$C_{2n}^n$, Then let's just make a difference , After simplification is ：
$\frac{C_{2n}^n}{n+1}$ This number is also known as the Cartland number

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

ll ksm(ll a,ll b){
    
    ll res = 1;
    for(;b;b>>=1,a=a*a%mod) if(b & 1) res = res * a % mod;
    return res;
}

ll C(ll a,ll b){
    
    b = min(a-b,b);
    ll ansL = 1,ansR = 1;
    for(int i = 1;i <= b; ++i){
    
        ansL = ansL * (a-i+1) % mod;
        ansR = ansR * i % mod;
    }
    ll ans = ansL * ksm(ansR,mod-2) % mod;
    return ans;
}

ll slove(ll n){
    
    return (C(2*n,n)-C(2*n,n-1) + mod) % mod;
}

int main()
{
    
    ll a;
    scanf("%lld",&a);
    printf("%lld\n",slove(a));
    
    return 0;
    
}