TLE代码：

#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
const int inf = 2147483647;
const long long mol = 10000007;
int num[19];
ll dp[19][170][170][170] = {0};
ll dfs(int pos , bool f , int sum , int d ,int k)
{
	if(!pos) return (d == 0 && sum == k);
	if(sum > k)return 0;
	if(!f && dp[pos][sum][d][k])return dp[pos][sum][d][k];
	int up = (f ? num[pos] : 9);
	ll ans = 0;
	for(int i = 0; i <= up ; i++)
	{
		ans += dfs(pos - 1 , f && (i == up) , sum + i , (d * 10 + i) % k , k);
	}
	if(!f)dp[pos][sum][d][k] = ans;
	return ans ;
}
ll work(ll k)
{
	int cnt = 0;
	while(k > 0)
	{
		num[++cnt] = k % 10;
		k /= 10;
	}
	ll tot = 0;
	for(int p = 1; p <= 9 * cnt; p++)
	tot += dfs(cnt , 1 , 0 , 0 , p);
	return tot;
}
int main()
{
	ll l , r;
	cin >> l >> r;
	cout << work(r) - work(l - 1);
	return 0;
}

AC代码：

#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
const int inf = 2147483647;
int num[19] = {0};
ll dp[19][171][171] = {0};
ll dfs(int pos , bool f , int sum , int d ,int k)
{
	if(!pos) return (d == 0 && sum == k);
	if(sum > k)return 0;
	if(!f && dp[pos][sum][d] != -1)return dp[pos][sum][d];
	int up = (f ? num[pos] : 9);
	ll ans = 0;
	for(int i = 0; i <= up ; i++)
	{
		ans += dfs(pos - 1 , f && (i == up) , sum + i , (d * 10 + i) % k , k);
	}
	if(!f)dp[pos][sum][d] = ans;
	return ans ;
}
ll work(ll k)
{
	int cnt = 0;
	while(k > 0)
	{
		num[++cnt] = k % 10;
		k /= 10;
	}
	ll tot = 0;
	for(int p = 1; p <= 9 * cnt; p++)
	{
		memset(dp , -1 , sizeof(dp));
		tot += dfs(cnt , 1 , 0 , 0 , p);
	}
	return tot;
}
int main()
{
	ll l , r;
	cin >> l >> r;
	cout << work(r) - work(l - 1);
	return 0;
}

将模数作为状态不应该更优吗，但反而T了，不将模数作为状态每次清空dp数组却可以AC，不太理解为什么。