CF2211F Learning Binary Search

你踏入了你的第一门数据结构课程，正在学习二分查找。你听教授在讲为什么二分查找的时间复杂度是 $O(\log{n})$，但你想看看能否找到一个更好的界限。 给定一个大小为 $n$ 的有序数组 $a$ 和一个整数 $k$，定义 $f(a, k, l, r)$ 为以下代码的结果： ``` function f(a, k, l, r): if a 不包含 k: return 0 mid = floor((l+r) / 2) if a[mid]==k: return 1 else if a[mid]

每组测试包含多组测试数据。第一行为测试用例数 $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$ 取模。

在第一个测试用例中，其中一个 good 数组 $a$ 是 $[2,2,3]$。此时，$f(a,1,1,n)=0$（因为 $1$ 不在 $a$ 中），$f(a,2,1,n)=1$，$f(a,3,1,n)=2$。因此，这个 good 数组的贡献是 $0+1+2=3$。 由 ChatGPT 5 翻译