hdu 6156 Palindrome Function

吐槽：比赛的时候智障了。。敲了一个多小时，最后有个地方忘了减1。。导致没做出来。。雪崩，还是数位DP做的比较少。

**题意：**f（n，k）表示n在k进制下是否为回文串，若是，f（n，k）=k，否则f（n，k）=1。

思路：数位DP，枚举进制，再枚举长度，可以搞出前一半，后一半翻转就好了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll ;
ll dp[][][];  //表示i进制下对称点是p，当前位置为pos的满足题意的个数。
int DIG[][];
ll dfs(int pos,int p , int lead,int jinzhi,int limit)
{
    if(pos < p)  //若过了对称点就返回
        return  ;
    if(!limit &&!lead && dp[jinzhi][p][pos] != -)
        return dp[jinzhi][p][pos];
    int end = limit ? DIG[jinzhi][pos] : jinzhi-;
    int ret = ;
    int st =  ;
    if(lead) st++;  //lead表示是否为第一个，第一个不能为0，0我们后面考虑
    for(int i = st ; i <= end ; i++)
        ret += dfs(pos-,p,,jinzhi,limit&&(end==i));
    if(!limit && !lead)
        dp[jinzhi][p][pos] = ret;
    return ret;
}
ll solve(ll n, ll l, ll r)
{
    ll ans =  ;
    ll tmp  ;
    ll now = ;   //now记录了是回文串的个数
    for(int i = l ; i <= r ; i++)   //枚举进制
    {
        int len =  ;
        tmp = n ;
        while(tmp)  //分解n
        {
            DIG[i][len++] = tmp % i ;
            tmp /= i ;
        }
        for(int j =  ; j <= len ; j++)  //枚举长度
        {
            tmp = j/;        //求出前面的长度
            ll t1 ;
            if(j == len) t1 = dfs(j-,tmp,,i,) ;  //若长度为len，考虑边界
            else t1 = dfs(j-,tmp,,i,);           
            ans += t1*i;
            now += t1 ;
            if(j == len)  //判边界条件
            {
                int ff = - ;
                for(int k = tmp- ; k >=  ; k--)
                    if(DIG[i][k] < DIG[i][len--k])
                    {
                        ff =  ; break ;
                    }
                    else if(DIG[i][k] > DIG[i][len--k])
                    {
                        ff =  ; break ;
                    }
                if(ff == ) //若原数字的前一半翻转过去后比原串大，就减去这种情况
                {
                    ans -= i ;
                    now -- ;  //就是这里，，我忘了减1。。
                }
            }
        }
        ans += i ; //0在这里加上去
    }
    ans += n*(r-l+)-now ;  //全部数减去回文串的个数，就是价值为1的数的个数
    return ans ;
}
int main()
{
    int t ;
    cin>> t ;
    int n1,n2,l,r;
    int count1 =  ;
    memset(dp,-,sizeof(dp));
    while(t--)
    {
        scanf("%d%d%d%d",&n1,&n2,&l,&r);
        ll ans = solve(n2,l,r) - solve(n1-,l,r);
        printf("Case #%d: %lld\n",++count1,ans);
    }
    return ;
}