gistfile1.txt

#include <iostream>
#include <set>
#include <string>
#include <vector>
#define optimizar ios_base::sync_with_stdio(0); cin.tie(0)
#define lld long long int
using namespace std;
const int MAXN = 100002;
const int LOG_N = 20;

int countBits(int x) {
    int c = 0;
    while(x) {
        if(x & 1) c++;
        x >>= 1;
    }
    return c;
}
int g[65];

string num;

int v[65][20];
int color;
lld dp[65][20];
lld distrib(int k, int i) {
    if(!k) return 1;
    if(i >= num.size()) return 0;
    if(v[k][i] != color) {
        v[k][i] = color;
        dp[k][i] = distrib(k - 1, i) + distrib(k, i + 1);
    }
    return dp[k][i];
}

lld distribuye(int k) {
    lld suma = 0;
    for(int i = 0; i < num.size(); i++) {
        if(num[i] == '1') {
            suma += distrib(k, i + 1);
            k--;
        }
    }
    return suma;
}

void transform(int x) {
    num.clear();
    color++;
    while(x) {
        num.push_back((x & 1) + '0');
        x >>= 1;
    }
    reverse(num.begin(), num.end());
}

lld solve(int x) {
    if(x == 0) return 1;
    if(x == 1) return distribuye(1) - 1;
    lld suma = 0;
    for(int i = 1; i < 65; i++) 
        if(g[i] == x - 1) suma += distribuye(i);
    return suma;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for(int i = 2; i < 65; i++) 
        g[i] = g[countBits(i)] + 1;

    int l, r, x;
    cin >> l >> r >> x;
    transform(r);
    cout << num << "\n";
    lld sol = solve(x);
    transform(l - 1);
    sol -= solve(x);
    cout << sol << "\n";
    return 0;
}