kuangbin带你飞 - 专题十五 - 数位dp
|
https://vjudge.net/contest/70324 A - Beautiful numbers 统计区间内的，被数位上各个为零数字整除的数的个数。 下面是暴力的数位dp写法，绝对会TLE的，因为这个要深入到每个数字的最后才能判断是否合法。因为记忆化的意义在询问不多的时候用处不大就去掉了。果然2400分的题不能这么暴力。
#include<bits/stdc++.h> using namespace std; #define ll long long int a[20]; int d[10]; ll dfs(int pos,ll sum,bool lead,bool limit) { //递归边界，最低位是0，那么pos==-1说明这个数枚举完了 if(pos==-1) { for(int i=1; i<=9; i++) { if(d[i]) { if(sum%i) return 0; } } return 1; } int up=limit?a[pos]:9;//根据limit判断枚举的上界up ll ans=0; //开始计数 for(int i=0; i<=up; i++) { //枚举，然后把不同情况的个数加到ans就可以了 //合法的状态向下搜索 if(i) d[i]++; ans+=dfs(pos-1,sum*10ll+i,lead && i==0,limit && i==a[pos]);//最后两个变量传参都是这样写的 if(i) d[i]--; } return ans; } ll solve(ll x) { //可能需要特殊处理0或者-1 if(x<=0) return 1; int pos=0; while(x) { //把数位分解 a[pos++]=x%10;//编号为[0,pos)，注意数位边界 x/=10; } memset(d,0,sizeof(d)); return dfs(pos-1,0,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛 } int main() { int t; scanf("%d",&t); ll le,ri; while(t--) { scanf("%lld%lld",&le,&ri); printf("%lldn",solve(ri)-solve(le-1)); } } 没想出来怎么解决，去查了题解，题解暗示说，这样是和最小公倍数有关的。好像的确很有道理，细节只能自己想了。 首先考虑1~9的最小公倍数，也就是 $1*2^3*3^2*5*7=2520$ ，题解提到一个充要条件，就是一个数假如要能被某些数整除，等价于被这些数的最小公倍数整除，这个充要条件的正确性可以由质因数分解得知，就是说这个数的质因数分解必须比他的各个数位的质因数分解“高”，也就比各个数位的质因数分解的“轮廓”也就是最小公倍数“高”。（注： $lcm(a,b)=frac{a*b}{gcd(a,b)}$ ，且满足结合律） ?然后怎么计数呢？这里受到之前做的数位dp的启发，由下一位的数位dp推出上一位的状态。设计状态的时候借鉴别人的思路，dp[i][j][k]表示i位数中能整除前面数位的最小公倍数j的且模2520的余数为k的数的个数。 假设某一位的枚举值为a，那么dp[i][j][k]+=dp[i-1][lcm(j,a)][(k*10+a)%p]，比如现在要求的数位是2836，现在已经枚举过了2，当前在处理8，枚举千位上的值，i=2，j=2，k=2，当千位枚举3时，向下转移一个i=1，j=6，k=23，意义是显然的，因为你多了一个3，必定要能整除最小公倍数6。记忆化的时候要注意，数位受限时不能取用dp值也不能更新dp值。 最后还要注意这样做会MLE，改进的方法是给每个可能的1~9的任意组合生成的最小公倍数都生成一个id值或者（假的）hash值，方法是枚举2520的各个质因数。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
