Untitled

 avatar
unknown
plain_text
2 years ago
1.8 kB
6
Indexable
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <map>
#include <math.h>
#include <cmath>
#include "assert.h"
 
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const ll INF = 4e18;
const int N = 310;
const int MOD = 1e9+7;
const ull B = 103;

string l, r;
int num[N], m;
int dp[N][12][2];

int solve(int i, int j, int f) {
    if (dp[i][j][f] != -1) return dp[i][j][f];
    if (i >= m) return dp[i][j][f] = 1;
    int cbegin = 0;
    dp[i][j][f] = 0;
    if (f == 0) {
        for (int c = max(cbegin, j); c < 10; c++) {
            dp[i][j][f] += solve(i + 1, c, f);
            dp[i][j][f] %= MOD;
        }
    }
    else {
        for (int c = max(cbegin, j); c <= num[i]; c++) {
            if (c == num[i]) dp[i][j][f] += solve(i + 1, c, 1);
            else dp[i][j][f] += solve(i + 1, c, 0);
            dp[i][j][f] %= MOD;
        }
    }
    return dp[i][j][f];
}

int solve(const string &s) {
    for (int i = 0; i < s.length(); i++) {
        num[i] = s[i] - '0';
    }
    m = s.length();
    for (int i = 0; i <= 200; i++) {
        for (int j = 0; j < 10; j++) {
            for (int f = 0; f < 2; f++) dp[i][j][f] = -1;
        }
    }
    return solve(0, 0, 1);
}

bool check(const string &s) {
    for (int i = 1; i < s.length(); i++) {
        if (s[i] < s[i - 1]) return false;
    }
    return true;
}

int main() {
    freopen("numbers.in", "r", stdin);
    freopen("numbers.out", "w", stdout);
    cin >> l;
    cin >> r;
    int ans = solve(r);
    ans = (ans - solve(l) + MOD) % MOD;
    if (check(l)) ans = (ans + 1) % MOD;
    cout << ans;
    return 0;
}
Editor is loading...