给定a,b,k，求[a,b]中有多少个数x满足x和x的各位之和都是k的倍数。
数位dp模板题。设dp[u][lim][m1][m2]为枚举到第u位(从低到高数)，是否受限，各位之和对k的模为m1，本身对k的模为m2时继续往下枚举能得到的答案数，往下一位转移即可。对b和a-1分别计算答案，然后相减就得到了最终答案。由于一个int类型的整数各位之和不会超过100(实际更小，不过懒得算了)，所以m1,m2开到100就够了，k大于100的时候特判一下。
状态转移方程见代码。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int N=31+3; 6 int bit[N],nb,d[N][2][100][100],a,b,k; 7 int dp(int u,int lim,int m1,int m2) { 8 if(u<0) { 9 if(m1==0&&m2==0)return 1; 10 return 0; 11 } 12 int& ret=d[u][lim][m1][m2]; 13 if(~ret)return ret; 14 ret=0; 15 for(int i=0; i<=(lim?bit[u]:9); ++i)ret+=dp(u-1,lim&&i==bit[u],(m1+i)%k,(m2*10+i)%k); 16 return ret; 17 } 18 19 int getans(int x) { 20 memset(d,-1,sizeof d); 21 for(nb=0; x; x/=10)bit[nb++]=x%10; 22 return dp(nb-1,1,0,0); 23 } 24 25 int main() { 26 int T; 27 scanf("%d",&T); 28 while(T--) { 29 scanf("%d%d%d",&a,&b,&k); 30 printf("%d ",getans(b)-getans(a-1)); 31 } 32 return 0; 33 }