#3709. 线段树的神秘请求

线段树的神秘请求

题目描述

线段树的神秘请求

CQ王在使用线段树时,发现了一个神奇的现象。每当你独自从根节点出发,遍历整个线段树,便会在某些节点上听到低语。这些低语只能在特定的访问顺序中听到,因此CQ王决定研究这个问题。

假设有 nn 个节点的线段树,节点从 11 到 nn 编号。CQ王定义了一个 <d, l, r> 顺序,它等价于如下的访问顺序:首先按 <d, l, (l+ r) / 2> 顺序访问左子节点,然后按 <d, (l + r + 1)/2, r> 顺序访问右子节点。当 l=rl=r 时,不进行任何访问。

现在CQ王想知道,在所有的可能的 <d, l, r> 访问顺序中,有多少种顺序会在访问过程中听到低语。因为答案可能很大,所以CQ王想让你帮他计算出这个数对 109+710^9 + 7 取模后的结果。

输入格式

输入共一行,一个整数 nn (1≤n≤1018)1 \le n \le 10^{18}),表示节点的数量。

输出格式

输出共一行,一个整数,表示答案对 109+710^9 + 7 取模后的值。

样例

3
9 
7
38 

说明/提示

CQ王的线段树是完全二叉树,所以 n=2h−1n=2^h - 1 ,其中 hh 为树的高度。但是今天CQ王研究的线段树却不是完全二叉树,而是由他定义的。

1 / 2 3 / 4 5 6 7 / 8 9 10 11 12 13 14 15 ...

如上图,n=15n=15 时的线段制就是这样的。CQ王发现,听到低语的访问顺序等于 n=3n=3 时的情况数与 n=7n=7 时代数意义的和。因此,他想让你帮忙计算出,当 n=2h−1n=2^h - 1 时,听到低语的 <d, l, r> 访问顺序一共有几种。

解析

解题思路

这个问题是关于计算在线段树中,所有可能的访问顺序中听到低语的顺序数量。根据题面的描述,线段树的访问顺序是一种递归的、分治的遍历方式。每个节点都有一个 <d, l, r> 的访问顺序,首先访问左子节点,然后访问右子节点。当 l = r 时,即为叶子节点。

CQ王发现,听到低语的访问顺序数量等于某些特定情况的和。比如,n=3 时的情况数是6,n=7时是20。这些数字似乎与2的幂有关,但具体的递推关系需要我们找到。

通过观察示例,当n是2^h -1时,比如n=1(2^1-1)、3(2^2-1)、7(2^3-1)等,问题变成了计算某些递推关系下的值。对于这些情况,答案可能具有递推的模式。

算法选择理由

首先,当线段树是完全二叉树时(即n=2^h -1),每个节点的访问顺序都会导致不同的低语情况。但当n不完全是完全二叉树时,如何计算这些情况成为了问题的关键。

根据题意,每个非叶子节点在访问其左子树和右子树时,可能由于右子树不完整而有所不同。因此,这个问题可以通过递归地分析每层的节点,并根据左子树和右子树的完成情况来计算可能的情况数。

复杂度分析

本题的关键是找到递推关系,并用动态规划的方法在O(log n)的时间复杂度内计算出结果。因为n可以达到1e18,所以任何O(n)的算法都会不现实。通过递推和矩阵指数等方法,可以在对数时间内得到答案。

具体来说,对于每个层级,我们可以通过一些参数a和b来表示情况的数量。这些参数可以通过递推关系在层级之间传递。最终,通过hierarchical的计算,得到答案。

代码解析

在代码中,首先需要找到树的高度h,使得2^h -1 >=n。然后,通过迭代的方式,根据左子树和右子树是否完整来更新参数a和b。这些参数a和b的物理意义在于,代表了某些情况的数量。最后,结合模逆元等方法计算出最终的结果。

通过观察,对于每个层级,正确的递推关系式是a和b的线性组合,这些组合可以通过代码中的for循环实现。最终,答案是a + b * 2^h % MOD。

来源

AI 生成 · olympiccoder:7b · 提高+/省选- · 线段树