AcWing 311. 月之谜
原题链接
中等
作者:
溪染
,
2020-10-15 11:18:06
,
所有人可见
,
阅读 4031
/*
数位DP
*/
#include<bits/stdc++.h>
using namespace std;
int m[50];
int f[15][100][100][100];//位,和,模,模结果
int now;
int dfs(int x,bool flag,int he,int mod) {
if(x==0) return (mod==0&&he==now);
if(he>now) return 0;
if(!flag&&f[x][he][mod][now]!=-1) return f[x][he][mod][now];
int MAX=flag?m[x]:9,ans=0;
for(int i=0; i<=MAX; i++)
ans+=dfs( x-1 , flag&&(i==MAX) , he+i , (mod*10+i)%now );
if(!flag) f[x][he][mod][now]=ans;
return ans;
}
int work(int x) {
memset(m,0,sizeof(m));
if(x==-1) return 0;
for(int i=1; x; i++) {
m[i]=x%10;
x/=10;
}
int tot=0;
for(int i=1; i<=90; i++) {
now=i;
tot+=dfs(10,1,0,0);
}
return tot+1;//0的情况特判
}
int main() {
memset(f,-1,sizeof(f));
int l,r;
cin>>l>>r;
cout<<work(r)-work(l-1)<<"\n";
return 0;
}