学习数位DP
在我们遇到一些什么对于一个区间内的数字找符合要求的个数或求和时，我们可能会想到枚举，但当$l,r$过大时我们便会难以枚举，这个时候就需要用到数位$DP$了,然而有一说一，这个数位$DP$不过只是把枚举的方法换了下而已，但对我这样的蒟蒻来说还是很难。
举个例子吧
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
1 <= A <= B <= 2000000000这道题明显暴力会超时，虽然有些大佬用分块打表过了，但正解还是数位DP，推荐作为数位DP的入门题。
这种题目怎么做呢，我们可以暴力枚举$[l,r]$然后每一位判断，显然，这是极为小学生的思路，身为拥有着更丰富(被吊打)经验的初中生。显然可以直接枚举每一位然后按照下界上界来算，但是又要维护上界又要维护下界(我是届不到)。所以我们可以运用前缀和的思想，便可以去掉下界这一约束。然后就简单多了，做这种题目有一个套路，便是记忆化搜索。先考虑要维护什么东西（1.当前位置now 2.是否有最高位限制limit 这两个是必备的都会用到）然后就是额外的，不难发现，我们需要维护上一位数字是什么，所以搞一个last记录下。还有是否有前导零，这个某些题（如此题需要）然后猛套板子。
long long dfs(long long now,bool limit,long long last,bool is_zero)//注意是从高位到低位
{
if (now>len) return 1;
if (!limit&&f[now][last]!=-1&&(!is_zero)) return f[now][last];//注意一下如果上一位没取满才可以记忆化，这个可以自己想一下
long long res=0,Max=limit?a[len-now+1]:9;//如果上一位是已经到最高值了，那么这一位必须要小于上界限制，否则可以取到9
for (long long i=0;i<=Max;i++)//枚举当前位
{
if (abs(i-last)<2) continue;
res+=dfs(now+1,limit&&(i==Max),(i==0)&&is_zero?-2:i,(i==0)&&is_zero);
}
if (!limit&&(!is_zero)) f[now][last]=res;
return res;
}上面的代码不保证正确，因为是我在写这篇博客的时候徒手撸的，我在做这题的时候还没有学会简单的记忆化代码，所以打了DP。额，好吧记忆化过了，那就一起放吧。
//记忆化
#include<bits/stdc++.h>
using namespace std;
long long f[20][20],l,r,len,a[20];
long long dfs(long long now,bool limit,long long last,bool is_zero)//注意是从高位到低位
{
if (now>len) return 1;
if (!limit&&f[now][last]!=-1&&(!is_zero)) return f[now][last];//注意一下如果上一位没取满才可以记忆化，这个可以自己想一下
long long res=0,Max=limit?a[len-now+1]:9;//如果上一位是已经到最高值了，那么这一位必须要小于上界限制，否则可以取到9
for (long long i=0;i<=Max;i++)//枚举当前位
{
if (abs(i-last)<2) continue;
res+=dfs(now+1,limit&&(i==Max),(i==0)&&is_zero?-2:i,(i==0)&&is_zero);
}
if (!limit&&(!is_zero)) f[now][last]=res;
return res;
}
inline long long solve(long long x)
{
len=0;
while (x){a[++len]=x%10;x/=10;}
memset(f,-1,sizeof(f));
return dfs(1,1,-2,1);
}
int main()
{
scanf("%lld%lld",&l,&r);
cout<<solve(r)-solve(l-1)<<endl;
return 0;
} //DP
#include<bits/stdc++.h>
using namespace std;
long long l,r;
long long solve(long long x)
{
long long ans=0,num[15],g[15][10],len=0;
memset(num,0,sizeof(num));
memset(g,0,sizeof(g));
while (x) {num[++len]=x%10;x/=10;}
for (long long i=0;i<=9;i++) g[1][i]=1LL;
for (long long i=1;i<=len-1;i++)
for (long long j=0;j<=9;j++)
for (long long k=0;k<=9;k++)
if (abs(j-k)>=2) g[i+1][j]+=g[i][k];
for (long long i=1;i<=len-1;i++)
for (long long j=1;j<=9;j++) ans+=g[i][j];
for (long long i=1;i<=num[len]-1;i++) ans+=g[len][i];
for (long long i=len-1;i>=1;i--)
{
for (long long j=0;j<=num[i]-1;j++)
if (abs(j-num[i+1])>=2) ans+=g[i][j];
if (abs(num[i]-num[i+1])<2) break;
}
return ans;
}
int main()
{
scanf("%lld%lld",&l,&r);
cout<<solve(r)-solve(l)<<endl;
return 0;
}是个人都看得出来记忆化简单，那就让我们学习下记忆化的套路吧（以下为例题讲解与板子分析）
例题讲解
[CQOI2016]手机号码
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个：号码中要出现至少 $33$ 个相邻的相同数字；号码中不能同时出现 $88$ 和$ 44$。号码必须同时包含两个特征才满足条件。满足条件的号码例如：$13000988721$、$23333333333$、$14444101000$。而不满足条件的号码例如：$1015400080$、$10010012022$。
手机号码一定是 $11 $位数，前不含前导的 $0$。工具接收两个数 $L$ 和$ R$，自动统计出 $[L,R]$ 区间内所有满足条件的号码数量。$L$和 $R$也是$11$ 位的手机号码。
思路
这题不难，我们只需要记录下前一位是什么数，前前一位是什么数，以及是否以及出现过相邻数字，还有是否有$4$，是否有$8$即可，这些都很简单，而且最主要的是这题不需要记录有无前导零，因为都是$11$位数字，没有影响，这题算是给大家加强一下数位dp吧，毕竟维护的值较多，而且也想告诉大家不是每个数位DP都要记录有无前导零的，这只是一种情况。
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL L,R,top,a[20],f[20][20][20][2][2][2];
LL dfs(LL now,LL las,LL laslas,bool flag,bool is_four,bool is_eight,bool limit)
{
if (now>top) return flag;
if (f[now][las][laslas][flag][is_four][is_eight]!=-1&&limit==0) return f[now][las][laslas][flag][is_four][is_eight];
LL Max=limit?a[top-now+1]:9;
LL res=0;
for (int i=(now==1);i<=Max;i++)
{
if (i==4&&is_eight) continue;
if (i==8&&is_four) continue;
res+=dfs(now+1,i,las,(i==las&&las==laslas)||flag,is_four||(i==4),is_eight||(i==8),limit&&(i==Max));
}
if (!limit) f[now][las][laslas][flag][is_four][is_eight]=res;
return res;
}
LL solve(LL x)
{
if (x<1e10) return 0;//坑，小于11位直接返回0
memset(f,-1,sizeof(f));
top=0;
while (x){a[++top]=x%10;x/=10;}
return dfs(1,10,10,0,0,0,1);
}
int main()
{
scanf("%lld%lld",&L,&R);
cout<<solve(R)-solve(L-1)<<endl;
return 0;
} 烦人的数学作业
题目大意：给定$[l,r]$，求$[l,r]$范围内数的数位之和对$10^9+7$取模。
思路
这题也不多$bb$了吧，经过上一道题的洗礼，直接记录当前数位和$now>len$时返回$sum$即可，同样，这题也不需要记录前导0。因为0对于和是没有影响的，这也是一种不需要记录前导零的情况。
代码
#include<bits/stdc++.h>
#define Mod 1000000007
#define LL long long
using namespace std;
LL l,r,f[20][200],T,a[20],top;
LL dfs(LL now,LL sum,LL limit)
{
if (now>top) return sum;
if (f[now][sum]!=-1&&(!limit)) return f[now][sum];
LL Max,res=0;
if (limit) Max=a[top-now+1];else Max=9;
for (int i=0;i<=Max;i++)
{
res+=dfs(now+1,sum+i,limit&&i==a[top-now+1]);
res%=Mod;
}
if (!limit) f[now][sum]=res;
return res;
}
LL solve(LL x)
{
top=0;
memset(a,0,sizeof(a));
while (x){a[++top]=x%10;x/=10;}
memset(f,-1,sizeof(f));
return dfs(1,0,1)%Mod;
}
int main()
{
scanf("%lld",&T);
while (T--)
{
scanf("%lld%lld",&l,&r);
cout<<(solve(r)-solve(l-1)+Mod)%Mod<<endl;
}
return 0;
}[AHOI2009]同类分布
给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。
思路
经典套路题，但是发现数字太大了，存不下，怎么办？
枚举各位数字之和，边把当前数字*10+i边取模这个枚举的和，如果最后的数位和=你枚举的数，那么就记录进答案贡献。变换思维的好题目，做题目不要死脑筋。
#include<bits/stdc++.h>
using namespace std;
long long l,r,len,a[20],f[20][205][205];
inline long long dfs(long long now,bool limit,long long ans,long long sum,long long Mod)
{
if (now>len)
{
if ((ans%Mod==0)&&(sum==Mod)) return 1;
else return 0;
}
if (!limit&&f[now][ans][sum]!=-1) return f[now][ans][sum];
long long Max,res=0;
if (limit) Max=a[len-now+1];else Max=9;
for (long long i=0;i<=Max;i++)
{
res+=dfs(now+1,i==Max&&limit,(ans*10+i)%Mod,sum+i,Mod);
}
if (!limit) f[now][ans][sum]=res;
return res;
}
long long solve(long long x)
{
long long res=0;
len=0;
while (x){a[++len]=x%10;x/=10;}
for (long long Mod=1;Mod<=len*9;Mod++)
{
memset(f,-1,sizeof(f));
res+=dfs(1,1,0,0,Mod);
}
return res;
}
int main()
{
scanf("%lld%lld",&l,&r);
cout<<solve(r)-solve(l-1)<<endl;
return 0;
}