自动搬运

查看原文

来自洛谷，原作者为

	Mathison **

搬运于2025-08-24 21:56:46，当前版本为作者最后更新于2018-10-22 21:50:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【题意简述】

给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。

【分析】

显然这就是数位dp呀

我们用记搜的模板进行数位dp

不了解记搜框架下的数位dp的话戳这里

好了我们开始本题

这个问题的记搜过程很简单：

1. 记录$pos,sum$(数字各位上的数的和),$st$(原数),limit
2. 转移：$dfs ( pos+1, sum+i , st*10+i , i==res\&\&limit )$
3. 结束返回：搜完之后如果$st\%sum=0$就返回1否则返回0

这样搜索框架完成

现在关键的问题是：怎样记录dp状态？

这里$st$可达到$\text{1e18}$显然是不能作为dp转移的下标直接记录的

所以我们考虑取模

我们最理想的模数当然是把每次搜到最后得到的数字各个位数之和

但是我们发现在这个过程中$sum$是发生变化的

所以我们就应该以一个定值作为模数

那好，我们虽然不知道最后各位之和的结果，我们枚举总可以吧

我们只需要枚举所有的各位数字之和作为模数

最后判断$sum$和枚举的$mod$相等并且$st\%sum=0$的数就是符合题意的答案

上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,dp[20][200][200];
int len,a[20],mod;
ll dfs(int pos,int sum,ll st,int limit)
{
	if(pos>len&&sum==0) return 0;
	if(pos>len) return st==0&&sum==mod?1:0;
	if(!limit&&dp[pos][sum][st]!=-1) return dp[pos][sum][st];
	ll ret=0;
	int res=limit?a[len-pos+1]:9;
	for(int i=0;i<=res;i++)
		ret+=dfs(pos+1,sum+i,(10ll*st+i)%mod,i==res&&limit);
	return limit?ret:dp[pos][sum][st]=ret;
}
ll part(ll x)
{
	len=0;
	while(x) a[++len]=x%10,x/=10;
	ll ret=0;
	for(mod=1;mod<=9*len;mod++)//枚举模数（就是各位数之和）
	{
		memset(dp,-1,sizeof dp);
	    ret+=dfs(1,0,0,1);
	}
	return ret;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",part(r)-part(l-1));
	return 0;
}