← 返回题目列表

Codeforces · 2211/F

F. 学习二分查找

中文机器翻译题面 查看原题

您进入了第一个数据结构课程,您正在学习二分搜索。你听到教授大喊大叫为什么二分搜索在 $$$O(\log{n})$$$ 中有效。但您想看看是否可以找到更好的界限。

给定 已排序 大小为 $$$n$$$ 的数组 $$$a$$$ 和整数 $$$k$$$,将 $$$f(a, k, l, r)$$$ 定义为以下代码的结果:

function f(a, k, l, r):
if a does not contain k:
return 0
mid = floor((l+r) / 2)
if a[mid]==k:
return 1
else if a[mid]<k:
return 1+f(a, k, mid+1, r)
else:
return 1+f(a, k, l, mid-1)

给你两个整数 $$$n$$$ 和 $$$m$$$。定义一个数组 $$$a$$$ 好,如果:

  • $$$|a|=n$$$ ($$$a$$$ 中有 $$$n$$$ 元素)。
  • $$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq m$$$ (该数组是非递减的,下面以 $$$1$$$ 为界,上面以 $$$m$$$ 为界)。
您有兴趣在所有好的数组 $$$a$$$ 上查找 $$$f(a,1,1,n)+f(a,2,1,n)+\ldots+f(a,m,1,n)$$$ 的总和。由于这个答案可能很大,因此输出对 $$$676\,767\,677$$$ 取模的答案。请注意,$$$676\,767\,677$$$ 是质数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n,m \leq 10^6$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$,所有测试用例的$$$m$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,在新行上输出请求的总和模 $$$676\,767\,677$$$。

示例

输入
复制

7
3 3
3 4
3 5
4 3
4 5
999967 99967
15 876543

输出
复制

26
60
115
50
315
93903683
322710644

注意

在第一个测试用例中,一个好的数组 $$$a$$$ 是 $$$[2,2,3]$$$。这里,$$$f(a,1,1,n)=0$$$(因为$$$1$$$不存在于$$$a$$$中),$$$f(a,2,1,n)=1$$$,$$$f(a,3,1,n)=2$$$。所以这个好阵的贡献就是$$$0+1+2=3$$$。