题目描述

难度分:$1800$

输入二进制数$s$，范围$1 \leq s \lt 2^{1000}$，不含前导零。

然后输入$k(0 \leq k \leq 1000)$。

定义$f(x)$为$x$的二进制表示中的$1$的个数。

定义$f^{*}(x)$为使$f(f(…f(x)))=1$的最少嵌套（迭代）次数。也就是不断地把$x$更新为$f(x)$，最少要更新多少次，才能使$x$变成$1$。

例如$f^{*}(6)=2$，因为$f(f(6))=f(2)=1$。

输出$[1,s]$中有多少个数$x$满足$f^{*}(x) = k$。答案模$10^9+7$。

输入样例$1$

110
2

输出样例$1$

3

输入样例$2$

111111011
2

输出样例$2$

169

算法

数位DP

这个题比较容易看出来是数位DP，因为即使$s$可以达到$2^{1000}$，它经过一步$f$也会变为$1000$以内。所以我们先做一个预处理，暴力计算$x \in [1,1000]$中所有$x$变到$1$的$f*$值，存入到$f[x]$数组中，然后就可以数位DP了。数位DP过程用灵佬的模板即可，非常套路。

状态定义

通过递归函数来定义状态，递归函数需要$4$个参数：(1) 当前遍历到第$i$位；(2) 当前构造的数有$x$个$1$；(3) 前面填的数字是否跟上限$s$一样$limit$；(4) 之前是否填过数字$isnum$。

状态转移

对齐上限$s$的位数，从最高位（从左往右第$0$位）开始往最低位（第$n-1$位）填数。

$base$ $case$：已经遍历完了最低位，且$isnum$为$1$，表示前面填过数字，此时就刚好形成了一种有效的方案，只要$f[x]+1=k$就说明当前构造出来一个$s$以内的$n$位二进制数，可以在$k$步操作后变成$1$。加$1$是因为存在一步从大数变到$1000$以内的先导操作，$f[x]$只是$1000$以内的数变到$1$的操作次数。

一般情况：$index \lt n$，说明当前位需要填数，分为以下几种情况：

1. $isnum$为$0$表示前面的位没有填过数，当前位仍然可以不填数，反正如果最后一个数都没填，这个分支返回的方案数就是$0$。
2. 当前位填数，如果前面的位和上限一模一样，那么当前位$i$能填的最大数$ub$就是$s[i]$，否则就是$1$。而我们是不允许有前导零的，所以如果前面填过数，就可以从$0$开始，否则应该从$1$开始。因此得到当前位能填的数字范围$d \in [1-isnum,ub]$，一个个尝试。

最后需要注意一种情况，如果$k=1$，那说明$1$多算了一次，需要从最终答案中减去。因为$1$经过一次操作后是保持不变的，不能按照上述思路的$f[1]+1=k$来统计。

复杂度分析

设$s$的长度为$n$。

时间复杂度

相较于DP过程，预处理的时间复杂度可以忽略不计，因此只要分析数位DP的时间复杂度即可。状态数量是$4n^2$，即$O(n^2)$规模，单次转移的时间复杂度为$O(1)$，因此整个算法的时间复杂度为$O(n^2)$。

空间复杂度

空间消耗主要在于DP数组，即状态数量的空间级别。因此，额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1001, MOD = 1e9 + 7;
string s;
int n, k, f[N], dp[N][N][2][2];

int dfs(int i, int x, int limit, int isnum) {
    if(i == n) {
        return isnum? (f[x] + 1 == k? 1: 0) : 0;
    }
    int &v = dp[i][x][limit][isnum];
    if(v != -1) return v;
    int digit = s[i] - '0';
    int cnt = isnum? 0: dfs(i + 1, x, 0, isnum);
    int ub = limit == 1? digit: 1;
    for(int d = 1 - isnum; d <= ub; d++) {
        cnt = (cnt + dfs(i + 1, x + d, (limit && d == digit)? 1: 0, 1)) % MOD;
    }
    return v = cnt;
}

int main() {
    cin >> s >> k;
    if(k == 0) {
        cout << "1" << endl;
        return 0;
    }
    n = s.size();
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            dp[i][j][0][0] = dp[i][j][0][1] = dp[i][j][1][0] = dp[i][j][1][1] = -1;
        }
    }
    for(int i = 1; i <= 1000; i++) {
        int x = i, op = 0;
        while(x > 1) {
            x = __builtin_popcount(x);
            op++;
        }
        f[i] = op;
    }
    cout << (dfs(0, 0, 1, 0) - (k == 1? 1: 0)) << '\n';
    return 0;
}