经典数位dp！而且这好像是数位dp的套路板子……不需要讨论原来我很头疼的一些边界。
改天用这个板子重做一下原来的一些数位dp题目。
http://blog.csdn.net/the_useless/article/details/53674906
题目大意:
给定a,b,k三个正整数,统计在[a,b]之间的整数n中,有多少n自身是k的倍数,且n的各个数字(十进制)之和也是k的倍数.(1⩽a⩽b⩽231)
题目分析:
这是一道典型的数位DP题.
n非常大,若是直接枚举的话会超时,考虑利用加法原理计算方案数.
将数拆分开来,拆成一位一位的,从前往后枚举.那么就会出现形如”32**”这样枚举了部分,还有部分未枚举.可以用三维状态来表示:f(d,m1,m2)表示当前还有d个数未枚举,m1表示前缀各数之和%k,m2表示组成数%k.如之前的数”32**”就应该对应为f(2,5%k,3200%k).
对应的转移方程则有
f(d,m1,m2)=∑f(d−1,(m1+i)%k,m2+i∗10d−1%k|0⩽i⩽9)
所以dp数组需要开多大.10∗10000∗10000≈109?开不下!
但是其实各个位数之和最大为1+9∗9=82,所以当k>82时,直接输出0.
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int a,b,MOD,T;
int dp[15][90][90],pow_10[15];
int f(int d,int m1,int m2){
if(dp[d][m1][m2]!=-1){
return dp[d][m1][m2];
}
dp[d][m1][m2]=0;
for(int i=0;i<10;i++){
dp[d][m1][m2]+=f(d-1,(m1+i)%MOD,(m2+i*pow_10[d-1])%MOD);
}
return dp[d][m1][m2];
}
int calc(int x)
{
int len=0;
if(!x){
len=1;
}
int t=x;
while(t){
++len;
t/=10;
}
int res=0,LeftSide=0,SumDigits=0;//LeftSideÊǵ±Ç°×ó±ß½ç£¬SumDigitsÊǵ±Ç°ËùÓÐÊýλ֮ºÍ
for(int i=1;i<=len;i++) {
while((ll)LeftSide+(ll)pow_10[len-i]-1ll<=(ll)x){
//ÅжÏÄÜ·ñ´ÓÕâÀï¼ÌÐøÍùÏÂÇó£¬ÒªÊDz»ÄܵĻ°¾ÍÒªÍùºóÍÆһλ
//±ÈÈç3212£¬Äã¾Í²»ÄÜ´Ó3200ÔÙÍù3299Ç󣬶øÓ¦¸ÃÍùºóÍƵ½Íù3209Çó
res+=f(len-i,SumDigits%MOD,LeftSide%MOD);
LeftSide+=pow_10[len-i];
++SumDigits;
}
}
return res;
}
int main(){
// freopen("uvaLive4123.in","r",stdin);
scanf("%d",&T);
pow_10[0]=1;
for(int i=1;i<=9;++i){
pow_10[i]=pow_10[i-1]*10;
}
for(;T;--T){
scanf("%d%d%d",&a,&b,&MOD);
if(MOD>82){
puts("0");
continue;
}
memset(dp,-1,sizeof(dp));
for(int i=0;i<MOD;++i){
for(int j=0;j<MOD;++j){
dp[0][i][j]=0;
}
}
dp[0][0][0]=1;
printf("%d\n",calc(b)-calc(a-1));
}
return 0;
}