数位dp 求l-r（10进制） 在k进制中有多少个回文数的模板

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
LL l, r;
int a[66];
LL dp[66][66][40];
LL dfs(int len, int l, int r, bool lim, bool ok,int k)//ok表示是回文串，k表示k进制
{


    if(l < r) return !lim || (lim && ok);
    if(!lim && ~dp[len][l][k]) return dp[len][l][k];
    LL ret = 0;
    int m = lim ? a[l] : (k-1);
    int i;
    for(i = 0; i <= m; i++)
    {
        if(l == len-1 && !i) continue;
        int g = ok;
        if(g) g = a[r] >= i;
        else g = a[r] > i;
        ret += dfs(len, l-1, r+1, lim&&i==m, g,k);
    }
    if(!lim) dp[len][l][k] = ret;
    return ret;
}


LL gao(LL n,int k)//n为数字，k为进制
{
    if(n < 0) return 0;
    if(n == 0) return 1;
    int len = 0;
    while(n) { a[len++] = n%k; n /= k; }
    LL ret = 1;
    int i;
    for(i = len; i >= 1; i--)//遍历回文数的长度
        ret += dfs(i, i-1, 0, i==len, 1,k);
    return ret;
}


int main()
{
    int i, cas,t1,t2;
    scanf("%d",&cas);
    memset(dp, -1, sizeof(dp));
    for(int ca = 1; ca <= cas; ca++)
    {
        scanf("%lld%lld%d%d",&l,&r,&t1,&t2);//求t1-t2进制有多少个回文串
        if(l > r) swap(l, r);
        LL res=0;
        for (int t=t1;t<=t2;t++)
         res+=(gao(r,t) - gao(l-1,t)) * (t-1) + r - l + 1;
        printf("Case #%d: %lld\n", ca,res);
    }
    return 0;
}