小象非常喜欢区间中的数.

此时他有一対整数l和r(l<=r). 小象需要找到满足以下条件的x(l<=x<=r),使得数x的第一个数字与最后一个数字相等. 例如, 101, 477474,9101,477474,9是符合这个条件的,而47, 253, 102047,253,1020则不符合.

请帮助他找到符合这个条件的数的数目.

输入格式:

一行两个数l,r(1<=l<=r<=10^18),意义如上.

题解：
数位dp模板

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 22;

int digit[maxn], tot, d;
ll dp[maxn][22];

ll dfs(int len, int top, int limit) {
    if (!len) {
        return 1;
    }
    if (!limit && dp[len][top] != -1) return dp[len][top];
    int up = (limit ? digit[len] : 9);
    ll res = 0;
    for (int i = 0; i <= up; i++) {
        if (len == 1) { //如果只剩下最后一位
            if (top == 0) { //如果最高位为0，剩下0-9都可以选择
                res += dfs(len - 1, (top?top:i), limit && (i == up));
            } else if(top == i) {//如果最高位不为0，最低位必须等于最高位topp
                res += dfs(len - 1, (top?top:i), limit && (i == up));
            }
        } else { //其他情况
            res += dfs(len - 1, (top?top:i), limit && (i == up));
        }

    }
    if (!limit) dp[len][top] = res;
    return res;
}

ll solve(ll n) {
    memset(dp, -1, sizeof(dp));
    tot = 0;
    while (n) {
        digit[++tot] = n % 10;
        n /= 10;
    }
    return dfs(tot, 0, 1);
}

int main() {
    //freopen("in.in", "r", stdin);
//    freopen("o2.out", "w", stdout);
    ll l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << endl;
    return 0;
}