LeetCode 3621. 位计数深度为 K 的整数数目 I

题目描述

给定两个整数 `n` 和 `k`。对任意正整数 `x`，定义序列：
- `p₀ = x`
- `pᵢ₊₁ = popcount(pᵢ)`（二进制中 1 的个数）

序列最终会到达 1。`x` 的 popcount-depth 定义为使得 `p_d = 1` 的最小非负整数 `d`。

求 `[1, n]` 中 popcount-depth 恰好等于 `k` 的整数个数。

约束： `1 ≤ n ≤ 10¹⁵`，`0 ≤ k ≤ 5`

---

解题思路

关键观察：
- `D(1) = 0`（1 本身就是终点）
- `x > 1` 时，`D(x) = 1 + D(popcount(x))`
- 因此 `D(x) = k` 等价于 `D(popcount(x)) = k - 1`

算法步骤：
1. 预处理深度：对 `1 ~ 60` 的所有数预计算 popcount-depth（`n ≤ 10¹⁵` 的二进制最多 50 位）
2. 确定目标 popcount：找出所有满足 `D(c) = k - 1` 的 `c`
3. 数位 DP：统计 `[1, n]` 中二进制恰好有 `c` 个 1 的数的个数
4. 边界处理：`k = 0` 时只有 `x = 1`；`k = 1` 时需排除 `x = 1`（因为 `D(1) = 0`）

时间复杂度： `O(log² n)`

空间复杂度： `O(log² n)`

---

Java 实现

```java
import java.util.*;

class Solution {

// 计算一个数的 popcount（二进制1的个数）
private int popcount(int x) {
int cnt = 0;
while (x > 0) {
cnt += (x & 1);
x >>= 1;
}
return cnt;
}

// 计算 popcount-depth
private int getDepth(int x, int[] memo) {
if (x == 1) return 0;
if (memo[x] != -1) return memo[x];
memo[x] = 1 + getDepth(popcount(x), memo);
return memo[x];
}

// 数位DP：统计 [0, n] 中二进制恰好有 targetOnes 个1的数的个数
// s 是 n 的二进制字符串
private long dfs(int pos, int ones, boolean tight, String s, int targetOnes, Long[][] memo) {
if (ones > targetOnes) return 0; // 1的个数已超，剪枝
if (pos == s.length()) {
return ones == targetOnes ? 1 : 0;
}

int tightFlag = tight ? 1 : 0;
if (!tight && memo[pos][ones] != null) {
return memo[pos][ones];
}

int limit = tight ? (s.charAt(pos) - '0') : 1;
long res = 0;

for (int d = 0; d <= limit; d++) {
res += dfs(pos + 1, ones + d, tight && (d == limit), s, targetOnes, memo);
}

if (!tight) {
memo[pos][ones] = res;
}
return res;
}

public long popcountDepth(long n, int k) {
// k = 0：只有 1 的深度为 0
if (k == 0) {
return n >= 1 ? 1 : 0;
}

// 预处理 1~60 的深度（n <= 1e15 < 2^50，popcount 最大为 50）
int[] depthMemo = new int[65];
Arrays.fill(depthMemo, -1);
depthMemo[1] = 0;

// 找出所有 popcount 值 c，使得 D(c) = k - 1
List<Integer> targetPopcounts = new ArrayList<>();
for (int i = 1; i <= 60; i++) {
if (getDepth(i, depthMemo) == k - 1) {
targetPopcounts.add(i);
}
}

if (targetPopcounts.isEmpty()) {
return 0;
}

// 将 n 转为二进制字符串
String s = Long.toBinaryString(n);
long ans = 0;

for (int c : targetPopcounts) {
// 记忆化数组：memo[pos][ones]，仅非 tight 状态有效
Long[][] memo = new Long[s.length() + 1][c + 1];
ans += dfs(0, 0, true, s, c, memo);
}

// k = 1 的特殊处理：popcount = 1 的数包括 1, 2, 4, 8...
// 但 D(1) = 0，不应计入 k=1，所以减去 1
if (k == 1) {
ans -= 1;
}

return ans;
}
}
```

---

代码要点

要点 说明
深度预处理 `getDepth` 用记忆化递归计算，利用 `D(x) = 1 + D(popcount(x))`
数位 DP 按二进制位从高到低枚举，`tight` 控制是否受 `n` 限制
非 tight 记忆化 只有 `tight = false` 时结果可复用，用 `Long[][]` 存储
k = 1 修正 `popcount = 1` 包含 `x = 1`，但其深度为 0，需减去
返回值类型 用 `long`，因为 `n` 最大时答案可能很大

如需其他语言版本（Python/C++/Go）或更详细的数位 DP 推导，可以继续问我。