求出[a,b]中各位数字之和能整除原数的数的个数。
有困难的一道题。*看了题解：枚举每一个各位数字的和($<=162$)，设计状态$f[len][sum][rest]$表示dp后面$len$位，要求这剩下的和是$sum$，并且其对$sum$取模是$rest$的方案数。
感觉也讲不出什么道理来，真的是。。经验问题啊。。。当时数位dp不太会，现在看来稍微好些了。或者也可以从最高位往后看，设前面填好的高位组成的各位和是sum，mod枚举剩rest，到最低位再检验正确性。
转移（向下一层dp）时就是把当前填的这一位数字从sum减掉，并且rest取$rest-i*10^{len-1}%p$，比如我一开始要求rest是0，第一位填3，后面的数要求的rest就变了。为什么是前面那个式子，这个可以推一下，很好推，就是剩余系相关的数学内容。然后每种sum都讨论一下，另外记搜可以带点剪枝什么的，卡卡就过啦。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const ll bin[]={,,,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15,1e16,1e17,1e18};
ll l,r,f[][][],p;
int flag,b[];
inline int mod(ll x){return x<?x+p:x;}
ll dp(int len,int s,int rest,bool limit){
if(!len){if(!s&&!rest)return ;else return ;}
if(s<||*len<s)return ;//剪枝
if(!limit&&~f[len][s][rest])return f[len][s][rest];
int num=limit?b[len]:;ll ret=;
for(register int i=;i<=num;++i)ret+=dp(len-,s-i,mod(rest-i*1ll*bin[len]%p),limit&&(i==num));
return limit?ret:f[len][s][rest]=ret;
}
inline ll solve(ll x){
ll k=,ret=;while(x)b[++k]=x%,x/=;
for(p=;p<=k*;++p)memset(f,-,sizeof f),ret+=dp(k,p,,);
return ret;
} int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
read(l),read(r);if(l>=1e18)return printf("1\n"),;if(r>=1e18)--r,++flag;
return printf("%lld\n",solve(r)-solve(l-)+flag),;
}