← 返回题目列表

Codeforces · 1982/E

E. k-good 子阵列的数量

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

让 $$$bit(x)$$$ 表示非负整数 $$$x$$$ 的二进制表示形式中 1 的数量。

数组的子数组称为 $$$k$$$-好,如果它仅由二进制表示中不超过 $$$k$$$ 的数字组成,即数组 $$$a$$$ 的子数组 $$$(l, r)$$$ 是好的,如果对于任何 $$$i$$$ 满足 $$$l \le i \le r$$$ 条件$$$bit(a_{i}) \le k$$$ 满足。

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,由从 $$$0$$$ 开始的连续非负整数组成,即 $$$a_{i} = i$$$ 表示 $$$0 \le i \le n - 1$$$(基于 $$$0$$$ 的索引)。您需要计算该数组中 $$$k$$$-good 子数组的数量。

由于答案可能非常大,因此输出它对 $$$10^{9} + 7$$$ 取模。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。以下几行描述了测试用例。

每个测试用例的单行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^{18}, 1 \le k \le 60$$$)。

输出

对于每个测试用例,输出一个整数 - $$$k$$$-好子数组的数量以 $$$10^{9} + 7$$$ 为模。

示例

输入 #1

10
6 1
16 2
1 1
3 1
31 3
14 1
1337 5
100000 20
795569939321040850 56
576460752303423268 59

输出 #1

7
35
1
6
155
8
7323
49965
741136395
66679884

注意

对于第一个测试用例 $$$a = [0, 1, 2, 3, 4, 5]$$$,$$$k = 1$$$。

为了找到答案,我们将所有数字写成二进制表示形式:

$$$$$$a = [\颜色{绿色}{000}、\颜色{绿色}{001}、\颜色{绿色}{010}、\颜色{红色}{011}、\颜色{绿色}{100}、\颜色{红色}{101}]$$$$$$

由此可见,数字 $$$3$$$ 和 $$$5$$$ 在其二进制表示中具有 $$$2 \ge (k = 1)$$$ 个,因此答案应包括所有不包含 $$$3$$$ 或 $$$5$$$ 的子数组,这些子数组是子数组(基于 $$$0$$$ 的索引): ($$$0$$$, $$$0$$$), ($$$0$$$, $$$1$$$), ($$$0$$$, $$$2$$$), ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$2$$$, $$$2$$$), ($$$4$$$, $$$4$$$)。