fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Global vector to hold zebra-like numbers (coins)
  5. vector<unsigned long long> coins;
  6.  
  7. // Precompute zebra-like numbers up to 1e18.
  8. // A zebra-like number is of the form: 1, 5, 21, 85, ...
  9. // where coin = coin*4 + 1 starting from coin = 1.
  10. void precomputeCoins(){
  11.     coins.clear();
  12.     unsigned long long limit = 1000000000000000000ULL; // 1e18
  13.     unsigned long long coin = 1;
  14.     while(coin <= limit){
  15.         coins.push_back(coin);
  16.         if(coin > (limit - 1) / 4) break;
  17.         coin = coin*4 + 1;
  18.     }
  19.     // For our DP we want coins in descending order.
  20.     reverse(coins.begin(), coins.end());
  21. }
  22.  
  23. // Given an integer N, compute its representation in our coin system 
  24. // (digits in the greedy algorithm). The vector "digits" corresponds to the
  25. // coins in the global 'coins' vector.
  26. vector<int> getDigits(unsigned long long N) {
  27.     vector<int> digits;
  28.     for(auto coin : coins){
  29.         int d = 0;
  30.         if(N >= coin){
  31.             d = N / coin; // d will be <= 3 due to the properties of coins.
  32.             N %= coin;
  33.         }
  34.         digits.push_back(d);
  35.     }
  36.     return digits;
  37. }
  38.  
  39. // We'll perform digit-DP. 
  40. // dpRec(pos, tight, curSum, target) returns the number of ways to choose
  41. // digits from position 'pos' onward (positions correspond to coins in descending order)
  42. // so that the overall digit sum equals 'target'. 'tight' indicates whether we are
  43. // still following the limit given by the representation of N.
  44.  
  45. // Our state parameters: pos (index in digit array), tight (0 or 1), curSum.
  46. // Maximum positions m is at most ~32 and maximum curSum is at most 100.
  47.  
  48. long long dpMemo[70][2][200];
  49. bool dpComputed[70][2][200];
  50.  
  51. long long dpRec(const vector<int>& limitDigits, int pos, int tight, int curSum, int target) {
  52.     int m = limitDigits.size();
  53.     if(pos == m){
  54.         return (curSum == target) ? 1LL : 0LL;
  55.     }
  56.     if(curSum > target) return 0LL; // prune if sum exceeds target.
  57.     if(dpComputed[pos][tight][curSum])
  58.         return dpMemo[pos][tight][curSum];
  59.  
  60.     long long ways = 0;
  61.     // Determine the maximum digit allowed in this position.
  62.     int up = (tight ? limitDigits[pos] : 3);
  63.     for(int d = 0; d <= up; d++){
  64.         int ntight = (tight && (d == up)) ? 1 : 0;
  65.         ways += dpRec(limitDigits, pos+1, ntight, curSum + d, target);
  66.     }
  67.     dpComputed[pos][tight][curSum] = true;
  68.     dpMemo[pos][tight][curSum] = ways;
  69.     return ways;
  70. }
  71.  
  72. // countUpTo(N, k) counts the number of positive integers in [1, N] whose zebra value equals k.
  73. long long countUpTo(unsigned long long N, int k) {
  74.     if(N < 0) return 0; // not needed since N is unsigned.
  75.     vector<int> digits = getDigits(N);
  76.     memset(dpComputed, 0, sizeof(dpComputed));
  77.     long long res = dpRec(digits, 0, 1, 0, k);
  78.     // Our DP includes the representation of 0 (all digits 0) when k==0.
  79.     // Since we want only positive integers, subtract the count for 0.
  80.     if(k == 0) res -= 1;
  81.     return res;
  82. }
  83.  
  84. int main(){
  85.     ios::sync_with_stdio(false);
  86.     cin.tie(nullptr);
  87.  
  88.     precomputeCoins();
  89.     int t;
  90.     cin >> t;
  91.     while(t--){
  92.         unsigned long long l, r, kULL;
  93.         cin >> l >> r >> kULL;
  94.         // Note: For numbers up to 1e18, the maximum zebra value is at most 3*m,
  95.         // where m is the number of coins used (at most ~32). If k is larger than that,
  96.         // no number in [l, r] can have zebra value k.
  97.         int m = coins.size();
  98.         if(kULL > (unsigned long long)(3 * m)){
  99.             cout << 0 << "\n";
  100.             continue;
  101.         }
  102.         int k = (int) kULL;
  103.         long long ans = countUpTo(r, k) - countUpTo(l - 1, k);
  104.         cout << ans << "\n";
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
5
1 100 3
1 1 1
15 77 2
2 10 100
1234567 123456789101112131 12
stdout
copy 
13
1
3
0
4163989352
https://ideone.com/OtKJ5v
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!