ivnikkk

Untitled

Dec 19th, 2022
767
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(mask) mask.begin(), mask.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef pair<int, int> pii;
  9. typedef long double ld;
  10. struct segtree{
  11.     int n, inf = INT_MAX;
  12.     vector<int> t;
  13.     vector<int> mod;
  14.     void build(int v, int l, int r, vector<int>& a) {
  15.         if (l == r) {
  16.             t[v] = a[l];
  17.             return;
  18.         }
  19.         int tm = (l + r) / 2;
  20.         build(v * 2, l, tm, a);
  21.         build(v * 2 + 1, tm + 1, r, a);
  22.         t[v] = max(t[v * 2], t[v * 2 + 1]);
  23.     }
  24.     segtree(vector<int>& a) {
  25.         n = a.size();
  26.         mod.resize(n * 4 + 10, 0);
  27.         t.resize(n * 4 + 10, -inf);
  28.         build(1, 0, n - 1, a);
  29.     }
  30.     void push(int l, int r, int v){
  31.         t[v] += mod[v];
  32.         if (l != r) {
  33.             mod[v * 2] += mod[v];
  34.             mod[v * 2 + 1] += mod[v];
  35.         }
  36.         mod[v] = 0;
  37.     }
  38.     void upd(int l, int r, int add, int tl, int tr, int v){
  39.         push(tl, tr, v);
  40.         if (tr < l || r < tl)
  41.             return;
  42.         if (l <= tl && tr <= r) {
  43.             mod[v] += add;
  44.             push(tl, tr, v);
  45.             return;
  46.         }
  47.         int tm = (tl + tr) / 2;
  48.         upd(l, r, add, tl, tm, v * 2);
  49.         upd(l, r, add, tm + 1, tr, v * 2 + 1);
  50.         t[v] = max(t[v * 2], t[v * 2 + 1]);
  51.     }
  52.     void upd(int l, int r, int val) {
  53.         upd(l, r, val, 0, n - 1, 1);
  54.     }
  55.     int get_mx(int l, int r, int tl, int tr, int v) {
  56.         push(tl, tr, v);
  57.         if (l <= tl && tr <= r)
  58.             return t[v];
  59.         if (tr < l || r < tl)
  60.             return -inf;
  61.         int tm = (tl + tr) / 2;
  62.         return max(get_mx(l, r, tl, tm, v * 2), get_mx(l, r, tm + 1, tr, v * 2 + 1));
  63.     }
  64.     int get_mx(int l, int r) {
  65.         return get_mx(l, r, 0, n - 1, 1);
  66.     }
  67. };
  68. const int mod = 1e9 + 7;
  69. vector<vector<int>> dp;
  70. int cnt(string &s, vector<vector<int>>& dp) {
  71.     int res = 0;
  72.     int last = 0;
  73.     for (int i = 0; i < (int)s.size(); i++) {
  74.         for (int f = last; f < s[i] - '0'; f++)
  75.             res = (res + dp[(int)s.size() - i][f]) % mod;
  76.         if (last > s[i] - '0')
  77.             break;
  78.         last = s[i] - '0';
  79.     }
  80.     return res;
  81. }
  82. signed main() {
  83. #ifdef _DEBUG
  84.     freopen("input.txt", "r", stdin);
  85.     freopen("output.txt", "w", stdout);
  86. #endif
  87.     ios_base::sync_with_stdio(false);
  88.     cin.tie(nullptr);
  89.     cout.tie(nullptr);
  90.     string a, b;
  91.     cin >> a >> b;
  92.     dp.resize((int)b.size() + 1, vector<int>(10,0));
  93.     for (int i = 1; i < 10; i++) {
  94.         dp[0][i] = 0, dp[1][i] = 1;
  95.     }
  96.     for (int i = 2; i <= b.size(); i++){
  97.         for (int j = 0; j < 10; j++){
  98.             for (int k = j; k < 10; k++){
  99.                 dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
  100.             }
  101.         }
  102.     }
  103.     int ans1 = cnt(a, dp), ans2 = cnt(b, dp), fl = 1;
  104.     for (int i = 1; i < (int) b.size(); i++) {
  105.         if (b[i - 1] > b[i]) {
  106.             fl = 0;
  107.             break;
  108.         }
  109.     }
  110.     cout << (ans2 - ans1 + mod + fl) % mod << '\n';
  111. }
Advertisement
Add Comment
Please, Sign In to add comment