P4127 同类分布【数位dp】

【题意简述】 给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。 【分析】 显然这就是数位dp呀 我们用记搜的模板进行数位dp 不了解记搜框架下的数位dp的话戳[这里](https://www.luogu.org/blog/virus2017/shuweidp) 好了我们开始本题 这个问题的记搜过程很简单： 1. 记录$pos,sum$(数字各位上的数的和),$st$(原数),limit 1. 转移：$dfs ( pos+1, sum+i , st*10+i , i==res\&\&limit )$ 1. 结束返回：搜完之后如果$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; } ```