题意描述
小蓝最近在学习二进制, 他想知道 $1$ 到 $N$ 中有多少个数满足其二进制表示中恰好有 $K$ 个 $1$。你能帮助他吗?
$1$ <= $N$ <= $10^{18}$, $k$ <= $50$.
蓝桥杯 $2021$ 国赛 $B$ 组 $H$ 题($C$ 组 $J$ 题)
数位$dp$
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
const int N = 70;
int len;
int nums[N], f[N][N];
int dfs(int pos, int cnt, int k, int limit) {
if (!pos) return cnt == k;
if (!limit && ~f[pos][cnt]) return f[pos][cnt];
int up = limit ? nums[pos] : 1, res = 0;
for (int i = 0; i <= up; i ++ )
if (i != 1 || cnt != k)
res += dfs(pos - 1, cnt + (i == 1), k, limit && i == up);
return limit ? res : f[pos][cnt] = res;
}
int calc(i64 x, int k) {
memset(f, -1, sizeof f);
while (x) nums[ ++ len] = x & 1, x >>= 1;
return dfs(len, 0, k, 1);
}
int main() {
i64 n; int k;
cin >> n >> k;
cout << calc(n, k);
return 0;
}