题解 | #二叉树的个数#
二叉树的个数
http://www.nowcoder.com/practice/78bdfba0a5c1488a9aa8ca067ce508bd
答案其实就是卡特兰数，求法有很多种，下面介绍逆元求法：
求等同于求
，
为
在
下的逆元
逆元存在定理：如果, 且
为质数，那么a存在逆元的充要条件是
，那么
是
的逆元，
也是
的逆元。
费马小定理：
如果是一个整数，
是一个质数
- 如果
是
的倍数：
- 否则
所以的逆元是
故同余结果为
;
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;
}
}; 
虾皮信息一面330人在聊
投递字节跳动等公司7个岗位 >
查看6道真题和解析