Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(mask) mask.begin(), mask.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- typedef long double ld;
- struct segtree{
- int n, inf = INT_MAX;
- vector<int> t;
- vector<int> mod;
- void build(int v, int l, int r, vector<int>& a) {
- if (l == r) {
- t[v] = a[l];
- return;
- }
- int tm = (l + r) / 2;
- build(v * 2, l, tm, a);
- build(v * 2 + 1, tm + 1, r, a);
- t[v] = max(t[v * 2], t[v * 2 + 1]);
- }
- segtree(vector<int>& a) {
- n = a.size();
- mod.resize(n * 4 + 10, 0);
- t.resize(n * 4 + 10, -inf);
- build(1, 0, n - 1, a);
- }
- void push(int l, int r, int v){
- t[v] += mod[v];
- if (l != r) {
- mod[v * 2] += mod[v];
- mod[v * 2 + 1] += mod[v];
- }
- mod[v] = 0;
- }
- void upd(int l, int r, int add, int tl, int tr, int v){
- push(tl, tr, v);
- if (tr < l || r < tl)
- return;
- if (l <= tl && tr <= r) {
- mod[v] += add;
- push(tl, tr, v);
- return;
- }
- int tm = (tl + tr) / 2;
- upd(l, r, add, tl, tm, v * 2);
- upd(l, r, add, tm + 1, tr, v * 2 + 1);
- t[v] = max(t[v * 2], t[v * 2 + 1]);
- }
- void upd(int l, int r, int val) {
- upd(l, r, val, 0, n - 1, 1);
- }
- int get_mx(int l, int r, int tl, int tr, int v) {
- push(tl, tr, v);
- if (l <= tl && tr <= r)
- return t[v];
- if (tr < l || r < tl)
- return -inf;
- int tm = (tl + tr) / 2;
- return max(get_mx(l, r, tl, tm, v * 2), get_mx(l, r, tm + 1, tr, v * 2 + 1));
- }
- int get_mx(int l, int r) {
- return get_mx(l, r, 0, n - 1, 1);
- }
- };
- const int mod = 1e9 + 7;
- vector<vector<int>> dp;
- int cnt(string &s, vector<vector<int>>& dp) {
- int res = 0;
- int last = 0;
- for (int i = 0; i < (int)s.size(); i++) {
- for (int f = last; f < s[i] - '0'; f++)
- res = (res + dp[(int)s.size() - i][f]) % mod;
- if (last > s[i] - '0')
- break;
- last = s[i] - '0';
- }
- return res;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- string a, b;
- cin >> a >> b;
- dp.resize((int)b.size() + 1, vector<int>(10,0));
- for (int i = 1; i < 10; i++) {
- dp[0][i] = 0, dp[1][i] = 1;
- }
- for (int i = 2; i <= b.size(); i++){
- for (int j = 0; j < 10; j++){
- for (int k = j; k < 10; k++){
- dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
- }
- }
- }
- int ans1 = cnt(a, dp), ans2 = cnt(b, dp), fl = 1;
- for (int i = 1; i < (int) b.size(); i++) {
- if (b[i - 1] > b[i]) {
- fl = 0;
- break;
- }
- }
- cout << (ans2 - ans1 + mod + fl) % mod << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment