圆内连弦 - 卡特兰数

知识点
总方案数是 $\frac{C_{2n}^2 * C_{2n -2}^2*\dots*C_2^2}{n!}$ 其中 $C_{2n}^2$ 表示每次选择2个，除以 $n!$ 表示这n次选择没有先后

而可行数是圆内连弦的个数，是个卡特兰数，不会的可以去上面的博客学习一下卡特兰数以及在圆内连弦的解法

化简总方案数 $= \frac{\frac{(2n)!}{2^n}}{n!}$

卡特兰数为 $\frac{1}{n + 1}C_{2n} ^n = \frac{1}{n + 1} * \frac{(2n)!}{n!n!}$

那么答案就是 $\frac{2^n}{(n + 1)!}$ ,求(n + 1)! % mod在mod下的逆元乘以 $2 ^ n$ % mod即可

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;
ll pow(ll a, ll b, ll p){
    ll ans = 1; a %= p;
    while(b){
        if(b & 1)ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int n, fac, f[N];
int main(){
    scanf("%d", &n);
    fac = 1;
    for(int i = 1; i <= n + 1; i++)
        fac = 1ll * fac * i % mod;
    printf("%lld\n", pow(2, n, mod) * pow(fac, mod - 2, mod) % mod);
    return 0;
}