Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "NROLOGY"
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- constexpr int N = 5e2 + 5;
- constexpr ll mod = 1e9 + 7;
- string b, s;
- ll dp[N][N][2][3], cnt[N][N][2][3];
- ll Pow[N];
- ll d[N][N], c[N][N];
- int n, m;
- void Read()
- {
- cin >> s >> b;
- reverse(b.begin(), b.end());
- while (b.size() < s.size())
- b.push_back('0');
- reverse(b.begin(), b.end());
- n = b.size();
- m = s.size();
- b = " " + b + " ";
- s = " " + s + " ";
- }
- ll toll(const string s)
- {
- ll ans(0);
- for (auto i : s)
- ans = ans * 10 + i - '0';
- return ans;
- }
- #define bit(i, x) (((x) >> (i)) & 1)
- ll f(int l, int r, bool okl, int okr)
- {
- ll &ans = dp[l][r][okl][okr], &res = cnt[l][r][okl][okr];
- if (ans != -1)
- return ans;
- int pos = n - (l + (n + 1 - r));
- if (pos == 0)
- {
- res = (okl || okr != 2);
- return ans = 0;
- }
- ans = 0;
- res = 0;
- if (okl || s[pos] <= b[l + 1])
- {
- (ans += f(l + 1, r, okl || s[pos] < b[l + 1], okr)) %= mod;
- (ans += (s[pos] - '0') * Pow[n - (l + 1)] % mod * cnt[l + 1][r][okl || s[pos] < b[l + 1]][okr] % mod) %= mod;
- (res += cnt[l + 1][r][okl || s[pos] < b[l + 1]][okr]) %= mod;
- }
- {
- int t;
- if (s[pos] > b[r - 1])
- t = 2;
- else if (s[pos] < b[r - 1])
- t = 1;
- else
- t = okr;
- (ans += f(l, r - 1, okl, t)) %= mod;
- (ans += (s[pos] - '0') * Pow[n - (r - 1)] % mod * cnt[l][r - 1][okl][t] % mod) %= mod;
- (res += cnt[l][r - 1][okl][t]) %= mod;
- }
- return ans;
- }
- ll g(int l, int r)
- {
- ll &ans = d[l][r],
- &res = c[l][r];
- if (ans != -1)
- return ans;
- ans = 0;
- res = 0;
- int pos = m - (l + (m + 1 - r));
- if (l + 1 == r)
- {
- res = 1;
- return 0;
- }
- {
- (ans += g(l + 1, r)) %= mod;
- (ans += (s[pos] - '0') * Pow[m - (l + 1)] % mod * c[l + 1][r] % mod) %= mod;
- (res += c[l + 1][r]) %= mod;
- };
- {
- (ans += g(l, r - 1)) %= mod;
- (ans += (s[pos] - '0') * Pow[m - (r - 1)] % mod * c[l + 1][r] % mod) %= mod;
- (res += c[l][r - 1]) %= mod;
- }
- return ans;
- }
- void Solve()
- {
- Pow[0] = 1;
- for (int i = 1; i <= n; ++i)
- Pow[i] = Pow[i - 1] * 10 % mod;
- if (s.size() < b.size())
- {
- memset(d, -1, sizeof d);
- cout << g(0, m + 1) * 500000004 % mod;
- }
- else
- {
- memset(dp, -1, sizeof dp);
- cout << f(0, n + 1, 0, 0) * 500000004 % mod;
- }
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement