记录编号	587303	评测结果	AAAAAAAAAA
题目名称	[BZOJ 1799]月之谜	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	4.180 s
提交时间	2024-03-21 21:45:37	内存使用	128.15 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
const ll inf = 1e17;
ll l,r,tot;
ll f[12][110][110][110],c[12],mod;
int dfn[12][110][110];
ll dfs(int p,int sum,int mo,bool lim){
    if(!p)return (!mo && (sum == mod));
    if(!lim && f[p][sum][mo][mod] != -1)return f[p][sum][mo][mod];
    ll cnt = 0;
    int lst = lim ? c[p] : 9;
    for(int i = 0;i <= lst;i++)cnt += dfs(p-1,sum+i,(mo*10+i)%mod,lim && (i==lst));
    if(!lim)f[p][sum][mo][mod] = cnt;
    return cnt;
}
ll sum(ll d){
    int l = 0;tot = 1;
    while(d){
        c[++l] = d % 10;
        d /= 10;
    }
    ll ans = 0;
    for(mod = 1;mod <= l*9;mod++)ans += dfs(l,0,0,1);
    return ans;
}
int main(){
	freopen("mystery.in","r",stdin);
    freopen("mystery.out","w",stdout);
    memset(f,-1,sizeof f);
    while(~scanf("%lld%lld",&l,&r))printf("%lld\n",sum(r) - sum(l-1));

	return 0;

}