Codeforces 914 C 数位DP+暴力打表+思维

题意

给出一个二进制数(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;
    }