![[DP]数位DP总结](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[DP]数位DP总结")
数位DP总结
By Wine93 2013.7
1.学习链接
[数位DP] Step by Step
http://blog.****.net/dslovemz/article/details/8540340
[总结] 数位统计模板
http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html
2.各人总结领悟
数位DP关键在于状态的设计,设计状态时要考虑当前状态(如dp[pos][s1][s2]),一旦当前状态确定后,pos后面几位随便怎么填结果都一样.一旦达到这个,状态设计就正确了!
3.例题(已解决)
一. HDU 2089 不要62
http://acm.hdu.edu.cn/showproblem.php?pid=2089
题意:求区间[n,m]数字中不含62的数字个数 （0<n≤m<1000000）
分析:简单数位DP (暴力也可以解决)
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define N
int dig[N],dp[N][]; //statu 6:1 62:2 4:3
int dfs(int pos,int statu,int limit)
{
int i,s,end,sum=;
if(pos==-)
return statu==;
if(!limit&&dp[pos][statu]!=-)
return dp[pos][statu];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
{
s=statu;
if(s==||s==&&i==||i==)
s=;
else if(i==)
s=;
else
s=;
sum+=dfs(pos-,s,limit&&i==end);
}
if(!limit)
dp[pos][statu]=sum;
return sum;
} int calc(int n)
{
int len=-;
memset(dp,-,sizeof(dp));
while(n)
{
dig[++len]=n%;
n/=;
}
return dfs(len,,);
} int main()
{
// freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
printf("%d\n",m-n+-(calc(m)-calc(n-)));
return ;
}
HDU 2089
二. HDU 3555 Bomb
http://acm.hdu.edu.cn/showproblem.php?pid=3555
题意:求[1,N]数字中不含49的数字个数N (1 <= N <= 2^63-1)
分析:简单数位DP
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define LL long long
# define N int dig[N];
LL dp[N][]; //statu 4:1 49:2
LL dfs(int pos,int statu,int limit)
{
int i,end,s;
LL sum=;
if(pos==-)
return statu==;
if(!limit&&dp[pos][statu]!=-)
return dp[pos][statu];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
{
s=statu;
if(s==||s==&&i==)
s=;
else if(i==)
s=;
else
s=;
sum+=dfs(pos-,s,limit&&i==end);
}
if(!limit)
dp[pos][statu]=sum;
return sum;
} void calc(LL n)
{
int len=-;
memset(dp,-,sizeof(dp));
while(n)
{
dig[++len]=n%;
n/=;
}
LL ans=dfs(len,,);
printf("%I64d\n",ans);
} int main()
{
int t;
LL n;
// freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
calc(n);
}
return ;
}
HDU 3555
三. UESTC 1307 windy数
http://www.acm.uestc.edu.cn/code.php?sid=442734
题意:求区间[A,B]之间的windy数 (windy数:不含前导0，并且相邻2个数字之间差至少为2)1 <= A <= B <= 2000000000
分析:状态设计时多加一个前导0，并且记录当前选择的数字(pre)递归到下一位数字选择时利于判断是否相差2
#include<cstdio>
# include<cmath>
# include<cstring>
using namespace std; typedef long long ll;
# define N
ll dp[N][N][],a,b;
int dig[N]; ll dfs(int pos,int pre,int statu,int limit) //statu; 1:前面全部是0 2:满足条件 0:不满足条件
{
int i,end,s;
ll sum=;
if(pos==-)
return statu==;
if(!limit&&dp[pos][pre][statu]!=-)
return dp[pos][pre][statu];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
{
if(statu==&&i!=)
s=;
else if(statu==&&i==)
s=;
else if(statu==&&abs((double)(pre-i))>=)
s=;
else
continue;
sum+=dfs(pos-,i,s,limit&&end==i);
}
if(!limit)
dp[pos][pre][statu]=sum;
return sum;
} ll calc(ll n)
{
int len=-;
memset(dp,-,sizeof(dp));
while(n)
{
dig[++len]=n%;
n/=;
}
return dfs(len,,,);
} int main()
{
while(scanf("%I64d%I64d",&a,&b)!=EOF)
printf("%lld\n",calc(b)-calc(a-));
return ;
}
UESTC 1307
四. HDU 3652 B-number
http://acm.hdu.edu.cn/showproblem.php?pid=3652
题意:求[1,n]数字中数字13并且能被13整除的数字个数(1 <= n <= 1000000000).
分析:多加一个状态,记录到当前位的数 最后判断下这个数能否被13整除
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define N
# define LL long long
LL dp[N][N][N];
int dig[N]; // statu 0:什么都没有 1:含有1 2:含有13
LL dfs(int pos,int pre,int statu,int limit)
{
int i,s,end;
LL res=;
if(pos==-)
return statu==&&pre==;
if(!limit&&dp[pos][pre][statu]!=-)
return dp[pos][pre][statu];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
{
s=statu;
if(s==||(s==&&i==))
s=;
else if(i==)
s=;
else
s=;
res+=dfs(pos-,(pre*+i)%,s,limit&&i==end);
}
if(!limit)
dp[pos][pre][statu]=res;
return res;
} LL calc(LL n)
{
int len=-;
memset(dp,-,sizeof(dp));
while(n)
{
dig[++len]=n%;
n/=;
}
return dfs(len,,,);
} int main()
{
LL n;
while(scanf("%I64d",&n)!=EOF)
printf("%I64d\n",calc(n));
return ;
}
HDU 3652
五. HDU 3709 Balanced Number
http://acm.hdu.edu.cn/showproblem.php?pid=3709
题意:求一个区间[x,y]内是平衡数的数个数 (平衡数:如果一个数能找到一个平衡点,使这个平衡点2边的每个数字乘以这个数字到平衡点距离的积的和相等 如 4139就是个平衡数 因为4*2 + 1*1 = 9*1) (0 ≤ x ≤ y ≤ 1018)
分析:枚举平衡点,数位DP
# include<cstdio>
# include<cstring>
# include<cmath>
# include<algorithm>
using namespace std; # define N
# define LL long long int dig[N];
LL dp[N][N][]; LL dfs(int pos,int central,int pre,int limit)
{
int i,s,end;
LL res=;
if(pos==-)
return pre==;
if(pre<)
return ;
if(!limit&&dp[pos][central][pre]!=-)
return dp[pos][central][pre];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
res+=dfs(pos-,central,pre+(pos-central)*i,limit&&i==end);
if(!limit)
dp[pos][central][pre]=res;
return res;
} LL calc(LL n)
{
if(n<)
return ;
int len=-;
LL res=;
while(n)
{
dig[++len]=n%;
n/=;
}
for(int central=;central<=len;central++) //枚举平衡点
res+=dfs(len,central,,);
return res-len;
} int main()
{
int t;
LL l,r;
memset(dp,-,sizeof(dp));
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",calc(r)-calc(l-));
} return ;
}
HDU 3709
六. HDU 4507吉哥系列故事——恨7不成妻
http://acm.hdu.edu.cn/showproblem.php?pid=4507
题意:求区间[L,R]数字中不满足下列3个条件的数的平方和 (1 <= L <= R <= 10^18)
1、整数中某一位是7；
2、整数的每一位加起来的和是7的整数倍
3、这个整数是7的整数倍；
分析:若求不满足上面条件的数字,简单的数位DP可以解决!但是我们我们要求平方和,则需要维护3个值 (不满足条件的数的个数，这些数的和，这些数的平方和)
如何来求平方和:如果我们求(ab)^2 则求(a*10+b)^2
(ab)^2=(a*10+b)^2
令x=a*10,y=b
则 (x+y)^2=x^2+y^2+2^x^y;
假设枚举到当前pos位时，我们选择的是数8(即x=8),再假设8带头的后面有12,13,是满足条件的,即812,813，那么我们要计算 812^2+813^2
812^2+813^2=(8*100+12)^2+(8*100+13)^2=2*800^2+12^2+13^3+2*800*(12+13)
2*800^2可以直接计算，而12^2+13^2已经通过递归维护好了，而12+13就是我们维护的这些数的和 所以，枚举到当前位的平方和=2*当前这个数*以该位开始满足条件的数的个数+以该位开始满足条件的那些数的平方和+2*当前数*以该位开始满足条件的数的和(而这些数的和又可以通过类似的方法进行维护)
所以一次得返回3个值，可以用返回一个存储3个值的节点(起初我用3个数位DP分别维护3个值)
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define N
# define LL long long
# define MOD struct node
{
LL c,s1,s2; //个数 连续和 连续平方和
}; node dp[N][N][N];
LL base[N];
int dig[N]; LL mul(LL a,LL b)
{
return ((a%MOD)*(b%MOD))%MOD;
} node dfs(int pos,int pre1,int pre2,int limit)
{
int i,s,end;
node cnt,next;
if(pos==-)
{
cnt.c=(!pre1||!pre2)?:;
cnt.s1=cnt.s2=;
return cnt;
}
if(!limit&&dp[pos][pre1][pre2].c!=-)
return dp[pos][pre1][pre2];
end=limit?dig[pos]:;
cnt.c=cnt.s1=cnt.s2=;
for(i=;i<=end;i++)
{
if(i==)
continue;
next=dfs(pos-,(pre1+i)%,(pre2*+i)%,limit&&i==end);
cnt.c=(cnt.c+next.c)%MOD;
cnt.s1=(cnt.s1+mul(mul(i,base[pos]),next.c)+next.s1)%MOD;
LL a=mul(i,base[pos]),x=mul(a,a);
cnt.s2=(cnt.s2+mul(x,next.c)+next.s2+*mul(a,next.s1))%MOD;
}
if(!limit)
dp[pos][pre1][pre2]=cnt;
return cnt;
} void init()
{
int i,j,k;
base[]=;
for(i=;i<N;i++)
base[i]=(base[i-]*)%MOD;
for(i=;i<N;i++)
for(j=;j<N;j++)
for(k=;k<N;k++)
dp[i][j][k].c=-;
} LL calc(LL n)
{
int len=-;
while(n)
{
dig[++len]=n%;
n/=;
}
return dfs(len,,,).s2;
} int main()
{
init();
int t;
LL l,r,ans;
// freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&l,&r);
ans=calc(r)-calc(l-);
printf("%I64d\n",(ans%MOD+MOD)%MOD);
}
return ;
}
HDU 4507
七. SPOJ 10606 Balanced Numbers
http://www.spoj.com/problems/BALNUM/
题意：求区间[A,B]数字中每个偶数数字出现奇数次，每个奇数数字出现偶数次的数的个数1 <= A <= B <= 1019
分析:用3进制表示当前状态,对于0-9的每个数字,0:没出现过，1:出现奇数次 2：出现偶数次 则每个状态都可以表示成一个3进制数(注意前导0)
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define LL long long
# define N
LL dp[N][];
int dig[N],vis[N],base[N]; bool check()
{
int i;
for(int i=;i<=;i++)
if(vis[i])
{
if(i&&&vis[i]&)
return ;
else if(!(i&)&&!(vis[i]&))
return ;
}
return ;
} LL dfs(int pos,int add,int statu,int limit)
{
int i,s,end,X;
LL res=;
if(pos==-)
return check()&&statu;
if(!limit&&dp[pos][add]!=-)
return dp[pos][add];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
{
s=statu;
if(s==&&i==)
s=;
else
s=;
int flag=;
X=add;
if(s)
{
if(vis[i]==)
flag=,vis[i]=,X=add+base[i];
else if(vis[i]==)
flag=,vis[i]=,X=add+base[i];
else
flag=,vis[i]=,X=add-base[i];
}
res+=dfs(pos-,X,s,limit&&i==end);
if(s)
vis[i]=flag;
}
if(!limit)
dp[pos][add]=res;
return res;
} LL calc(LL n)
{
int len=-;
memset(vis,,sizeof(vis));
while(n)
{
dig[++len]=n%;
n/=;
}
return dfs(len,,,);
} int main()
{
int i,t;
LL l,r;
base[]=;
for(i=;i<=;i++)
base[i]=base[i-]*;
memset(dp,-,sizeof(dp));
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",calc(r)-calc(l-));
}
return ;
}
SPOJ 10606
八. URAL 1057 Amount of Degrees
题意:求区间[x,y]内，有多少个数可以分解成K个不同B的次方 (1 ≤ X ≤ Y ≤ 231−1).
(1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
分析:先将数字表示成B进制, 然后数位DP，枚举每一位的时候注意不是0就是1,因为要要求k个不同的B进制相加 最后判断下是否刚好有k个即可
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define LL __int64
# define N
int dig[N];
int dp[N][N]; int dfs(int pos,int statu,int k,int limit)
{
int i,s,end,res=;
if(pos==-)
return statu==k;
if(!limit&&dp[pos][statu]!=-)
return dp[pos][statu];
end=limit?dig[pos]:;
for(i=;i<=end;i++)
{
if(i>)
break;
res+=dfs(pos-,statu+i,k,limit&&i==end);
}
if(!limit)
dp[pos][statu]=res;
return res;
} int calc(int n,int k,int b)
{
int len=-;
while(n)
{
dig[++len]=n%b;
n/=b;
}
return dfs(len,,k,);
} int main()
{
// freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
int x,y,k,b;
while(scanf("%d%d%d%d",&x,&y,&k,&b)!=EOF)
{
memset(dp,-,sizeof(dp));
printf("%d\n",calc(y,k,b)-calc(x-,k,b));
}
return ;
}
ural 1057
4.更多题目(未解决)
1. codeforces 55d / SPOJ JZPEXT
2. HDU 4352
3. SGU 258
4. SPOJ 1182 Sorted bit sequence
5. HDU 3271 SNIBB
6. SPOJ 2319 Sequence
7. SGU 390 Tickets