[数位dp] Jzoj P3316 非回文数字

Description

如果一个字符串从后往前读与从前往后读一致，我们则称之为回文字符串。当一个数字不包含长度大于1的子回文数字时称为非回文数字。例如，16276是非回文数字，但17276不是，因为它包含回文数字727。

你的任务是在一个给定的范围内计算非回文数字的总数。

Input

输入仅一行，包含两个整数a和b。

Output

输出仅一行，包含一个整数，表示a到b范围内（包括a和b）非回文数字的总数。

Sample Input

输入1：

123 321

输入2：

123456789 987654321

Sample Output

输出1：

153

输出2：

167386971

Data Constraint

25%的数据：b-a<=100 000.

100%的数据：0<=a<=b<=10^18

题解

f[len][pre][pre2][zero1][zero2][0/1]表示第len位，第len-1位是pre，第len-2位是pre2，第len-1位是否是前导零，第len-2位是否是前导零，是否到达上界的方案数
然后记忆化深搜就可以过了

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define ll long long
 5 using namespace std;
 6 ll a,b,len,f[20][10][10][2][2][2],s[20];
 7 ll dp(int l,int fi,int se,bool bz1,bool bz2,bool bz)
 8 {
 9     if (l>len) return 1;
10     if (f[l][fi][se][bz1][bz2][bz]) return f[l][fi][se][bz1][bz2][bz];
11     ll sum=0;
12     if (bz)
13     {
14         for (int i=0;i<=s[l];i++) if ((bz1||i!=fi)&&(bz2||i!=se)) sum+=dp(l+1,i,fi,bz1&&(i==0),bz1,bz&&i==s[l]);
15         return f[l][fi][se][bz1][bz2][bz]=sum;
16     }
17     else
18     {
19         for (int i=0;i<=9;i++) if ((bz1||i!=fi)&&(bz2||i!=se)) sum+=dp(l+1,i,fi,bz1&&(i==0),bz1,0);
20         return f[l][fi][se][bz1][bz2][bz]=sum;
21     }
22 }
23 ll calc(ll x)
24 {
25     memset(f,0,sizeof(f)),len=0;
26     if (x<0) return 0;     
27     while (x) s[++len]=x%10,x/=10;
28     for (int i=1;i<=len/2;i++) swap(s[i],s[len-i+1]);
29     return dp(1,0,0,1,1,1); 
30 }
31 int main()
32 {
33     scanf("%lld%lld",&a,&b),a--,printf("%lld",calc(b)-calc(a));
34 }