#1471. 「THUPC 2021 初赛」线段树

「THUPC 2021 初赛」线段树

题目描述

线段树是小 L 最喜欢的数据结构,它能高效地解决许多实际问题。

给定一个正整数 nn,小 L 构建出一棵下标属于整数区间 [1,n][1, n] 的线段树:

  • 初始线段树只有一个结点 [1,n][1, n]
  • 对于结点 [L,R][L, R],若 L<RL < R,则令 mid=[L+R2]mid = \left[ \frac{L + R}{2} \right][x][x] 表示不超过 xx 的最大整数),小 L 对这个结点建出两个子结点 [L,mid][L, mid][mid+1,R][mid + 1, R]

小 L 定义了一个函数 cover(a,b)cover(a, b)1abn1 \le a \le b \le n),表示用若干个线段树结点不重不漏地覆盖区间 [a,b][a, b],则使用的线段树结点个数的最小值。

小 L 尝试使用这棵线段树解决某个复杂问题,并想要粗略地评估这棵线段树的性能。

具体来说,区间 [1,n][1, n]n(n+1)2\frac{n (n + 1)}{2} 个不同的子区间,如果小 L 从这 n(n+1)2\frac{n (n + 1)}{2} 个子区间中等概率随机地选取一个,将其记为 [A,B][A, B],则小 L 认为 cover(A,B)cover(A, B) 的期望值可用于评估此线段树的性能。

小 L 想请你帮他计算出 cover(A,B)cover(A, B) 的期望值与 n(n+1)2\frac{n (n + 1)}{2} 的乘积对 1,000,000,0071, 000, 000, 007 取模的结果,可以发现此结果一定是一个整数。

输入格式

第一行一个正整数 TT1T10001 \le T \le 1000)表示数据组数。
接下来 TT 行,其中第 ii1iT1 \le i \le T)行一个正整数 nn1n10181 \le n \le {10}^{18})表示第 ii 组数据。

输出格式

TT 行,第 ii1iT1 \le i \le T)行一个整数表示第 i 组数据的答案。

样例

1
3

7

cover(1,1)=1cover(1, 1) = 1cover(2,2)=1cover(2, 2) = 1cover(3,3)=1cover(3, 3) = 1cover(1,2)=1cover(1, 2) = 1cover(2,3)=2cover(2, 3) = 2cover(1,3)=1cover(1, 3) = 1,故 cover(A,B)cover(A, B) 的期望 =1+1+1+1+2+16=76= \frac{1 + 1 + 1 + 1 + 2 + 1}{6} = \frac{7}{6}

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。