从一个状态开始转移时，若其为 $0$，直接跳过，不转移。实测快很多。因为有很多这样的空状态。

没优化的 / 优化过的，时间复杂度均为 $O(m^4)$，$m$ 为各位数字之和，至多为 $162$。

以我的代码为例：（注意代码中含有 //** 的行）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[20][180][180][2];
int len(int x){
	int u=(int)log10(x);
	return u+1;
}
int ret(int x,int pos){
	int u=len(x)-pos;
	x/=(int)pow(10,u);
	return x%10;
}
const int p=165;
int sol(int x,int sum){
	memset(f,0,sizeof(f));
	f[0][0][0][1]=1;
	int l=len(x);
	for(int i=0;i<l;i++){
		int w=ret(x,i+1);
		for(int j=0;j<=sum;j++){
			for(int k=0;k<sum;k++){
				if(f[i][j][k][0]!=0){//**
					for(int h=0;h<=9;h++){
						f[i+1][j+h][(k*10+h)%sum][0]+=f[i][j][k][0];
					}
				}
				if(f[i][j][k][1]!=0){//**
					for(int h=0;h<=w;h++){
						if(h==w){
							f[i+1][j+h][(k*10+h)%sum][1]+=f[i][j][k][1];
						}
						else{
							f[i+1][j+h][(k*10+h)%sum][0]+=f[i][j][k][1];
						}
					}
				}
			}
		}
	}
	return f[l][sum][0][0]+f[l][sum][0][1];
}
int get_res(int x){
	if(x==0) return 0;
	int ans=0;
	for(int i=1;i<=p;i++){
		ans+=sol(x,i);
	}
	return ans;
}
signed main(){
	int x,y;
	scanf("%lld%lld",&x,&y);
	printf("%lld\n",get_res(y)-get_res(x-1));
}