CF1982E.Number of k-good subarrays

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

设 $bit(x)$ 表示非负整数 $x$ 的二进制表示中 $1$ 的个数。

一个数组的子数组被称为 $k$ -好子数组，如果它只包含二进制表示中 $1$ 的个数不超过 $k$ 的数。也就是说，数组 $a$ 的子数组 $(l, r)$ 是 $k$ -好子数组，当且仅当对于任意 $l \le i \le r$ ，都有 $bit(a_i) \le k$ 。

给定一个长度为 $n$ 的数组 $a$ ，其元素为从 $0$ 开始的连续非负整数，即 $a_i = i$ ，其中 $0 \le i \le n - 1$ （下标从 $0$ 开始）。你需要计算该数组中 $k$ -好子数组的数量。

由于答案可能非常大，请输出对 $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

说明/提示

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

我们将所有数字写成二进制：

$a = [\color{green}{000}, \color{green}{001}, \color{green}{010}, \color{red}{011}, \color{green}{100}, \color{red}{101}]$

可以看到，数字 $3$ 和 $5$ 的二进制中 $1$ 的个数为 $2 \ge (k = 1)$ ，所以答案应包括所有不包含 $3$ 或 $5$ 的子数组，即（下标从 $0$ 开始）： $(0, 0)$ ， $(0, 1)$ ， $(0, 2)$ ， $(1, 1)$ ， $(1, 2)$ ， $(2, 2)$ ， $(4, 4)$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页