Output a single integer — the number of special numbers not greater than n, modulo 109 + 7.

链接

一、题意

        对一个数v，记一种操作R(v) { v = ( v的二进制表示中，1的个数)  }，该操作可以将v变为v的二进制表示中1的个数，如12 = (1100)b，所以12经过一次操作后结果为2。现在给定一个的二进制表示的数n，问在[1,n]中有多少个数经过k次R操作结果刚好为1。

二、思路

        由输入范围可知上界n最多为1000位二进制数，其中1的个数ones<=1000，经过一次变化后结果不会超过1000。可以先通过递推关系对前1000的数求解，求得dp[i]为i到达1所需的变换次数。设v为一个满足题意的值，记v的二进制表示中1的个数为m，则由题意可知dp[m] = k-1。所以可以枚举1~1000内的所有dp[m] = k-1的数，再通过类似数位DP的方法求有m个1的且不大于n的数有多少个。

        solve(sum)函数求解1的个数为sum时原数的可能情况，从最高位开始枚举每一位的可能值。若上界中该位为1，则可填入0或1，填入0时，后面剩余的位置可以随意填入sum个1，情况数由组合数求得，填入1时，后面剩余的位置可以填入sum-1个1。若上界中该位为0，则只能填入0，然后后面的位置填入sum个1。因为当sum=ones时，solve函数会遗漏n自身的情况，所以代码中加了特判，可以手推样例1观察到为什么。

        最后求解时应注意k=0和k=1的情况。k=0时只有数字1是满足情况的。k=1时，k-1=0，所以1会被solve函数算入答案，最后应该特判减去。

三、代码

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long LL;
const int MAXN = 1100;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int INF = 2e9;
const double EPS = 1e-6;
const double PI = 3.14159265358979;
const int dir_4r[] = { -1, 1, 0, 0 };
const int dir_4c[] = { 0, 0, -1, 1 };
const int dir_8r[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dir_8c[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

int len, ans, k, ones;
char input[MAXN];
int dp[MAXN];
int C[MAXN][MAXN];//C(n,m)

int foo(int val) {
	int sum = 0;
	while (val) {
		int digit = val & 0x01;
		sum += digit;
		val >>= 1;
	}
	return sum;
}

void init() {
	for (int i = 0; i < MAXN; ++i)
		C[i][0] = 1;
	for (int i = 1; i < MAXN; ++i)
		for (int j = 1; j < MAXN; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD7;

	dp[1] = 0;
	for (int i = 2; i < MAXN; ++i)
		dp[i] = dp[foo(i)] + 1;
}

void solve(int sum) {
	for (int i = 0; i < len; ++i) {
		if (input[i] == '1' && sum >= 0) {
			ans += C[len - 1 - i][sum];//当前位填0，后面填入sum个1
			ans %= MOD7;
			sum--;//当前位填1
		}
	}
}

int main() {
	scanf("%s", input);
	scanf("%d", &k);
	len = strlen(input);
	init();

	ans = 0;
	if (k == 0)
		ans = 1;
	else {
		ones = 0;
		for (int i = 0; i < len; ++i)
			ones += (input[i] - '0');

		for (int i = 1; i < MAXN; ++i)
			if (dp[i] == k - 1) {
				solve(i);
				if (i == ones)//当填入1的个数和输入1的个数相等时，应将自己考虑进来
					ans = (ans + 1) % MOD7;
			}
		if (k == 1)
			ans = (ans - 1 + MOD7) % MOD7;
	}
	cout << ans << endl;

	//system("pause");
	return 0;
}