记录编号	587300	评测结果	ATTTTTTTTT
题目名称	2972.[BZOJ 1799]月之谜	最终得分	10
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	9.020 s
提交时间	2024-03-21 21:32:35	内存使用	6.84 MiB

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

	return 0;

}