Fshl0

Fancy That!

Sep 11th, 2021
525
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. vector <ll> digits;
  7. ll dp[12][2][2][2];
  8.  
  9. ll calcDP (ll idx, ll parity, ll flag, ll started) {
  10.     if (idx == (ll) digits.size())
  11.         return parity == 0;
  12.        
  13.     if (dp[idx][parity][flag][started] != -1)
  14.         return dp[idx][parity][flag][started];
  15.        
  16.     ll res = 0;
  17.     if (started) {
  18.         if (!flag) {
  19.             for (ll i = digits[idx] - 1; i >= 0; i--)
  20.                 res += calcDP (idx + 1, parity, 1, 1);
  21.             res += calcDP (idx + 1, parity, 0, 1);
  22.         } else {
  23.             for (ll i = 0; i <= 9; i++)
  24.                 res += calcDP (idx + 1, parity, 1, 1);
  25.         }
  26.        
  27.         return dp[idx][parity][flag][started] = res;
  28.     }
  29.    
  30.     if (!flag) {
  31.         for (ll i = digits[idx] - 1; i >= 0; i--)
  32.             res += calcDP (idx + 1, i % 2, 1, i != 0);
  33.         res += calcDP (idx + 1, digits[idx] % 2, 0, digits[idx] != 0);
  34.     } else {
  35.         for (ll i = 0; i <= 9; i++)
  36.             res += calcDP (idx + 1, i % 2, 1, i != 0);
  37.     }
  38.    
  39.     return dp[idx][parity][flag][started] = res;
  40. }
  41.  
  42. ll get (ll x) {
  43.     digits.clear();
  44.     memset (dp, -1, sizeof (dp));
  45.    
  46.     while (x) {
  47.         digits.push_back (x % 10);
  48.         x /= 10;
  49.     }
  50.    
  51.     reverse (digits.begin(), digits.end());
  52.     return calcDP (0, 0, 0, 0);
  53. }
  54.  
  55. int main () {
  56.     ll t;
  57.     cin >> t;
  58.    
  59.     while (t--) {
  60.         ll l, r;
  61.         cin >> l >> r;
  62.        
  63.         //cout << get (l) << ' ' << get (r) << "\n";
  64.         cout << get (r) - get (l - 1) << "\n";
  65.     }
  66.    
  67.     return 0;
  68. }
  69.  
RAW Paste Data