原题链接

题解

1.如果数字为 \(100110101\)
那么答案为 \(000000000\) ~ \(011111111\) 中，k个1的组合数 + \(100000000\) ~ \(100011111\) 中k-1个1的组合数 +...+ \(1010101...\) （有k个1） 中0个1的组合数，也就是1
当遇见当遇见k个1 后就可以退出了，最后判断数的1的个数够不够k，如果够，就把最后那个1加上

code

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

ll C(ll a, ll b)
{
    b = min(b, a - b);
    ll sum = 1;
    for(ll i = 1; i <= b; i++) sum = sum * (a - i + 1) / i;
    return sum;
}

int main()
{
    ll n, k;
    read(n); read(k);
    vector<ll> a;
    ll one=0;
    while(n)
    {
        a.push_back(n % 2);
        one+=n%2;
        n /= 2;
    }

    ll ans = 0, cnt = 0;
    for(ll i = a.size() - 1; i >= 0; i--)
    {
        if(i < k - cnt||cnt==k) break;
        if(a[i] == 1)
        {
            ans += C(i, k - cnt);
            cnt++;
        }
    }

    write(ans+(one>=k));
    return 0;
}