fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. // Precompute the "zebra-coin" values.
  5. // They are defined by: coin[0] = 1, and coin[i+1] = 4 * coin[i] + 1.
  6. // In binary these are: 1, 101, 10101, 1010101, etc.
  7. vector<unsigned long long> computeCoins() {
  8.     vector<unsigned long long> coins;
  9.     // Use __int128 to avoid overflow when computing 4*coin + 1.
  10.     __int128 cur = 1;
  11.     unsigned long long LIMIT = 1000000000000000000ULL; // 1e18
  12.     while(cur <= LIMIT) {
  13.         coins.push_back((unsigned long long)cur);
  14.         cur = 4 * cur + 1;
  15.     }
  16.     // Push one extra coin to serve as the upper bound for the maximum digit length.
  17.     coins.push_back((unsigned long long)cur);
  18.     return coins;
  19. }
  20.  
  21. // Given a number X (which we know has exactly L digits in our zebra numeral system)
  22. // convert it to its digit representation (most-significant digit first).
  23. vector<int> convertToDigits(unsigned long long X, int L, const vector<unsigned long long>& coins) {
  24.     vector<int> digits(L, 0);
  25.     // The weight for the most-significant digit is coins[L-1], then coins[L-2], down to coins[0].
  26.     for (int i = 0; i < L; i++) {
  27.         unsigned long long weight = coins[L-1-i];
  28.         digits[i] = (int)(X / weight);
  29.         X %= weight;
  30.     }
  31.     return digits;
  32. }
  33.  
  34. // A DP routine to count, for a fixed digit length L,
  35. // the number of zebra–numbers (represented by a vector of digits)
  36. // between the lower bound LB and upper bound UB (inclusive)
  37. // that have digit sum (i.e. zebra value) exactly equal to target.
  38. // The DP state is (pos, tightLow, tightHigh, sum) where pos is the current digit index.
  39.  
  40. long long dpDigits(int pos, int L, int tightL, int tightU, int sum, int target,
  41.                     const vector<int>& LB, const vector<int>& UB, 
  42.                     vector<vector<vector<vector<long long>>>> &memo) {
  43.     if(pos == L){
  44.         return (sum == target) ? 1LL : 0LL;
  45.     }
  46.     if(sum > target) return 0; // no need to continue if we've overshot our target.
  47.     if(memo[pos][tightL][tightU][sum] != -1)
  48.         return memo[pos][tightL][tightU][sum];
  49.     int lowDigit = (tightL ? LB[pos] : (pos==0 ? 1 : 0)); // ensure the first digit is nonzero
  50.     int highDigit = (tightU ? UB[pos] : 4);
  51.     long long ways = 0;
  52.     for (int d = lowDigit; d <= highDigit; d++){
  53.         int ntl = (tightL && d == LB[pos]) ? 1 : 0;
  54.         int ntu = (tightU && d == UB[pos]) ? 1 : 0;
  55.         ways += dpDigits(pos+1, L, ntl, ntu, sum+d, target, LB, UB, memo);
  56.     }
  57.     memo[pos][tightL][tightU][sum] = ways;
  58.     return ways;
  59. }
  60.  
  61. // For fixed digit-length L, count numbers in [A, B] (which are guaranteed to have L-digit zebra representation)
  62. // that have zebra value exactly 'target'.
  63. long long countForLength(int L, unsigned long long A, unsigned long long B, int target, const vector<unsigned long long>& coins) {
  64.     if(A > B) return 0;
  65.     if(target > 4 * L) return 0; // no chance if target is too high
  66.     vector<int> LB = convertToDigits(A, L, coins);
  67.     vector<int> UB = convertToDigits(B, L, coins);
  68.     int sumDim = 4 * L + 1;
  69.     // Create a 4D DP table: dimensions: pos (0..L), tightL (0,1), tightU (0,1), sum (0..4*L)
  70.     vector<vector<vector<vector<long long>>>> memo(
  71.         L+1, vector<vector<vector<long long>>>(2, vector<vector<long long>>(2, vector<long long>(sumDim, -1)))
  72.     );
  73.     long long res = dpDigits(0, L, 1, 1, 0, target, LB, UB, memo);
  74.     return res;
  75. }
  76.  
  77. // Main – we partition the search range [l, r] by zebra-digit length and run digit-DP on each part.
  78. int main(){
  79.     ios::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.  
  82.     int t;
  83.     cin >> t;
  84.     vector<unsigned long long> coins = computeCoins();
  85.     // For a skeptical twist: Our coins grow so fast you might suspect a magic trick—
  86.     // but math (and our DP) never lies!
  87.  
  88.     while(t--){
  89.         unsigned long long l, r;
  90.         long long k;
  91.         cin >> l >> r >> k;
  92.  
  93.         long long ans = 0;
  94.  
  95.         // The zebra–digit representation for numbers with L digits is in [coins[L-1], coins[L]-1].
  96.         // We loop over all possible L such that coins[L-1] ≤ r.
  97.         for (int L = 1; L < (int)coins.size(); L++){
  98.             if(coins[L-1] > r) break;
  99.             unsigned long long lowRange = coins[L-1];
  100.             unsigned long long highRange = coins[L] - 1; // full range for L-digit numbers
  101.             // Restrict to our query interval.
  102.             unsigned long long A = max(l, lowRange);
  103.             unsigned long long B = min(r, highRange);
  104.             if(A > B) continue;
  105.  
  106.             // If k is outside the possible zebra value range for this digit–length, skip.
  107.             if(k > 4LL * L) continue;
  108.  
  109.             long long cnt = countForLength(L, A, B, (int)k, coins);
  110.             ans += cnt;
  111.         }
  112.  
  113.         cout << ans << "\n";
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
5
1 100 3
1 1 1
15 77 2
2 10 100
1234567 123456789101112131 12
stdout 
13
1
3
0
4694715292
https://ideone.com/0UwCBM
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!