D - Palindromic Numbers (15-12)

#include <bits/stdc++.h>
#define int64_t long long
using namespace std;

int L, R;
int digit[50];
int64_t dp[50][50][2];
int num[50];

int64_t getNum(int pre, int pos, int start, bool limit) {
    if(pos == -1) return start;

    if(dp[pre][pos][start] != -1 && !limit)
        return dp[pre][pos][start];

    int64_t ans = 0;
    int up = (limit) ? digit[pos] : 9;

    for(int i = 0; i <= up; ++i) {
        num[pos] = i;
        if(pos == pre && i==0)
            ans += getNum(pre-1, pos-1, start, limit && i == up);
        else if(start && pos < (pre + 1)/2)
            ans += getNum(pre, pos-1, num[pre-pos] == i, limit && i == up);
        else
            ans += getNum(pre, pos-1, start, limit && i == up);
    }

    if(!limit)
        dp[pre][pos][start] = ans;

    return ans;
}

int64_t getDigits(int64_t x) {
    int pos = 0;
    while(x) {
        digit[pos++] = x % 10;
        x /= 10;
    }
    return getNum(pos - 1, pos - 1, 1, 1);
}

void solve(int Tcase) {
    if(L > R) swap(L, R);

    cout << "Case " << Tcase << ": " << getDigits(R) - getDigits(L - 1) << '\n';
}

int32_t main() {
#ifdef DN
    freopen("in.txt", "r", stdin);
#endif
    //freopen("D-Palindromic Numbers.inp", "r", stdin);
    //freopen("D-Palindromic Numbers.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= t; ++i) {
        cin >> L >> R;
        solve(i);
    }

    return 0;
}