Advertisement
kostes

Untitled

Dec 26th, 2018
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define all(c) c.begin(),c.end()
  4. #define f first
  5. #define s second
  6. using namespace std;
  7. typedef long long ll;
  8. const ll INF64 = 1e18 + 1337;
  9. const int INF32 = 1e9 + 228;
  10. const int MOD = 1e9 + 7;
  11. void plusOne(string& s)
  12. {
  13. s[s.length() - 1]++;
  14. int i = s.length() - 1;
  15. while(s[i] > '9')
  16. {
  17. if(i == 0)
  18. {
  19. string h = "1";
  20. for(int j = 0; j < s.length(); j++)
  21. h += "0";
  22. s = h;
  23. return;
  24. }
  25. s[i] = '0';
  26. s[i - 1]++;
  27. i--;
  28. }
  29. }
  30. ll formula(ll n, ll fd)
  31. {
  32. ll res = 1;
  33. set<ll> divide;
  34. for(int i = 2; i <= n - 1; i++)
  35. {
  36. divide.insert(i);
  37. }
  38. for(int k = 10 - fd; k < 9 + n - fd; k++)
  39. {
  40. res *= k;
  41. set<ll> buf;
  42. for(auto& it : divide)
  43. {
  44. if(res % it == 0)
  45. {
  46. res /= it;
  47. buf.insert(it);
  48. }
  49. }
  50. for(auto& it : buf)
  51. {
  52. divide.erase(it);
  53. }
  54. res %= MOD;
  55. //cerr << n << " " << fd << " " << res << "\n";
  56. }
  57. return res;
  58. }
  59. int main()
  60. {
  61. ios_base::sync_with_stdio(0);
  62. #ifndef __WIN32
  63. ifstream cin("input.txt");
  64. ofstream cout("output.txt");
  65. #endif
  66. cin.tie(0);cout.tie(0);
  67.  
  68. string l, r;
  69. cin >> l >> r;
  70. ///move l to number like 10000000..
  71. ///move r to number like 9999999..
  72. if(r.size() <= 4)
  73. {
  74. ll ans = 0;
  75. while(l != r)
  76. {
  77. bool tooManyBooleans = 0;
  78. for(int i = 1; i < l.length(); i++)
  79. {
  80. if(l[i] < l[i - 1])
  81. {
  82. tooManyBooleans = 1;
  83. break;
  84. }
  85. }
  86. if(!tooManyBooleans) ans++;
  87. plusOne(l);
  88. }
  89. cout << ans;
  90. return 0;
  91. }
  92. bool gofuckyourself = 0;
  93. for(int i = 1; i < r.size(); i++)
  94. {
  95. if(r[i - 1] > r[i])
  96. {
  97. gofuckyourself = 1;
  98. break;
  99. }
  100. }
  101. if(gofuckyourself)
  102. {
  103. string buf = "";
  104. for(int i = 0; i < r.size() - 1; i++)
  105. buf += "9";
  106. r = buf;
  107. }
  108. ll sum = 0;
  109. for(int n = l.size(); n <= r.size(); n++)
  110. {
  111. ll st = 1, en = 9;
  112. if(n == l.size())
  113. st = l[0] - '0';
  114. if(n == r.size())
  115. en = r[0] - '0';
  116. for(int fd = st; fd <= en; fd++)
  117. {
  118. sum += formula(n, fd);
  119. sum %= MOD;
  120. }
  121. }
  122. cout << sum;
  123.  
  124.  
  125. #ifndef __WIN32
  126. cin.close();
  127. cout.close();
  128. #endif
  129. return 0;
  130. }
  131. ///(9 + n - fd)!/((10 - fd)!*(n - 1)!)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement