Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- // dp[i][j] - кол-во чисел длины i с последней цифрой j,
- const int MOD = 1e9 + 7;
- typedef long long ll;
- int count(const string &s) {
- vector<vector<int>> dp((int)s.size() + 1, vector<int>(10, 0));
- for(int j = 0; j <= s[0] - '0'; j++){
- dp[1][j] = 1;
- }
- for(int len = 2; len <= (int)s.size(); len++) {
- for(int from = 0; from <= (s[len - 2] - '0'); from++) {
- for(int last = from; last <= 9; last++) {
- if(from < (s[len - 2] - '0')) {
- dp[len][last] += dp[len - 1][from];
- } else {
- assert(from == (s[len - 2] - '0'));
- if(last >= (s[len - 1] - '0')) continue;
- dp[len][last] = 1;
- }
- }
- }
- }
- printf("ans = %d\n", dp[(int)s.size()][s.back() - '0']);
- return dp[(int)s.size()][s.back() - '0'];
- }
- int main() {
- string left, right;
- cin >> left >> right;
- printf("%d", (int)(count(right) - count(left)));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement