思路
通常而言数位DP都可以用记搜做,此题我们也考虑记搜
首先求出数字的和,去判断各位数字之和能否整除他的想法是错误的,因为每个数字都要判断一次,记搜变成暴搜。
转换思路,能够整除就是模数为0,所以可以考虑把每步的模数给算出来,算到最后一位判断模数是否为0即可
但是我们不知道各位数字之和是多少呀?没关系,不知道的枚举就好了。各位数字之和很小,可以直接暴力枚举,搜到最后一位时判断和是否为枚举的值。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=(a);i<=(b);++(i))
#define com(i,a,b) for(int i=(a);i>=(b);--(i))
#define mem(a,b) memset((a),(b),sizeof(a))
#define inf 0x3f3f3f3f
#define fin freopen("input.txt","r",stdin)
#define fout freopen("output.txt","w",stdout)
typedef long long ll;
const int maxn=100010;
int num[20],n,p;
ll f[20][200][200],_pow[20];
ll dfs(int len,int sum,bool limit,int mod){
if(!len){
if(sum==p&&!mod) return 1;
return 0;
}
if(!limit&&f[len][sum][mod]!=-1) return f[len][sum][mod];
int up=limit?num[len]:9;
ll ret=0;
go(i,0,up){
ret+=dfs(len-1,sum+i,limit&&i==num[len],(mod*10+i)%p);
}
return f[len][sum][mod]=ret;
}
ll solve(ll val){
n=0;
while(val){
num[++n]=val%10;
val/=10;
}
ll ans=0;
for(p=1;p<=200;p++)
mem(f,-1),ans+=dfs(n,0,1,0);
return ans;
}
signed main(){
//fin;
ll a,b;
scanf("%lld%lld",&a,&b);
printf("%lld",solve(b)-solve(a-1));
return 0;
}