题解 | #小q的数列#

小q的数列

https://www.nowcoder.com/practice/76796815518f4db5b800775581cda1e4

所有C语言题解中，排名第一的代码

理解题目：

这个题目围绕一个递推数列 $f$ 的性质展开，分为两个任务：

计算数列的第 $n$ 项 $f[n]$ 的值。
- 数列的递推公式为：
  - f[0] = 0
  - f[1] = 1
  - f[i] = f[i / 2] + f[i % 2]，其中 i >= 2。
- 这个公式的本质：
  - f[i] 的值是由 i 在二进制表示中 1 的个数决定的。i/2 等价于右移一位，i%2 等价于最低位是否是 1。
  - 所以，f[i] 等于 i 的二进制表示中 1 的个数。
- 例子：
```
f[0] = 0   (二进制 0，1 的个数为 0)
f[1] = 1   (二进制 1，1 的个数为 1)
f[2] = 1   (二进制 10，1 的个数为 1)
f[3] = 2   (二进制 11，1 的个数为 2)
f[4] = 1   (二进制 100，1 的个数为 1)
```

找出 $f[n]$ 首次出现在数列中的最小位置 $n'$ 。

如果 f[n] = k，需要输出 f[i] = k 时的最小 i。

这个值 $n'$ 实际上对应于二进制中恰好包含 k 个 1 的最小数。比如：

f[3] = 2，首次出现值为 2 的位置是 3（11 二进制全是 1）。
f[6] = 2，值为 2 的最小位置仍然是 3。
f[15] = 4，值为 4 的最小位置是 15（二进制全是 4 个 1）。

常规解题代码

#include <stdio.h>

int main() {
    long long t; // 操作次数
    scanf("%lld", &t);

    while (t--) {
        long long n;
        scanf("%lld", &n);

        // 计算二进制中1的个数
        long long sum = 0, temp = n;
        while (temp) {
            sum += temp & 1;
            temp >>= 1;
        }

        // 计算二进制全为1的最小数
        long long num = (1LL << sum) - 1;

        // 输出结果
        printf("%lld %lld\n", sum, num);
    }

    return 0;
}

优化解决方案：

1. 计算 f[n] 的值

利用二进制中 1 的个数快速计算 f[n]：
```
sum = __builtin_popcountll(n);
```
这是一种高效的位运算，用于统计二进制中 1 的个数。

2. 计算 n' 的值

n' 的定义是满足 f[n'] = f[n] 的最小值，其中 n' 二进制全为 1，且 1 的个数等于 f[n]。
构造这个数的方法：
- 如果 f[n] = k，则 n' = 2^k - 1，因为 2^k - 1 的二进制是 k 个 1 组成。

优化思路：

对于大范围的 n 和 t，直接逐项计算 f[i] 不可行，因此需要 O(1) 的方法：
1. f[n] 用位运算直接得到。
2. n' 用公式 (1LL << f[n]) - 1 快速构造。

最终代码实现：

#include <stdio.h>

int main() {
    int t; // 测试用例数量
    scanf("%d", &t);

    while (t--) {
        long long n;
        scanf("%lld", &n);

        // 计算 f[n]，即 n 的二进制中 1 的个数
        int sum = __builtin_popcountll(n);

        // 计算 n'，即 sum 个 1 的二进制数
        long long n_prime = (1LL << sum) - 1;

        // 输出结果
        printf("%d %lld\n", sum, n_prime);
    }

    return 0;
}

代码解读：

__builtin_popcountll(n)：
- 这是 GCC 提供的内建函数，用于快速统计 long long 类型变量中二进制位 1 的个数。
- 复杂度接近 O(1)。
(1LL << sum) - 1：
- 生成二进制中全为 1 的数字，1LL << sum 等价于 2^sum。
循环处理每个测试用例：
- 对每个输入的 n，计算 f[n] 和 n' 并输出。

复杂度分析：

时间复杂度：O(t)，每个 n 的计算只需 O(1)。
空间复杂度：O(1)。

详细介绍生成二进制全为 1 的表达式

表达式 (1LL << sum) - 1 是一种典型的位操作，主要用于生成一个特定长度的位掩码或用于其他类似的场景。详细解释：

表达式分解

1LL:
- 这里的 1LL 表示一个长整型（long long）的整数值 1。
- 加 LL 的目的是为了确保它是一个 64 位的整数，防止位操作时溢出或引起未定义行为（尤其是在 C/C++ 中）。
<< sum:
- << 是位左移运算符。
- 将 1LL 的二进制位向左移动 sum 位。
- 例如：
  - 若 sum = 3，则 1LL << 3 结果是 1000（二进制），即 8（十进制）。
  - 若 sum = 5，则 1LL << 5 结果是 100000（二进制），即 32（十进制）。
- 1:
- 最后将结果减去 1。
- 减去 1 的效果是将最高位的 1 减去，并将剩下的低位全部置为 1。
- 例如：
  - 若 1LL << 3 = 1000，则 (1LL << 3) - 1 = 0111（二进制），即 7（十进制）。
  - 若 1LL << 5 = 100000，则 (1LL << 5) - 1 = 011111（二进制），即 31（十进制）。