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 <iostream>
#include <cstdio>
#include <vector>
#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("%dn", ans[n]);
	}
	system("pause");
	return 0;
}

最后

以上就是尊敬蜜蜂为你收集整理的ZCMU 1934: ly的二叉树【Catalan数】【大数取模求逆元】【快速幂】ZCMU 1934: ly的二叉树的全部内容，希望文章能够帮你解决ZCMU 1934: ly的二叉树【Catalan数】【大数取模求逆元】【快速幂】ZCMU 1934: ly的二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。