Advertisement
Galebickosikasa

Untitled

Aug 23rd, 2020
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.24 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 cnt[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. reverse (all (a));
  102. while (sz (a) < sz (b)) a.pb ('0');
  103. reverse (all (a));
  104. int j = 0;
  105. while (j < sz (a) && a[j] == b[j]) ++j;
  106. if (j == sz (a)) {
  107. cout << 0 << '\n';
  108. exit (0);
  109. }
  110. int s = a[j] - '0', t = b[j] - '0';
  111. for (int i = s; i <= t; ++i) cnt[j][i] = 1;
  112. for (int i = j + 1; i < sz (a); ++i) {
  113. int sum = 0;
  114. fr (k, 10) sum += cnt[i - 1][k];
  115. --sum;
  116. s = a[i] - '0', t = b[i] - '0';
  117. fl (z, s, 10) cnt[i][z] += 1;
  118. --sum;
  119. fr (z, 10) cnt[i][z] += sum;
  120. fr (z, t + 1) ++cnt[i][z];
  121. for (auto& x: cnt[i]) x %= mod;
  122. }
  123. // cnt[0][0] = 9;
  124. // if (a[0] == '0') {
  125. // int gay = 0;
  126. // fr (k, sz (a)) {
  127. // gay = mult (gay, 10);
  128. // gay = add (gay, a[k] - '0');
  129. // }
  130. // dbg (gay);
  131. // while (a[j] == '0') {
  132. // if (j == 0) cnt[j][0] = powmod (10, sz (a) - j - 1) - gay;
  133. // else cnt[j][0] += powmod (10, sz (a) - j - 1) - gay;
  134. // cnt[j][0] %= mod;
  135. // ++j;
  136. // }
  137. // j = 0;
  138. // }
  139.  
  140. int ans = 0;
  141. fl (k, j, sz (a)) {
  142. fr (i, 10) {
  143. dbg (k);
  144. dbg (i);
  145. dbg (cnt[k][i]);
  146. fl (j, i + 1, 10) {
  147. ans += (j - i) * cnt[k][i] * cnt[k][j] % mod;
  148. if (ans >= mod) ans -= mod;
  149. }
  150. }
  151. }
  152. cout << ans * 2 % mod << '\n';
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement