3352. 统计小于 N 的 K 可约简数字

Hard

题目描述

给你一个表示数字 n 的二进制字符串 s。

同时给你一个整数 k。

如果一个整数 x 通过执行以下操作最多 k 次可以约简为 1，那么它被称为 k-可约简的：

将 x 替换为其二进制表示中设置位的个数。

例如，6 的二进制表示是 “110”。执行一次操作后约简为 2（因为 “110” 有两个设置位）。对 2（二进制 “10”）再次执行操作约简为 1（因为 “10” 有一个设置位）。

返回小于 n 的 k-可约简正整数的个数。

由于答案可能很大，请返回结果模 10^9 + 7。

示例 1：

输入：s = "111", k = 1
输出：3
解释：n = 7。小于 7 的 1-可约简整数有 1、2 和 4。

示例 2：

输入：s = "1000", k = 2
输出：6
解释：n = 8。小于 8 的 2-可约简整数有 1、2、3、4、5 和 6。

示例 3：

输入：s = "1", k = 3
输出：0
解释：没有小于 n = 1 的正整数，所以答案是 0。

约束：

1 <= s.length <= 800
s 没有前导零
s 只包含字符 ‘0’ 和 ‘1’
1 <= k <= 5

解题思路

这道题需要结合数位动态规划和预处理来解决。

核心思路：

预处理约简步数：首先预计算每个可能的设置位数量（1到800）需要多少步约简为1。由于每次约简都是将数字替换为其二进制中1的个数，我们可以递归计算。
数位DP：使用数位动态规划来统计小于给定二进制数的所有数字中，有多少个数字的设置位数量经过最多k步可以约简为1。
状态定义：
- dp[pos][cnt][tight][started] 表示从第pos位开始，已经选择了cnt个1，是否受到上界限制，是否已经开始选择非零位的方案数
组合数学优化：为了处理大数情况，我们需要预计算组合数，用于快速计算在剩余位置中选择特定数量1的方案数。

算法步骤：

预处理1到800每个数字的约简步数
使用数位DP遍历所有可能的位组合
对于每个有效的设置位数量，检查是否可以在k步内约简为1
累加所有满足条件的方案数

时间复杂度主要由数位DP和组合数预处理决定，整体是可接受的。

代码实现

class Solution {
public:
    const int MOD = 1e9 + 7;
    
    int countKReducibleNumbers(string s, int k) {
        int n = s.length();
        
        // 预处理约简步数
        vector<int> steps(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            steps[i] = steps[__builtin_popcount(i)] + 1;
        }
        
        // 预处理组合数
        vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
        
        long long result = 0;
        
        // 对于每个可能的1的个数
        for (int ones = 1; ones <= n; ones++) {
            if (steps[ones] > k) continue;
            
            // 计算有多少个小于s的数字恰好有ones个1
            long long count = 0;
            int prefix_ones = 0;
            
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') {
                    // 在第i位放0，后面n-1-i位中选ones-prefix_ones个位置放1
                    int remaining_pos = n - 1 - i;
                    int remaining_ones = ones - prefix_ones;
                    
                    if (remaining_ones >= 0 && remaining_ones <= remaining_pos) {
                        count = (count + C[remaining_pos][remaining_ones]) % MOD;
                    }
                    
                    prefix_ones++;
                }
            }
            
