YBTOJ数字整除（数位DP）
明显的数位DP
变量解释：
- pos表示枚举到的位数
- mod表示枚举的模数
- sum表示当前各位数字的和
- res表示模剩下的值
思路：
每一位的数字和最大是9*len（位数），所以可暴力枚举模数，然后判断各位数字的和是否等于模数。
具体代码实现套板子即可。
然而……
正当你开开心心敲完板子提交的时候，你发现自己TLE了！打开测试点一看……才T了50ms？就这？加亿点小剪枝不就得了？然后……一晚上过去了。卡常手段都用尽了，可就是T掉7ms。无奈之下求问大佬，大佬说：
不要每次把f数组清空！！！
……？！豁然开朗
因为是从高位到低位进行数位DP，也就是从大到小，所以之前处理过的区间不需要在进行处理，这能节省大量的时间！！！
然后
AC代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=3000500;
const int N=102;
int n;
int dp[11][N][N][N];
int a[15];
int l,r;
int Mod=83;
ll mi[15];
int find(int pos,int mod,int sum,int res,int lim)
{
if(pos==0) return sum==mod&&res==0;
if(sum>mod) return 0;
if(!lim&&dp[pos][mod][sum][res]!=-1) return dp[pos][mod][sum][res];
int ans=0;
int mx= lim?a[pos]:9;
for(int i=0; i<=mx; i++)
{
ll res1=(ll)((ll)mi[pos-1]*i+res)%mod;
ans+=find(pos-1,mod,sum+i,res1,lim&&i==mx);
}
if(!lim) dp[pos][mod][sum][res]=ans;
return ans;
}
int solve(int x)
{
n=0;
while(x)
{
a[++n]=x%10;
x/=10;
}
int tot=0;
for(int i=1; i<=Mod; i++) tot+=find(n,i,0,0,1);
return tot;
}
int main() {
memset(dp,-1,sizeof(dp));
mi[0]=1;
for(int i=1; i<=10; i++) mi[i]=mi[i-1]*10;
while(scanf("%d%d",&l,&r)!=EOF)printf("%d\n",solve(r)-solve(l-1));
return 0;
}