题解：P12191 [蓝桥杯 2025 省研究生组] 01 串
qwqerty
·
·
题解
其实这是我真正意义上的第一次不看题解作出的绿题，因为我做题前总会把题解先扫一遍看看难不难。
解题思路
先将完整的数统一处理，再处理剩余部分。
比方说 x=25：
为方便处理，直接丢掉第一位。再通过位数进行分割。
$\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$ 位。
这一部分的代码如下：
```cpp
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}$ 的前缀和。
部分内容借鉴自[该博客](https://kaiserwilheim.github.io/OI/fast-popcnt-sum/)，如侵删。
如果我们把二进制下的 $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)$ 了。
这个部分的代码如下：
```cpp
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 代码
别问我这是什么语言。
```cpp
#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);
# */
```