            result = (result + count) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def countKReducibleNumbers(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(s)
        
        # 预处理约简步数
        steps = [0] * (n + 1)
        for i in range(2, n + 1):
            steps[i] = steps[bin(i).count('1')] + 1
        
        # 预处理组合数
        C = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            C[i][0] = 1
            for j in range(1, i + 1):
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
        
        result = 0
        
        # 对于每个可能的1的个数
        for ones in range(1, n + 1):
            if steps[ones] > k:
                continue
                
            # 计算有多少个小于s的数字恰好有ones个1
            count = 0
            prefix_ones = 0
            
            for i in range(n):
                if s[i] == '1':
                    # 在第i位放0，后面n-1-i位中选ones-prefix_ones个位置放1
                    remaining_pos = n - 1 - i
                    remaining_ones = ones - prefix_ones
                    
                    if remaining_ones >= 0 and remaining_ones <= remaining_pos:
                        count = (count + C[remaining_pos][remaining_ones]) % MOD
                    
                    prefix_ones += 1
            
            result = (result + count) % MOD
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    public int CountKReducibleNumbers(string s, int k) {
        int n = s.Length;
        
        // 预处理约简步数
        int[] steps = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            steps[i] = steps[CountBits(i)] + 1;
        }
        
        // 预处理组合数
        long[,] C = new long[n + 1, n + 1];
        for (int i = 0; i <= n; i++) {
            C[i, 0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i, j] = (C[i-1, j-1] + C[i-1, j]) % MOD;
            }
        }
        
        long result = 0;
        
        // 对于每个可能的1的个数
        for (int ones = 1; ones <= n; ones++) {
            if (steps[ones] > k) continue;
            
            // 计算有多少个小于s的数字恰好有ones个1
            long count = 0;
            int prefixOnes = 0;
            
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') {
                    // 在第i位放0，后面n-1-i位中选ones-prefixOnes个位置放1
                    int remainingPos = n - 1 - i;
                    int remainingOnes = ones - prefixOnes;
                    
                    if (remainingOnes >= 0 && remainingOnes <= remainingPos) {
                        count = (count + C[remainingPos, remainingOnes]) % MOD;
                    }
                    
                    prefixOnes++;
                }
            }
            
            result = (result + count) % MOD;
        }
        
        return (int)result;
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

var countKReducibleNumbers = function(s, k) {
    const MOD = 1e9 + 7;
    const n = s.length;
    
    // Precompute which numbers of set bits are k-reducible
    const isKReducible = new Array(n + 1).fill(false);
    for (let i = 1; i <= n; i++) {
        let steps = 0;
        let curr = i;
        while (curr > 1 && steps < k) {
            curr = curr.toString(2).split('1').length - 1;
            steps++;
        }
        isKReducible[i] = (curr === 1 && steps <= k);
    }
    
    // Precompute combinations
    const C = Array(n + 1).fill(null).map(() => Array(n + 1).fill(0));
    for (let i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (let j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    
    // Count numbers less than s with each possible number of set bits
    const dp = Array(n + 1).fill(null).map(() => Array(n + 1).fill(0));
    dp[0][0] = 1;
    
    let tight = true;
    for (let pos = 0; pos < n; pos++) {
        const bit = parseInt(s[pos]);
        
        for (let bits = 0; bits <= pos; bits++) {
            if (dp[pos][bits] === 0) continue;
            
            // Place 0
            dp[pos + 1][bits] = (dp[pos + 1][bits] + dp[pos][bits]) % MOD;
            
            // Place 1 if allowed
            if (bit === 1) {
                dp[pos + 1][bits + 1] = (dp[pos + 1][bits + 1] + dp[pos][bits]) % MOD;
            }
        }
    }
    
    // Count all numbers with fewer digits
    let result = 0;
    for (let len = 1; len < n; len++) {
        for (let bits = 1; bits <= len; bits++) {
            if (isKReducible[bits]) {
                result = (result + C[len - 1][bits - 1]) % MOD;
            }
        }
    }
    
    // Count numbers with same number of digits but less than s
    for (let bits = 1; bits < n; bits++) {
        if (isKReducible[bits]) {
            result = (result + dp[n][bits]) % MOD;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
预处理约简步数	O(n log n)	O(n)
预处理组合数	O(n²)	O(n²)
主循环计算	O(n²)	O(1)
总体	O(n²)	O(n²)

其中 n 是字符串 s 的长度（最大800），所以实际复杂度是可接受的。空间复杂度主要用于存储组合数表。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析