题解 | #二叉树的个数#

答案其实就是卡特兰数，求法有很多种，下面介绍逆元求法：
求等同于求， 为在下的逆元
逆元存在定理：如果, 且为质数，那么a存在逆元的充要条件是，那么是的逆元，也是的逆元。
费马小定理：
如果是一个整数， 是一个质数

1. 如果是的倍数：
2. 否则

所以的逆元是
故同余结果为 ;

Lucas定理：

class Solution {
public:
#define LL long long
    LL factor[200010], mod = 1e9 + 7;
    LL qp(LL a,LL b) {
        LL ans = 1;
        a %= mod;
        while(b) {
            if(b & 1) ans = ans * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }
    int C(LL n, LL m) {
        if(n < m) return 0;
        return factor[n] * qp(factor[m] * factor[n-m], mod-2) % mod;
    }
    LL Lucas(LL n, LL m) {
        if(m == 0) return 1;
        return C(n % mod, m % mod) * Lucas(n / mod, m / mod);
    }

    int numberOfTree(int n) {
        // write code here
        factor[1]=1;
        for (int i=2; i<=2*n; i++) {
            factor[i] = factor[i-1]*i%mod;
        }
        LL ans = (Lucas(2*n,n) - Lucas(2*n,n+1)) % mod;
        if(ans < 0) ans += mod;
        return ans;
    }
};