Advertisement
ivnikkk

Untitled

Nov 10th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long            ll;
  19. typedef unsigned long long   ull;
  20. typedef long double          ld;
  21.  
  22. #define sqrt              sqrtl
  23. #define endl              "\n"
  24. #define all(a)            a.begin(), a.end()
  25. #define pb                push_back
  26. #define F               first
  27. #define S                second
  28. const ll       inf = 1e18;
  29. long double    eps = 1e-18;
  30. ll             mod = 1e9 + 7;
  31. const ll         MAXN = 1 << 20;
  32. const ll maxs = 1 << 20;
  33.  
  34. template <typename T>
  35. istream& operator >> (istream& in, vector <T>& a) {
  36.     for (T& i : a) {
  37.         in >> i;
  38.     }
  39.     return in;
  40. }
  41.  
  42. template <typename T>
  43. ostream& operator << (ostream& out, vector <T>& a) {
  44.     for (T& i : a) {
  45.         out << i << ' ';
  46.     }
  47.     return out;
  48. }
  49. const int N = 1e5 + 10;
  50.  
  51. int dp[N][20][11][2];
  52.  
  53. int dp_cnt(string& s) {
  54.     if (s == "0")
  55.         return 1;
  56.     for (int i = 0; i < N; i++) {
  57.         for (int d = 0; d < 20; d++) {
  58.             for (int last = 0; last < 11; last++) {
  59.                 for (int f = 0; f < 2; f++) {
  60.                     dp[i][d][last][f] = 0;
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     dp[0][0][10][1] = 1;
  66.     for (int i = 0; i < s.size(); i++) {
  67.         for (int d = 0; d < 20; d++) {
  68.             int dif = d - 10;
  69.             for (int last = 0; last < 11; last++) {
  70.                 for (int k = 0; k < 2; k++) {
  71.                     if (d == 0) {
  72.                         for (int newd = 0; newd <= (int)(k == 1 ? s[i] - '0' : 9); newd++) {
  73.                             if (last != 10) {
  74.                                 dp[i + 1][newd - last + 10][newd][(k == 1 && newd == s[i] - '0')] += dp[i][d][last][k];
  75.                             }
  76.                             else {
  77.                                 if (newd&1)
  78.                                     dp[i + 1][0][newd][(k == 1 && newd == s[i] - '0')] += dp[i][d][last][k];
  79.                                 else {
  80.                                     dp[i + 1][0][10][(k == 1 && newd == s[i] - '0')] += dp[i][d][last][k];
  81.                                 }
  82.                             }
  83.                         }
  84.                     }
  85.                     else {
  86.                         if (k == 1 && (last + dif + 10) % 10 > s[i] - '0')
  87.                             continue;
  88.                         int buffer = (k == 1 && (last + dif + 10) % 10 == s[i] - '0');
  89.                         dp[i + 1][d][(last + dif + 10) % 10][buffer] += dp[i][d][last][k];
  90.                     }
  91.                 }
  92.             }
  93.         }
  94.     }
  95.     int ans = 0;
  96.     for (int d = 0; d < 20; d++)
  97.         for (int last = 0; last < 11; last++)
  98.             for (int f = 0; f < 2; f++)
  99.                 ans += dp[s.size()][d][last][f];
  100.     return ans;
  101. }
  102.  
  103. signed main() {
  104.     ios_base::sync_with_stdio(false);
  105.     cin.tie(nullptr);
  106.     string l, r;
  107.     cin >> l >> r;
  108.     int i = l.size() - 1;
  109.     while (l[i] == '0') {
  110.         l[i] = '9';
  111.         i--;
  112.     }
  113.     l[i]--;
  114.     cout << dp_cnt(r) - dp_cnt(l);
  115.     return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement