题目链接：点击打开链接
题目大意：给出一个二进制数m，这个二进制数中1的个数为n，将m转变为n记做操作一次，知道将m转变为1结束，操作的总次数记为m的步长。
现在给出一个数n，和步长k，求小于等于n的数中有多少个数的步长为k。因为个数过多，需要模109 + 7.
思路：
2的1000次方是一个很大的数，但是只要经过一次操作之后，就会变成一个小于等于1000的数，所以我们可以先预处理出来所有小于等于1000的数需要多少次操作转化为1。
现在的n需要经过x次操作变成1，那么n经过一次操作得到的数就需要经过x-1次操作变成1
根据预处理的结果，我们可以找到哪些数经过x-1次操作变成1
如果找到了数r,那么就需要在小于等于n的范围内，排列r个1
要保证小于等于n的话，可以从最高位开始进行这样的操作，i代表现在的位数,nones表示已经出现了多少个1
当该位为1的时候，我们考虑：
如果将该为的1变为0，则在后面的n.size()-i-1个位置中找j-nones个位置 即C(n.size()-i-1,j-nones)
如果该为1不变，则nones++,继续进行下一位操作
如果该位为0，
则只有直接nones++,继续进行下一位操作。
注意点：有三个特例需要注意，如果k==0，则直接输出1
如果k==1，计算的时候不要把1也记为步长为1
因为考虑的时候没有考虑的本身，所以最后要特别检验下自身是否满足
#include <bits/stdc++.h>using namespace std;#define MOD 1000000007int dp[1004];long long ncr[1004][1004];int ones(int n){int cnt = 0;while(n){if(n%2 == 1){cnt++;}n /= 2;}return cnt;}void calcncr()//预处理组合数{for(int i = 0; i <= 1000; i++){ncr[i][0] = 1;}for(int i = 1; i <= 1000; i++){for(int j = 1; j <= 1000; j++){ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%MOD;}}}int main(){string n;int k;calcncr();dp[1] = 0;for(int i = 2; i <= 1000; i++)//预处理小于等于1000的数到1的步数{dp[i] = dp[ones(i)] + 1;}cin >> n >> k;if(k == 0){cout << "1\n";return 0;}long long nones = 0, ans = 0;for(int i = 0; i < n.size(); i++){if(n[i] == '0'){continue;}for(int j = max(nones, 1LL); j < 1000; j++){if(dp[j] == k-1){ans = (ans + ncr[n.size()-i-1][j-nones])%MOD;if(i == 0 && k == 1)//这里主要去掉1本身这种特殊的情况 1到1的步数是0不是1{ans = (ans+MOD-1)%MOD;}}}nones++;}int cnt = 0;for(int i = 0; i < n.size(); i++){if(n[i] == '1'){cnt++;}}if(dp[cnt] == k-1)//加上自己本身{ans = (ans + 1)%MOD;}cout << ans << endl;return 0;}
