蓝桥杯 2021 国BC

[蓝桥杯 2021 国 BC] 二进制问题

题目描述

小蓝近期正在钻研二进制数的相关知识，他希望了解在从 1 到 N 的范围内，存在多少个数值的二进制形式中恰好包含 K 个 1。你是否能够为他提供解答？

输入格式

给出一行数据，其中包含两个整数 N 和 K。

输出格式

请提供一个整数形式的答案。

样例分析与呈现

样例输入 #1

    7 2
    
    
      
    

样例输出结构解析

    3
    
    
      
    

提示

针对 30 \% 的测试案例，变量 N 的取值范围为 1 \leq N \leq 10^{6}，而 K 的取值范围则限定在 1 \leq K \leq 10 。

在 60 \% 的测试案例中，N 的取值上限扩展至 2 \times 10^{9}，同时 K 的最大值提升至 30。

对于全部测试案例而言，N 的最大可能值达到 10^{18}，而 K 的上限则设定为 50。

蓝桥杯 2021 国赛 B 组 H 题（C 组 J 题）。

思路

**总结：从个人理解来看，数位dp主要可分为两类题目类型：一