2025-06-05：统计小于 N 的 K 可约简整数。用go语言，给定一个二进制字符串 s，它表示一个整数 n 的二进制形式。

同时给定一个整数 k。

定义操作：对一个整数 x，令 x 变为其二进制表示中 “1” 的个数（置位数）。

如果一个整数 x 能够通过最多 k 次这样的操作，最终变成 1，则称这个整数是 k-可约简的。

举个例子：数字 6 的二进制是 “110”，它的置位数是 2，经过一次操作，6 变为 2；数字 2 的二进制是 “10”，置位数是 1，经过第二次操作变成 1。所以，6 是 2-可约简的。

问题是：计算小于 n 的正整数中，有多少个是 k-可约简的。

由于结果可能非常大，需要对 1000000007 取模后返回。

1 <= s.length <= 800。

s 中没有前导零。

s 仅由字符 ‘0’ 和 ‘1’ 组成。

输入： s = “1000”, k = 2。

输出： 6。

解释：

n = 8。小于 8 的 2-可约简整数有 1，2，3，4，5 和 6。

题目来自力扣3352。

解题步骤

1. 预处理每个数的操作次数：

   • 对于每个可能的数 i（1 <= i < n），计算其变为 1 所需的操作次数 f[i]。
   • f[i] 的定义是：f[i] = f[bits.OnesCount(i)] + 1，初始时 f[1] = 0（因为 1 已经是目标，不需要操作）。
   • 例如：
     • f[1] = 0。
     • f[2] = f[bits.OnesCount(2)] + 1 = f[1] + 1 = 1。
     • f[3] = f[bits.OnesCount(3)] + 1 = f[2] + 1 = 2。
     • f[4] = f[1] + 1 = 1。
     • f[5] = f[2] + 1 = 2。
     • f[6] = f[2] + 1 = 2。
     • f[7] = f[3] + 1 = 3。

2. 统计满足条件的数：

   • 对于每个 i（1 <= i < n），如果 f[i] <= k，则我们需要统计所有小于 n 且二进制表示中“1”的个数为 i 的数的个数。
   • 例如，n = 8，k = 2：
     • i = 1：f[1] = 0 <= 2，统计小于 8 且“1”的个数为 1 的数（“1”, “10”, “100” → 1, 2, 4）。
     • i = 2：f[2] = 1 <= 2，统计小于 8 且“1”的个数为 2 的数（“11”, “101”, “110” → 3, 5, 6）。
     • i = 3：f[3] = 2 <= 2，统计小于 8 且“1”的个数为 3 的数（“111” → 7，但 f[7] = 3 > 2，不满足）。
     • 其他 i 的 f[i] 更大或超出范围。
   • 实际满足的是 i = 1（3 个数）和 i = 2（3 个数），共 6 个。

3. 动态规划统计“1”的个数为 i 的数：

   • 使用数位动态规划（Digit DP）的方法统计小于 n 的二进制数中“1”的个数为 i 的数的个数。
   • dfs(i, left1, isLimit)：
     • i：当前处理到第 i 位（从 0 开始）。
     • left1：还需要放置的“1”的个数。
     • isLimit：是否受到 n 的限制（即前几位是否已经和 n 的前几位一致）。
   • 递归过程中，逐位决定放置 0 或 1，同时更新 left1 和 isLimit。
   • 使用记忆化缓存（memo）避免重复计算。

4. 组合结果：

   • 对于所有 i 满足 f[i] <= k，累加“1”的个数为 i 的数的个数。
   • 最后对结果取模。

时间复杂度和空间复杂度

• 时间复杂度：
  • 预处理 f 数组：O(n)，其中 n 是 s 表示的数的最大值（即 2^800，但实际上 f 的计算最多到 800，因为 bits.OnesCount 最多为 800）。
  • 数位 DP：对于每个 i（最多 len(s) 次），进行一次 dfs，dfs 的状态数是 O(len(s)^2)（因为 i 和 left1 的范围都是 len(s)），每次 dfs 的时间是 O(1)（记忆化后）。
  • 总时间复杂度：O(len(s)^3)，即 O(800^3)。
• 空间复杂度：
  • f 数组：O(len(s))。
  • memo 数组：O(len(s)^2)。
  • 总空间复杂度：O(len(s)^2)。

总结

• 预处理 f 数组计算每个数的操作次数。
• 使用数位动态规划统计满足“1”的个数为 i 的数的个数。
• 累加所有 f[i] <= k 的数的个数。
• 时间：O(len(s)^3)，空间：O(len(s)^2)。

Go完整代码如下：

package main

import (
	"fmt"
	"math/bits"
)

func countKReducibleNumbers(s string, k int) (ans int) {
	const mod = 1_000_000_007
	n := len(s)
	memo := make([][]int, n)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var dfs func(int, int, bool) int
	dfs = func(i, left1 int, isLimit bool) (res int) {
		if i == n {
			if !isLimit && left1 == 0 {
				return 1
			}
			return
		}
		if !isLimit {
			p := &memo[i][left1]
			if *p >= 0 {
				return *p
			}
			defer func() { *p = res }()
		}
		up := 1
		if isLimit {
			up = int(s[i] - '0')
		}
		for d := 0; d <= min(up, left1); d++ {
			res += dfs(i+1, left1-d, isLimit && d == up)
		}
		return res % mod
	}

	f := make([]int, n)
	for i := 1; i < n; i++ {
		f[i] = f[bits.OnesCount(uint(i))] + 1
		if f[i] <= k {
			// 计算有多少个二进制数恰好有 i 个 1
			ans += dfs(0, i, true)
		}
	}
	return ans % mod
}

func main() {
	s := "1000"
	k := 2
	fmt.Println(countKReducibleNumbers(s, k))
}