Test Case Pass: all ✅

blog_openai_o4_mini_coding_cf_zebra_like_numbers_question_response.cpp

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

static const int KMAX = 200;  // an upper bound on f(x) -- about 4*M ~ 120

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 1) Build the zebra‐like coins z[i] = (4^{i+1} - 1)/3
    vector<ull> z;
    z.push_back(1);
    while(z.back() <= (ull)1e18){
        __uint128_t nxt = (__uint128_t)4*z.back() + 1;
        if(nxt > ( (__uint128_t)1e18 + 5)) break;
        z.push_back((ull)nxt);
    }
    int M = (int)z.size();  // number of coins

    // 2) Build dp[i][h] = # of x in [0, z[i]-1] with f(x)=h
    static ull dp[64][KMAX+1];
    memset(dp,0,sizeof(dp));
    // Base: i=0 ==> [0, z[0]-1] = [0,0]
    dp[0][0] = 1;  

    for(int i = 1; i < M; i++){
        for(int h = 0; h <= KMAX; h++){
            // sum over t=0..3 of dp[i-1][h-t]
            ull sum = 0;
            for(int t = 0; t <= 3; t++){
                if(h - t >= 0) sum += dp[i-1][h - t];
            }
            // the special point x = z[i]-1 has f(x)=4
            if(h == 4) sum += 1;
            dp[i][h] = sum;
        }
    }

    // 3) Define a recursive function get(R,k) returning # of x in [0,R] with f(x)=k.
    function<ull(long long,long long)> get = [&](long long R, long long K)->ull {
        if(R < 0 || K < 0 || K > KMAX) return 0ULL;
        // If R < z[0] = 1, then R=0, and only x=0 is possible, f(0)=0
        if(R < 1) {
            return (K == 0 ? 1ULL : 0ULL);
        }
        // Find i so that z[i] <= R < z[i+1]
        int i = int(upper_bound(z.begin(), z.end(), (ull)R) - z.begin()) - 1;
        // how many copies of z[i] fit into R
        int cnt = int(R / z[i]);
        if(cnt > 4) cnt = 4;  // in fact R < z[i+1] = 4*z[i]+1
        
        ull ans = 0;
        // full blocks t=0..cnt-1
        for(int t = 0; t < cnt; t++){
            if(K - t >= 0 && K - t <= KMAX){
                ans += dp[i][K - t];
            }
        }
        // the partial block t = cnt
        long long rem = R - (long long)cnt * (long long)z[i];
        if(cnt < 4){
            ans += get(rem, K - cnt);
        } else {
            // cnt=4 ==> R >= 4*z[i], but still R<z[i+1], so R==4*z[i], rem=0
            // that single x gives f=x(=4) iff K==4
            if(K == 4) ans += 1;
        }
        return ans;
    };

    // Process queries
    int t; 
    cin >> t;
    while(t--){
        long long L,R,K;
        cin >> L >> R >> K;
        if(K > KMAX){
            // impossible to need more than ~120 coins for 10^18
            cout << 0 << "\n";
        } else {
            ull ways = get(R, K) - get(L-1, K);
            cout << ways << "\n";
        }
    }

    return 0;
}

Problem link: https://codeforces.com/problemset/problem/2086/E