转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
题目意思：问在区间[A,B]有多少个数不仅满足自身是k的倍数，而且其各个位数上的和（十进制）也是k的倍数。
分析：数位dp
首先注意到1+9*9=82，即k最大只能是82，所以，在大于82是直接输出答案为0；
dp[i][j][t]——表示从左往右递推到第i位时（后面所有位数用0填充），各个位数上的和mod k等于j，且这个数mod k等于t时的方案数
状态转移方程为dp[i][j][t]=∑dp[i-1][((j-x)%k+k)%k][((t-x*10^i)%k+k)%k] (x=0,1,2,……,9)
注意递推的时候相应的位次上是有限制的，并且不要忘记判断其自身
#include <iostream>
#include <cstring>
using namespace std;
int k;
int d[];
int p[];
int dp[][][];
int dfs(int size,int n,int m)
{
if(!size)
{
if(n==&&m==)return ;
return ;
}
if(dp[size][n][m]>=)return dp[size][n][m];
dp[size][n][m]=;
for(int i=;i<;i++)
{
dp[size][n][m]+=dfs(size-,((n-i)%k+k)%k,((m-i*p[size-])%k+k)%k);
}
return dp[size][n][m];
}
int solve(int num)
{
int n=,m=,size=,ans=;
if(num==)return ;
while(num)
{
d[size++]=num%;
temp+=d[size-];
num/=;
}
d[]++;
for(int i=size-;i>=;i--)
{
for(int j=;j<d[i];j++)
{
ans+=dfs(i,((k-n-j)%k+k)%k,((k-m-j*p[i])%k+k)%k);
}
n=(n+d[i])%k;
m=(m+d[i]*p[i])%k; }
return ans; } int main()
{
ios::sync_with_stdio(false);
p[]=;
for(int i=;i<;i++)p[i]=p[i-]*;
int a,b,t;
cin>>t;
while(t--)
{
cin>>a>>b>>k;
if(k>)cout<<<<endl;
else
{
memset(dp,-,sizeof(dp));
cout<<solve(b)-solve(a-)<<endl;
}
}
return ;
}