P7143 [THUPC 2021 初赛] 线段树

线段树是小 L 最喜欢的数据结构，它能高效地解决许多实际问题。 给定一个正整数 $n$，小 L 构建出一棵下标属于整数区间 $[1, n]$ 的线段树： - 初始线段树只有一个结点 $[1, n]$。 - 对于结点 $[L, R]$，若 $L < R$，则令 $mid = \left[ \frac{L + R}{2} \right]$（$[x]$ 表示不超过 $x$ 的最大整数），小 L 对这个结点建出两个子结点 $[L, mid]$、$[mid + 1, R]$。 小 L 定义了一个函数 $cover(a, b)$（$1 \le a \le b \le n$），表示用若干个线段树结点不重不漏地覆盖区间 $[a, b]$，则使用的线段树结点个数的最小值。 小 L 尝试使用这棵线段树解决某个复杂问题，并想要粗略地评估这棵线段树的性能。 具体来说，区间 $[1, n]$ 有 $\frac{n (n + 1)}{2}$ 个不同的子区间，如果小 L 从这 $\frac{n (n + 1)}{2}$ 个子区间中等概率随机地选取一个，将其记为 $[A, B]$，则小 L 认为 $cover(A, B)$ 的期望值可用于评估此线段树的性能。 小 L 想请你帮他计算出 $cover(A, B)$ 的期望值与 $\frac{n (n + 1)}{2}$ 的乘积对 $1, 000, 000, 007$ 取模的结果，可以发现此结果一定是一个整数。

无

无

**【样例解释 #1】** $cover(1, 1) = 1$，$cover(2, 2) = 1$，$cover(3, 3) = 1$，$cover(1, 2) = 1$，$cover(2, 3) = 2$，$cover(1, 3) = 1$，故 $cover(A, B)$ 的期望 $= \frac{1 + 1 + 1 + 1 + 2 + 1}{6} = \frac{7}{6}$。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。 题解等资源可在 查看。