题意是定义一种运算
对于数字x把它变成x的二进制表示下1的个数
比如7(10)即111(2) 会变成 3
给你一个二进制表示的数字n和一个k，问1到n的范围内有多少个可以通过k次这样的运算变成1的数字
n最大为2的1000次方
所以一次运算之后得到的结果肯定在1000以内
枚举1000以内经过k-1步能得到1的所有数字
再对这些数字做数位dp即可
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e3;
const long long MOD = 1e9 + 7;
long long C[MAXN + 10][MAXN + 10];
string n;
vector<int> v;
int maxpos;
long long ans = 0;
/*
@input pos 当前处理的位置
@input limit 是否取到最大值
@input rem 剩余的要填充的1的个数
*/
void DigDfs(int pos, bool limit, int rem) {
if (maxpos - pos + 1 < rem) {
return;
}
if (rem == 0) {
ans = (ans + 1) % MOD;
return;
}
if (pos > maxpos) {
return;
}
if (!limit) {
ans = (ans + C[maxpos - pos + 1][rem]) % MOD;
return;
}
if (n[pos - 1] == '1') {
DigDfs(pos + 1, limit, rem - 1);
DigDfs(pos + 1, false, rem);
} else {
/* if (!limit) DigDfs(pos + 1, limit, rem - 1); */
DigDfs(pos + 1, limit, rem);
}
}
int main()
{
int k;
cin >> n >> k;
if (k == 0) {
cout << 1;
return 0;
}
// 1000以内的组合数表
for (int i = 1; i <= MAXN; i++) {
C[i][0] = C[i][i] = 1;
}
for (int i = 2; i <= MAXN; i++) {
for (int j = 1; j < i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
for (int i = 1; i <= MAXN; i++) {
int tmp = i, step = 0;
while (tmp != 1) {
tmp = __builtin_popcount(tmp), step++; // stl函数, 返回一个数字二进制下1的个数, 时间复杂度O(1)
}
if (step == k - 1) {
v.push_back(i);
}
}
maxpos = n.size();
for (int i : v) {
DigDfs(1, true, i);
}
if (k == 1) {
ans = (ans - 1 + MOD) % MOD;
}
cout << ans;
return 0;
}
