Untitled
unknown
plain_text
2 years ago
1.8 kB
9
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...