20230719
数位DP
P4127 [AHOI2009] 同类分布
题目描述
传送门
求出 [a,b] 中各位数字之和能整除原数的数的个数 \(a,b ≤ 1e18\)
Solution
对于这种求是否能整除的题
我们只有在最后才能得到答案
这道题很明显是数位DP
考虑用记忆化搜索来实现
对于每一位我们需要维护前面的数字之和和前面所组成的数
而由于前面所组成的数太大了，可以到达\(1e18\)
但是数字之和又一定\(\le 9* 18\)
我们就考虑取模数
这样进行\(9 * 18\)次dfs即可
每一次要判断数字之和\(=mod\)
这样记录答案就可以了
H_W_Y-Coding
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,mod,dp[20][185][185];
int len=0,p[20];
ll dfs(int id,int sum,ll st,int limit){
if(id>len) return st==0&&sum==mod?1:0;
if(!limit&&dp[id][sum][st]!=-1) return dp[id][sum][st];
int u=limit?p[id]:9;
ll res=0;
for(int i=0;i<=u;i++)
res+=dfs(id+1,sum+i,(st*10+i)%mod,limit&&i==u);
if(!limit) dp[id][sum][st]=res;
return res;
}
ll solve(ll x){
len=0;
while(x){
p[++len]=x%10;
x/=10;
}
ll res=0;
for(int i=1;i<=len/2;i++) swap(p[i],p[len-i+1]);
for(mod=1;mod<=9*len;mod++){
memset(dp,-1,sizeof(dp));
res+=dfs(1,0,0,1);
}
return res;
}
int main(){
/*2023.7.19 H_W_Y P4127 [AHOI2009] 同类分布 数位DP*/
scanf("%lld%lld",&a,&b);
printf("%lld\n",solve(b)-solve(a-1));
return 0;
}