题目定义了一种操作：将一个数变为这个数二进制下的1的个数。询问有多少个不大于n的数，进行了恰好k次操作后等于1。
数据范围（1<n<21000),观察可知，任意一个大于1000的数进行一次操作后都会变成小于等于1000的数，因此可以枚举1000以内的数变为1的操作个数，当某个数x的操作数为m-1时，统计长度小于等于n的位数下所有满足1的个数为x的数的数量，易知1的位置摆放为组合，所以需要预处理组合数
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int mod=1000000007; char s[1314]; ll C[1010][1010]; ll l; int a[1314]; int num[1314]; ll total=0; int wei(ll x) { int cnt=0; while(x) { cnt+=(x&1); x>>=1; } return cnt; } void dfs(int dep,int now,int flag)//d几位now几个1 { if(now>l)return; if(now==0){ total=(total+1)%mod; return; } if(dep==0)return; if(flag==0)//放0则后面若干个1排列组合 { total=(total+C[dep][now])%mod; } else { if(a[dep]==0) { dfs(dep-1,now,flag); } if(a[dep]==1) { dfs(dep-1,now-1,flag); dfs(dep-1,now,0); } } } int main(){ ll m; cin>>s+1; l=strlen(s+1); cin>>m; if(m==0) { cout<<1; return 0; } if(m==1) { cout<<l-1; return 0; } for(int i=0;i<=l;i++) { C[i][0]=1; } for(int i=1;i<=l;i++) { for(int j=1;j<=i;j++) { C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; // cout<<C[i][j]<<" "; } //cout<<endl; } for(int i=1;i<=l;i++) { a[l-i+1]=s[i]-‘0‘; } /*for(int i=l;i>=1;i--) { cout<<a[i]; } cout<<endl;*/ num[1]=0; for(int i=2;i<=1000;i++) { int w=wei(i); //cout<<w<<endl; num[i]=num[w]+1; if(num[i]==m-1) { dfs(l,i,1); } } cout<<total; return 0; }