本文共 3993 字，大约阅读时间需要 13 分钟。

个人认为是比较简单的 $dp$。

首先，状态不难想，可求状态有这些：位数，前导零，limit标记，余数，满足条件的数的和，满足条件的数的平方和等。

其次，注意编程的细节。然后这道题就搞定了。

数位$dp$的时间复杂度很好分析，就是所有可能的状态数。一般状态数$s$<=1e5时不容易超时，如果状态数小，不考虑常数的话，可以将$int$宏定义成$longlong$。

若数值大于$longlong$，则用字符串输入，其他操作与正常的数相同

结果一般要取模（因为数太多）

以 CQOI2016手机号码 为例：

这里用了一个小技巧。实际上前导零在判断数是否合法时会产生错误答案，但是由于$[l,r]$不含前导零，而$[1,l-1]$又都被以同种规则算了一次，所以会抵消。

但是当 $l=10^{10}$时，$l-1$是10位数，而$r$是$11$位数，所以判断条件其实是不等价的。我们只需在第$11$位补一个$0$即可，这样和$r$算出来的重叠部分就可以抵消了。

#include
   
    #define int long long//This is made by something //O(状态数)int n,m,F[20][10][3][2][2][2];int a[20],len;int dfs(int x,int pre,int num,int f,int e,int d,int limit) {   	//强行改状态 	if(num>=3) d=1;	if(d==1) pre=num=0;	if(f==1&&e==1) {   		return 0;	}	if(x==0) {   		return d;	}	if(!limit&&F[x][pre][num][f][e][d]!=-1) return F[x][pre][num][f][e][d];	int maxn= (limit==1?a[x]:9),ans=0;	for(int i=0;i<=maxn;i++) {   		ans+=dfs(x-1,i,(i==pre?num+1:1),f||(i==4),e||(i==8),d,limit&&i==a[x]);	}	if(!limit) F[x][pre][num][f][e][d]=ans;	return ans;}int solve(int x) {   	len=0; while(x) a[++len]=x%10,x/=10;	if(len!=11) a[++len]=0;	return dfs(len,-1,0,0,0,0,1);}signed main() {   	memset(F,-1,sizeof(F));	scanf("%lld%lld",&n,&m);	printf("%lld\n",solve(m)-solve(n-1));}
   

以 HDU4507恨 7 不成妻 为例：

这道题很新颖的地方就在于没有单纯求个数，而是求满足条件的数的平方和。

其实本质是一样的。我们仍然沿用dfs计数的思想，不过记录三个值：满足条件的数的个数，满足条件的数的和，满足条件的数的平方和。

我们可以用$f_{x,s1,s2}$来表示还剩$x$位，这个数除末$x$位以外模$7$余$s1$，这个数每一位之和除末$x$位以外模$7$余$s2$时所有与$7$无关的数的末$x$位的平方和

数学转化

让我们来研究一下$(x_1+t\ast 10^y{)}^2+(x_2+t\ast 10^y{)}^2+...+(x_n+t\ast 10^y{)}^2$这个式子。

用完全平方公式展开即可。

#include
   
    #define int long longusing namespace std;const int mod=1e9+7;//coding makes a full manstruct Number{   	int num,nc,nc2,vis;}f[20][7][7];int n,m,a[20],len;int fpow(int x,int y) {   	int tot=1;	for(;y;y>>=1) {   		if(y&1) tot=tot*x%mod;		x=x*x%mod;	}	return tot;}Number dfs(int x,int y,int z,int limit) {   	if(x==0) {   		if(y&&z) f[x][y][z].num=1;		return f[x][y][z];	} 	if(!limit&&f[x][y][z].vis!=0) return f[x][y][z];	int maxn= (limit==1?a[x]:9),ans=0;	Number u=(Number){   };	for(int i=0;i<=maxn;i++) {   		if(i==7) continue;		Number v=dfs(x-1,(y+i)%7,(z*10+i)%7,limit&&i==a[x]);		u.num=(u.num+v.num)%mod;		u.nc=(u.nc+v.nc+fpow(10,x-1)*i*v.num%mod)%mod;		u.nc2=(u.nc2+v.nc2+2*i*fpow(10,x-1)%mod*v.nc%mod+fpow(10,2*(x-1))*i*i%mod*v.num%mod)%mod;	}	if(!limit) f[x][y][z]=u,f[x][y][z].vis=1;	return u;}int solve(int x) {   	len=0; while(x) a[++len]=x%10,x/=10;	return dfs(len,0,0,1).nc2;}signed main() {   	int T;	scanf("%lld",&T);	while(T--) {   		scanf("%lld%lld",&n,&m);		printf("%lld\n",(solve(m)-solve(n-1)+mod)%mod);	}}
   

以SAC#1 - 萌数为例：

n<=1000，但仍然可以用数位dp的框架来做。只不过搜索层数和状态数增加了而已。

#include
   
    using namespace std;const int mod=1e9+7;//萌数：含回文子串//若数值大于longlong，则用字符串输入，其操作与正常的数相同//结果一般要取模（因为数太多） int f[1005][10][10][2]; int a[1005],len,res1,res2,flag;//只需分析出一个性质：回文串的长度只可能是2或者3//前导零不能拿来判回文串 bool checker() {   	for(int i=2;i<=len;i++) {   		if(a[i]==a[i-1]) return 1;		if(i>2&&a[i]==a[i-2]) return 1;	}	return 0;}int dfs(int x,int pre,int pre2,int d,int limit,int zero) {   	if(x<1) return d;	if(d) pre=pre2=0;	if(!limit&&!zero&&pre>=0&&pre2>=0&&f[x][pre][pre2][d]!=-1) return f[x][pre][pre2][d];	int maxn= (limit==1?a[x]:9),ans=0;	for(int i=0;i<=maxn;i++) {   		ans+=dfs(x-1,pre2,(zero&&!i)?-1:i,d||(!zero&&(i==pre2||i==pre)),limit&&i==a[x],zero&&!i);		ans%=mod;	}	if(!limit&&!zero&&pre>=0&&pre2>=0) f[x][pre][pre2][d]=ans;	return ans;}int solve() {   	len=0; char c=getchar();	while(c<'0'||c>'9') c=getchar();	while(c>='0'&&c<='9') a[++len]=c-'0',c=getchar();	reverse(a+1,a+1+len);	return dfs(len,-1,-1,0,1,1);} signed main() {   	memset(f,-1,sizeof(f));	res1=solve();	if(checker()) flag=1;	res2=solve();	printf("%d",(res2-res1+flag+mod)%mod);}
   

转载地址：http://eown.baihongyu.com/