学步园

枚举各位数字之和进行记忆化搜索。

#include<bits/stdc++.h>
using namespace std;
int num[20],times,cur;
long long a,b,v[2][20][166][166],f[2][20][166][166];
inline long long calc(bool less,int dep,int left,int rem){
	if(!dep)return (!left&&!rem);
	if(v[less][dep][left][rem]==times)return f[less][dep][left][rem];
	v[less][dep][left][rem]=times;f[less][dep][left][rem]=0;
	int st=max(left-(dep-1)*9,0),ed=min(less?9:num[dep],left);
	for(int i=st;i<=ed;i++)
		f[less][dep][left][rem]+=calc(less||i<num[dep],dep-1,left-i,(rem*10+i)%cur);
	return f[less][dep][left][rem];
}
inline long long count(long long k){
	num[0]=0;
	while(k>0){
		num[++num[0]]=k%10;
		k/=10;
	}
	long long ans=0;
	for(cur=1;cur<=num[0]*9;cur++)
		times++,ans+=calc(0,num[0],cur,0);
	return ans;
}
int main(){
	cin>>a>>b;
	cout<<count(b)-count(a-1)<<endl;
	return 0;
}