本文共 1150 字，大约阅读时间需要 3 分钟。

对于数字x，令F[x] = x二进制中1的个数

输入两个数字n（输入为二进制）和k，问有多少个满足①<=n；②刚好进行k次F[]计算后变为1

思路：

显然n<=2^1000但是第一次F[]计算之后一定会变成一个<=1000的数

先预处理1到1000每个数要变几次，然后对于刚好变k-1次的数x就相当于求出有多少个数满足

①<=n；②二进制刚好有x个1

这可以用数位DP或者组合数学解决

大概就是如果当前位是1的话把它变成0后面所有数字都可以01任选了，具体看代码

最后对于每个合法的x算出来的情况数全部加在一起就是答案

不过这样有两个坑，一个是k=0是答案一定为1，第二个是k=1时注意计算出的答案要-1

#include
   
    #include
    
     #define LL long long#define mod 1000000007int a[1005];LL C[1005][1005];char str[1005];int Jud(int x){	int now, sum = 0;	while(x>1)	{		sum++;		now = 0;		while(x)		{			if(x%2==1)				now++;			x /= 2;		}		x = now;	}	return sum;}LL Sech(int x){	LL sum = 0;	int i, n, cnt = 0;	n = strlen(str+1);	for(i=1;i<=n;i++)	{		if(str[i]=='1')		{			if(cnt<=x)				sum = (sum+C[n-i][x-cnt])%mod;			cnt++;		}	}	if(cnt==x)		sum = (sum+1)%mod;	return sum;}int main(void){	LL ans;	int i, j, k;	for(i=1;i<=1000;i++)		a[i] = Jud(i);	C[0][0] = 1;	for(i=1;i<=1000;i++)	{		C[i][0] = 1;		for(j=1;j<=i;j++)			C[i][j] = (C[i-1][j-1]+C[i-1][j])%mod;	}	scanf("%s%d", str+1, &k);	if(k==0)	{		printf("1\n");		return 0;	}	ans = 0;	for(i=1;i<=1000;i++)	{		if(a[i]==k-1)			ans = (ans+Sech(i))%mod;	}	if(k==1)		ans--;	printf("%I64d\n", ans);	return 0;}