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;
    }