Advertisement
Galebickosikasa

Untitled

Aug 23rd, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.02 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3. // #pragma comment(linker, "/stack:200000000"]
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <stack>
  17. #include <random>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define ll long long
  26. #define ld long double
  27. #define hm unordered_map
  28. #define pii pair<int, int>
  29. #define sz(a) (int)a.size()
  30. #define all(a) a.begin(), a.end()
  31. #define cinv(v) for (auto& x: v) cin >> x
  32. #define fr(i, n) for (int i = 0; i < n; ++i)
  33. #define fl(i, l, n) for (int i = l; i < n; ++i)
  34.  
  35. #define int ll
  36.  
  37. using namespace std;
  38.  
  39. #ifdef __LOCAL
  40. #define dbg(x) cerr << #x << " : " << x << '\n'
  41. const int maxn = 20;
  42. #else
  43. #define dbg(x)
  44. const int maxn = 5e4 + 20;
  45. #endif
  46.  
  47. //tg: @galebickosikasa
  48.  
  49. ostream& operator << (ostream& out, vector<int>& v) {
  50. for (auto& x: v) out << x << ' ';
  51. return out;
  52. }
  53.  
  54. ostream& operator << (ostream& out, pii& v) {
  55. out << v.fi << ", " << v.se;
  56. return out;
  57. }
  58.  
  59. istream& operator >> (istream& in, pii& a) {
  60. in >> a.fi >> a.se;
  61. return in;
  62. }
  63.  
  64. const ll inf = (ll) 2e9;
  65. const ld pi = asin (1) * 2;
  66. const ld eps = 1e-8;
  67. const ll mod = (ll)1e9 + 7;
  68. const ll ns = 97;
  69.  
  70. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  71.  
  72. ll mult (ll a, ll b) {
  73. return a * b % mod;
  74. }
  75.  
  76. ll add (ll a, ll b) {
  77. int c = a + b;
  78. if (c >= mod) c -= mod;
  79. return c;
  80. }
  81.  
  82. ll powmod (ll a, ll n) {
  83. if (n == 0) return 1;
  84. if (n % 2) return mult (a, powmod (a, n - 1));
  85. ll b = powmod (a, n / 2);
  86. return mult (b, b);
  87. }
  88.  
  89. ll inv (int a) {
  90. return powmod (a, mod - 2);
  91. }
  92.  
  93. int cnt1[maxn][10], cnt2[maxn][10], dp[maxn][10];
  94.  
  95. signed main () {
  96. ios_base::sync_with_stdio(false);
  97. cin.tie(nullptr);
  98. cout.tie(nullptr);
  99. string a, b;
  100. cin >> a >> b;
  101. if (a == b) {
  102. cout << 0 << '\n';
  103. exit (0);
  104. }
  105. reverse (all (a));
  106. int t = 0;
  107. reverse (all (b));
  108. int j = sz (a) - 1;
  109. while (j >= 0 && a[j] == b[j]) --j;
  110. int sum = 0;
  111. for (int i = sz (a) - 1; i >= 0; --i) {
  112. sum = (sum * 10 + a[i] - '0') % mod;
  113. }
  114. ++sum;
  115. fl (i, 1, sz (a)) {
  116. int x = a[i] - '0';
  117. t = add (t, powmod (10, i - 1) * x % mod);
  118. }
  119.  
  120. fr (i, 10) cnt1[0][i] = t;
  121. int s = a[0] - '0';
  122. fr (i, s + 1) ++cnt1[0][i];
  123. fl (i, 1, sz (a)) {
  124. s = a[i] - '0';
  125. t -= powmod (10, i - 1) * s;
  126. if (t < 0) t += mod;
  127. fr (k, 10) cnt1[i][k] = t;
  128. fr (k, s + 1) cnt1[i][k] = add (cnt1[i][k], powmod (10, i));
  129. }
  130.  
  131. int r = 0;
  132. for (auto& x: cnt1[sz (a) - 1]) r += x;
  133. r -= cnt1[sz (a) - 1][s];
  134. cnt1[sz (a) - 1][s] = sum - r;
  135. if (cnt1[sz (a) - 1][s] < 0) cnt1[sz (a) - 1][s] += mod;
  136. fl (i, sz (a), sz (b)) cnt1[i][0] = sum;
  137.  
  138. sum = 0;
  139. t = 0;
  140. for (int i = sz (b) - 1; i >= 0; i--) {
  141. sum = (sum * 10 + b[i] - '0') % mod;
  142. }
  143. ++sum;
  144. fl (i, 1, sz (b)) {
  145. int x = b[i] - '0';
  146. t = add (t, powmod (10, i - 1) * x % mod);
  147. }
  148. fr (i, 10) cnt2[0][i] = t;
  149. s = b[0] - '0';
  150. fr (i, s + 1) ++cnt2[0][i];
  151. fl (i, 1, sz (b)) {
  152. s = b[i] - '0';
  153. t -= powmod (10, i - 1) * s;
  154. if (t < 0) t += mod;
  155. fr (k, 10) cnt2[i][k] = t;
  156. fr (k, s + 1) cnt2[i][k] = add (cnt2[i][k], powmod (10, i));
  157. }
  158. r = 0;
  159. for (auto& x: cnt2[sz (b) - 1]) r += x;
  160. r -= cnt2[sz (b) - 1][s];
  161. cnt2[sz (b) - 1][s] = sum - r;
  162. if (cnt2[sz (b) - 1][s] < 0) cnt2[sz (b) - 1][s] += mod;
  163.  
  164. s = a[0] - '0';
  165. --cnt1[sz (a) - 1][s];
  166. ++cnt1[0][0];
  167. for (auto& x: cnt1) --x[0];
  168. fr (i, sz (b)) {
  169. fr (k, 10) {
  170. dbg (i);
  171. dbg (k);
  172. dbg (cnt1[i][k]);
  173. dbg (cnt2[i][k]);
  174. dp[i][k] = cnt2[i][k] - cnt1[i][k];
  175. dbg (dp[i][k]);
  176. }
  177. }
  178. int ans = 0;
  179. fr (i, sz (b)) {
  180. fr (ii, 10) {
  181. fl (jj, ii + 1, 10) {
  182. ans = add (ans, (jj - ii) * dp[i][ii] * dp[i][jj] % mod);
  183. }
  184. }
  185. }
  186. cout << ans * 2 % mod << '\n';
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement