Advertisement
Guest User

Untitled

a guest
Jan 20th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // dp[i][j] - кол-во чисел длины i с последней цифрой j,
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. typedef long long ll;
  9.  
  10. int count(const string &s) {
  11. vector<vector<int>> dp((int)s.size() + 1, vector<int>(10, 0));
  12. for(int j = 0; j <= s[0] - '0'; j++){
  13. dp[1][j] = 1;
  14. }
  15. for(int len = 2; len <= (int)s.size(); len++) {
  16. for(int from = 0; from <= (s[len - 2] - '0'); from++) {
  17. for(int last = from; last <= 9; last++) {
  18. if(from < (s[len - 2] - '0')) {
  19. dp[len][last] += dp[len - 1][from];
  20. } else {
  21. assert(from == (s[len - 2] - '0'));
  22. if(last >= (s[len - 1] - '0')) continue;
  23. dp[len][last] = 1;
  24. }
  25. }
  26. }
  27. }
  28. printf("ans = %d\n", dp[(int)s.size()][s.back() - '0']);
  29. return dp[(int)s.size()][s.back() - '0'];
  30. }
  31.  
  32. int main() {
  33. string left, right;
  34. cin >> left >> right;
  35. printf("%d", (int)(count(right) - count(left)));
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement