Advertisement
kostes

Untitled

Dec 26th, 2018
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 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. do
  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.  
  87. if(!tooManyBooleans) ans++;
  88. if(l==r) break;
  89. plusOne(l);
  90. }while(1);
  91. cout << ans;
  92. return 0;
  93. }
  94. bool gofuckyourself = 0;
  95. for(int i = 1; i < r.size(); i++)
  96. {
  97. if(r[i - 1] > r[i])
  98. {
  99. gofuckyourself = 1;
  100. break;
  101. }
  102. }
  103. if(gofuckyourself)
  104. {
  105. string buf = "";
  106. for(int i = 0; i < r.size() - 1; i++)
  107. buf += "9";
  108. r = buf;
  109. }
  110. ll sum = 0;
  111. for(int n = l.size(); n <= r.size(); n++)
  112. {
  113. ll st = 1, en = 9;
  114. for(int fd = st; fd <= en; fd++)
  115. {
  116. sum += formula(n, fd);
  117. sum %= MOD;
  118. }
  119. }
  120. cout << sum;
  121.  
  122.  
  123. #ifndef __WIN32
  124. cin.close();
  125. cout.close();
  126. #endif
  127. return 0;
  128. }
  129. ///(9 + n - fd)!/((10 - fd)!*(n - 1)!)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement