Advertisement
Galebickosikasa

Untitled

Aug 23rd, 2020
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.38 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 = 2e5 + 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 MAX_SIZE = 0;
  94.  
  95. vector<vector<int>> get (string s) {
  96. int sum = 0;
  97. fr (i, sz (s)) {
  98. sum = (sum * 10 + s[i] - '0') % mod;
  99. }
  100. ++sum;
  101. vector<vector<int>> ans = vector<vector<int>> (sz (s), vector<int> (10));
  102. int t = 0;
  103. reverse (all (s));
  104. fl (i, 1, sz (s)) {
  105. t = add (t, powmod (10, i - 1) * (s[i] - '0') % mod);
  106. }
  107. fr (i, 10) ans[0][i] = t;
  108. fr (i, s[0] - '0' + 1) ++ans[0][i];
  109. fl (i, 1, sz (s)) {
  110. t -= powmod (10, i - 1) * (s[i] - '0') % mod;
  111. if (t < 0) t += mod;
  112. fr (j, 10) ans[i][j] = t;
  113. int r = (t * 10 + powmod (10, i) * (s[i] - '0')) % mod;
  114. fr (j, s[i] - '0') ans[i][j] = add (ans[i][j], powmod (10, i));
  115. ans[i][s[i] - '0'] = sum - r;
  116. if (ans[i][s[i] - '0'] < 0) ans[i][s[i] - '0'] += mod;
  117. }
  118. vector<int> tmp (10);
  119. tmp[0] = sum - 1;
  120. while (sz (ans) < MAX_SIZE) ans.pb (tmp);
  121. return ans;
  122. }
  123.  
  124. signed main () {
  125. ios_base::sync_with_stdio(false);
  126. cin.tie(nullptr);
  127. cout.tie(nullptr);
  128. string a, b;
  129. cin >> a >> b;
  130. MAX_SIZE = sz (b);
  131. auto x = get (a), y = get (b);
  132. // --x[sz (a) - 1][a[0] - '0'];
  133. reverse (all (a));
  134. fr (i, sz (a)) --x[i][a[i] - '0'];
  135. vector<vector<int>> d (sz (b), vector<int> (10));
  136. fr (i, sz (b)) {
  137. fr (j, 10) {
  138. d[i][j] = y[i][j] - x[i][j];
  139. dbg (i);
  140. dbg (j);
  141. dbg (d[i][j]);
  142. dbg (x[i][j]);
  143. dbg (y[i][j]);
  144. }
  145. }
  146. int ans = 0;
  147. fr (k, sz (b)) {
  148. fr (i, 10) {
  149. fr (j, 10) {
  150. ans = add (ans, abs (i - j) * d[k][i] * d[k][j] % mod);
  151. }
  152. }
  153. }
  154. cout << ans << '\n';
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement