Untitled
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...