题目描述

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

同时，另给你一个整数 k。

如果整数 x 可以通过最多 k 次下述操作约简到 1，则将整数 x 称为 k-可约简 整数：

• 将 x 替换为其二进制表示中的置位数（即值为 1 的位）。

例如，数字 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。

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

输出： 6

解释：

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

输入： s = "1", k = 3

输出： 0

解释：

小于 n = 1 的正整数不存在，因此答案为 0。

限制

• 1 <= s.length <= 800
• s 中没有前导零。
• s 仅由字符 '0' 和 '1' 组成。
• 1 <= k <= 5

算法

(思维题，数位统计，组合数学) $O(n^2)$

1. 暴力预处理 $1$ 到 $800$ 的每个数字变为 $1$ 的操作次数。
2. 找到每个操作次数小于 $k$ 的数字 $t$，统计有多少个初始的数字，其二进制 $1$ 的个数恰好等于 $t$。
3. 预处理组合数。
4. 开始数位统计，即从高位到低位，如果当前位为 $1$，则可以假设当前位为 $0$，然后通过组合数计算低位中 $1$ 填充的方案数。

时间复杂度

• 预处理的时间复杂度为 $O(n^2)$。
• 单次数位统计的时间复杂度为 $O(n)$，共有 $O(n)$ 种可能的数字。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储预处理的操作次数和组合数。

C++ 代码

const int N = 800;
const int mod = 1000000007;

int num[N + 1];
int c[N + 1][N + 1];

auto init = []{
    for (int i = 1; i <= N; i++) {
        int x = i, t = 0;

        while (x > 1) {
            ++t;
            x = __builtin_popcount(x);
        }

        num[i] = t;
    }

    c[0][0] = 1;
    for (int i = 1; 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;
    }

    return 0;
}();

class Solution {
private:
    int n;

    int calc(const string &s, int t) {
        int res = 0, seen = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == '0')
                continue;

            res = (res + c[n - i - 1][t - seen]) % mod;
            ++seen;

            if (seen > t)
                break;
        }

        return res;
    }

public:
    int countKReducibleNumbers(string s, int k) {
        n = s.size();

        int ans = 0;

        for (int i = 1; i <= N; i++)
            if (num[i] < k)
                ans = (ans + calc(s, i)) % mod;

        return ans;
    }
};