// uva 11361 Investigating Div-Sum Property 数位dp//// 题目大意:// // 给你一个整数a和一个整数b,问在[a,b]范围内,有多少个自身被k整除而且// 各位数之和也能被k整除.比方k = 7 ,322满足条件,由于332能被整除7,并// 3 + 2 + 2 = 7 也能被7整除//// 解题思路://// 求一个区间的题目,这类题目,往往能够转化为不超过x的f(x).则最后要求// 的就是f(b) - f(a-1).怎样确定这个f(x).设d(i,m1,m2)为不确定的数字有// i个,已经确定的位的数子之和对k的余数对于k来说还须要m1才干凑成0,已经// 确定的位的数值大小对于k的余数对k来说还须要m2才干凑成0的满足要求的个数// 则d(i,m1,m2) = sigma(d(i-1,((m1-x)%k+k)%k,((m2 - x * 10^(i-1))%k+k))// {0<=k<=9},逐位求解.最后求和.採用记忆话搜索的方式.非常经典而且状态十分// 完美的题目.//// 感悟://// 这是在训练指南上看到的题目,開始看的时候,被k<=10000给吓到了.搞不了啊.这里// 就要批评一下自己啦,要认真分析题目,不要被题目给的数据吓到了.认真分析啊!!!// 看书上的分段求解还是云里雾里的.与传说中的数位dp有点相似.没想到还真是0.0// 顺着书往下看,发现书上定义的状态十分的让人赞不绝口.不是我这等菜鸟所能想到的// 状态.状态有了,dp的转移倒不是非常难理解,实现起来对于我来说还是有点困难,由于// 比較难掌控一些细节.总体的格局也不是非常清楚.看了看大神们的优美代码,发现// 记忆化搜索还是更好理解一些.尽管可能会慢一点,但重在好理解不是嘛.//// 初步接触数位dp,尽管知道是逐位进行,可是状态不是非常好想.// 不说什么啦,继续加油~~~FIGHTING#include #include #include #include using namespace std;typedef long long ll;int x,y,k;int a[15];int vis[15][105][105];ll d[15][105][105];ll pow[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};ll dp(int cnt,int m1,int m2){ if (cnt==0) return (m1==0 && m2==0)? 1:0; if (vis[cnt][m1][m2]) return d[cnt][m1][m2]; vis[cnt][m1][m2] = 1; ll& ans = d[cnt][m1][m2]; for (int j=0;j<10;j++){ ans += dp(cnt-1,((m1-j)%k+k)%k,((m2 - j * pow[cnt-1])%k+k)%k); } return ans; } ll solve(int n){ int cnt = 0; while(n){ a[cnt++] = n%10; n/=10; } ll ans = 0; memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); int m1=0,m2=0; for (int i = cnt-1;i>=0;i--){ for (int j=0;j<a[i];j++){ //注意,我们求的解不包含n本身 ans += dp(i,(k-(m1+j)%k+k)%k,(k-(m2+j*pow[i])%k+k)%k); } m1 = (m1 + a[i])%k; m2 = (m2 + (pow[i] * a[i])%k)%k; } return ans; } void input(){ scanf("%d%d%d",&x,&y,&k); if (k>=100){ puts("0"); return ; } printf("%lld\n",solve(y+1) - solve(x)); } int main(){ int t; // freopen("1.txt","r",stdin); scanf("%d",&t); while(t--){ input(); } return 0; }