洛谷 P3413 SAC#1

这道题用了正难则反的思想，毕竟正面求回文很麻烦，不知道长度也不知道位置。

但是可以求不构成回文的数然后做补集。

dp[i][j][k]表示前i位前两个数字是j，前一个数字是k，不构成回文的数量。

注意消除前导零的影响。

下附代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
ll dp[1005][10][10],dim[1005];
ll dfs(int x,int st,int pre,int jb,int fz){
    if (!x){
        return 1;
    }
    if (!jb && dp[x][st][pre]!=-1 && !fz && pre!=-1 && st!=-1) return dp[x][st][pre];
    ll ret=0;
    int maxn=9;
    if (jb) maxn=dim[x];
    for (int i=0; i<=maxn; i++){
        if (fz==1){
            if (i==0) ret=(ret+dfs(x-1,-1,-1,(jb==1 && i==maxn),1))%MOD;
            else ret=(ret+dfs(x-1,i,-1,(jb==1 && maxn==i),0))%MOD;
        }
        else {
           if (i!=st && i!=pre) ret=(ret+dfs(x-1,i,st,(jb==1 && maxn==i),0))%MOD;
        }
    }
    if (!jb && !fz && pre!=-1 && st!=-1) return dp[x][st][pre]=ret;
    return ret;
}
int main(){
    memset(dp,-1,sizeof(dp));
    string a,b;
    cin>>a>>b;
    for (int i=0; i<a.length(); i++){
        dim[a.length()-i]=a[i]-'0';
    }
    dim[1]-=1;
    int j=1;
    while (dim[j]<0){
        dim[j]+=10;
        dim[j+1]-=1;
        j++;
    }
    int len=a.length();
    while (dim[len]==0 && len>1) len--;
    ll l=dfs(len,-1,-1,1,1);
    for (int i=0; i<b.length(); i++){
        dim[b.length()-i]=b[i]-'0';
    }    
    ll r=dfs(b.length(),-1,-1,1,1);
    ll numl=0,numr=0;
    for (int i=0; i<a.length(); i++){
        numl=(numl*10+a[i]-'0'+MOD)%MOD;
    }
    numl=(numl-1+MOD)%MOD;
    for (int i=0; i<b.length(); i++){
        numr=(numr*10+b[i]-'0')%MOD;
    }
    printf("%lld",((numr-numl+MOD)%MOD-(r-l+MOD)%MOD+MOD)%MOD);
}