Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long lli;
- const int maxn = 3030, mod = 1e9 + 7;
- int dp[maxn][2][2];
- bool bio[maxn][2][2];
- int dp2[maxn][maxn][3][2];
- bool bio2[maxn][maxn][3][2];
- bool dp3[maxn][maxn];
- bool bio3[maxn][maxn];
- int n;
- int arr[maxn];
- int pot10[maxn];
- int add(int a, int b) {
- if(a + b >= mod)
- return a + b - mod;
- return a + b;
- }
- int sub(int a, int b) {
- if(b > a)
- return a - b + mod;
- return a - b;
- }
- int mlt(int a, int b) {
- return lli(a) * b % mod;
- }
- bool check(int l, int r) {
- if(l >= r) {
- return true;
- }
- if(bio3[l][r]) {
- return dp3[l][r];
- }
- bio3[l][r] = true;
- if(arr[l] == arr[r]) {
- return dp3[l][r] = check(l + 1, r - 1);
- } else {
- return dp3[l][r] = false;
- }
- }
- int count(int l, int r, int diff, bool must) {
- if(l == r) {
- if(diff <= 1) {
- return max(0, arr[l] + diff - must);
- } else {
- return 10 - must;
- }
- }
- if(l > r) {
- return (!must && diff);
- }
- if(bio2[l][r][diff][must]) {
- return dp2[l][r][diff][must];
- }
- bio2[l][r][diff][must] = true;
- int ret = 0;
- if(diff <= 1) {
- if(arr[l] >= must) {
- ret = add(ret, mlt(arr[l] - must, count(l + 1, r - 1, 2, false)));
- if(arr[r] > arr[l]) {
- ret = add(ret, count(l + 1, r - 1, 1, false));
- } else if(arr[r] == arr[l]) {
- ret = add(ret, count(l + 1, r - 1, diff, false));
- } else {
- ret = add(ret, count(l + 1, r - 1, 0, false));
- }
- }
- } else {
- ret = add(ret, mlt(10 - must, count(l + 1, r - 1, 2, false)));
- }
- return dp2[l][r][diff][must] = ret;
- }
- int solve(int l, bool diff, bool must) {
- if(l == n) {
- return !must;
- }
- if(bio[l][diff][must]) {
- return dp[l][diff][must];
- }
- bio[l][diff][must] = true;
- int ret = 0;
- if(must) {
- if(diff) {
- for(int r = l; r < n; r++) {
- ret = add(ret, mlt(9, mlt(pot10[(r - l) / 2], solve(r + 1, 1, 0))));
- }
- } else {
- for(int r = l; r < n; r++) {
- ret = add(ret, mlt(count(l, r, 0, 1), solve(r + 1, 1, 0)));
- if(check(l, r) && arr[l] != 0) {
- ret = add(ret, solve(r + 1, 0, 0));
- }
- }
- }
- } else {
- if(diff) {
- for(int r = l; r < n; r++) {
- ret = add(ret, mlt(pot10[(r - l + 1 + 1) / 2], solve(r + 1, 1, 0)));
- }
- } else {
- for(int r = l; r < n; r++) {
- ret = add(ret, mlt(count(l, r, 0, 0), solve(r + 1, 1, 0)));
- if(check(l, r)) {
- ret = add(ret, solve(r + 1, 0, 0));
- }
- }
- }
- }
- return dp[l][diff][must] = ret;
- }
- int calc(string &s) {
- n = s.size();
- for(int i = 0; i < n; i++) {
- arr[i] = s[i] - '0';
- }
- memset(bio, 0, sizeof bio);
- memset(bio2, 0, sizeof bio2);
- memset(bio3, 0, sizeof bio3);
- int ans = solve(0, false, true);
- for(int i = 1; i < n; i++) {
- ans = add(ans, solve(i, true, true));
- }
- return ans;
- }
- void reduce(string &s) {
- s[s.size() - 1]--;
- for(int i = s.size() - 1; i >= 0; i--) {
- if(s[i] < '0') {
- s[i] = '9';
- s[i - 1]--;
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- pot10[0] = 1;
- for(int i = 1; i < maxn; i++) {
- pot10[i] = mlt(pot10[i - 1], 10);
- }
- string s, z;
- cin >> s >> z;
- reduce(s);
- cout << sub(calc(z), calc(s)) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement