信息学奥赛一本通T1588-数字游戏-题解（C++代码）

        数位DP板子题（本质记忆化搜索）

constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
	#include <bits/stdc++.h>
#endif

typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) < 'A' || o > 'Z'); return o;
	}
	inline double reod() {
		double o = read(), f = 1; char c;
		while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
		return o;
	}
}
using namespace IO;

const int SIZE = 1E4 + 7, Mod = 1E9 + 7;

int dig[23], Ind; LL DP[23][12][2][103];
int N;

LL DFS(int pos, int pre, int lim, int S) {
	if (pos == 0) return S == 0;
	if (DP[pos][pre][lim][S] != -1) return DP[pos][pre][lim][S];
	LL res = 0;
	for (int e = 0; e <= (lim == 0 ? dig[pos] : 9); e++)
		res += DFS(pos - 1, e, lim || e < dig[pos], (S + e) % N);
	return DP[pos][pre][lim][S] = res;
}

LL Split(LL w) {
	Ind = 0; memset(DP, -1, sizeof DP);
	while (w) dig[++Ind] = w % 10, w /= 10;
	return DFS(Ind, 0, 0, 0);
}

int main() {
	LL L, R;
	while (~scanf("%lld%lld%d", &L, &R, &N)) 
		printf("%lld\n", Split(R) - Split(L - 1));
}