入门与面试 B3883

· · 题解

观前提示：本题解建议已经有数位 dp 基础的谷民食用。如果不知道什么是数位 dp，请移步 P2602，那里有非常详细的数位 dp 解析。

求回文数（加强版）题解

题意

给出一个正整数 n，求 [1,n] 中回文数的个数对 20091119 取模的值。

n≤10^{100}

思路

观察到 n 很大，可以考虑数位 dp。
简单思考可以发现，对于不足 n 位的数，可以提前计算出回文数的个数。
而对于 n 位的数，可以采用暴力求回文数的做法，枚举回文数的一半得到整个回文数，并用记忆化搜索优化。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105,MOD=20091119;
char s[MAXN];
int a[MAXN],len;
int dp[2][MAXN];
int temp[MAXN],total;
int check(){
    for(int i=total,j=(len>>1)+(len&1);i&&j;i--,j--){//+(len&1)判断奇/偶回文数。
        if(temp[i]>a[j]) return 0;
        if(temp[i]<a[j]) return 1;
    }
    return 1;
}
int dfs(bool lim,int pos){//lim为1时代表前面高位的都和原数一样，pos为当前下标。
    if(pos==(len>>1)){//枚举到一半。
        if(!lim) return 1;//如果lim为0，后面可以随便取，返回1。
        return check();//否则判断一下是否超出原数，仅会判断1次。
    }
    if(~dp[lim][pos]) return dp[lim][pos];
    int res=0;
    for(int i=0;i<=9;i++){
        if(pos==len&&!i) continue;//最高位必不等0。
        if(lim&&i>a[pos]) break;//超出原数就终止循环。
        temp[++total]=i;//存下回文数的一半。
        res=(res+dfs(lim&&i==a[pos],pos-1))%MOD;
        total--;
    }
    return dp[lim][pos]=res;
}
int solve(){
    for(int i=1;i<=len;i++) a[i]=s[len-i+1]-48;//转成数字，a[1]为个位。
    int res=0;
    for(int i=len-1;i;i--){
        int res2=9;//避免前导零。
        for(int j=i-1;j>(i>>1);j--) res2=(res2*10)%MOD;
        res=(res+res2)%MOD;
    }
    //提前计算不足n位的数的回文数个数。
    memset(dp,-1,sizeof(dp));
    res=(res+dfs(1,len))%MOD;
    return res;
}
int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    printf("%d",solve());
    return 0;
}