记录编号 |
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;
}