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 ;
}