【题目来源】
【题目描述】
小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？
【输入格式】
输入一行包含两个整数 N 和 K。
【输出格式】
输出一个整数表示答案。
【输入样例】
7 2
【输出样例】
3
【数据范围】
对于 30% 的评测用例，1≤N≤10^6, 1≤K≤10。
对于 60% 的评测用例，1≤N≤2×10^9, 1≤K≤30。
对于所有评测用例，1≤N≤10^18，1≤K≤50。
【算法分析】
● 本题“暴力法”代码如下所示。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
LL n,k,cnt;int main() {cin>>n>>k;for(LL i=1; i<=n; i++) {LL t=i,sum=0;while(t) {if(t%2!=0) sum++;t/=2;}if(sum==k) cnt++;}cout<<cnt<<endl;return 0;
}/*
in:7 2
out:3
*/
由于暴力法时间复杂度达 O(nlogn)，而本题问题规模达 10^18，故求解只过了 5 个样例，得 50 分，其他 5 个样例 TLE。因此，可以考虑“数位DP”算法求解。
● 整数 10^18 的二进制表示有 60 位。下面给出了求整数 10^18 的二进制位数的代码。
#include <bits/stdc++.h>
using namespace std;long long cnt,x=1e18;
int main() {while(x) {if(x) cnt++;x/=2;}cout<<cnt; //60return 0;
}● 数位DP（Digit Dynamic Programming）是一种用于解决数字数位相关计数问题的动态规划算法。其核心思想是将数字按位拆解，通过递归或递推的方式处理每一位的选择，并利用记忆化搜索来避免重复计算，从而高效统计满足特定条件的数字数量。
● 数位DP通过记录前导零、数位限制等状态，将问题复杂度降低至 O(log n)，能够处理非常大的数字范围（如 10^18）。其实现通常是将统计 [le, ri] 的问题转化为统计 [1, ri] 和 [1, le-1] 的结果相减。
● 数位DP题型的特点：求某个区间 [le, ri] 内，满足某种性质的数的个数。
● 数位DP问题中经常用到的“组合数”公式：C(i, j)=C(i-1, j-1)+C(i-1, j)
● 状态及状态转移方程
（1）状态：f[i][j] 表示从 i 个二进制位中选 j 个位置填 1 的方案数。
（2）状态转移方程：f[i][j]=f[i-1][j-1]+f[i-1][j]
边界：f[i][0]=1（表示从 i 个二进制位中选 0 个位置填 1，只有 1 种方案，即全填 0）。
递推：f[i][j]=f[i-1][j-1]+f[i-1][j]（从 i 个二进制位中选 j 个位置填 1 的方案数，等价于两种情况的和。一是若第 i 位填 1，则有 f[i-1][j-1]， 表示从 i-1 个二进制位中选 j-1 个位置填 1 的方案数。二是若第 i 位填 0，则有 f[i-1][j]， 表示从 i-1 个二进制位中选 j 个位置填 1 的方案数）。
● 执行过程模拟
若以 n=8、k=2 为例，完整模拟这段数位DP核心循环的执行步骤，如下所示。
（一）前置准备（先明确基础数据）
（1）n=8 的二进制：8 → 1000（十进制转二进制：8=2³，所以二进制是 1 后面 3 个 0）。
（2）拆分二进制到 v 数组：代码中是低位到高位存储（不断取余 2、除以 2），所以：
8 % 2 = 0 → v.push_back(0)
4 % 2 = 0 → v.push_back(0)
2 % 2 = 0 → v.push_back(0)
1 % 2 = 1 → v.push_back(1)
最终 v=[0, 0, 0, 1]（v[0]=最低位，v[3]=最高位）。注意：一个二进制数的左端是高位，右端是低位。
（3）v.size()=4，循环从 i=4-1=3 开始（从最高位往最低位遍历）。
（4）预处理的组合数关键值：f[3][2]=3、f[2][2]=1、f[1][2]=0（j>i 时无意义，视为 0）、f[0][2]=0。→ 注意：每一维的下标都是从 0 开始。求解组合数 f[i][j] 的代码如下所示。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=8;
LL f[N][N];void init() {for(LL i=0; i<N; i++) {for(LL j=0; j<=i; j++) {if(j==0) f[i][j]=1;else f[i][j]=f[i-1][j-1]+f[i-1][j];cout<<f[i][j]<<" ";}cout<<endl;}
}int main() {init();return 0;
}/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
*/（5）初始化：cnt=0（结果计数），pre=0（已选 1 的个数），k=2（目标 1 的个数）。
（二）逐行模拟循环执行过程（注意：一个二进制数的左端是高位，右端是低位。）
第一步：i=3（遍历最高位，v[3]=1）
LL x=v[i]; //x=v[3]=1（最高位是1）
if(x==1) { //进入分支if(k-pre>=0 && k-pre<=i) { //k-pre=2-0=2，0≤2≤3 →条件成立cnt+=f[i][k-pre]; //cnt=0+f[3][2]=0+3=3}pre++; //pre=0+1=1（已选1个1）if(pre>k) break; //1>2？不成立，不break
}
if(i==0 && pre==k) cnt++; //i=3≠0 →跳过当前状态：cnt=3，pre=1，i=3 → 下一步 i=2。
通俗解释：最高位选 0，剩余 3 个低位（i=3）需要凑 2 个 1，组合数 f [3][2]=3（对应数字：0011=3、0101=5、0110=6）。
第二步：i=2（遍历第 3 位，v [2]=0）
LL x=v[i]; //x=v[2]=0
if(x==1) { //不成立，跳过分支//无操作
}
if(i==0 && pre==k) cnt++; //i=2≠0 →跳过当前状态：cnt=3，pre=1，i=2 → 下一步 i=1。
通俗解释：当前位是 0，只能选 0，pre 不变，继续遍历下一位。
第三步：i=1（遍历第 2 位，v [1]=0）
LL x=v[i]; //x=v[1]=0
if(x==1) { //不成立，跳过分支//无操作
}
if(i==0 && pre==k) cnt++; //i=1≠0 →跳过当前状态：cnt=3，pre=1，i=1 → 下一步 i=0。
通俗解释：当前位还是 0，只能选 0，pre 仍为 1，继续遍历最后一位。
第四步：i=0（遍历最低位，v [0]=0）
LL x=v[i]; //x=v[0]=0
if(x==1) { //不成立，跳过分支//无操作
}
if(i==0 && pre==k) cnt++; //i=0，但pre=1≠2 →条件不成立，跳过当前状态：cnt=3，pre=1，i=0 → 循环结束（i-- 后为 -1）。
（三）最终结果
函数返回 cnt=3，即 [0,8] 中二进制恰好有 2 个 1 的数字有 3 个：3 (0011)、5 (0101)、6 (0110)。
【算法代码：数位DP】→ f[i][j] 表示从 i 个二进制位中选 j 个位置填 1 的方案数
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=60;
LL f[N][N];
LL n,k;void init() {for(LL i=0; i<N; i++) {for(LL j=0; j<=i; j++) {if(j==0) f[i][j]=1;else f[i][j]=f[i-1][j-1]+f[i-1][j];}}
}LL dp(LL n) {if(n==0) return 0;vector<int> v;while(n) {v.push_back(n%2);n/=2;}LL cnt=0,pre=0;for(LL i=v.size()-1; i>=0; i--) {LL x=v[i];if(x==1) {if(k-pre>=0 && k-pre<=i) {cnt+=f[i][k-pre];}pre++;if(pre>k) break;}if(i==0 && pre==k) cnt++;}return cnt;
}int main() {cin>>n>>k;init();cout<<dp(n)-dp(0)<<endl;return 0;
}/*
in:7 2
out:3
*/
【参考文献】
https://www.luogu.com.cn/training/82023
https://blog.csdn.net/hnjzsyjyj/article/details/155972543
https://blog.csdn.net/hnjzsyjyj/article/details/155997570
https://blog.csdn.net/WhereIsHeroFrom/article/details/148437243