Lucky 数

题目描述

定义一个数为 (Lucky) 数当且仅当以这个数中心为轴的对应数位的值不相等。

1231不是 (Lucky) 数因为第一位和最后一位对应相等，而1234是 (Lucky) 数。

求给定区间 ([A,B]) 中 (Lucky) 数的个数

解法

容易想到从 数位dp 这方面入手。

显然轴的前面部分和后面部分的操作是不一样的，所以想到把其分成两次不同的计数。而因为有前导零的存在，数的位数不确定，那么轴的位置就是不确定的，所以一共需要记录四种标记：(st) 当前枚举到第几位，(lim) 是否达到上界，(lead) 是否有前导零，(len) 除去前导零后数的长度。第一个计数只分两种转移，若 (lead) 为真并且当前位不是 (0)，那么整个数的不为零部分就开始了，可以算出后面的长度 (cnt-now+1)，并将前导零标记设为 (0)；否则，则直接继承状态转移到下一位。当枚举的位置到了轴，分两种情况。若没有达到上界，则后面的每位都可以取 (9) 种值（除去轴前面对应的那个值），那么贡献就是 (9) 的后面数的位数次方；若达到上界，那么后面的数也要按上界处理，并保证对应位不相等即可，可以看出是一个简单的 (dp)，随便处理一下即可。

#include<stdio.h>
#include<string.h>
#define LL long long

int s[20],cnt=0;
LL dp1[20][20],pw[20]={1},dp2[20][20];

LL dfs2(int now,bool lim,int len) {
    if(now==cnt+1) return 1;
    if(!lim&&~dp2[now][len]) return dp2[now][len];
    int rg=lim? s[now]:9; LL ret=0;
    for(int i=0;i<=rg;i++){
        int pos=cnt*2-len-now+1;
        if(s[pos]!=i)
            ret+=dfs2(now+1,lim&(i==rg),len);
    }
    if(!lim) dp2[now][len]=ret;
    return ret;
}

LL dfs1(int now,bool lim,bool lead,int len) {
    if(cnt-len/2+1==now){
        memset(dp2,-1,sizeof(dp2));
        if(!lim) return pw[len>>1];
        else return dfs2(now,lim,len);
    }
    if(!lim&&!lead&&~dp1[now][len]) return dp1[now][len];
    int rg=lim? s[now]:9; LL ret=0;
    for(int i=0;i<=rg;i++){
        if(lead&&i) ret+=dfs1(now+1,lim&(i==rg),0,cnt-now+1);
        else ret+=dfs1(now+1,lim&(i==rg),lead,len);
    }
    if(!lim&&!lead) dp1[now][len]=ret;
    return ret;
}

inline void swap(int &x,int &y){x^=y,y^=x,x^=y;}
LL solve(LL x) {
    memset(dp1,-1,sizeof(dp1));
    cnt=0;
    while(x) s[++cnt]=x%10,x/=10;
    for(int i=1;i<=(cnt>>1);i++) swap(s[i],s[cnt-i+1]);
    return dfs1(1,1,1,0);
}

LL A,B;
int main() {
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    for(int i=1;i<=10;i++) pw[i]=pw[i-1]*9;
    scanf("%lld%lld",&A,&B);
    printf("%lld",solve(B)-solve(A-1));
}