题意:给出一个二进制数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。
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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; }View Code
标签:cnt,二进制,914C,ll,CodeForces,Numbers,ans,1005,define From: https://www.cnblogs.com/capterlliar/p/16858842.html