[AHOI2009]同类分布

数位dp。记录前面的数字和，枚举模数，$f[l][s][m]$表示到第i位，前面数字总和为$s$，$\%m$的余数为$mo$.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[21][201][201],c[21],a,b,m;
inline ll dfs(int l,int s,int mo,bool o){if(l==0) return (mo==0&&s==m);if(!o&&f[l][s][mo]!=-1) return f[l][s][mo];int r=o?c[l]:9;ll res=0;for(int i=0;i<=r;++i) res+=dfs(l-1,s+i,(mo*10+i)%m,o&&r==i);if(!o) f[l][s][mo]=res;return res;
}
ll calc(ll n){int l=0,mod=0;while(n) mod+=n%10,c[++l]=n%10,n/=10;ll res=0;for(m=1;m<=l*9;++m){memset(f,-1,sizeof(f));res+=dfs(l,0,0,1);}return res;
}
int main(){scanf("%lld%lld",&a,&b);return !printf("%lld",calc(b)-calc(a-1));
}