【fjwc2015】世界树

2015年2月4日1,8590

【题目描述】

奥丁杀死的巨人伊米尔后,从伊米尔的尸体上生长出来一株巨大的梣树,它是整个宇宙的核心,被称为世界之树,这个巨木的枝干构成了整个世界,它被神秘的奥术力量所守护。

奥丁发现,世界树的每个节点至多有两棵子树,其蕴含的奥术力量是子树奥术力量的最大值+1,如果一个节点没有子树,其奥术力量为1,这些节点被称为“源”。

世界树在悠长的岁月里形成了奇妙的魔法平衡,具体来说,它的左子树与右子树的奥术力量的差的绝对值不会超过1。若一个节点只有一棵子树(不妨设为左子树),则右子树的奥术力量视为0。

现在奥丁想知道,在n个节点的世界树中,最高和最低的两个“源”的深度差最大是多少?

【输入格式】

第一行一个整数T,表示数据组数。

以下T行,每行一个整数n表示世界树的节点数。

【输出格式】

T行,每行一个整数表示任意两个“源”的奥术力量的差的最大值。

【样例输入】

2

5

12345

【样例输出】

1

9

【数据范围】

对于10%的数据,n <= 10

对于40%的数据,n <= 2^31 – 1

对于60%的数据,n <= 10^100

对于80%的数据,n <= 10^1000

对于100%的数据,1 <= n <= 10^10000, T <= 50

前八个点时间限制2000ms,最后两个数据点时间限制6000ms

题解

搬运coolinging神犇学长的题解

为了求在包含n个节点的世界树中,最高与最低的叶节点之间的深度差的最大值,考虑固定最低的叶节点的深度为h(h也即树的高度),转而去求最高的叶节点的深度的最小值。

以下结论可通过数学归纳法或递推证明得到:(定义空树的高度为-1)

高度为h的世界树,至少包含S(h) = fib(h+3) – 1个节点。

在高度为h的世界树中,任一叶节点的深度均不小于[h/2](上取整)。

以下结论可通过构造法证明得出:

存在高度为h的世界树,它的某个叶节点的深度为[h/2](上取整)

当n大于10时,n个节点的世界树的最高与最低的叶节点的深度差不小于n-1个节点的世界树的最高与最低的叶节点的深度差,即本题满足答案单调性(实际上仅n=6时不满足单调性)。

故本题转化为判断n处在哪两个Fibonacci数之间,更准确地说是找到最大的h,满足fib(h+3) – 1 <= n,本题答案即为[h/2](下取整)

对于40%的数据,n <= 2^31 – 1。

直接递推Fibonacci数列即可求出答案。

对于60%的数据,n <= 10^100。

使用高精度即可。

对于80%的数据,n <= 10^1000。

线性递推会超时,使用二分答案与矩阵乘法快速幂快速求解Fibonacci。

时间复杂度:O(T * log^2n * 高精度运算)

对于100%的数据,n <= 10^10000。

边矩阵乘法边进行二分。

时间复杂度:O(T * logn * 高精度运算)

实际上边矩乘边二分说的是二进制拆分