Codeforces-914C

题意是定义一种运算
对于数字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;
}