传送门
数位dp板子题。
f[i][mod]" role="presentation" style="position: relative;">f[i][mod]f[i][mod]表示当前进行到第i位，所有数位数字之和的余数是mod" role="presentation" style="position: relative;">modmod时的种类数，根据当前位选择是否有限制转移就行了。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll l,r,modd,num[15],f[15][105],len;
inline ll dfs(ll pos,ll mod,int lim){
if(pos==len+1)return !mod;
if(~f[pos][mod]&&(!lim))return f[pos][mod];
ll tmp=0;
int up=lim?num[pos]:9;
for(int i=0;i<=up;++i)tmp+=dfs(pos+1,(mod+i)%modd,(lim&&(i==up)));
return f[pos][mod]=(!lim)*tmp,tmp;
}
inline ll solve(ll x){
if(!x)return 1;
len=0,memset(f,-1,sizeof(f));
while(x)num[++len]=x%10,x/=10;
reverse(num+1,num+len+1);
return dfs(1,0,1);
}
int main(){
while(~scanf("%lld%lld%lld",&l,&r,&modd))cout<<solve(r)-solve(l-1)<<'\n';
return 0;
}