1934: ly的二叉树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 42  Solved: 9
[Submit][Status][Web Board]

Description

某一天，ly正在上数据结构课。老师在讲台上面讲着二叉树，ly在下面发着呆。
突然ly想到一个问题：对于一棵n个无编号节点的有根二叉树，有多少种形态呐？你能告诉她吗？  

Input

多组输入，处理到文件结束
每一组输入一行，一个正整数n(1≤n≤1000000),意义如题目所述。  

Output

每组数据输出一行，包含一个正整数表示答案，由于数字可能非常大，你只需要把最后的结果对1000000007取模即可。  

Sample Input

3

Sample Output

5 卡特兰数公式：h(n)=h(n-1)*(4*n-2)/(n+1);这里直接取模是不对的。因为涉及了除法，所以我们改成成（n+1）的逆元。 #include using namespace std; #define LL long long #define N 1000005 #define MOD 1000000007 long long ans[N]; void Egcd(LL a,LL b,LL &x,LL &y)//扩展欧几里德 { if(b==0) { x=1; y=0; return ; } Egcd(b,a%b,x,y); LL tmp=x; x=y; y=tmp-a/b*y; } int main() { int n; ans[0] = 0, ans[1] = 1; for(int i=2; i<=N; i++) { LL x,y; Egcd(i+1,MOD,x,y);//求i+1的乘法逆元x ans[i]=ans[i-1]*(4*i-2)%MOD*(x%MOD+MOD)%MOD; } while(~scanf("%d",&n)) { printf("%lld ",ans[n]); } return 0; }