[CSES] Counting Numbers

ll dp[22][10][2];
ll get_dp(ll i, ll last_digit, string a, bool tight)
{
    // ans for numbers calculated till ith digit which ends at last_digit
    if (dp[i][last_digit][tight] != -1)
        return dp[i][last_digit][tight];

    if (i == sz(a))
    {
        return dp[i][last_digit][tight] = 1;
    }

    ll ans = 0LL, ad = a[i] - '0';
    if (i == 0)
    {
        rep(d, ad + 1)
        {
            if (d == 0)
                continue;
            if (d < ad)
                ans += get_dp(i + 1, d, a, 0);
            else if (d == ad)
                ans += get_dp(i + 1, d, a, 1);
        }
    }
    else
    {
        if (!tight)
        {
            rep(d, 10)
            {
                if (d != last_digit)
                    ans += get_dp(i + 1, d, a, tight);
            }
        }
        else
        {
            rep(d, ad + 1)
            {
                if (d != last_digit)
                {
                    if (d < ad)
                        ans += get_dp(i + 1, d, a, 0);
                    else
                        ans += get_dp(i + 1, d, a, 1);
                }
            }
        }
    }

    return dp[i][last_digit][tight] = ans;
}

ll get_ans(ll i, ll last_digit, ll a, bool tight)
{
    if (a < 0)
        return 0LL;
    if (a < 10)
        return a + 1LL;

    ll cnt = 1LL, temp = 10LL, ans = 0LL;
    while (temp - 1 < a)
    {
        if (temp - 1 == 9)
        {
            ans += 10;
        }
        else
        {
            rep(i, cnt + 1) rep(j, 10) rep(k, 2) dp[i][j][k] = -1;
            ans += get_dp(0, 0, to_string(temp - 1), 0);
        }
        
        ++cnt;
        temp *= 10;
    }

    rep(i, cnt + 1) rep(j, 10) rep(k, 2) dp[i][j][k] = -1;
    ans += get_dp(0, 0, to_string(a), 0);

    return ans;
}
void solve()
{
    ll a, b;
    cin >> a >> b;

    --a;

    ll ansA = get_ans(0, 0, a, 0);
    ll ansB = get_ans(0, 0, b, 0);
    debug(a, b, ansA, ansB);

    cout << ansB - ansA << "\n";
}