记录编号	96160	评测结果	AAAAAAAAAA
题目名称	[AHOI 2009] 同类分布	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	1.242 s
提交时间	2014-04-11 15:44:25	内存使用	12.77 MiB

#include <algorithm>
#include <cstdio>
#include <fstream>
#include <cmath>
	  
using namespace std;
ifstream fi("self.in");
ofstream fo("self.out");
      
typedef long long LL;
      
const int MAXN = 22, MAXS = 166;
      
int cur, idx, a[MAXN], v[2][MAXN][MAXS][MAXS];
LL f[2][MAXN][MAXS][MAXS];//f[less][dep][sum][rem]表示是否已小于N。。处理到dep位。。和还剩下sum。。余数为rem的答案。。
      
LL calc(bool less, int dep, int sum, int rem) {
    if (!dep)
        return !sum && !rem;
    if (v[less][dep][sum][rem] == idx)
        return f[less][dep][sum][rem];
    v[less][dep][sum][rem] = idx;
    f[less][dep][sum][rem] = 0;
    int ed = min(less ? 9 : a[dep], sum);
    for (int i = max(sum - 9 * (dep - 1), 0); i <= ed; ++i)
        f[less][dep][sum][rem] += calc(less || i < a[dep], dep - 1, sum - i, (rem * 10 + i) % cur);
    return f[less][dep][sum][rem];
}
      
inline LL get(LL x) {
    LL ret = a[0] = 0;
    for (; x; x /= 10)
        a[++a[0]] = x % 10;
    for (cur = 1; cur <= a[0] * 9; ++cur) {
        ++idx;
        ret += calc(0, a[0], cur, 0);
    }
    return ret;
}
      
int main() {
	//freopen("self.in","r",stdin);
	//freopen("self.out","w",stdout);
    LL x, y;
    //scanf("%lld%lld", &x, &y);
    //printf("%lld\n", get(y) - get(x - 1));
	fi>>x>>y;
	fo<<get(y)-get(x-1)<<endl;
    return 0;
}