$P4124 [CQOI2016] $*

#$Description$ [题面](https://www.luogu.org/problem/P4124) 给定$[L,R]$，求在$[L,R]$内满足下列条件的数的个数: $1.$长度为$11$，不含前导零 $2.$存在三个相邻的数相等 $3.$不能同时出现$4、8$ #$Solution$ 数位$DP$我习惯于写递推版本，于是预处理就崩溃了 [](https://imgchr.com/i/MQVaon) 发现预处理需要考虑的情况太多了，看了看题解，基本也都是$6、7$层$for$循环 于是我学习了下记忆化搜索数位$DP$ 它的优点在于不需要预处理（把数位拆开还是要处理的），代码量小且比较好理解，大概结构是这么写 ``` ll dfs(int p,int a,int c,int d,int flag) { //p表示当前位置,a表示上一位（或其他）状态,c(0/1)表示是否小于边界（就是不卡在最大值上） //d=1表示不用考虑前导零了，否则还处于前导零（这个模板不写也可以，因为讨论过了），flag记录其他状态 if(!flag) return 0; if(p<=0) return 1;//递归边界 if(~f[p][a][b][c][d][flag]) return f[p][a][b][c][d][flag];//记忆化 int lim=(d?9:tmp[p]);//表示当前位枚举边界 ll res=0; for(int i=0;i<=lim;++i) res+=dfs(p-1,i, c||i对于本题，需要注意不用考虑前导零而缩小位数，唯一的坑点就是题目范围给错了，特判一下吧

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
using namespace std;
inline ll read()
{
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll a,b,dp[15][11][11][2][2][2][2],cnt,tmp[15];
ll dfs(int p,int a,int b,int c,int d,int _4,int _8)
{
	//a表示上一位,b表示上上位 
	//c表示是否小于边界,d表示是否出现三个相同的数
	if(_4&&_8) return 0;
	if(p<=0) return d;//如果枚举完看看有没有出现三个相等的情况 
	if(~dp[p][a][b][c][d][_4][_8]) return dp[p][a][b][c][d][_4][_8];//记忆化啊 
	int lim=(c?9:tmp[p]);
	ll res=0;
	for(int i=0;i<=lim;++i)
	 res+=dfs(p-1,i,a,c||(i<lim),d||(i==a&&i==b),_4||(i==4),_8||(i==8));//注意这些取逻辑或的地方 
	return dp[p][a][b][c][d][_4][_8]=res;
}
ll calc(ll x)
{
	if(x<1e10) return 0;//这真是个大坑，数据范围出锅了，题目保证>=10^10但出现了x<10^10
	//这种情况不是手机号
	memset(dp,-1,sizeof(dp));
	cnt=0;
	while(x)
	{
		tmp[++cnt]=x%10;
		x/=10;
	}
	ll res=0;
	for(re int i=1;i<=tmp[cnt];++i)//第一位不能是0，因此单独枚举第一位 
	 res+=dfs(10,i,0,i<tmp[cnt],0,i==4,i==8);
	return res;
}
int main()
{
	a=read(),b=read();
	printf("%lld
",calc(b)-calc(a-1));//记忆化搜索不用考虑边界了 
	return 0;
}