题解 | #小q的数列#

题目链接

HIGH12 小q的数列

题目描述

小q定义了一个数列 f(x)：

f(0) = 0
f(1) = 1
f(x) = f(floor(x/2)) + f(x mod 2)，对于 x >= 2

给定 T 次询问，每次询问一个非负整数 x，请你输出 f(x) 的值，以及满足 f(k) = f(x) 的最小非负整数 k。

解题思路

这个问题的核心在于理解递推公式 f(x) = f(floor(x/2)) + f(x mod 2) 的真正含义。

1. 分析递推公式

让我们观察一下这个公式中的操作：

floor(x/2)：这在整数运算中等价于 x >> 1，即二进制右移一位，丢弃最低位。
x mod 2：这等价于 x & 1，即取二进制的最低位。

这个递推关系实际上是将一个数 x 的 f 值，分解为它的“主体部分”（右移后的数）的 f 值与“最低位”的 f 值之和。

我们可以将这个过程展开： f(x) = f(x >> 1) + f(x & 1) f(x >> 1) = f(x >> 2) + f((x >> 1) & 1) ... 这个过程会一直持续到 x 变为 0。 f(x) = f(0) + f(x的第0位) + f(x的第1位) + ...

由于 f(0)=0 且 f(1)=1，上述展开式的结果就是 x 在二进制表示下所有位的值的总和。这恰好就是 x 的二进制表示中 1 的个数（也称为 population count 或 popcount）。

所以，第一个答案 f(x) 就是 x 的二进制表示中 1 的个数。

2. 求解最小的 k

现在问题变成了：给定一个数 x，计算出其二进制中 1 的个数，我们称之为 c。然后，找到一个最小的非负整数 k，使得 k 的二进制表示中也有 c 个 1。

如何构造一个具有 c 个 1 且值最小的数？为了使一个数的值最小，我们应该让它的高位尽可能为 0，低位尽可能为 1。因此，具有 c 个 1 的最小的数，其二进制表示必然是 c 个连续的 1，前面全是 0。例如：

如果 c=1，最小的数是 ...001 (二进制)，即 1。
如果 c=2，最小的数是 ...011 (二进制)，即 3。
如果 c=3，最小的数是 ...111 (二进制)，即 7。

这个由 c 个 1 构成的数，其数学表达式为 2^c - 1。在编程中，这可以更高效地通过位运算 (1 << c) - 1 来实现。

所以，第二个答案 k 就是 (1 << f(x)) - 1。

3. 最终算法

对于每个输入的 x：
计算 c = popcount(x)（x 的二进制中 1 的个数）。
计算 k = (1 << c) - 1。
输出 c 和 k。

代码

cpp
java
python

#include <iostream>

#if defined(__GNUC__) || defined(__clang__)
#define popcount __builtin_popcountll
#else
int popcount(long long n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}
#endif

using namespace std;

void solve() {
    long long x;
    cin >> x;
    int c = popcount(x);
    long long k = (1LL << c) - 1;
    cout << c << " " << k << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long x = sc.nextLong();
            int c = Long.bitCount(x);
            long k = (1L << c) - 1;
            System.out.println(c + " " + k);
        }
    }
}

import sys
input=sys.stdin.readline

# 读取测试用例的数量
t = int(input())

for _ in range(t):
    x = int(input())
    
    # 计算二进制中 1 的个数
    c = bin(x).count('1')
    
    # 计算最小的 k
    k = (1 << c) - 1
    
    print(c, k)

算法及复杂度

算法：位运算、数论
时间复杂度： $\mathcal{O}(T)$ 。对于 T 次查询，每次查询的核心是计算 popcount，这通常是一个非常快速的硬件指令，可以视为 $\mathcal{O}(1)$ 。
空间复杂度： $\mathcal{O}(1)$ 。