CF431D Random Task(CF431D Random Task)

题面:

CF431D Random Task

题意:

给定两个数 \(m\) 和 \(k\) ,要求输出一个 \(ans\) ,满足在 $[ ans + 1 , 2 ans] $ 这个区间中恰有 \(m\) 个数的二进制表示中恰有 \(k\) 个 1 (输出的 \(ans\) 为任一满足题意的即可)。

解法:

这题的第一步也是最重要的一步,在于挖掘题目性质。

性质一

我们用 \(cnt_i\) 表示在 \([i + 1 , 2 i]\) 这个区间内二进制表示中恰有 \(k\) 个 1 的数的个数 。

那么这个 \(cnt_i\) 一定随 \(i\) 的增大而 单调不减 。

证明:

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

可以看出两个区间中 \([i+2,2i]\) 这一段是重合的 。

前者可表示为 \(\{i+1\} \cup [i+2,2i]\) 。
后者可表示为 \(\{2i+1 , 2i + 2\} \cup [i + 2 , 2i]\) 。

而 \(2i+2 = (i + 1) << 1\) ,它们两者包含 1 的个数相同。所以我们可以知道 \(cnt_{i+1}\) 比 \(cnt_i\) 对其大小贡献多的部分在于 \(2i+1\) , 其他部分完全相同,所以 \(cnt_i\) 单调不减 。

自此,我们可以知道这道题的答案具有可二分性。

性质二:

如果我们用 \(f_i\) 表示在 \([1,i]\) 这个区间内二进制表示中恰有 \(k\) 个 1 的数的个数,那么 \(cnt_i\) 即为 \(f_{2i} – f_i\) 。

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

这里我们就需要一些组合数学的知识了。

首先我们需要把一个数字十进制转二进制。

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

然后对这个二进制数进行 \(f_i\) 的计算 。

举个例子:\(i_{10} = 183\) , \(k = 3\) 时 , \(i_2 = 10110111\) 。

我们把 \([1,10110111]\) 按位从高到低拆成若干个区间:

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

在第一个区间中,可以理解成 7 个数中选 3 个的组合数个数 。第二个区间中,已经有一个 1 被确定,那么其组合数为 5 个数中选 2 个的组合数个数 ……

以此类推,设 \(w\) 为一个区间右端点最低的 1 处于的位置,\(h\) 为区间左端点 1 的个数,那么该区间符合条件数的个数为 \(C_{w – 1}^{k – h}\) 。然后 \([1,i]\) 的答案其实就是各区间的答案相加。

代码实现极其简单而又清新:

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 ++;
}

综上:这题只需要先预处理 \(C_1^1\) ~ \(C_{64}^{64}\) ,然后二分答案判断 \(mid\) 的 \(f_{2mid} – f_{mid}\) 是否等于 \(m\) 就行啦。

时间复杂度:

预处理是 \(O(64^2)\) 的 ,二分答案 + 计算 \(f_i\) 是 \(O(\log^2 n)\) 的。

所以总复杂度为 \(O(\log^2 n)\) 。

Code

————————

Question surface:

CF431D Random Task

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