[数据结构与算法]蓝桥杯 二进制问题

#include<bits/stdc++.h>

using namespace std;
vector<int> a(70);
long long N, K;
vector<vector<vector<long long>>> dp(70, vector<vector<long long>>(70, vector<long long>(2, -1)));

long long dfs(int pos, long long count, int num, int limit)
{
    if (pos == -1)
    {
        return count == K;
    }
    if (!limit && dp[pos][count][num] != -1)
    {
        return dp[pos][count][num];
    }
    int upper = limit ? a[pos] : 1;
    long long res = 0;
    for (int i = 0; i <= upper; i++)
    {
        res += dfs(pos - 1, count + (i == 1), i, limit && i == upper);
    }
    if (!limit)
    {
        dp[pos][count][num] = res;
    }
    return res;
}

long long solve(long long x)
{
    int pos = 0;
    while (x)
    {
        a[pos++] = x & 1;
        x >>= 1;
    }
    return dfs(pos - 1, 0, 0, 1);
}

int main()
{
    cin >> N >> K;
    cout << solve(N);
    return 0;
}