2025-06-05：统计小于 N 的 K 可约简整数用go语言，给定一个二进制

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

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 取模后返回。

s 中没有前导零。

s 仅由字符 '0' 和 '1' 组成。

输入： s = "1000", k = 2。

输出： 6。

解释：

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

题目来自力扣3352。

1. 预处理每个数的操作次数：• 对于每个可能的数 i（1 • 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 • 例如，n = 8，k = 2：• i = 1：f[1] = 0 • i = 2：f[2] = 1 • i = 3：f[3] = 2 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] • 最后对结果取模。• 时间复杂度：• 预处理 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)。package mainimport ( "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 { return1 } return } if !isLimit { p := &memo[i][left1] if *p >= 0 { return *p } deferfunc { *p = res } } up := 1 if isLimit { up = int(s[i] - '0') } for d := 0; d