题解：01 串

源题目地址：https://www.luogu.com.cn/problem/P12191

题目分析

题目要求计算由数字0,1,2,…的二进制表示拼接而成的无限01串的前x位中1的个数。例如前7位是"0110111"，包含5个1。

解题思路

1. 理解字符串构造方式：字符串由数字的二进制表示按顺序拼接而成。数字0对应"0"，1对应"1"，2对应"10"，3对应"11"，依此类推。

2. 分段处理：我们可以将数字按二进制位数分组处理：
   • 1位数字：0,1
   • 2位数字：2,3
   • 3位数字：4-7
   • 以此类推

3. 计算每段的贡献：
   • 对于完整的l位数字段，可以快速计算其总1的个数
   • 对于不完整的段，需要单独处理部分数字或部分位

4. 关键公式：
   • F(n)函数计算0到n所有数字的二进制1的总和
   • 对于l位数字段，总1的个数为2^(l-1) + (l-1)*2^(l-2)

代码实现

import java.util.Scanner;

public class Main {
    // 计算 F(n) = sum_{i=0}^{n} popcount(i)
    static long F(long n) {
        if (n == 0)
            return 0;
        // 找到 n 的二进制最高位 p, 使得 2^p <= n
        int p = 63 - Long.numberOfLeadingZeros(n);
        long power = 1L << p; // 2^p
        long rem = n - power;
        // 公式：F(n) = p*2^(p-1) + (n - 2^p + 1) + F(n - 2^p)
        return (long) p * (power >> 1) + (rem + 1) + F(rem);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long ones = 0; // 累计 1 的个数
        long bitsUsed = 0; // 已经统计的位数

        // 先处理数字 0 ("0") —— 长度 1，0 个 1
        if (x > 0) {
            bitsUsed++; // 用去1位
            // 如果 x 仅为1，则答案为 0
            if (bitsUsed == x) {
                System.out.println(0);
                return;
            }
        }

        // 接下来处理 l 位数字（l>=1）
        int l = 1;
        long groupStart = 1; // l位数字的起始值（l=1时仅有1）
        while (true) {
            long countNumbers = 1L << (l - 1); // 数字个数 = 2^(l-1)
            long segmentBits = countNumbers * (long) l; // 这一段总位数
            if (bitsUsed + segmentBits <= x) {
                // 整段都被计入
                // 对于 l位数字，其总 1 数按已知公式为：
                // 对 l = 1，只有数字 1，本身贡献 1；
                // 对 l>=2，总和为: 2^(l-1) + (l-1)*2^(l-2)
                long sumOnesGroup;
                if (l == 1) {
                    sumOnesGroup = 1;
                } else {
                    sumOnesGroup = (1L << (l - 1)) + (l - 1) * (1L << (l - 2));
                }
                ones += sumOnesGroup;
                bitsUsed += segmentBits;
                l++;
                groupStart <<= 1; // 下个分段起点乘以2
            } else {
                // 本分段仅部分数字被用到
                long remain = x - bitsUsed; // 当前分段内剩余的位数
                // 完整的数字个数：
                long fullNumbers = remain / l;
                if (fullNumbers > 0) {
                    // 计算区间 [groupStart, groupStart + fullNumbers - 1] 内 1 的和
                    long a = groupStart;
                    long b = groupStart + fullNumbers - 1;
                    long sumOnesPart = F(b) - F(a - 1); // a>=1，此时 F(a-1)计算正确（F(0)=0）
                    ones += sumOnesPart;
                    bitsUsed += fullNumbers * l;
                }
                // 处理下一个数字的部分位：如果还余下 partial 位
                long partial = remain % l;
                if (partial > 0) {
                    long nextNumber = groupStart + fullNumbers;
                    // 此数字保证有 l 位（二进制字符串的长度为 l）
                    // 取其前 partial 位（从最高位开始），统计其中 1 的数目
                    for (int i = 0; i < partial; i++) {
                        // 取第 i 位：从最高位开始，对应下标 l - i - 1（0 表示最低位）
                        if (((nextNumber >> (l - i - 1)) & 1) == 1) {
                            ones++;
                        }
                    }
                }
                break;
            }
        }
        System.out.println(ones);
    }
}

复杂度分析

• 时间复杂度：O(log²x)，因为F(n)函数是递归实现，每次递归处理n的最高位，而主循环也是按数字的位数递增处理。
• 空间复杂度：O(logx)，递归深度与n的二进制位数成正比。

该算法高效地处理了极大范围的x值（直到10^18），通过分段处理和递归计算避免了暴力枚举的低效问题。