ZCMU 1934: ly的二叉树

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

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

Input

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

Output

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

Sample Input

3

Sample Output

5

思路

一开始看到这道题我是懵逼的，经过一个上午和一个中午的猛肝，终于从CSDN各大大佬们的相关博客中得到启发，成功AC。 这是一道以离散数学结论为幌子，考察大数取模运算中除法取模处理的题，在此总结一下自己的理解。

用结论

本题要用到二叉树形态的Catalan数结论：
n个节点的二叉树形态求解递推公式：，其中h(0)=0,h(1)=1。
 本题数据过大，需要按题目要求对1000000007取模，但是在四则运算中，在除法运算时取模不等于对除法运算结果取模，由于本题表达式中又含有除法，因此无法直接求出。

求逆元

可将对商取模转换为对被除数和其除数关于1000000007的逆元，即： (a / b) % p = (a % p * inv(b) % p) % p 将除数用其逆元替换，将除法转为乘法可得出不爆表的结果。 求逆元的公式为： a关于b的逆元等于a^(b-2) 又由于这题的b很大.......坑爹啊   导致常规的从1到b循环相乘很慢，并且没算几次就会爆表，所以我们有：

快速幂算法

因为十进制数b可以用二进制表示为：其中bn表示b的二进制形式中的第n位。（其实就是个二进制转十进制公式） 故a的b次方可以表示为 这就是快速幂算法的理论公式了。 我们能够发现如果b的某一位是0的话，那么那一位所在的a因子为1，不必计算，因此可以加入一个if排除它。 我们还能够发现在二进制里每一位的数要么是0要么是1，也就是说a公式的每个因子，如果当前因子的b非零，其值都是前一个因子在b非0条件下值的平方，所以我们完全可以用一个几行的循环来算出每一个因子，并把它们取模乘起来。实现代码如下： //快速幂算法 long long int quickpow(long long int a, long long int b) { a %= MOD;//每次都记得取模 //res用于记录结果 long long int res = 1; for (; b; b >>= 1)//b右移一位，本质上是对b的二进制数每一个数进行遍历 { //b和1做与运算，本质上就是判断b的二进制形式上最右位是否为1，是则结果为1，否则为0 if (b & 1)//如果b的二进制末位不为0 { res = (res*a) % MOD; } a = (a*a) % MOD;//每次记录本次a因子中b不为0情况下的值，用于下一次循环的求解 } return res; } 在解决方法问题之后，接下来就是用一个循环将1到1000000的所有结果全部肝出来，每次输入直接输出对应结果，美滋滋。 那么接下来就上代码：

AC代码

#define _CRT_SECURE_NO_WARNINGS #include #include #include #define MOD 1000000007 int ans[1000001]; using namespace std; //快速幂 long long int quickpow(long long int a, long long int b) { a %= MOD;//每次都记得取模 //res用于记录结果 long long int res = 1; for (; b; b >>= 1)//b右移一位，本质上是对b的二进制数每一个数进行遍历 { //b和1做与运算，本质上就是判断b的二进制形式上最右位是否为1，是则结果为1，否则为0 if (b & 1)//如果b的二进制末位不为0 { res = (res*a) % MOD; } a = (a*a) % MOD;//每次记录本次a因子中b不为0情况下的值，用于下一次循环的求解 } return res; } //求逆元 long long int inv(long long int a, long long int b) { return quickpow(a, b - 2); } int main() { long long int n, i; ans[0] = 0; ans[1] = 1; for (i = 2; i <= 1000000; i++) { ans[i] = ans[i - 1] * (4 * i - 2) % MOD*inv(i + 1, MOD) % MOD; } while(scanf("%lld",&n)!=EOF) { printf("%d ", ans[n]); } system("pause"); return 0; }