CodeForces - 914C Travelling Salesman and Special Numbers

题意：给出一个二进制数a，每次操作将当前数变成其二进制下1的个数，若干次操作后可以将其变为1.给定k，求不大于a的数中，经过k次操作能变成1的数的数量。

解：观察一下这个操作，可以求出1000以内的数变成1的次数，设其为cnt[i]。对于1000以外的数，可以在一次操作后变到1000以内。枚举i，如果cnt[i]+1=k，那就说明二进制下拥有i个1的数，能在k次操作后变成1.接下来问题变成了有多少小于等于a的，二进制下有i个1的数。进行一些数位dp。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxx 100005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 1000000007
char a[1005];
int len;
ll dp[1005][1005][2]={0};
int cnt[1005]={0};
int k;
ll dfs(ll pos,ll kk,ll limit){
    if(pos==len+1) {
        return kk==0;
    }
    if(kk<0)
        return 0;
    if(!limit&&dp[pos][kk][limit]!=-1)
        return dp[pos][kk][limit];
    ll ret=0;
    ll res=limit?a[pos]-'0':1;
    for(int i=0;i<=res;i++){
        ret=(ret+dfs(pos+1,kk-i,limit&&(i==a[pos]-'0')))%mod;
    }
    return !limit?dp[pos][kk][limit]=ret:ret;
}
signed main() {
//    int T;
//    scanf("%d",&T);
//    while(T--) {;
//
//    }
    memset(dp,-1,sizeof dp);
    scanf("%s",a+1);
    scanf("%d",&k);
    if(k==0){
        printf("1\n");
        return 0;
    }
    len=strlen(a+1);
    ll ans=0;
    for(int i=1;i<=1000;i++){
        if(i>1) {
            bitset<1005> b = i;
            cnt[i] = cnt[b.count()] + 1;
        }
        if(cnt[i]==k-1) {
            ans = (ans + dfs(1, i, 1)) % mod;
        }
    }
    if(k==1) ans--;
    printf("%lld\n",ans);
    return 0;
}