自动搬运

查看原文

来自洛谷，原作者为

	qwqerty 计算机科学教育新生态。

搬运于2025-08-24 23:13:34，当前版本为作者最后更新于2025-04-16 19:36:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其实这是我真正意义上的第一次不看题解作出的绿题，因为我做题前总会把题解先扫一遍看看难不难。

解题思路

先将完整的数统一处理，再处理剩余部分。
比方说 $x=25$：
$0110111001011101111000100$。
为方便处理，直接丢掉第一位。再通过位数进行分割。
$\color{red}1\color{blue}1011\color{green}100101110111\color{purple}1000\color{IAKIOI}100$。
分析一下具体的分割过程：

• 割下 $1$ 位数，共有 $2^{1-1}=1$ 个数，每个数有 $1$ 位，一共 $1\times2^{1-1}=1$ 位。还剩 $24-1=23$ 位。
• 割下 $2$ 位数，共有 $2^{2-1}=2$ 个数，每个数有 $2$ 位，一共 $2\times2^{2-1}=4$ 位。还剩 $23-4=19$ 位。
• 割下 $3$ 位数，共有 $2^{3-1}=4$ 个数，每个数有 $3$ 位，一共 $3\times2^{3-1}=12$ 位。还剩 $19-12=7$ 位。
• 割下 $4$ 位数，由于剩下的数小于 $4\times2^{4-1}=32$ 位，所以无法完全分割。只能割下 $\lfloor\frac{7}{4}\rfloor=1$ 个数，还剩 $7\bmod 4=3$ 位。

这一部分的代码如下：

x--;
int i;
for (i = 0; ; i++) {
    if (x < (i + 1) * (1ll << i)) break;
    x -= (i + 1) * (1ll << i);
    res += (1ll << i);
}
res += x / (i + 1);
x %= (i + 1);

所以一共分割出了 $1+2+4+1=8$ 个数。
我们先处理这 $8$ 个数，再将剩下的 $3$ 个数单独处理。

现在的任务是求 $\operatorname{popcount}$ 的前缀和。
部分内容借鉴自该博客，如侵删。
如果我们把二进制下的 $0$ 至 $15$ 的数全部列出来，找一下规律：

$$\color{blue}0000000011111111\\ \color{green}0000111100001111\\ \color{purple}0011001100110011\\ \color{red}0101010101010101 $$

分开观察一下每一行，可以发现每一行 $0$ 的个数和 $1$ 的个数都相等！
这是因为如果 $n$ 的二进制下第 $k$ 位数是 $1$ 的话，那么有 $\dfrac{n\bmod2^k}{2^{k-1}}\ge1$，也就是说，$n\bmod2^k\ge2^{k-1}$。可以发现，它正好是占一半的。
所以 $\sum\limits_{i=0}^{2^k-1}\operatorname{popcount}(i)=\dfrac{k\times2^k}{2}=k\times2^{k-1}$。
那么对于一个任意的正整数 $n$，如何计算 $\sum\limits_{i=0}^{n}\operatorname{popcount}(i)$ 呢。考虑拆位计算贡献的方式，下面以 $n=22=(10110)_2$ 为例：

• 最高位为 $1$，统计 $(00000)_2$ 至 $(01111)_2$。共对答案产生了 $4\times2^{4-1}=32$ 的贡献。
• 第三高位为 $1$，统计 $(10000)_2$ 至 $(10011)_2$，共对答案产生了 $1\times2^2+2\times2^{2-1}=8$ 的贡献。
• 第四高位为 $1$，统计 $(10100)_2$ 至 $(10101)_2$，共对答案产生了 $2\times2^1+1\times2^{1-1}=5$ 的贡献。

最后还要统计 $\operatorname{popcount}(n)$，所以答案为 $32+8+5+3=48$。
为方便处理，可以直接将 $n$ 增加 $1$ 在进行计算，最后就不用统计 $\operatorname{popcount}(n)$ 了。
这个部分的代码如下：

int getsum(int x) {
	int res = 0, cnt = 0;
	x++;
	while (x) {
	    if(x & 1) res += (cnt * (1ll << (cnt - 1))) + (1ll << cnt) * popcount(x >> 1);
	    x >>= 1;
	    cnt++;
	}
	return res;
}

现在我们已经处理完了完整部分，接下来我们处理剩余部分。
还是分析我们的事例，最后剩下 $3$ 位。可以发现，这个数就是下一个数的前三位。
我们如何计算 $n$ 的前 $k$ 位？首先我们计算 $n$ 的二进制位数，也就是 $\lfloor\log_2n\rfloor$。我们可以将后 $\lfloor\log_2n\rfloor-k+1$ 位直接删去。这样留下来的就是前 $k$ 位了。最后我们对它求一遍 $\operatorname{popcount}$ 即可。

于是我们就做完了这道题。
本篇题解共有 $3703$ 字符（包含这句话）。

AC 代码

别问我这是什么语言。

#include <bits/stdc++.h>
#define int long long/*
'''
*/
using namespace std;
int x, res;
int popcount(int x) {
	int res = 0;
	while (x) {
		res += x & 1;
		x >>= 1;
	}
	return res;
}
int getsum(int x) {
	int res = 0, cnt = 0;
	x++;
	while (x) {
	    if(x & 1) res += (cnt * (1ll << (cnt - 1))) + (1ll << cnt) * popcount(x >> 1);
	    x >>= 1;
	    cnt++;
	}
	return res;
}
signed main() {
	cin >> x; x--;
	int i;
	for (i = 0; ; i++) {
		if (x < (i + 1) * (1ll << i)) break;
		x -= (i + 1) * (1ll << i);
		res += (1ll << i);
	}
	res += x / (i + 1);
	x %= (i + 1);
	cout << getsum(res) + popcount(res + 1 >> (int)log2l(res + 1) - x + 1);
    return 0;
}
/*
'''
def popcount(x):
    res = 0;
    while x:
        res += x & 1;
        x >>= 1;
    return res;
def getsum(x):
    res = 0;cnt = 0;
    x += 1;
    while x:
        if x & 1:
            if cnt >= 1:res += cnt * (1 << (cnt - 1)) + (1 << cnt) * popcount(x >> 1);
            else:res += (1 << cnt) * popcount(x >> 1);
        x >>= 1;
        cnt += 1;
    return res;
x = int(input())
x -= 1;
res = 0;i = 0;
while True:
    if x < (i + 1) * (1 << i):break
    x -= (i + 1) * (1 << i);
    res += (1 << i);
    i += 1;
res += x // (i + 1);
x %= (i + 1);
ans = getsum(res) + popcount((res + 1) >> ((res + 1).bit_length() - x));
print(ans);
# */