BZOJ 1799 self 同类分布(数位dp，区间各位数字和能整除原数的数字个数)

题目链接：
BZOJ 1799 self 同类分布
题意：
给出$a$,$b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。
数据范围：$a\leq b\leq 10^{18}$
分析：
暴力枚举所有可能的数字和即可。
需要判断余数等于0并且所有数字和等于设定的sum。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;int digit[20];
ll dp[20][200][200];ll dfs(int pos, int rem, int pre, int sum, int limit)
{if (pos == -1) return rem == 0 && pre == sum;if (!limit && dp[pos][rem][pre] != -1) return dp[pos][rem][pre];if (pre > sum) return 0;int last = limit ? digit[pos] : 9;ll ret = 0;for (int i = 0; i <= last; ++i) {ret += dfs(pos - 1, (rem * 10 + i) % sum, pre + i, sum, limit && (i == last));} if (!limit) dp[pos][rem][pre] = ret;return ret; 
}ll solve(ll x)
{int len = 0;memset(digit, 0, sizeof(digit));while (x) {digit[len++] = x % 10;x /= 10;}ll ret = 0;for (int i = 1; i <= 9 * len; ++i) {memset(dp, -1, sizeof(dp));ret += dfs(len - 1, 0, 0, i, 1);}return ret;
}   int main()
{ll n, m;while (~scanf("%lld%lld", &n, &m)) {printf("%lld\n", solve(m) - solve(n - 1));}return 0;
}