P4127 同类分布【数位dp】

· · 题解

【题意简述】

给出两个数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;
}