题意

给出一个二进制数\(n\)，每次操作可以将一个整数\(x\)简化为\(x\)的二进制表示中\(1\)的个数，如果一个数简化为\(1\)所需的最小次数为\(k\)，将这个数叫做特殊的数，

问从\(1\)到\(n\)一共有多少个特殊的数，答案对\(1e9+7\)取模。

分析

\(n\)最大为\(2^{1000}\)，二进制表示中最多有\(1000\)个\(1\)，所以\(n\)以内的数经过一次简化后将变为\(1000\)以内的数，我们可以暴力打表\(1000\)以内的数简化为\(1\)所需的最少次数，将求得的次数加\(1\)即为二进制中\(1\)的个数为\(x\)的数简化为\(1\)所需的最少次数为\(cnt[x]\)，\(1\)这个数要特判，没特判wa了3发。。。

然后分情况讨论：

• \(k=0\),答案为\(1\),只有\(1\)是经过\(0\)次简化到\(1\)的数

• \(k=1\),答案为\(n\)的位数\(-1\)，\(n\)除了第\(1\)位，其余每一位为\(1\)都是特殊的数

• \(k>1\),直接数位dp，设\(dp[i][j]\)为枚举到第\(i\)位二进制中\(1\)的个数为\(j\)，\(cnt[x]==k\)的数为特殊的数

Code

    #include<bits/stdc++.h>

    #define fi first

    #define se second

    using namespace std;

    typedef long long ll;

    const double PI=acos(-1.0);

    const double eps=1e-6;

    const int inf=1e9;

    const int mod=1e9+7;

    const int maxn=1e5+10;

    char s[1010];

    int a[1010],cnt[1010],k;

    ll dp[1010][1010];

    ll dfs(int pos,int x,int limit){

        if(pos==0) return cnt[x]==k;

        if(!limit&&~dp[pos][x]) return dp[pos][x];

        int up=limit?a[pos]:1;

        ll ret=0;

        for(int i=0;i<=up;i++){

            ret+=dfs(pos-1,x+(i==1),limit&&i==a[pos]);

            ret%=mod;

        }

        if(!limit) dp[pos][x]=ret;

        return ret;

    }

    int solve(int x){

    	if(x==1) return 0;

    	int ret=0;

    	int cnt=0;

    	while(x){

    		if(x&1) cnt++;

    		x>>=1;

    	}

    	ret+=solve(cnt)+1;

    	return ret;

    }

    void init(int n){

    	for(int i=1;i<=n;i++){

    		cnt[i]=solve(i)+1;

    	}

    }

    int main(){

        ios::sync_with_stdio(false);

        init(1005);

        memset(dp,-1,sizeof(dp));

        cin>>s+1>>k;

        int n=strlen(s+1);

        for(int i=1;i<=n;i++){

            a[n-i+1]=s[i]-'0';

        }

    	if(k==1){

    		cout<<n-1;

    	}else if(k==0) cout<<1;

        else cout<<dfs(n,0,1);

        return 0;

    }