### 解法：

\(cnt_i\) 中包含的数为 \([i + 1 , 2 i]\) 。
\(cnt_{i+1}\) 中包含的数为 \([i+2,2i+2]\) 。

### 重难点：如何算出 \(f_i\) :

``````void change(int x){
if(x == 0) return ;
change(x >> 1);
s += ((x & 1) + '0');
}
``````

\([0,10000000) , [10000000 , 10100000) …… [10110110,10110111) , \{10110111\}\) 。

``````for(int i=0;i<siz;i++){
if(s[i] == '0') continue;
if(k - numone <= 0) break;
sum += zhs[siz - i - 1][k - numone];
numone ++;
}
``````

Code

————————

### Meaning:

Given two numbers \ (m \) and \ (K \), it is required to output one \ (ANS \) to satisfy that there are exactly \ (K \) 1 in the binary representation of exactly \ (m \) numbers in the interval \$[ans + 1,2 ans] \$(the output \ (ANS \) can be any one that satisfies the meaning of the question).

### Solution:

The first and most important step of this problem is to explore the nature of the problem.

< strong > nature I < / strong >:

We use \ (cnt_i \) to represent the number of exactly \ (K \) 1s in the binary representation in the interval \ ([i + 1,2, I] \).

Then this \ (cnt_i \) must be monotonous with the increase of \ (I \).

prove:

\The number contained in (cnt_i \) is \ ([i + 1, 2, I] \).
\The number contained in (cnt_{I + 1} \) is \ ([i + 2,2i + 2] \).

It can be seen that \ ([i + 2,2i] \) of the two intervals coincides.

The former can be expressed as \ (\ {I + 1 \} \ cup [i + 2,2i] \).
The latter can be expressed as \ (\ {2I + 1, 2I + 2 \} \ cup [i + 2, 2I] \).

And \ (2I + 2 = (I + 1) & lt; & lt; 1 \), they both contain the same number of 1. Therefore, we can know that the part where \ (cnt_{I + 1} \) contributes more to its size than \ (cnt_i \) lies in \ (2I + 1 \), and the other parts are exactly the same, so \ (cnt_i \) is monotonous.

Since then, we can know that the answer to this question is dichotomous.

< strong > property 2: < / strong >

If we use \ (f_i \) to represent the number of exactly \ (K \) 1s in the binary representation in the interval \ ([1, I] \), then \ (cnt_i \) is \ (f_{2i} – f_i \).

### Key and difficult points: how to calculate \ (f_i \):

Here we need some knowledge of combinatorial mathematics.

First, we need to convert a number from decimal to binary.

``````void change(int x){
if(x == 0) return ;
change(x >> 1);
s += ((x & 1) + '0');
}
``````

Then, the binary number is calculated by \ (f_i \).

For example, \ (i_2 = 10110111 \) when \ (i_ {10} = 183 \), \ (k = 3 \).

We divide \ ([110111] \) into several intervals from high to low:

\([0,10000000) , [10000000 , 10100000) …… [10110110,10110111) , \{10110111\}\) 。

In the first interval, it can be understood as a combination of 3 out of 7 numbers. In the second interval, if a 1 has been determined, its combination number is the combination number of 2 out of 5

By analogy, let \ (w \) be the position where the lowest 1 at the right end of an interval is located, and \ (H \) be the number of 1 at the left end of the interval, then the number of qualified numbers of the interval is \ (C {W – 1} ^{K – H} \). Then the answer to \ ([1, I] \) is actually the sum of the answers in each interval.

The code implementation is extremely simple and fresh:

``````for(int i=0;i<siz;i++){
if(s[i] == '0') continue;
if(k - numone <= 0) break;
sum += zhs[siz - i - 1][k - numone];
numone ++;
}
``````

To sum up: this question only needs to preprocess \ (c_1 ^ 1 \) ~ \ (c_ {64} ^ {64} \), and then judge whether the \ (f_ {2mid} – f_ {mid} \) of \ (mid \) is equal to \ (m \).

### Time complexity:

Preprocessing is \ (O (64 ^ 2) \), and binary answer + calculation \ (f_i \) is \ (O (\ log ^ 2 n) \).

So the total complexity is \ (O (\ log ^ 2 n) \).

Code