Вова на даче

Давайте решим другую задачу — научимся вычислять функцию $$$f(x)$$$, равную количеству чисел от 1 до $$$x - 1$$$, в битовой записи которых без лидирующих нулей ровно $$$k$$$ нулевых битов. Тогда ответ на исходную задачу — это $$$f(R + 1) - f(L)$$$.

Приступим к вычислению $$$f(x)$$$. Сначала рассмотрим все числа, битовая запись которых короче битовой записи $$$x$$$. Все они меньше $$$x$$$, следовательно, количество чисел длиной $$$len$$$ с $$$k$$$ нулями равно $$${len - 1} \choose k$$$ (так как первый бит обязан быть 1) (число сочетаний из $$$len-1$$$ по $$$k$$$).

Теперь рассмотрим числа такой же длины. Переберём первый слева бит, в котором $$$x$$$ и наше потенциальное число различаются. Такие позиции соответствуют единичным битам в $$$x$$$, кроме самой старшей единицы, так как числа меньшей длины мы уже рассмотрели. Пусть битовая длина $$$x$$$ равна $$$len$$$, мы рассмотрели $$$t$$$ позиций префикса и стоим в позиции $$$t + 1$$$, а также уже поставили $$$p$$$ нулей, тогда на суффиксе длиной $$$len - t - 1$$$ требуется расставить $$$k - p - 1$$$ ноль. Это можно сделать $$${len - t - 1} \choose {k - p - 1}$$$ способами.

Таким образом, требуется предподсчитать все цешки для $$$1, 2, \ldots, n$$$, где $$$n = \log_2 R$$$. Это можно легко сделать за квадратичное от $$$n$$$ время, воспользовавшись формулой $$${n \choose k} = {{n - 1} \choose {k - 1}} + {{n - 1} \choose k}$$$.

Итоговое время работы — $$$\mathcal{O}(\log^2 R)$$$.