fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define initial first
  8. #define added second
  9. #define sort_all(v) sort(v.begin(), v.end())
  10.  
  11. #define ya_sayed_ya_badawy            \
  12.     ios_base::sync_with_stdio(false); \
  13.     cin.tie(NULL);
  14.  
  15. const int MAX = 50 + 5;
  16. int MOD = 1000000007;
  17. const int OO = 1e9;
  18. const double EPS = (double)1e-9;
  19.  
  20. const int MAX_N = 500;
  21.  
  22. ll K;
  23. string a, b;
  24.  
  25. ll zebra[35];
  26.  
  27. int mem[MAX][2][2][2][MAX_N];
  28. int visited[MAX][2][2][2][MAX_N];
  29.  
  30. const int offset = 17;
  31.  
  32. int id = 1;
  33.  
  34. int add(ll a, ll b)
  35. {
  36.     return (a + b) % MOD;
  37. }
  38.  
  39. int mul(ll a, ll b)
  40. {
  41.     return (a * b) % MOD;
  42. }
  43.  
  44. ll fp(ll base, ll pow)
  45. {
  46.     if (pow == 0)
  47.     {
  48.         return 1;
  49.     }
  50.  
  51.     ll res = fp(base, pow / 2);
  52.  
  53.     if (pow % 2 == 0)
  54.     {
  55.         return res * res;
  56.     }
  57.     return base * res * res;
  58. }
  59.  
  60. bool check(ll number)
  61. {
  62.  
  63.     int cost = 0;
  64.  
  65.     for (int i = 31; i >= 0; i--)
  66.     {
  67.         cost += number / zebra[i];// 3 
  68.         number = number - (number / zebra[i]) * zebra[i];
  69.     }
  70.  
  71.     return (cost == K);
  72. }
  73.  
  74. int dp(int pos, bool exceeded_lower, bool below_upper, int started, ll number)
  75. {
  76.  
  77.     if (pos == (int)b.size())
  78.     {
  79.         return check(number);
  80.     }
  81.  
  82.     int &ret = mem[pos][exceeded_lower][below_upper][started][number];
  83.     if (visited[pos][exceeded_lower][below_upper][started][number] == id)
  84.     {
  85.         return ret;
  86.     }
  87.  
  88.     visited[pos][exceeded_lower][below_upper][started][number] = id;
  89.  
  90.     ret = 0;
  91.     int low = exceeded_lower ? 0 : (a[pos] - '0');
  92.     int high = below_upper ? 9 : (b[pos] - '0');
  93.  
  94.     for (int d = low; d <= high; ++d)
  95.     {
  96.         bool new_tight_low = exceeded_lower || (d > (a[pos] - '0'));
  97.         bool new_tight_high = below_upper || (d < (b[pos] - '0'));
  98.         bool new_started = started || (d != 0);
  99.  
  100.         int new_number = number * 10 + d;
  101.  
  102.         ret = add(ret, dp(pos + 1, new_tight_low, new_tight_high, new_started, new_number));
  103.     }
  104.  
  105.     return ret;
  106. }
  107.  
  108. string normalize_length(string s, int len)
  109. {
  110.     return (string(len - (int)s.size(), '0') + s);
  111. }
  112.  
  113. void solve(int t)
  114. {
  115.  
  116.     cin >> a >> b >> K;
  117.  
  118.     int max_len = max(a.size(), b.size());
  119.     a = normalize_length(a, max_len);
  120.     b = normalize_length(b, max_len);
  121.  
  122.     zebra[0] = 1;
  123.  
  124.     ll res = 1;
  125.     int j = 1;
  126.  
  127.     for (int i = 2; i < 64; i += 2)
  128.     {
  129.  
  130.         res += fp(2, i);
  131.  
  132.         zebra[j] = res;
  133.  
  134.         // cout << zebra[j] << " ";
  135.         // cout << "j: " << j << endl;
  136.         j++;
  137.     }
  138.  
  139.     cout << dp(0, 0, 0, 0, 0);
  140.  
  141.     id++;
  142.  
  143. }
  144.  
  145. signed main()
  146. {
  147.     ya_sayed_ya_badawy int t = 1;
  148.     cin >> t;
  149.  
  150.     for (int i = 1; i <= t; i++)
  151.     {
  152.         solve(i);
  153.         if (i != t)
  154.         {
  155.             cout << endl;
  156.         }
  157.     }
  158.  
  159.     return 0;
  160. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/m9d6f7
language:
C++14 (gcc 8.3)
created:
5 days 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!