精华内容
下载资源
问答
  • 数位DP入门

    2014-08-22 09:53:03
    数位DP入门思想,包括详细的思考过程以及一些习题的讲解
  • 初探数位dp.pdf

    2019-09-16 17:47:17
    lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
  • 数位DP

    2017-07-18 14:50:48
    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每...

    转载自:http://blog.csdn.net/wust_zzwh/article/details/52100392


    基础篇

    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每一位就是数位啦!

    之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使得新的枚举方式满足dp的性质,然后记忆化就可以了。

    两种不同的枚举:对于一个求区间[le,ri]满足条件数的个数,最简单的暴力如下:

    [cpp]  view plain  copy
    1. for(int i=le;i<=ri;i++)  
    2.         if(right(i)) ans++;  

    然而这样枚举不方便记忆化,或者说根本无状态可言。

    新的枚举:控制上界枚举,从最高位开始往下枚举,例如:ri=213,那么我们从百位开始枚举:百位可能的情况有0,1,2(觉得这里枚举0有问题的继续看)

    然后每一位枚举都不能让枚举的这个数超过上界213(下界就是0或者1,这个次要),当百位枚举了1,那么十位枚举就是从0到9,因为百位1已经比上界2小了,后面数位枚举什么都不可能超过上界。所以问题就在于:当高位枚举刚好达到上界是,那么紧接着的一位枚举就有上界限制了。具体的这里如果百位枚举了2,那么十位的枚举情况就是0到1,如果前两位枚举了21,最后一位之是0到3(这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。最后一个问题:最高位枚举0:百位枚举0,相当于此时我枚举的这个数最多是两位数,如果十位继续枚举0,那么我枚举的就是以为数咯,因为我们要枚举的是小于等于ri的所以数,当然不能少了位数比ri小的咯!(这样枚举是为了无遗漏的枚举,不过可能会带来一个问题,就是前导零的问题,模板里用lead变量表示,不过这个不是每个题目都是会有影响的,可能前导零不会影响我们计数,具体要看题目)

    由于这种新的枚举只控制了上界所以我们的Main函数总是这样:

    [cpp]  view plain  copy
    1. int main()  
    2. {  
    3.     long long le,ri;  
    4.     while(~scanf("%lld%lld",&le,&ri))  
    5.         printf("%lld\n",solve(ri)-solve(le-1));  
    6. }  
    w_w 是吧!统计[1,ri]数量和[1,le-1],然后相减就是区间[le,ri]的数量了,这里我写的下界是1,其实0也行,反正相减后就没了,注意题目中le的范围都是大于等于1的(不然le=0,再减一就G_G了)

    在讲例题之前先讲个基本的动态模板(先看后面的例题也行):dp思想,枚举到当前位置pos,状态为state(这个就是根据题目来的,可能很多,毕竟dp千变万化)的数量(既然是计数,dp值显然是保存满足条件数的个数)

    [cpp]  view plain  copy
    1. typedef long long ll;  
    2. int a[20];  
    3. ll dp[20][state];//不同题目状态不同  
    4. ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零  
    5. {  
    6.     //递归边界,既然是按位枚举,最低位是0,那么pos==-1说明这个数我枚举完了  
    7.     if(pos==-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的,那么这里就需要你在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */  
    8.     //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)  
    9.     if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];  
    10.     /*常规写法都是在没有限制的条件记忆化,这里与下面记录状态是对应,具体为什么是有条件的记忆化后面会讲*/  
    11.     int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了  
    12.     ll ans=0;  
    13.     //开始计数  
    14.     for(int i=0;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了  
    15.     {  
    16.         if() ...  
    17.         else if()...  
    18.         ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的  
    19.         /*这里还算比较灵活,不过做几个题就觉得这里也是套路了 
    20.         大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论 
    21.         去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目 
    22.         要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类, 
    23.         前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/  
    24.     }  
    25.     //计算完,记录状态  
    26.     if(!limit && !lead) dp[pos][state]=ans;  
    27.     /*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/  
    28.     return ans;  
    29. }  
    30. ll solve(ll x)  
    31. {  
    32.     int pos=0;  
    33.     while(x)//把数位都分解出来  
    34.     {  
    35.         a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来,反正注意数位边界就行  
    36.         x/=10;  
    37.     }  
    38.     return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛  
    39. }  
    40. int main()  
    41. {  
    42.     ll le,ri;  
    43.     while(~scanf("%lld%lld",&le,&ri))  
    44.     {  
    45.         //初始化dp数组为-1,这里还有更加优美的优化,后面讲  
    46.         printf("%lld\n",solve(ri)-solve(le-1));  
    47.     }  
    48. }  

    相信读者还对这个有不少疑问,笔者认为有必要讲一下记忆化为什么是if(!limit)才行,大致就是说有无limit会出现状态冲突,举例:

    约束:数位上不能出现连续的两个1(11、112、211都是不合法的)

    假设就是[1,210]这个区间的个数

    状态:dp[pos][pre]:当前枚举到pos位,前面一位枚举的是pre(更加前面的位已经合法了),的个数(我的pos从0开始)

    先看错误的方法计数,就是不判limit就是直接记忆化

    那么假设我们第一次枚举了百位是0,显然后面的枚举limit=false,也就是数位上0到9的枚举,然后当我十位枚举了1,此时考虑dp[0][1],就是枚举到个位,前一位是1的个数,显然dp[0][1]=9;(个位只有是1的时候是不满足的),这个状态记录下来,继续dfs,一直到百位枚举了2,十位枚举了1,显然此时递归到了pos=0,pre=1的层,而dp[0][1]的状态已经有了即dp[pos][pre]!=-1;此时程序直接return dp[0][1]了,然而显然是错的,因为此时是有limit的个位只能枚举0,根本没有9个数,这就是状态冲突了。有lead的时候可能出现冲突,这只是两个最基本的不同的题目可能还要加限制,反正宗旨都是让dp状态唯一

    对于这个错误说两点:一是limit为true的数并不多,一个个枚举不会很浪费时间,所以我们记录下! limit的状态解决了不少子问题重叠。第二,有人可能想到把dp状态改一下dp[pos][state][limit]就是分别记录不同limit下的个数,这种方法一般是对的,关于这个具体会讲,下面有题bzoj3209会用到这个。

    数位的部分就是这些,然后就是难点,dp部分,dp大牛的艺术,弱鸡只能看看+...+

    既然从高位往低位枚举,那么状态一般都是与前面已经枚举的数位有关并且通常是根据约束条件当前枚举的这一位能使得状态完整(比如一个状态涉及到连续k位,那么就保存前k-1的状态,当前枚举的第k个是个恰好凑成成一个完整的状态,不过像那种状态是数位的和就直接保存前缀和为状态了),不过必然有一位最简单的一个状态dp[pos]当前枚举到了pos位。dp部分就要开始讲例题了,不过会介绍几种常用防tle的优化。

    实战篇

    例一:HDU 2089 不要62
    入门题。就是数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。
    dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。
    [cpp]  view plain  copy
    1. #include<iostream>  
    2. #include<cstdio>  
    3. #include<cstring>  
    4. #include<string>  
    5. using namespace std;  
    6. typedef long long ll;  
    7. int a[20];  
    8. int dp[20][2];  
    9. int dfs(int pos,int pre,int sta,bool limit)  
    10. {  
    11.     if(pos==-1) return 1;  
    12.     if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];  
    13.     int up=limit ? a[pos] : 9;  
    14.     int tmp=0;  
    15.     for(int i=0;i<=up;i++)  
    16.     {  
    17.         if(pre==6 && i==2)continue;  
    18.         if(i==4) continue;//都是保证枚举合法性  
    19.         tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);  
    20.     }  
    21.     if(!limit) dp[pos][sta]=tmp;  
    22.     return tmp;  
    23. }  
    24. int solve(int x)  
    25. {  
    26.     int pos=0;  
    27.     while(x)  
    28.     {  
    29.         a[pos++]=x%10;  
    30.         x/=10;  
    31.     }  
    32.     return dfs(pos-1,-1,0,true);  
    33. }  
    34. int main()  
    35. {  
    36.     int le,ri;  
    37.     //memset(dp,-1,sizeof dp);可优化  
    38.     while(~scanf("%d%d",&le,&ri) && le+ri)  
    39.     {  
    40.         memset(dp,-1,sizeof dp);  
    41.         printf("%d\n",solve(ri)-solve(le-1));  
    42.     }  
    43.     return 0;  
    44. }  

    入门就不多讲了,开始讲常用优化吧!

    第一:memset(dp,-1,sizeof dp);放在多组数据外面。

    这一点是一个数位特点,使用的条件是:约束条件是每个数自身的属性,而与输入无关。
    具体的:上一题不要62和4,这个约束对每一个数都是确定的,就是说任意一个数满不满足这个约束都是确定,比如444这个数,它不满足约束条件,不管你输入的区间是多少你都无法改变这个数不满足约束这个事实,这就是数自身的属性(我们每组数据只是在区间计数而已,只能说你输入的区间不包含444的话,我们就不把它统计在内,而无法改变任何事实)。
    由此,我们保存的状态就可以一直用(注意还有要limit,不同区间是会影响数位在有限制条件下的上限的)
    这点优化就不给具体题目了,这个还有进一步的扩展。不过说几个我遇到的简单的约束:
    1.求数位和是10的倍数的个数,这里简化为数位sum%10这个状态,即dp[pos][sum]这里10 是与多组无关的,所以可以memset优化,不过注意如果题目的模是输入的话那就不能这样了。
    2.求二进制1的数量与0的数量相等的个数,这个也是数自身的属性。
    3.。。。。。
    还是做题积累吧。搞懂思想!
    下面介绍的方法就是要行memset优化,把不满足前提的通过修改,然后优化。
    介绍之前,先说一种较为笨拙的修改,那就是增加状态,前面讲limit的地方说增加一维dp[pos][state][limit],能把不同情况下状态分别记录(不过这个不能memset放外面)。基于这个思想,我们考虑:约束为数位是p的倍数的个数,其中p数输入的,这和上面sum%10类似,但是dp[pos][sum]显然已经不行了,每次p可能都不一样,为了强行把memset提到外面加状态dp[pos][sum][p],对于每个不同p分别保存对应的状态。这里前提就比较简单了,你dp数组必须合法,p太大就G_G了。所以对于与输入有关的约束都可以强行增加状态(这并不代表能ac,如果题目数据少的话就随便你乱搞了)

    第二:相减。

    例题:HDU 4734
    题目给了个f(x)的定义:F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1,Ai是十进制数位,然后给出a,b求区间[0,b]内满足f(i)==f(a)的i的个数。
    常规想:这个f(x)计算就和数位计算是一样的,就是加了权值,所以dp[pos][sum],这状态是基本的。a是题目给定的,f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值,那就是dp[10][4600][4600],这显然不合法。
    这个时候就要用减法了,dp[pos][sum],sum不是存当前枚举的数的前缀和(加权的),而是枚举到当前pos位,后面还需要凑sum的权值和的个数,
    也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值,显然sum=0时就是满足的,后面的位数凑足sum位就可以了。
    仔细想想这个状态是与f(a)无关的(新手似乎很难理解),一个状态只有在sum=0时才满足,如果我们按常规的思想求f(i)的话,那么最后sum=f(a)才是满足的条件。
    [cpp]  view plain  copy
    1. #include<cstdio>  
    2. #include<cstring>  
    3. #include<iostream>  
    4. #include<string>  
    5.   
    6. using namespace std;  
    7. const int N=1e4+5;  
    8. int dp[12][N];  
    9. int f(int x)  
    10. {  
    11.     if(x==0) return 0;  
    12.     int ans=f(x/10);  
    13.     return ans*2+(x%10);  
    14. }  
    15. int all;  
    16. int a[12];  
    17. int dfs(int pos,int sum,bool limit)  
    18. {  
    19.     if(pos==-1) {return sum<=all;}  
    20.     if(sum>all) return 0;  
    21.     if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];  
    22.     int up=limit ? a[pos] : 9;  
    23.     int ans=0;  
    24.     for(int i=0;i<=up;i++)  
    25.     {  
    26.         ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);  
    27.     }  
    28.     if(!limit) dp[pos][all-sum]=ans;  
    29.     return ans;  
    30. }  
    31. int solve(int x)  
    32. {  
    33.     int pos=0;  
    34.     while(x)  
    35.     {  
    36.         a[pos++]=x%10;  
    37.         x/=10;  
    38.     }  
    39.     return dfs(pos-1,0,true);  
    40. }  
    41. int main()  
    42. {  
    43.     int a,ri;  
    44.     int T_T;  
    45.     int kase=1;  
    46.     scanf("%d",&T_T);  
    47.     memset(dp,-1,sizeof dp);  
    48.     while(T_T--)  
    49.     {  
    50.         scanf("%d%d",&a,&ri);  
    51.         all=f(a);  
    52.         printf("Case #%d: %d\n",kase++,solve(ri));  
    53.     }  
    54.     return 0;  
    55. }  

    减法的艺术!!!

    例题 POJ 3252
    这题的约束就是一个数的二进制中0的数量要不能少于1的数量,通过上一题,这题状态就很简单了,dp[pos][num],到当前数位pos,0的数量减去1的数量为num的方案数,一个简单的问题,中间某个pos位上num可能为负数(这不一定是非法的,因为我还没枚举完嘛,只要最终的num>=0才能判合法,中途某个pos就不一定了),这里比较好处理,Hash嘛,最小就-32吧(好像),直接加上32,把32当0用。这题主要是要想讲一下lead的用法,显然我要统计0的数量,前导零是有影响的。至于!lead&&!limit才能dp,都是类似的,自己慢慢体会吧。
    [cpp]  view plain  copy
    1. #pragma comment(linker, "/STACK:10240000,10240000")  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<string>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<vector>  
    9. #include<map>  
    10. #include<stack>  
    11. #include<cmath>  
    12. #include<algorithm>  
    13. using namespace std;  
    14. const double R=0.5772156649015328606065120900;  
    15. const int N=1e5+5;  
    16. const int mod=1e9+7;  
    17. const int INF=0x3f3f3f3f;  
    18. const double eps=1e-8;  
    19. const double pi=acos(-1.0);  
    20. typedef long long ll;  
    21. int dp[35][66];  
    22. int a[66];  
    23. int dfs(int pos,int sta,bool lead,bool limit)  
    24. {  
    25.     if(pos==-1)  
    26.         return sta>=32;  
    27.     if(!limit && !lead && dp[pos][sta]!=-1) return dp[pos][sta];  
    28.     int up=limit?a[pos]:1;  
    29.     int ans=0;  
    30.     for(int i=0;i<=up;i++)  
    31.     {  
    32.         if(lead && i==0) ans+=dfs(pos-1,sta,lead,limit && i==a[pos]);//有前导零就不统计在内  
    33.         else ans+=dfs(pos-1,sta+(i==0?1:-1),lead && i==0,limit && i==a[pos]);  
    34.     }  
    35.     if(!limit && !lead ) dp[pos][sta]=ans;  
    36.     return ans;  
    37. }  
    38. int solve(int x)  
    39. {  
    40.     int pos=0;  
    41.     while(x)  
    42.     {  
    43.         a[pos++]=x&1;  
    44.         x>>=1;  
    45.     }  
    46.     return dfs(pos-1,32,true,true);  
    47. }  
    48. int main()  
    49. {  
    50.     memset(dp,-1,sizeof dp);  
    51.     int a,b;  
    52.     while(~scanf("%d%d",&a,&b))  
    53.     {  
    54.         printf("%d\n",solve(b)-solve(a-1));  
    55.     }  
    56.     return 0;  
    57. }  
    然后就是一些需要自己yy的题:
    HDU 3709 这题就是要枚举中轴,然后数位dp
    UVA 1305 这题我二分然后数位dp搞(好像不是正解,我水过的)
    Hbzoj 1799 这题讲一下:
    (偷偷告诉你,这个oj是单组测试,然后memset什么的都是浮云了)
    约束:一个数是它自己数位和的倍数,直接dp根本找不到状态,枚举数位和,因为总就162,然后问题就变成了一个数%mod=0,mod是枚举的,想想状态:dp[pos][sum][val],当前pos位上数位和是sum,val就是在算这个数%mod,(从高位算  *10+i),因为我们枚举的数要保证数位和等于mod,还要保证这个数是mod的倍数,很自然就能找到这些状态,显然对于每一个mod,val不能保证状态唯一,这是你要是想加一维dp[pos][sum][val][mod],记录每一个mod的状态(这里sum可以用减法,然而val不行,就只能加一维),那你就想太多了,这样是会超时的(因为状态太多,记忆化效果不好)。这里直接对每一个mod,memset一次就能ac。下面的代码还把limit的当做了状态,因为每次都要初始化,所以能这样,memset在多组外面是不能这样的,不过奇葩的,这代码,如果不把limit当状态,还是在!limit 条件下记录dp,提交一发,时间竟然更短了,可能是每次memset的关系!!!
    [cpp]  view plain  copy
    1. #include<cstdio>  
    2. #include<cstring>  
    3. #include<iostream>  
    4. #include<string>  
    5.   
    6. using namespace std;  
    7.   
    8. typedef long long ll;  
    9.   
    10. ll dp[20][163][163][2];  
    11. int a[20];  
    12. ll dfs(int pos,int sum,int val,int mod,bool limit)  
    13. {  
    14.     if(sum-9*pos-9>0) return 0;//最坏的情况,这一位及后面的全部为9都不能达到0那就直接GG,这个剪枝不会影响ac  
    15.     if(pos==-1) return sum==0 && val==0;  
    16.     if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit];  
    17.     int up=limit?a[pos]:9;  
    18.     ll ans=0;  
    19.     for(int i=0;i<=up;i++)  
    20.     {  
    21.         if(sum-i<0) break;  
    22.         ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit && i==a[pos]);  
    23.     }  
    24.     dp[pos][sum][val][limit]=ans;  
    25.     return ans;  
    26. }  
    27. ll solve(ll x)  
    28. {  
    29.     int pos=0;  
    30.     while(x)  
    31.     {  
    32.         a[pos++]=x%10;  
    33.         x/=10;  
    34.     }  
    35.     ll ans=0;  
    36.     for(int i=1;i<=pos*9;i++)//上限就是每一位都是9  
    37.     {  
    38.         memset(dp,-1,sizeof dp);  
    39.         ll tmp=dfs(pos-1,i,0,i,true);  
    40.         ans+=tmp;  
    41.     }  
    42.     return ans;  
    43. }  
    44. int main()  
    45. {  
    46. //    cout<<18*9<<endl;  
    47.     ll le,ri;  
    48. //    memset(dp,-1,sizeof dp);  
    49.     while(~scanf("%lld%lld",&le,&ri))  
    50.         printf("%lld\n",solve(ri)-solve(le-1));  
    51.     return 0;  
    52. }  
    53. /* 
    54. 1 1000000000000000000 
    55. */  
    基本讲的差不多了。前段时间学了点新东西!!

    新的领域--计数转求和

    这题麻烦就是要求数的平方和。
    我们先考虑求和的问题,一个区间,数位dp能在一些约束下计数,现在要这些数的和。其实组合数学搞搞就可以了:如 现在枚举的某一位pos,我统计了这一位枚举i的满足条件的个数cnt,其实只要算i对总和的贡献就可以了,对于一个数而已第pos位是i,那么对求和贡献就是i*10^pos,就是十进制的权值,然后有cnt个数都满足第pos位是i,最后sum=cnt*i*10^pos.原理就是这样平方和可以看做(a*10^pos+b)^2,a是你当前pos位要枚举的,b其实是个自问题,就是pos之后的位的贡献值,把这个平方展开就可以了!
    [cpp]  view plain  copy
    1. #pragma comment(linker, "/STACK:10240000,10240000")  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<string>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<vector>  
    9. #include<map>  
    10. #include<stack>  
    11. #include<cmath>  
    12. #include<algorithm>  
    13. using namespace std;  
    14. const double R=0.5772156649015328606065120900;  
    15. const int N=1e5+5;  
    16. const int mod=1e9+7;  
    17. const int INF=0x3f3f3f3f;  
    18. const double eps=1e-8;  
    19. const double pi=acos(-1.0);  
    20. typedef long long ll;  
    21. ll fact[20];  
    22. void init()  
    23. {  
    24.     fact[0]=1;  
    25.     for(int i=1;i<20;i++)  
    26.         fact[i]=fact[i-1]*10%mod;  
    27. }  
    28. struct node  
    29. {  
    30.     ll cnt,sum,sqr;  
    31.     node(ll cnt=-1,ll sum=0,ll sqr=0):cnt(cnt),sum(sum),sqr(sqr){}  
    32. }dp[20][7][7];  
    33. int a[20];  
    34. ll fac(ll x)  
    35. {  
    36.     return x*x%mod;  
    37. }  
    38. ll dfs(int pos,ll num,ll val,ll&cnt,ll&sum,bool limit)  
    39. {  
    40.     if(pos==-1) {  
    41.         if(num==0 || val==0)  
    42.             return 0;  
    43.         cnt=1;  
    44.         return 0;  
    45.     }  
    46.     if(!limit && dp[pos][num][val].cnt!=-1) {  
    47.             cnt=dp[pos][num][val].cnt;  
    48.             sum=dp[pos][num][val].sum;  
    49.             return dp[pos][num][val].sqr;  
    50.     }  
    51.     int up=limit?a[pos]:9;  
    52.     ll sq=0;  
    53.     for(int i=0;i<=up;i++)  
    54.     if(i!=7)  
    55.     {  
    56.         ll cn=0,su=0;  
    57.         ll tmp=dfs(pos-1,(num+i)%7,(val*10+i)%7,cn,su,limit && i==a[pos]);  
    58.         ll tm=i*fact[pos]%mod;  
    59.         tmp=(tmp+fac(tm)*cn%mod+(tm*su%mod)*2%mod)%mod;//计数之后要更新sum,sqr  
    60.         sum=(sum+su+(i*fact[pos]%mod)*cn%mod)%mod;  
    61.         cnt=(cnt+cn)%mod;  
    62.         sq=(sq+tmp)%mod;  
    63.     }  
    64.     if(!limit) dp[pos][num][val]=node(cnt,sum,sq);  
    65.     return sq;  
    66. }  
    67. ll solve(ll x)  
    68. {  
    69.     int pos=0;  
    70.     while(x)  
    71.     {  
    72.         a[pos++]=x%10;  
    73.         x/=10;  
    74.     }  
    75.     ll t1=0,t2=0;  
    76.     return dfs(pos-1,0,0,t1,t2,true);  
    77. }  
    78. bool judge(ll x)  
    79. {  
    80.     int sum=0;  
    81.     int pos=0;  
    82.     if(x%7==0) return false;  
    83.     while(x)  
    84.     {  
    85.         if(x%10==7) return false;  
    86.         sum+=x%10;  
    87.         x/=10;  
    88.     }  
    89.     sum%=7;  
    90.     return sum!=0;  
    91. }  
    92. int main()  
    93. {  
    94.     init();  
    95.     for(int i=0;i<20;i++)  
    96.         for(int j=0;j<7;j++)  
    97.         for(int k=0;k<7;k++)//memset  
    98.     {  
    99.         dp[i][j][k].cnt=-1;  
    100.         dp[i][j][k].sum=0;  
    101.         dp[i][j][k].sqr=0;  
    102.     }  
    103.     int T_T;  
    104.     scanf("%d",&T_T);  
    105.     while(T_T--)  
    106.     {  
    107.         ll le,ri;  
    108.         scanf("%I64d%I64d",&le,&ri);  
    109.         ll ans=solve(ri)-solve(le-1);  
    110.         ans=(ans%mod+mod)%mod;  
    111.         printf("%I64d\n",ans);  
    112.     }  
    113.     return 0;  
    114. }  
    做题去~~

    展开全文
  • 数位DP.pdf

    2015-07-12 15:11:42
    数位DP整理的模板和一些题目的题解。QAQ没钱下载资源了只好上传点东西。
  • 数位dp

    万次阅读 2018-11-17 21:38:32
    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位...

    原文地址:
    https://blog.csdn.net/brazy/article/details/77427699

    觉得写得很不错~~

    =我是可爱的分割线啦=

    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位…数的每一位就是数位啦!

    之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使得新的枚举方式满足dp的性质,然后记忆化就可以了。

    两种不同的枚举:对于一个求区间[le,ri]满足条件数的个数,最简单的暴力如下:

    for(int i=le;i<=ri;i++)  
            if(right(i)) ans++;  
    

    然而这样枚举不方便记忆化,或者说根本无状态可言。
    新的枚举:控制上界枚举,从最高位开始往下枚举,例如:ri=213,那么我们从百位开始枚举:百位可能的情况有0,1,2(觉得这里枚举0有问题的继续看)

    然后每一位枚举都不能让枚举的这个数超过上界213(下界就是0或者1,这个次要),当百位枚举了1,那么十位枚举就是从0到9,因为百位1已经比上界2小了,后面数位枚举什么都不可能超过上界。所以问题就在于:当高位枚举刚好达到上界是,那么紧接着的一位枚举就有上界限制了。具体的这里如果百位枚举了2,那么十位的枚举情况就是0到1,如果前两位枚举了21,最后一位之是0到3(这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。最后一个问题:最高位枚举0:百位枚举0,相当于此时我枚举的这个数最多是两位数,如果十位继续枚举0,那么我枚举的就是以为数咯,因为我们要枚举的是小于等于ri的所以数,当然不能少了位数比ri小的咯!(这样枚举是为了无遗漏的枚举,不过可能会带来一个问题,就是前导零的问题,模板里用lead变量表示,不过这个不是每个题目都是会有影响的,可能前导零不会影响我们计数,具体要看题目)

    由于这种新的枚举只控制了上界所以我们的Main函数总是这样:

    int main()  
    {  
        long long le,ri;  
        while(~scanf("%lld%lld",&le,&ri))  
            printf("%lld\n",solve(ri)-solve(le-1));  
    }  
    

    w_w 是吧!统计[1,ri]数量和[1,le-1],然后相减就是区间[le,ri]的数量了,这里我写的下界是1,其实0也行,反正相减后就没了,注意题目中le的范围都是大于等于1的(不然le=0,再减一就G_G了)
    在讲例题之前先讲个基本的动态模板(先看后面的例题也行):dp思想,枚举到当前位置pos,状态为state(这个就是根据题目来的,可能很多,毕竟dp千变万化)的数量(既然是计数,dp值显然是保存满足条件数的个数)

    typedef long long ll;  
    int a[20];  
    ll dp[20][state];//不同题目状态不同  
    ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零  
    {  
        //递归边界,既然是按位枚举,最低位是0,那么pos==-1说明这个数我枚举完了  
        if(pos==-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的,那么这里就需要你在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */  
        //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)  
        if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];  
        /*常规写法都是在没有限制的条件记忆化,这里与下面记录状态是对应,具体为什么是有条件的记忆化后面会讲*/  
        int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了  
        ll ans=0;  
        //开始计数  
        for(int i=0;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了  
        {  
            if() ...  
            else if()...  
            ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的  
            /*这里还算比较灵活,不过做几个题就觉得这里也是套路了 
            大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论 
            去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目 
            要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类, 
            前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/  
        }  
        //计算完,记录状态  
        if(!limit && !lead) dp[pos][state]=ans;  
        /*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/  
        return ans;  
    }  
    ll solve(ll x)  
    {  
        int pos=0;  
        while(x)//把数位都分解出来  
        {  
            a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来,反正注意数位边界就行  
            x/=10;  
        }  
        return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛  
    }  
    int main()  
    {  
        ll le,ri;  
        while(~scanf("%lld%lld",&le,&ri))  
        {  
            //初始化dp数组为-1,这里还有更加优美的优化,后面讲  
            printf("%lld\n",solve(ri)-solve(le-1));  
        }  
    }  
    
    
    展开全文
  • 数位dp总结 之 从入门到模板

    万次阅读 多人点赞 2018-08-07 08:49:57
    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每...

    转自巨佬:https://blog.csdn.net/wust_zzwh/article/details/52100392

    基础篇

    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每一位就是数位啦!

     

    之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使得新的枚举方式满足dp的性质,然后记忆化就可以了。

    两种不同的枚举:对于一个求区间[le,ri]满足条件数的个数,最简单的暴力如下:

    for(int i=le;i<=ri;i++)
    
    if(right(i)) ans++;


    然而这样枚举不方便记忆化,或者说根本无状态可言。

     

    新的枚举:控制上界枚举,从最高位开始往下枚举,例如:ri=213,那么我们从百位开始枚举:百位可能的情况有0,1,2(觉得这里枚举0有问题的继续看)

    然后每一位枚举都不能让枚举的这个数超过上界213(下界就是0或者1,这个次要),当百位枚举了1,那么十位枚举就是从0到9,因为百位1已经比上界2小了,后面数位枚举什么都不可能超过上界。所以问题就在于:当高位枚举刚好达到上界是,那么紧接着的一位枚举就有上界限制了。具体的这里如果百位枚举了2,那么十位的枚举情况就是0到1,如果前两位枚举了21,最后一位之是0到3(这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。最后一个问题:最高位枚举0:百位枚举0,相当于此时我枚举的这个数最多是两位数,如果十位继续枚举0,那么我枚举的就是以为数咯,因为我们要枚举的是小于等于ri的所以数,当然不能少了位数比ri小的咯!(这样枚举是为了无遗漏的枚举,不过可能会带来一个问题,就是前导零的问题,模板里用lead变量表示,不过这个不是每个题目都是会有影响的,可能前导零不会影响我们计数,具体要看题目)

    由于这种新的枚举只控制了上界所以我们的Main函数总是这样:

    int main()
    {
        long long le,ri;
        while(~scanf("%lld%lld",&le,&ri))
            printf("%lld\n",solve(ri)-solve(le-1));
    }

     w_w 是吧!统计[1,ri]数量和[1,le-1],然后相减就是区间[le,ri]的数量了,这里我写的下界是1,其实0也行,反正相减后就没了,注意题目中le的范围都是大于等于1的(不然le=0,再减一就G_G了)

    在讲例题之前先讲个基本的动态模板(先看后面的例题也行):dp思想,枚举到当前位置pos,状态为state(这个就是根据题目来的,可能很多,毕竟dp千变万化)的数量(既然是计数,dp值显然是保存满足条件数的个数)

    typedef long long ll;
    int a[20];
    ll dp[20][state];//不同题目状态不同
    ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
    {
        //递归边界,既然是按位枚举,最低位是0,那么pos==-1说明这个数我枚举完了
        if(pos==-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的,那么这里就需要你在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
        //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
        if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
        /*常规写法都是在没有限制的条件记忆化,这里与下面记录状态是对应,具体为什么是有条件的记忆化后面会讲*/
        int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
        ll ans=0;
        //开始计数
        for(int i=0;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了
        {
            if() ...
            else if()...
            ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
            /*这里还算比较灵活,不过做几个题就觉得这里也是套路了
            大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论
            去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目
            要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类,
            前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/
        }
        //计算完,记录状态
        if(!limit && !lead) dp[pos][state]=ans;
        /*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
        return ans;
    }
    ll solve(ll x)
    {
        int pos=0;
        while(x)//把数位都分解出来
        {
            a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来,反正注意数位边界就行
            x/=10;
        }
        return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
    }
    int main()
    {
        ll le,ri;
        while(~scanf("%lld%lld",&le,&ri))
        {
            //初始化dp数组为-1,这里还有更加优美的优化,后面讲
            printf("%lld\n",solve(ri)-solve(le-1));
        }
    }

     相信读者还对这个有不少疑问,笔者认为有必要讲一下记忆化为什么是if(!limit)才行,大致就是说有无limit会出现状态冲突,举例:

     

    约束:数位上不能出现连续的两个1(11、112、211都是不合法的)

    假设就是[1,210]这个区间的个数

    状态:dp[pos][pre]:当前枚举到pos位,前面一位枚举的是pre(更加前面的位已经合法了),的个数(我的pos从0开始)

    先看错误的方法计数,就是不判limit就是直接记忆化

    那么假设我们第一次枚举了百位是0,显然后面的枚举limit=false,也就是数位上0到9的枚举,然后当我十位枚举了1,此时考虑dp[0][1],就是枚举到个位,前一位是1的个数,显然dp[0][1]=9;(个位只有是1的时候是不满足的),这个状态记录下来,继续dfs,一直到百位枚举了2,十位枚举了1,显然此时递归到了pos=0,pre=1的层,而dp[0][1]的状态已经有了即dp[pos][pre]!=-1;此时程序直接return dp[0][1]了,然而显然是错的,因为此时是有limit的个位只能枚举0,根本没有9个数,这就是状态冲突了。有lead的时候可能出现冲突,这只是两个最基本的不同的题目可能还要加限制,反正宗旨都是让dp状态唯一

    对于这个错误说两点:一是limit为true的数并不多,一个个枚举不会很浪费时间,所以我们记录下! limit的状态解决了不少子问题重叠。第二,有人可能想到把dp状态改一下dp[pos][state][limit]就是分别记录不同limit下的个数,这种方法一般是对的,关于这个具体会讲,下面有题bzoj3209会用到这个。

    数位的部分就是这些,然后就是难点,dp部分,dp大牛的艺术,弱鸡只能看看+...+

    既然从高位往低位枚举,那么状态一般都是与前面已经枚举的数位有关并且通常是根据约束条件当前枚举的这一位能使得状态完整(比如一个状态涉及到连续k位,那么就保存前k-1的状态,当前枚举的第k个是个恰好凑成成一个完整的状态,不过像那种状态是数位的和就直接保存前缀和为状态了),不过必然有一位最简单的一个状态dp[pos]当前枚举到了pos位。dp部分就要开始讲例题了,不过会介绍几种常用防tle的优化。

    实战篇

    例一:HDU 2089 不要62

    入门题。就是数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。

    dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    using namespace std;
    typedef long long ll;
    int a[20];
    int dp[20][2];
    int dfs(int pos,int pre,int sta,bool limit)
    {
        if(pos==-1) return 1;
        if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
        int up=limit ? a[pos] : 9;
        int tmp=0;
        for(int i=0;i<=up;i++)
        {
            if(pre==6 && i==2)continue;
            if(i==4) continue;//都是保证枚举合法性
            tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);
        }
        if(!limit) dp[pos][sta]=tmp;
        return tmp;
    }
    int solve(int x)
    {
        int pos=0;
        while(x)
        {
            a[pos++]=x%10;
            x/=10;
        }
        return dfs(pos-1,-1,0,true);
    }
    int main()
    {
        int le,ri;
        //memset(dp,-1,sizeof dp);可优化
        while(~scanf("%d%d",&le,&ri) && le+ri)
        {
            memset(dp,-1,sizeof dp);
            printf("%d\n",solve(ri)-solve(le-1));
        }
        return 0;
    }

     

    入门就不多讲了,开始讲常用优化吧!

    第一:memset(dp,-1,sizeof dp);放在多组数据外面。

    这一点是一个数位特点,使用的条件是:约束条件是每个数自身的属性,而与输入无关。

    具体的:上一题不要62和4,这个约束对每一个数都是确定的,就是说任意一个数满不满足这个约束都是确定,比如444这个数,它不满足约束条件,不管你输入的区间是多少你都无法改变这个数不满足约束这个事实,这就是数自身的属性(我们每组数据只是在区间计数而已,只能说你输入的区间不包含444的话,我们就不把它统计在内,而无法改变任何事实)。

    由此,我们保存的状态就可以一直用(注意还有要limit,不同区间是会影响数位在有限制条件下的上限的)

    这点优化就不给具体题目了,这个还有进一步的扩展。不过说几个我遇到的简单的约束:

    1.求数位和是10的倍数的个数,这里简化为数位sum%10这个状态,即dp[pos][sum]这里10 是与多组无关的,所以可以memset优化,不过注意如果题目的模是输入的话那就不能这样了。

    2.求二进制1的数量与0的数量相等的个数,这个也是数自身的属性。

    3.。。。。。

    还是做题积累吧。搞懂思想!

    下面介绍的方法就是要行memset优化,把不满足前提的通过修改,然后优化。

    介绍之前,先说一种较为笨拙的修改,那就是增加状态,前面讲limit的地方说增加一维dp[pos][state][limit],能把不同情况下状态分别记录(不过这个不能memset放外面)。基于这个思想,我们考虑:约束为数位是p的倍数的个数,其中p数输入的,这和上面sum%10类似,但是dp[pos][sum]显然已经不行了,每次p可能都不一样,为了强行把memset提到外面加状态dp[pos][sum][p],对于每个不同p分别保存对应的状态。这里前提就比较简单了,你dp数组必须合法,p太大就G_G了。所以对于与输入有关的约束都可以强行增加状态(这并不代表能ac,如果题目数据少的话就随便你乱搞了)

    第二:相减。

    例题:HDU 4734

    题目给了个f(x)的定义:F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1,Ai是十进制数位,然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。

    常规想:这个f(x)计算就和数位计算是一样的,就是加了权值,所以dp[pos][sum],这状态是基本的。a是题目给定的,f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值,那就是dp[10][4600][4600],这显然不合法。

    这个时候就要用减法了,dp[pos][sum],sum不是存当前枚举的数的前缀和(加权的),而是枚举到当前pos位,后面还需要凑sum的权值和的个数,

    也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值,那么最后枚举完所有位 sum>=0时就是满足的,后面的位数凑足sum位就可以了。

    仔细想想这个状态是与f(a)无关的(新手似乎很难理解),一个状态只有在sum>=0时才满足,如果我们按常规的思想求f(i)的话,那么最后sum>=f(a)才是满足的条件。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<string>
     
    using namespace std;
    const int N=1e4+5;
    int dp[12][N];
    int f(int x)
    {
        if(x==0) return 0;
        int ans=f(x/10);
        return ans*2+(x%10);
    }
    int all;
    int a[12];
    int dfs(int pos,int sum,bool limit)
    {
        if(pos==-1) {return sum<=all;}
        if(sum>all) return 0;
        if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];
        int up=limit ? a[pos] : 9;
        int ans=0;
        for(int i=0;i<=up;i++)
        {
            ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);
        }
        if(!limit) dp[pos][all-sum]=ans;
        return ans;
    }
    int solve(int x)
    {
        int pos=0;
        while(x)
        {
            a[pos++]=x%10;
            x/=10;
        }
        return dfs(pos-1,0,true);
    }
    int main()
    {
        int a,ri;
        int T_T;
        int kase=1;
        scanf("%d",&T_T);
        memset(dp,-1,sizeof dp);
        while(T_T--)
        {
            scanf("%d%d",&a,&ri);
            all=f(a);
            printf("Case #%d: %d\n",kase++,solve(ri));
        }
        return 0;
    }

     

    减法的艺术!!!

     

    例题 POJ 3252

    这题的约束就是一个数的二进制中0的数量要不能少于1的数量,通过上一题,这题状态就很简单了,dp[pos][num],到当前数位pos,0的数量减去1的数量不少于num的方案数,一个简单的问题,中间某个pos位上num可能为负数(这不一定是非法的,因为我还没枚举完嘛,只要最终的num>=0才能判合法,中途某个pos就不一定了),这里比较好处理,Hash嘛,最小就-32吧(好像),直接加上32,把32当0用。这题主要是要想讲一下lead的用法,显然我要统计0的数量,前导零是有影响的。至于!lead&&!limit才能dp,都是类似的,自己慢慢体会吧。

    #pragma comment(linker, "/STACK:10240000,10240000")
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<set>
    #include<vector>
    #include<map>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const double R=0.5772156649015328606065120900;
    const int N=1e5+5;
    const int mod=1e9+7;
    const int INF=0x3f3f3f3f;
    const double eps=1e-8;
    const double pi=acos(-1.0);
    typedef long long ll;
    int dp[35][66];
    int a[66];
    int dfs(int pos,int sta,bool lead,bool limit)
    {
        if(pos==-1)
            return sta>=32;
        if(!limit && !lead && dp[pos][sta]!=-1) return dp[pos][sta];
        int up=limit?a[pos]:1;
        int ans=0;
        for(int i=0;i<=up;i++)
        {
            if(lead && i==0) ans+=dfs(pos-1,sta,lead,limit && i==a[pos]);//有前导零就不统计在内
            else ans+=dfs(pos-1,sta+(i==0?1:-1),lead && i==0,limit && i==a[pos]);
        }
        if(!limit && !lead ) dp[pos][sta]=ans;
        return ans;
    }
    int solve(int x)
    {
        int pos=0;
        while(x)
        {
            a[pos++]=x&1;
            x>>=1;
        }
        return dfs(pos-1,32,true,true);
    }
    int main()
    {
        memset(dp,-1,sizeof dp);
        int a,b;
        while(~scanf("%d%d",&a,&b))
        {
            printf("%d\n",solve(b)-solve(a-1));
        }
        return 0;
    }

    然后就是一些需要自己yy的题:

    HDU 3709 这题就是要枚举中轴,然后数位dp

    UVA 1305 这题我二分然后数位dp搞(好像不是正解,我水过的)

    Hbzoj 1799 这题讲一下:

    (偷偷告诉你,这个oj是单组测试,然后memset什么的都是浮云了)

    约束:一个数是它自己数位和的倍数,直接dp根本找不到状态,枚举数位和,因为总就162,然后问题就变成了一个数%mod=0,mod是枚举的,想想状态:dp[pos][sum][val],当前pos位上数位和是sum,val就是在算这个数%mod,(从高位算  *10+i),因为我们枚举的数要保证数位和等于mod,还要保证这个数是mod的倍数,很自然就能找到这些状态,显然对于每一个mod,val不能保证状态唯一,这是你要是想加一维dp[pos][sum][val][mod],记录每一个mod的状态(这里sum可以用减法,然而val不行,就只能加一维),那你就想太多了,这样是会超时的(因为状态太多,记忆化效果不好)。这里直接对每一个mod,memset一次就能ac。下面的代码还把limit的当做了状态,因为每次都要初始化,所以能这样,memset在多组外面是不能这样的,不过奇葩的,这代码,如果不把limit当状态,还是在!limit 条件下记录dp,提交一发,时间竟然更短了,可能是每次memset的关系!!!

     

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<string>
     
    using namespace std;
     
    typedef long long ll;
     
    ll dp[20][163][163][2];
    int a[20];
    ll dfs(int pos,int sum,int val,int mod,bool limit)
    {
        if(sum-9*pos-9>0) return 0;//最坏的情况,这一位及后面的全部为9都不能达到0那就直接GG,这个剪枝不会影响ac
        if(pos==-1) return sum==0 && val==0;
        if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit];
        int up=limit?a[pos]:9;
        ll ans=0;
        for(int i=0;i<=up;i++)
        {
            if(sum-i<0) break;
            ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit && i==a[pos]);
        }
        dp[pos][sum][val][limit]=ans;
        return ans;
    }
    ll solve(ll x)
    {
        int pos=0;
        while(x)
        {
            a[pos++]=x%10;
            x/=10;
        }
        ll ans=0;
        for(int i=1;i<=pos*9;i++)//上限就是每一位都是9
        {
            memset(dp,-1,sizeof dp);
            ll tmp=dfs(pos-1,i,0,i,true);
            ans+=tmp;
        }
        return ans;
    }
    int main()
    {
    //    cout<<18*9<<endl;
        ll le,ri;
    //    memset(dp,-1,sizeof dp);
        while(~scanf("%lld%lld",&le,&ri))
            printf("%lld\n",solve(ri)-solve(le-1));
        return 0;
    }
    /*
    1 1000000000000000000
    */

    基本讲的差不多了。前段时间学了点新东西!!

     

    新的领域--计数转求和

    HDU 4507

    这题麻烦就是要求数的平方和。

    我们先考虑求和的问题,一个区间,数位dp能在一些约束下计数,现在要这些数的和。其实组合数学搞搞就可以了:如 现在枚举的某一位pos,我统计了这一位枚举i的满足条件的个数cnt,其实只要算i对总和的贡献就可以了,对于一个数而言第pos位是i,那么对求和贡献就是i*10^pos,就是十进制的权值,然后有cnt个数都满足第pos位是i,最后sum=cnt*i*10^pos.原理就是这样平方和可以看做(a*10^pos+b)^2,a是你当前pos位要枚举的,b其实是个子问题,就是pos之后的位的贡献值,把这个平方展开就可以了!

    #pragma comment(linker, "/STACK:10240000,10240000")
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<set>
    #include<vector>
    #include<map>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const double R=0.5772156649015328606065120900;
    const int N=1e5+5;
    const int mod=1e9+7;
    const int INF=0x3f3f3f3f;
    const double eps=1e-8;
    const double pi=acos(-1.0);
    typedef long long ll;
    ll fact[20];
    void init()
    {
        fact[0]=1;
        for(int i=1;i<20;i++)
            fact[i]=fact[i-1]*10%mod;
    }
    struct node
    {
        ll cnt,sum,sqr;
        node(ll cnt=-1,ll sum=0,ll sqr=0):cnt(cnt),sum(sum),sqr(sqr){}
    }dp[20][7][7];
    int a[20];
    ll fac(ll x)
    {
        return x*x%mod;
    }
    ll dfs(int pos,ll num,ll val,ll&cnt,ll&sum,bool limit)
    {
        if(pos==-1) {
            if(num==0 || val==0)
                return 0;
            cnt=1;
            return 0;
        }
        if(!limit && dp[pos][num][val].cnt!=-1) {
                cnt=dp[pos][num][val].cnt;
                sum=dp[pos][num][val].sum;
                return dp[pos][num][val].sqr;
        }
        int up=limit?a[pos]:9;
        ll sq=0;
        for(int i=0;i<=up;i++)
        if(i!=7)
        {
            ll cn=0,su=0;
            ll tmp=dfs(pos-1,(num+i)%7,(val*10+i)%7,cn,su,limit && i==a[pos]);
            ll tm=i*fact[pos]%mod;
            tmp=(tmp+fac(tm)*cn%mod+(tm*su%mod)*2%mod)%mod;//计数之后要更新sum,sqr
            sum=(sum+su+(i*fact[pos]%mod)*cn%mod)%mod;
            cnt=(cnt+cn)%mod;
            sq=(sq+tmp)%mod;
        }
        if(!limit) dp[pos][num][val]=node(cnt,sum,sq);
        return sq;
    }
    ll solve(ll x)
    {
        int pos=0;
        while(x)
        {
            a[pos++]=x%10;
            x/=10;
        }
        ll t1=0,t2=0;
        return dfs(pos-1,0,0,t1,t2,true);
    }
    bool judge(ll x)
    {
        int sum=0;
        int pos=0;
        if(x%7==0) return false;
        while(x)
        {
            if(x%10==7) return false;
            sum+=x%10;
            x/=10;
        }
        sum%=7;
        return sum!=0;
    }
    int main()
    {
        init();
        for(int i=0;i<20;i++)
            for(int j=0;j<7;j++)
            for(int k=0;k<7;k++)//memset
        {
            dp[i][j][k].cnt=-1;
            dp[i][j][k].sum=0;
            dp[i][j][k].sqr=0;
        }
        int T_T;
        scanf("%d",&T_T);
        while(T_T--)
        {
            ll le,ri;
            scanf("%I64d%I64d",&le,&ri);
            ll ans=solve(ri)-solve(le-1);
            ans=(ans%mod+mod)%mod;
            printf("%I64d\n",ans);
        }
        return 0;
    }

     

    展开全文
  • 【算法小讲堂】数位dp(简单入门)

    千次阅读 多人点赞 2019-03-19 22:35:24
     数位dp(打牌),这是一个相当深刻的话题。在不会这个内容的时候就是一脸懵逼。这里我们主要介绍的是dfs模式实现的数位打牌模式  当然博主也不是说自己会这个高深的算法了,只是看(抄)完别人的代码,突有所悟...

    数位打牌

    爷爷,你没有关注的博主又更新博客啦!!

    数位dp(打牌),这是一个相当深刻并且具有意义的话题。在没看懂这个内容的时候完完全全就是一脸懵逼,现在依旧是一脸懵逼。你以为你会了,题目:不,你不会!!就像你可能以为博主已经掌握了这个算法。
    欸,你错了,我压根就不会。
     在这里插入图片描述
    博主只是看(抄)完别人的代码,突有所悟。又厚颜无耻的出一期博客(瞎bb)!
      
    在这里插入图片描述
    好了!今天,在这里,我主要介绍的是dfs模式实现的数位打牌模式 ;先来个简单点的问题吧。

    给出一个数n,1~n有多少数包含49,测试数据1<=T<=10000,1<=n<=2^63-1

    样例

    3
    1
    50
    500

    输出

    0
    1
    15

    看完这个,就是下面这表情

    在这里插入图片描述
    那么我们开始讲讲思路:
     这个问题怎么搞呢,首先我们看到n的范围非常的大,根本没有办法一个一个判断。这时候开动我们的脑袋瓜子,那我们可不可几十个几十个,或者几百个几百个一次算呢?Of course!why not!,这,就是我们打牌数组的来历(dp数组的作用),举个栗子,比如1~500的范围中:1–100,101–200,201–300,都是有一样的个数的符合条件的数字的,因为他们的最高位都与49的4无关,所以这三个区段又与401-500之间的个数不同,综上我们的打牌数组只需要两个维度dp【位数】【最高位是不是4】。接下来就是按从高到低依次枚举就好了。
    ----哇,博主,看你这么多,我完全没懂啊!
    ----莫慌,先看代码,下面还有讲解。

    看代码!接招!

    #include<bits/stdc++.h>
    using namespace std;
    const int Max = 99999;
    const int Min = 0;
    const int inf = 1e6;
    const int mod = 1e9+7;
    #define M 1000
    #define N 1000
    #define ll long long
    #define swap(x,y) x^=y^=x^=y
    ll dp[20][6];
    int digit[20];
    ll dfs(int pos,int pre,int sta,bool limit){  //以53421为例 
    	if(pos==-1) return 1;                   //代表这种情况搜索结束,+1 
    	if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];           //如果没有达到上限比如搜索0--50000 的时候,第一位是0,1,2,3,4的时候没有限制,5的时候有 
    	int up = limit?digit[pos]:9;                                  //有限制的话选取下一位的值,如万位是0,1,2,3,4,千位可以是1-9,但是万位是5,千位不能超过3 
    	ll sum(0); 
    	for(int i=0;i<=up;i++){                                       //每一位进行枚举 
    		if(pre==4&&i==9) continue;                                 //符合条件的不搜了 
    		sum += dfs(pos-1,i,i==4,limit&&i==digit[pos]);             //不符合条件的加上,pre记录这一位的值,sta记录是否有可能成为49,最后一个表示是否有限制 
    	}
    	if(!limit) dp[pos][sta] = sum;                        //没有限制将dp的数值存起来,以便调用 
    	return sum;                                        //返回值 
    }
    ll solve(ll a){
    	int cnt = 0;                       //分解这个数
    	while(a>0){              
    		digit[cnt++] = a%10;
    		a/=10;
    	}
    	ll ans = dfs(cnt-1,0,0,true);          //对这个数进行dfs
    	return ans;
    }
    int main(){
    	#ifdef LOCAL
    		freopen("test.txt","r",stdin);
    	#endif
    	int T;
    	cin >> T;
    	memset(dp,-1,sizeof(dp));
    	while(T--){
    		ll a;
    		scanf("%I64d",&a);
    		ll ans = solve(a); 
    		cout << a+1-ans << endl;
    	}
        return 0;
    }
    

    在这里插入图片描述

    头大啊,这谁顶得住啊!看的我脑阔痛。欸,莫急,看我一一道来

    dp数组的作用是什么呢,看这句dp【位数】【最高位是不是4】,dp【20】【2】,一维存储的是每一位(十百千等,这就是我们的存储阶级)中符合条件的个数,比如dp[2][0]存储的就是每一百个数中符合要求的数字数量,dp[2][1]则是400–500中符合要求的数量。为啥要额外计算最高位为4的情况呢,因为400开头,很明显有490-499这一段数是与其他阶段不同的,而且无论题目是49,还是62,道理都是一样的。

    因为深搜的特性,在计算dp[4][0]和dp[4][1]的时候(即每一万个数的符合条件的个数)会一口气深搜到底,顺势就得到了4位数以下的数目,因为得到每一万位的时候需要每一千位的值,同样每一千位需要每一百位等等等等。经过存储之后的dp,再经由第15行的返回dp的值,就大大体现了记忆化搜索的好处。

    我们这里以53421为例:我们的dfs实际计算过程是分别计算:1–50000,50000–53000,53000–53400,53400-53420,53420-53421.
     首先是最高位5,进入循环pos=4,pre=0,sta = 0,limit = true;
     第14行  不用判断(为什么是1呢,因为深搜是按次数搜索的,每一次深搜结果,代表有一种情况)
     第15行  dp数组的值目前全都是-1,所以依旧跳过,
     第16行  limit有限制,up = 5(这里我们不能让遍历的值超过这一位的数),
     第18行 开始进行对这位数的数值进行遍历,分别是0,1,2,3,4,5
     第19行 判断上一位是不是4,如果是4,并且这一位遍历的是9,那么跳过他,因为没有上一位,肯定不是。
     第20行 汇总这一个sum值。
     第22行 如果没有数字限制(这里的限制就是指有没有遍历到遍历的上限,这里就是5)则可以继续访问,比如这一位枚举了0(不是5,所以没有限制),则下一位就可以枚举到9,如果这一位枚举了5,则下一位就没法枚举到9,只能枚举到digit[3],也就是3了。所以无限制就意味着枚举肯定到了9,这个值就是这一个阶梯(十百千等)所含的值。赋值给dp数组,以便于记忆化搜索
     后面的过程基本一样,我就不赘述,有兴趣可以自己模拟一下。

    稍微拓展

    第45行为啥是"a+1-ans"呢?如果题目问50到500之间有多少个这种数怎么办呢?
       在这里插入图片描述

    问得好!

    1.a+1-ans的原因是因为在遍历的时候dfs的内容把0这个数也加了进去,所以ans是比正确答案多1的。
     +1,-1抵消. 欸,完美,无懈可击
    2.如果,题目问的是50到500之间怎么办!根本不用盘他,开前缀和啊!solve(50) 记录的是0–50之间的个数,solve(500) 记录的是0–500之间的个数,那么两者相减自然就是 (50,500](注意这里是开区间)的个数了。如果是【50,500】的话就是solve(500)-solve(50-1)。一样的。

    好了,这次就到这里了,肝不行了。老板!换肾!!

    在这里插入图片描述

    展开全文
  • 数位dp与ac自动机

    2016-07-08 09:09:04
    数位dp与ac自动机算法
  • 数位DP总结+例题

    2019-02-23 16:38:12
    学了数位DP很久了,今天就简单的总结一下吧。 一、什么是数位DP 数位DP简单来说是一种统计数的DP,该类题一般可以用暴力写出来,但是由于数据太大,一般会超时。数位DP一般是统计[l,r]中满足题中要求的数的个数,...
  • 数位dp详解及模板

    千次阅读 2018-08-03 10:04:29
    数位dp一般应用于: 求出在给定区间[A,B]内,符合条件P(i)的数i的个数.条件P(i)一般与数的大小无关,而与 数的组成有关. 比如说在HDU2089中, 让求区间内数中不有`4`和`62`的数字个数之和 对于此类问题,我们一般设...
  • 好不容易做的,放在电脑中不小心删了咋整
  • 数位DP总结

    2017-04-03 20:58:42
    数位DP基于动态的思想,记录状态以至于不用重复的计算,能够处理大规模的数 其时间复杂度为O(状态数*转移数) //状态数是dp数组的大小,转移数是for循环大小(这个时间我也不是很想得通,某大佬讲的。。) 基本模板...
  • 数位DP小结

    千次阅读 2015-07-12 15:13:34
    数位DP:一般是求小于等于数字N的某些特征数字个数,或者是区间[L,R]的之间的某些特征数字个数,后者一般可以转换成求差的方式来做。
  • 数位 dp 是一种计数用的 dp一般就是要统计一个区间 [le,ri] 内满足一些条件数的个数 比如 [1,10000] 中统计不含有 4 的数 所谓数位 dp字面意思就是在数位上进行 dp 咯 就是对数字每一位每一位递推 此类题目最基本的...
  • count 数字计数 (数位dp

    千次阅读 2017-11-09 21:56:24
    做一个结构题存储所有的0到9的的个数,并储存现在的个数。 每次统计是把现在的个数储存,并把以前存储的数字的数量一起进行赋值。 这个题主要是统计10位数,麻烦一点。 代码: #...
  • 数位DP,看这一篇就足够了!

    千次阅读 多人点赞 2020-06-21 19:54:40
    数位DP用来解决什么问题? 我们有时候会遇到这样一类题目,给你一个区间 [l,r] ,找区间上符合某种特定要求的数的个数,这个要求可能很简单,很好理解,但是由于区间范围太大,以至于对每个数进行遍历判别是不太...
  • 那么算法的话就很容易想到数位dp。看到&运算,肯定是二进制,那就是数二进制位。 再看,因为要求i&j==0,那么i和j中每一位中都最多只能有一个1(每一位只能有00,01,10,3种情况); 又因为log运算,那么...
  • 总结数位DP算法.doc

    2021-10-08 21:47:51
    总结数位DP算法.doc
  • 数位dp加上前导0的判断。注意状态是:abs(i-pre)>=2... 代码: #include #include #include #include #include #include #include using namespace std; #define print(a) printf("%d", a)
  • 数位dp入门详解

    千次阅读 2017-02-19 23:07:41
    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每...
  • 数位DP】专题

    千次阅读 2015-06-11 23:11:56
    所谓数位DP就是基于考虑数字的每一位来转移的DP。  例如求比456小的数,可以这么考虑,  4 5 6  4 5 (0~6)  4 (0~4) (0~9)  (0~3)(0~9) (0~9)
  • 数位DP入门+数位DP模板

    千次阅读 多人点赞 2017-08-20 11:58:20
    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每...
  • 这道题对友用的暴力超时,他们打表过了,不过应该是数据水,这道题的正解应该是数位DP。 就是找1-n所有数,b进制下各个位的数的和,这不就是数位DP吗,虽然我DP很差,但是我套了个板子就过了。 AC代码: #include...
  • 又因为这道题满足“前缀和相减”的性质,所以我们考虑使用数位 DP。 那么确定了方法之后,我们先要了解数位 DP 的做法。它通常是遍历每一位数,对每一位数及其之后的数统计答案。 以下的“第几位”指从低到高...
  • 文章目录数位DP数位DP介绍数位DP解法数位DP经典例题例题1:度的数量例题2:计数问题例题3:数字游戏例题4:windy数数位DP总结 数位DP 数位DP介绍 数位DP往往都是这样的题型,给定一个闭区间[l,r][l,r][l,r],让你求...
  • 数位DP - 数字1的数量

    2017-05-20 12:03:21
    dp[i]=dp[i-1]*10+po; po*=10; } 然后对于每一数字,要考虑数字与1的关系。 好比141,到第三个1的时候,实际上已经算出了1~41的1的数量,那我把这个数量想象成是在100~141里面除开开头的1的数量,加上42个...
  • POJ3208 启示录 题目传送门 ...这一道题显然是一道数位DP的题目,那么我们先来了解一下什么是数位DP 众所周知 数位DP是与数字相关的一类计数问题,它往往指的是这样的题型: 给定一个闭区间 [l,r][l
  • 数位DP 入门学习详解

    2018-08-19 20:31:19
    数位DP 什么是数位DP 数位DP是DP的一种,顾名思义,按每一个数位来进行DP。 什么时候使用 题目的要求与一个数字相关,并且它能通过每一个数位来进行转移。 例题:求所有nnn位数中能被mmm整除的数的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,695
精华内容 35,078
关键字:

数位dp