Advertisement
Guest User

Untitled

a guest
Mar 18th, 2018
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long lli;
  6.  
  7. const int maxn = 3030, mod = 1e9 + 7;
  8.  
  9. int dp[maxn][2][2];
  10. bool bio[maxn][2][2];
  11.  
  12. int dp2[maxn][maxn][3][2];
  13. bool bio2[maxn][maxn][3][2];
  14.  
  15. bool dp3[maxn][maxn];
  16. bool bio3[maxn][maxn];
  17.  
  18. int n;
  19. int arr[maxn];
  20.  
  21. int pot10[maxn];
  22.  
  23. int add(int a, int b) {
  24.     if(a + b >= mod)
  25.         return a + b - mod;
  26.     return a + b;
  27. }
  28.  
  29. int sub(int a, int b) {
  30.     if(b > a)
  31.         return a - b + mod;
  32.     return a - b;
  33. }
  34.  
  35. int mlt(int a, int b) {
  36.     return lli(a) * b % mod;
  37. }
  38.  
  39. bool check(int l, int r) {
  40.     if(l >= r) {
  41.         return true;
  42.     }
  43.  
  44.     if(bio3[l][r]) {
  45.         return dp3[l][r];
  46.     }
  47.  
  48.     bio3[l][r] = true;
  49.  
  50.     if(arr[l] == arr[r]) {
  51.         return dp3[l][r] = check(l + 1, r - 1);
  52.     } else {
  53.         return dp3[l][r] = false;
  54.     }
  55. }
  56.  
  57. int count(int l, int r, int diff, bool must) {
  58.     if(l == r) {
  59.         if(diff <= 1) {
  60.             return max(0, arr[l] + diff - must);
  61.         } else {
  62.             return 10 - must;
  63.         }
  64.     }
  65.  
  66.     if(l > r) {
  67.         return (!must && diff);
  68.     }
  69.  
  70.     if(bio2[l][r][diff][must]) {
  71.         return dp2[l][r][diff][must];
  72.     }
  73.  
  74.     bio2[l][r][diff][must] = true;
  75.     int ret = 0;
  76.  
  77.     if(diff <= 1) {
  78.         if(arr[l] >= must) {
  79.             ret = add(ret, mlt(arr[l] - must, count(l + 1, r - 1, 2, false)));
  80.  
  81.             if(arr[r] > arr[l]) {
  82.                 ret = add(ret, count(l + 1, r - 1, 1, false));
  83.             } else if(arr[r] == arr[l]) {
  84.                 ret = add(ret, count(l + 1, r - 1, diff, false));
  85.             } else {
  86.                 ret = add(ret, count(l + 1, r - 1, 0, false));
  87.             }
  88.         }
  89.     } else {
  90.         ret = add(ret, mlt(10 - must, count(l + 1, r - 1, 2, false)));
  91.     }
  92.  
  93.     return dp2[l][r][diff][must] = ret;
  94. }
  95.  
  96. int solve(int l, bool diff, bool must) {
  97.     if(l == n) {
  98.         return !must;
  99.     }
  100.  
  101.     if(bio[l][diff][must]) {
  102.         return dp[l][diff][must];
  103.     }
  104.  
  105.     bio[l][diff][must] = true;
  106.     int ret = 0;
  107.  
  108.     if(must) {
  109.         if(diff) {
  110.             for(int r = l; r < n; r++) {
  111.                 ret = add(ret, mlt(9, mlt(pot10[(r - l) / 2], solve(r + 1, 1, 0))));
  112.             }
  113.         } else {
  114.             for(int r = l; r < n; r++) {
  115.                 ret = add(ret, mlt(count(l, r, 0, 1), solve(r + 1, 1, 0)));
  116.  
  117.                 if(check(l, r) && arr[l] != 0) {
  118.                     ret = add(ret, solve(r + 1, 0, 0));
  119.                 }
  120.             }
  121.         }
  122.     } else {
  123.         if(diff) {
  124.             for(int r = l; r < n; r++) {
  125.                 ret = add(ret, mlt(pot10[(r - l + 1 + 1) / 2], solve(r + 1, 1, 0)));
  126.             }
  127.         } else {
  128.             for(int r = l; r < n; r++) {
  129.                 ret = add(ret, mlt(count(l, r, 0, 0), solve(r + 1, 1, 0)));
  130.  
  131.                 if(check(l, r)) {
  132.                     ret = add(ret, solve(r + 1, 0, 0));
  133.                 }
  134.             }
  135.         }
  136.     }
  137.  
  138.     return dp[l][diff][must] = ret;
  139. }
  140.  
  141. int calc(string &s) {
  142.     n = s.size();
  143.  
  144.     for(int i = 0; i < n; i++) {
  145.         arr[i] = s[i] - '0';
  146.     }
  147.  
  148.     memset(bio, 0, sizeof bio);
  149.     memset(bio2, 0, sizeof bio2);
  150.     memset(bio3, 0, sizeof bio3);
  151.  
  152.     int ans = solve(0, false, true);
  153.  
  154.     for(int i = 1; i < n; i++) {
  155.         ans = add(ans, solve(i, true, true));
  156.     }
  157.  
  158.     return ans;
  159. }
  160.  
  161. void reduce(string &s) {
  162.     s[s.size() - 1]--;
  163.     for(int i = s.size() - 1; i >= 0; i--) {
  164.         if(s[i] < '0') {
  165.             s[i] = '9';
  166.             s[i - 1]--;
  167.         }
  168.     }
  169. }
  170.  
  171. int main() {
  172.     ios_base::sync_with_stdio(false);
  173.     cin.tie(nullptr);
  174.  
  175.     pot10[0] = 1;
  176.     for(int i = 1; i < maxn; i++) {
  177.         pot10[i] = mlt(pot10[i - 1], 10);
  178.     }
  179.  
  180.     string s, z;
  181.  
  182.     cin >> s >> z;
  183.  
  184.     reduce(s);
  185.  
  186.     cout << sub(calc(z), calc(s)) << endl;
  187.  
  188.     return 0;
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement