Proficient.
Put your skills to the test.

Problem summary

Call a positive integer k-odd when repeated floor-division by 2 down to 1 encounters at least k consecutive odd values. Count k-odd integers in the inclusive interval [a,b].

Constraints

1 ≤ k ≤ 100000; 1 ≤ a ≤ b ≤ 10^100.

Worked example

An independently prepared example for this explanation.

3
7
42

9

Solution analysis

1. Successive parity bits under division by two are exactly the binary digits from right to left. Thus k consecutive odd quotients mean that the binary representation contains a run of at least k ones. The order of reading bits does not change whether such a run exists.
2. For a bound X, run a binary digit DP from most significant bit to least. State (run,tight) records the current trailing run, saturated at k once a qualifying run has occurred. State k is absorbing. Leading zeros do not create runs. At each bit add the counts of allowed transitions, respecting the upper bound.
3. Use exact decimal-string addition because counts can have 101 digits. Convert decimal bounds to binary with repeated division by two, and compute count(b)−count(a−1). For k=3 and [7,42], the qualifying values are 7,14,15,23,28,29,30,31,39, totaling nine.

Why it works

The quotient parity sequence is the reversed binary digit sequence, so the original property is equivalent to a binary run of k ones. By induction on processed bits, each DP entry counts exactly the prefixes with its bound status and run state; the two next-bit transitions partition the valid extensions. Saturating at k remembers exactly that the required run has occurred. Summing its two final tight states counts all qualifying numbers through X, and subtracting prefix counts yields the interval.

Watch out. A leading zero must reset an unqualified run, but a qualified state remains qualified forever. Do not use fixed-width integer types for the interval or count.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string add(const string&a,const string&b){
    string result;
    int i=static_cast<int>(a.size())-1;
    int j=static_cast<int>(b.size())-1;
    int carry=0;
    while(i>=0||j>=0||carry){
        int value=carry;
        if(i>=0){
            value+=a[i--]-'0';
        }
        if(j>=0){
            value+=b[j--]-'0';
        }
        result.push_back(static_cast<char>('0'+value%10));
        carry=value/10;
    }
    reverse(result.begin(),result.end());
    return result;
}
string subtract(const string&a,const string&b){
    string result;
    int j=static_cast<int>(b.size())-1;
    int borrow=0;
    for(int i=static_cast<int>(a.size())-1;i>=0;i--){
        int value=a[i]-'0'-borrow;
        if(j>=0){
            value-=b[j--]-'0';
        }
        borrow=value<0;
        if(borrow){
            value+=10;
        }
        result.push_back(static_cast<char>('0'+value));
    }
    while(result.size()>1&&result.back()=='0'){
        result.pop_back();
    }
    reverse(result.begin(),result.end());
    return result;
}
string binary(string decimal){
    string bits;
    while(decimal!="0"){
        string quotient;
        int carry=0;
        for(char digit:decimal){
            int value=carry*10+digit-'0';
            if(!quotient.empty()||value/2!=0){
                quotient.push_back(static_cast<char>('0'+value/2));
            }
            carry=value%2;
        }
        bits.push_back(static_cast<char>('0'+carry));
        decimal=quotient.empty()?"0":quotient;
    }
    reverse(bits.begin(),bits.end());
    return bits;
}
string countThrough(const string&bound,int k){
    string bits=binary(bound);
    if(k>static_cast<int>(bits.size())){
        return "0";
    }
    vector<array<string,2>>dp(k+1),next(k+1);
    for(auto&state:dp){
        state={"0","0"};
    }
    dp[0][1]="1";
    for(char character:bits){
        for(auto&state:next){
            state={"0","0"};
        }
        int boundBit=character-'0';
        for(int run=0;run<=k;run++){
            for(int tight=0;tight<=1;tight++){
                int limit=tight?boundBit:1;
                for(int bit=0;bit<=limit;bit++){
                    int newRun=run==k?k:(bit==0?0:run+1);
                    int newTight=tight&&bit==boundBit;
                    next[newRun][newTight]=add(next[newRun][newTight],dp[run][tight]);
                }
            }
        }
        dp.swap(next);
    }
    return add(dp[k][0],dp[k][1]);
}
int main(){
    int k;
    string a,b;
    cin>>k>>a>>b;
    // Inclusive interval count is the difference of two prefix counts.
    cout<<subtract(countThrough(b,k),countThrough(subtract(a,"1"),k))<<'\n';
}