Обозначим за $$$bit(x)$$$ количество единичных бит в двоичной записи неотрицательного целого числа $$$x$$$.
Назовем подотрезок массива $$$k$$$-хорошим, если он состоит только из чисел, в которых не более $$$k$$$ единичных бит, то есть подотрезок $$$(l, r)$$$ массива $$$a$$$ хороший, если для любого $$$i$$$, такого, что $$$l \le i \le r$$$ выполняется $$$bit(a_{i}) \le k$$$.
У вас есть массив $$$a$$$ длины $$$n$$$, состоящий из последовательных неотрицательных целых чисел начиная с $$$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$$$.
106 116 21 13 131 314 11337 5100000 20795569939321040850 56576460752303423268 59
7 35 1 6 155 8 7323 49965 741136395 66679884
Для первого набора входных данных $$$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$$$ имеют $$$2 \ge (k = 1)$$$ единичных бита в двоичной записи, поэтому в ответ должны войти все подотрезки, в которых нет ни $$$3$$$, ни $$$5$$$, это отрезки (в $$$0$$$-индексации): ($$$0$$$, $$$0$$$), ($$$0$$$, $$$1$$$), ($$$0$$$, $$$2$$$), ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$2$$$, $$$2$$$), ($$$4$$$, $$$4$$$).
Название |
---|