二进制问题

解题思路:

1 这个【评测用例规模与约定】格式有问题，N的上限基本上是long long的上限，所以这题N和结果都要用long long类型。

对于 30% 的评测用例，1 ≤ N ≤ 10⁶, 1 ≤ K ≤ 10。
对于 60% 的评测用例，1 ≤ N ≤ 2 × 10⁹, 1 ≤ K ≤ 30。
对于所有评测用例，1 ≤ N ≤ 10¹⁸, 1 ≤ K ≤ 50。

2 求含有k个1的个数，就是N的二进制表示，从1开始数，有多少个含k个1的组合数。但是从1开始循环到N，肯定超时，应该用Cn m的组合公式去算。

3 先从long long的8个字节最高位开始，向右依次判断是否为1，找到N的最高位，此时最高位1后面全都是0的那个2的i次记为t。最后的结果就可以=小于t的i-1个1的全组合个数Ci-1,k  +  N-t之后的差，继续向右寻找最高位，继续以上过程所得的所有组合数。这是一个可以递归的过程。

4 组合数公式计算用到3个数的阶乘，n! m!  (n-m)!，按照普通方法去计算，long long也会溢出，所以需要计算时一边乘一边除，尽早约掉因子。

5 递归的结束条件，不止一个吧，f( i ,1)的话就直接返回i 。

参考代码:

#include <stdio.h>

unsigned  long long cnm(int n,int m)
{
    long long s = 1;
    int k = 1;
    if(m > n/2)
        m = n-m;
    for(int i=n-m+1;i<=n;i++)
    {
        s *= (long long)i;
        while(k<=m && s%k == 0)
        {
            s /= (long long)k;
            k++;
        }
    }
    return s;
}

unsigned long long f(unsigned long long n,int k)
{
    unsigned long long c1=0,c2=0,c=0,t=0x8000000000000000;
    int i=64;
    while(~n&t){
        t=t>>1;
        i--;
    }
    if(k==1) return i;
    if((i-1)<k) return 0;
    if(n&t){
        c1=cnm(i-1,k);
        if(k>1){
            c2=f(n-t,k-1) ;
            c=c1+c2;
        }
        else
            c=c1;
    }
    return c;
}

int main()
{
    unsigned long long n, y,c=0,m;
    int k;
    scanf("%lld%d",&n,&k);
    c=f(n,k);
    printf("%lld",c);
}