[Java知识库]Java第十二届蓝桥杯国赛 二进制问题

题目描述：
小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？

【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ N ≤ 106, 1 ≤ K ≤ 10。
对于 60% 的评测用例，1 ≤ N ≤ 2 × 109, 1 ≤ K ≤ 30。
对于所有评测用例，1 ≤ N ≤ 1018, 1 ≤ K ≤ 50。

思路：简单的数位dp
f[i][j]表示（二进制）长度为i，有j的1的方案总数。

初始化：f[i][0] = 1， 所以长度为i，且有0个1的方案数都为1，即这个数就是0.

// czl
import java.util.*;
public class Main
{
    static int N = 65, M = 55;

    static long f[][] = new long[N][M];
    static int num[] = new int[N];
    static int cnt;

    static void init() {
        for(int i = 0; i < N; i ++ )
            f[i][0] = 1;
        for(int i = 1; i < N; i ++ ) {
            for(int j = 1; j < M; j ++ ) {
                f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int k = sc.nextInt();

        init();

        while(n != 0) {
            num[cnt ++ ] = (int) (n & 1);
            n >>= 1;
        }

        long res = 0;
        int last = 0;
        for(int i = cnt - 1; i >= 0; i -- ) {
            if(num[i] == 1) {
                res += f[i][k - last];
                last ++ ;
            }
            if(last == k) {
                res ++ ;
                break;
            }
        }
        
        System.out.println(res);
    }
}