数位dp入门 - CSDN
精华内容
参与话题
  • 原文:...所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每一位就是数位啦!之所以要引入数位的概念完全就是为了dp。...

    原文:https://blog.csdn.net/wust_zzwh/article/details/52100392

    基础篇

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

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

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

    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函数总是这样:

    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值显然是保存满足条件数的个数)

    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的情况可视为同种,不会影响计数。
    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)才是满足的条件。
    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,都是类似的,自己慢慢体会吧。
    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的关系!!!
    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之后的位的贡献值,把这个平方展开就可以了!
    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入门

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

    数位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函数总是这样:

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

    统计[1,ri]数量和[1,le-1],然后相减就是区间[le,ri]的数量了,这里我写的下界是1,其实0也行,反正相减后就没了,注意题目中le的范围都是大于等于1的(不然le=0,再减一就GG了)
    在讲例题之前先讲个基本的动态模板(先看后面的例题也行):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));  
        }  
    } 
    

    下面是一道模板题
    【HDU2089】不要六二

    #include <iostream>
    #include <cstring>
    using namespace std;
    typedef long long ll;
    ll a[20];
    ll dp[20][2];
    ll dfs(ll pos,ll pre,ll state,bool limit)//若state为1说明前一位为6
    {
        if(pos==-1)return 1;
        if(!limit&&dp[pos][state]!=-1)return dp[pos][state];
        int up=limit?a[pos]:9;//limit若为1,即前一位高位枚举刚好达到上界,所以此位数最多等于a[pos],否则最多等于9
        ll ans=0;
        for(ll i=0;i<=up;i++)
        {
            if(i==4)continue;
            if(pre==6&&i==2)continue;
            ans+=dfs(pos-1,i,i==6? 1 : 0,limit&&i==a[pos]);//若limit有一次不为0,后面都不为0,即若高位小于a[pos],则后面的位数都可以取到9
        }
        if(!limit)dp[pos][state]=ans;//储存
        return ans;
    }
    ll solve(ll x)
    {
        ll pos=0;
        while(x)
        {
            a[pos++]=x%10;
            x/=10;
        }//执行完后ans会多+1
        return dfs(pos-1,0,0,true);//从高位开始dp,第一位数位只能取到a[pos]所以limit置为true
    }
    int main()
    {
        ll n,m;
        while(cin>>n>>m&&(n||m))//因为n,m要同时满足0
        {
            memset(dp,-1,sizeof(dp));//注意重置
            cout<<solve(m)-solve(n-1)<<endl;//使用减法
        }
        return 0;
    }
    
    展开全文
  • 【算法小讲堂】数位dp(简单入门

    千次阅读 多人点赞 2019-04-17 17:59:40
     数位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入门

    2017-09-01 23:35:45
    考试考dp的时候时常会碰见有关数位dp的问题,每次考到就是一脸懵逼加吃惊,所以今天抽空看了一下有关数位dp的知识,网上有很多大神都说的很好,推荐看几篇blog。 入门经典 慢慢看,很不错数位DP的套路数位dp其实看...

    考试考dp的时候时常会碰见有关数位dp的问题,每次考到就是一脸懵逼加吃惊,所以今天抽空看了一下有关数位dp的知识,网上有很多大神都说的很好,推荐看几篇blog。
    入门经典
    慢慢看,很不错

    数位DP的套路

    数位dp其实看了那么多篇blog感觉就是一个套路,一个记忆化搜索,方法无非是用两个端点的答案相减得到答案。dp主要考得是状态的设定和转移及其优化,对于数位dp来说,转移和优化其实是固定的,变的只是状态的设定,把状态设好了,套上板子处理下边界和正确性就好了,感觉还是要多做题,先贴两道题,之后慢慢更新,可以去vj上坐kuangbin带你飞系列的数位dp专题,题目很适合入门的人。

    HDU2089

    题面

    统计区间 [a,b] 中不含 4 和 62 的数字有多少个。

    分析

    这其实是一道模板题看了上面两篇blog的做这题会很简单,部分注释写在代码里了。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/24 21:55:11
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    int read()
    {
        register int sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    
    int n,m,num;
    int a[maxn];
    
    void fj(int x)
    {
        num = 0;
        while(x){a[num++] = x % 10;x/=10;}
    }
    int dp[1010][2];//dp[i][j]表示dp到i位前一位是不是6?的方案数 
    
    int dfs(int pos,int pre,int flag,bool lim)//数位dp精华 
    {
        if(pos == -1)return 1;//搜到叶子节点返回 
        if(!lim && dp[pos][flag] != -1)return dp[pos][flag];//要没有上限才能返回,因为可能引起状重复 
        int up = lim ? a[pos] : 9;//上限 
        int sum = 0;
        REP(i,0,up)
        {
            if(pre == 6 && i == 2)continue;
            if(i == 4)continue;//搜索可行状态 
            sum += dfs(pos-1,i,i==6,lim && i == a[pos]); 
        }
        if(!lim)dp[pos][flag] = sum;
        return sum;
    }   
    
    int main()
    {
        while(scanf("%d%d",&n,&m) && n + m)
        {
            mem(dp,-1);fj(m);
            int ans = dfs(num-1,-1,0,1);
            fj(n-1);
            ans -= dfs(num-1,-1,0,1);//前缀和思想 
            cout<<ans<<endl;
        }
        return 0;
    }

    HDU3555

    题面

     给一个数字n,范围在1~2^63-1,求1~n之间含有49的数字有多少个。

    分析

    其实又是一道模板题,只是逆向思维下用总答案减去你搜出来的不包含49的数的个数就好了(网上貌似没什么人写这种方法,都是正面刚的)

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/25 20:27:39
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const LL inf = 1e9;
    const LL maxn = 100000;
    
    LL T,a[maxn],num;
    LL dp[maxn][2];
    
    LL dfs(int pos,int pre,bool lim)
    {
        bool flag = (pre == 4);
        if(pos == 0)return 1;
        if(!lim && dp[pos][flag]!=-1)return dp[pos][flag];
        int up = lim ? a[pos] : 9;
        LL res = 0;
        REP(i,0,up)
        {
            if(pre == 4 && i == 9)continue;
            res += dfs(pos-1,i,lim && i == a[pos]);
        }
        if(!lim) dp[pos][flag] = res;
        return res;
    }
    
    LL solve(LL x)
    {
        num = 0;LL tmp = x;
        while(x) {a[++num] = x % 10;x /= 10;}
        return tmp - dfs(num,-1,1);
    }
    
    int main()
    {
        T = read();
        mem(dp,-1);
        while(T--)
        {
            LL x = read();
            cout<<solve(x)+1<<endl;
        }
        return 0;
    }

    CF Beautiful Numbers

    题面

    这个数能整除它的所有位上非零整数。问[l,r]之间的Beautiful Numbers的个数。

    分析

    这道题首先要知道一个东西,我们设这个数为X,lcm(19)=2520
    如果lcm(Ai)|X,并且lcm(Ai)|2520,那么X|2520
    通过这个式子我们可以把范围下降到2520,这样我们时间复杂度和空间复杂度都可行了,但是发现还是会爆,于是我们把2520 的约数用Hash映射下就好了,具体看代码吧。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/25 19:31:25
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    const int Max_L = 2520;
    int Hash[Max_L+10],cnt;
    
    int T;
    LL dp[25][50][2530],num,a[maxn];
    
    LL gcd(LL a,LL b) {return b == 0 ? a : gcd(b,a%b);}
    
    LL lcm(LL a,LL b) { return a / gcd(a,b) * b; }
    
    LL dfs(int pos,int prelcm,int prenum,int lim)
    {
        if(pos == 0)return prenum%prelcm == 0;
        if(!lim && dp[pos][Hash[prelcm]][prenum] != -1)return dp[pos][Hash[prelcm]][prenum];
        int up = lim ? a[pos] : 9;
        LL res = 0;
        REP(i,0,up)
        {
            int nownum = (prenum*10 + i ) % Max_L;
            int nowlcm = prelcm;
            if(i)nowlcm = lcm(nowlcm,i);
            res += dfs(pos-1,nowlcm,nownum,lim && i == up);
        }
        if(!lim)dp[pos][Hash[prelcm]][prenum] = res;
        return res;
    }
    
    LL solve(LL x)
    {
        num = 0;
        while(x)a[++num] = x % 10,x /= 10;
        return dfs(num,1,0,1);
    }
    
    int main()
    {
        REP(i,1,Max_L)if(Max_L % i == 0)Hash[i] = ++cnt;
        T = read();
        mem(dp,-1);
        while(T--)
        {
            LL l = read(),r = read();
            cout<<solve(r) - solve(l-1)<<endl;
        }
        return 0;
    }

    SAK大神今天模拟赛出了一道数位dp的题目,md又没做出来,真是的,刚刚学就出这种题目,哎,我也很无奈啊,又是一道数位dp的裸题,没办法,只能靠慢慢积累了,不栽几个跟头又怎么会印象深刻呢?

    题面

    问你从1到n有多少数是符合其内部没有回文串的呢?

    分析

    感觉看了weary的代码对这个内容有了新的理解,之前学习的板子都是从后面往前面搜的,现在还有种方法可以用vector的reverse的功能,从前往后搜索,加上&的传地址功能,代码显得很简练,我们设dp[i][j][k][0/1] 表示当前在第i位,前一位的数字为j,前两位的数字为k,是否达到了上届转移很简单了,记忆化搜索会显得很好理解,不多说了,直接上代码。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/26 10:12:32
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    
    LL dp[50][11][11][2],num;
    LL n,m;
    vector<int>a;
    
    LL dfs(int pos,int pre,int ppre,int lim,int lead = 0)
    {
        if(pos == a.size())return 1;    
        if(dp[pos][pre][ppre][lim]!=-1)return dp[pos][pre][ppre][lim];
        int up= lim ? a[pos] : 9;
        LL res = 0;
        REP(i,lead,up)
            if(i != pre && i != ppre)
                res += dfs(pos+1,i,pre,lim && i == a[pos]); 
        return dp[pos][pre][ppre][lim] = res;
    }
    
    LL solve(LL x)
    {
        a.clear();
        mem(dp,-1);
        while(x) { a.push_back(x%10); x/= 10;}
        reverse(a.begin(),a.end());
        LL res = 0;
        REP(i,0,a.size()-1)res+=dfs(i,10,10,i==0,1);
        return res + 1;
    }
    
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("numbers.in", "r", stdin);
        freopen("numbers.out", "w", stdout);
    #endif
        int F = 0;
        n = read(),m = read();
        if(n)n--;
        else F = 1;
        cout<<solve(m) - solve(n)+F<<endl;
        return 0;
    }
    

    XHXJ’s LIS

    define xhxj (Xin Hang senior sister(学姐))
    If you do not know xhxj, then carefully reading the entire description is very important.
    As the strongest fighting force in UESTC, xhxj grew up in Jintang, a border town of Chengdu.
    Like many god cattles, xhxj has a legendary life:
    2010.04, had not yet begun to learn the algorithm, xhxj won the second prize in the university contest. And in this fall, xhxj got one gold medal and one silver medal of regional contest. In the next year’s summer, xhxj was invited to Beijing to attend the astar onsite. A few months later, xhxj got two gold medals and was also qualified for world’s final. However, xhxj was defeated by zhymaoiing in the competition that determined who would go to the world’s final(there is only one team for every university to send to the world’s final) .Now, xhxj is much more stronger than ever,and she will go to the dreaming country to compete in TCO final.
    As you see, xhxj always keeps a short hair(reasons unknown), so she looks like a boy( I will not tell you she is actually a lovely girl), wearing yellow T-shirt. When she is not talking, her round face feels very lovely, attracting others to touch her face gently。Unlike God Luo’s, another UESTC god cattle who has cool and noble charm, xhxj is quite approachable, lively, clever. On the other hand,xhxj is very sensitive to the beautiful properties, “this problem has a very good properties”,she always said that after ACing a very hard problem. She often helps in finding solutions, even though she is not good at the problems of that type.
    Xhxj loves many games such as,Dota, ocg, mahjong, Starcraft 2, Diablo 3.etc,if you can beat her in any game above, you will get her admire and become a god cattle. She is very concerned with her younger schoolfellows, if she saw someone on a DOTA platform, she would say: “Why do not you go to improve your programming skill”. When she receives sincere compliments from others, she would say modestly: “Please don’t flatter at me.(Please don’t black).”As she will graduate after no more than one year, xhxj also wants to fall in love. However, the man in her dreams has not yet appeared, so she now prefers girls.
    Another hobby of xhxj is yy(speculation) some magical problems to discover the special properties. For example, when she see a number, she would think whether the digits of a number are strictly increasing. If you consider the number as a string and can get a longest strictly increasing subsequence the length of which is equal to k, the power of this number is k.. It is very simple to determine a single number’s power, but is it also easy to solve this problem with the numbers within an interval? xhxj has a little tired,she want a god cattle to help her solve this problem,the problem is: Determine how many numbers have the power value k in [L,R] in O(1)time.
    For the first one to solve this problem,xhxj will upgrade 20 favorability rate。
    Input
    First a integer T(T<=10000),then T lines follow, every line has three positive integer L,R,K.(
    0 < L <= R < 2 63-1 and 1<=K<=10).
    Output
    For each query, print “Case #t: ans” in a line, in which t is the number of the test case starting from 1 and ans is the answer.

    题目实际上就是让你求一串数字满足LIS==k的数字个数

    分析

    这道题比前面的题目都要难一些,需要用到状态压缩,把数字压缩在一个二进制位中表示这一位的数字出现在了数字中,每次|一下就好了,实际上也没什么变化。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/26 16:24:58
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const LL inf = 1e9;
    const LL maxn = 100000;
    
    LL n,m,T,k;
    LL dp[20][(1<<10)+10][2][11];
    vector<LL>a;
    
    LL New(LL s,LL p)
    {
        REP(i,p,9)
            if(s & (1<<i)) {s ^= (1<<i);break;}
        return s|(1<<p);
    }
    
    LL dfs(LL pos,LL st,LL lim,LL lead=0)
    {
        if(pos == a.size())return __builtin_popcount(st) == k;
        if(dp[pos][st][lim][k]!=-1)return dp[pos][st][lim][k];
        LL up = lim ? a[pos] : 9;
        LL res = 0;
        REP(i,lead,up)
            res += dfs(pos+1,New(st,i),lim && i == a[pos]);
        return dp[pos][st][lim][k] = res;
    }
    
    LL solve(LL x)
    {
        a.clear();
        LL tmp = x;
        while(tmp) a.push_back(tmp%10),tmp/=10;
        reverse(a.begin(),a.end());
        LL res = 0;
        mem(dp,-1);
        REP(i,0,a.size()-1)res+=dfs(i,0,(i==0),1);
        return res;
    }
    
    int main()
    {
        T = read();
        REP(I,1,T)
        {
            n = read(),m = read();k = read();
            cout<<"Case #"<<I<<": ";
            cout<<solve(m)-solve(n-1)<<endl;
        }
        return 0;
    }

    HUD3652

    题面

    A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string “13” and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
    Input
    Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
    Output
    Print each answer in a single line.

    问你1到n有多少数字满足被13整除并且包含13这个数。

    分析

    dp[i][j][k][l] 分别表示在第i位,前面的数mod13 为j,包不包含13,前面一位的数字是l然后记忆化搜索就好了。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/28 20:13:56
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    int read()
    {
        register int sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    
    LL n;
    LL dp[20][20][2][10]; 
    vector<int>a;
    
    LL dfs(int pos,int mod,int has,int pre,int lim)
    {
        if(pos == -1)return (has && (!mod));
        if(!lim && dp[pos][mod][has][pre]!=-1)return dp[pos][mod][has][pre];
        int up = lim ? a[pos] : 9;
        LL res = 0;
        REP(i,0,up)
        {
            int Has = has;
            if(pre == 1 && i == 3)Has = 1;
            int Mod = (mod * 10 + i)%13;
            res += dfs(pos-1,Mod,Has,i,lim&&i==a[pos]);
        }
        if(!lim)dp[pos][mod][has][pre] = res;
        return res;
    }
    LL solve(LL x)
    {
        a.clear();
        while(x) a.push_back(x%10),x/=10;
        return dfs(a.size()-1,0,0,-1,1);
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("G.in", "r", stdin);
        freopen("G.out", "w", stdout);
    #endif
        mem(dp,-1);
        while(scanf("%lld",&n)!=EOF)
            cout<<solve(n)<<endl;
        return 0;
    }
    

    Balanced numbers

    The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using hooves.
    They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both “round numbers”, the first cow wins,
    otherwise the second cow wins.
    A positive integer N is said to be a “round number” if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
    Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.
    Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

    问你有多少数字在给定区间里满足以一个数为中心左右两边的力矩乘数字之和相等的数字的个数。

    分析

    dp[i][j][k] 分别表示第i位,j为力矩中心,k为和然后记忆化就好了。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/28 19:36:05
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    
    int T;
    LL dp[30][30][2010];
    vector<int>a;
    
    LL dfs(int pos,int cen,int sum,int lim)
    {
        if(pos == -1)return sum == 0;
        if(sum < 0)return 0;
        if(!lim && dp[pos][cen][sum]!=-1)return dp[pos][cen][sum];
        int up = lim ? a[pos] : 9;
        LL res = 0;
        REP(i,0,up)
            res += dfs(pos-1,cen,sum+(pos-cen)*i,lim && a[pos] == i);
        if(!lim)dp[pos][cen][sum] = res;
        return res;
    }
    
    LL solve(LL x)
    {
        a.clear();
        while(x)a.push_back(x%10),x/=10;
        LL res = 0;
        REP(i,0,a.size()-1)
            res += dfs(a.size()-1,i,0,1);
        return res - a.size() + 1;
    }
    
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("F.in", "r", stdin);
        freopen("F.out", "w", stdout);
    #endif
        T = read();
        mem(dp,-1);
        while(T--)
        {
            LL x = read(),y = read();
            cout<<solve(y)-solve(x-1)<<endl;
        }
        return 0;
    }

    BZOJ3209: 花神的数论题

    背景
    众所周知,花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
    描述
    话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
    花神的题目是这样的
    设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ,花神要问你
    派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

    这题要转换一下思路,题目要求的是sumisumj 的积,我们求有多少个数字有k个1,然后快速幂就好了。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/28 21:14:43
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    const int mod = 10000007;
    
    LL n;
    LL dp[100][100],a[maxn],cnt;
    
    LL dfs(int pos,int num,int lim)
    {
        if(num > pos)return 0;
        if(pos == 0 && num == 0)return 1;
        if(pos == 0)return 0;
        if(!lim && dp[pos][num]!=-1)return dp[pos][num];
        int up = lim ? a[pos] : 1;
        LL res = 0;
        REP(i,0,up)res = res + dfs(pos-1,num-(i==1),lim && a[pos] == i);
        if(!lim)dp[pos][num] = res;
        return res;
    }
    
    LL N[maxn];
    
    LL qpow(LL x,LL y)
    {
        LL ans = 1;
        while(y)
        {
            if(y & 1) ans = ans * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return ans%mod;
    }
    
    LL solve(LL x)
    {
        while(x)a[++cnt] = x % 2, x /= 2;
        LL res = 1;
        REP(i,1,cnt)
        {
            LL k = dfs(cnt,i,1);
            if(k)res = (res * qpow(i,k))%mod;
        }
        return res;
    }
    int main()
     {
    #ifndef ONLINE_JUDGE
        freopen("bzoj3209.in", "r", stdin);
        freopen("bzoj3209.out", "w", stdout);
    #endif
        n = read();
        mem(dp,-1);
        cout<<solve(n)<<endl;
        return 0;
    }
    

    POJ3252Round Numbers

    题面

    有多少数的二进制零的个数大于1的个数?

    分析

    dp[i][j][k] 分别表示在i位,有j个0,k个1,记得特判一下第一个一放的位置就好了。

    /*************************************************************************
         > Author: Drinkwater
         > Created Time: 2017/8/29 21:08:24
     ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    #prag\
    ma GCC optimize("O3")
    
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long uLL;
    
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    
    LL read()
    {
        register LL sum = 0,fg = 0;char c = getchar();
        while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return fg ? -sum : sum;
    }
    
    const int inf = 1e9;
    const int maxn = 100000;
    
    LL n,m;
    LL dp[70][70][70];
    vector<int>a;
    
    LL dfs(int pos,int n0,int n1,int has,int lim)
    {
        if(pos == -1) return (n0 >= n1 || has);
        if(!lim && dp[pos][n0][n1]!=-1 && !has)return dp[pos][n0][n1];
        int up = lim ? a[pos] : 1;
        LL res = 0;
        REP(i,0,up)
        {
            if(has)
            {
                if(i == 0)res += dfs(pos-1,0,0,1,lim&&a[pos]==i);
                else res += dfs(pos-1,n0,n1+1,0,lim&&a[pos]==i);
            }
            else
            {
                if(i == 0)res += dfs(pos-1,n0+1,n1,0,lim&&a[pos]==i);
                else res += dfs(pos-1,n0,n1+1,0,lim&&a[pos]==i);
            }
        }
        if(!lim && !has)dp[pos][n0][n1] = res;
        return res;
    }
    
    LL solve(LL x)
    {
        a.clear();
        while(x) a.push_back(x%2),x/=2;
        return dfs(a.size()-1,0,0,1,1);
    }
    
    int main()
    {
        mem(dp,-1);
        while(scanf("%lld%lld",&n,&m)!=EOF) 
            cout<<solve(m)-solve(n-1)<<endl;
        return 0;
    }   
    

    HDU4734

    题意

    找出i在0到b之间的f(i)小于等于f(a)的数的个数。

    分析

    跟前面的题目差不多,记dp[i][j] 为第i位,比j小的数的个数。

    /*************************************************************************
        > File Name: H.cpp
        > Author: Drinkwater-cnyali
    ************************************************************************/
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    
    typedef long long LL;
    #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
    #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
    #define mem(a, b) memset((a), b, sizeof(a))
    
    LL read()
    {
        LL sum = 0, fg = 1; char c = getchar();
        while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }
        while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
        return sum * fg;
    }
    
    LL T;
    vector<int>a;
    LL dp[20][50010],A,B;
    
    int f()
    {
        int res = 0,len = 1;
        LL tmp = A;
        while(tmp)
        {
            res += tmp%10 * len;
            len <<= 1;tmp/=10;
        }
        return res;
    }
    
    LL dfs(int pos,int F,int lim)
    {
        if(pos == -1)return F >= 0;
        if(F < 0)return 0;
        if(!lim && dp[pos][F]!=-1)return dp[pos][F];
        int up = lim ? a[pos] : 9;
        LL res = 0;
        REP(i,0,up)
            res += dfs(pos-1,F-i*(1<<pos),lim && a[pos] == i);
        if(!lim)dp[pos][F] = res;
        return res;
    }
    
    LL solve(LL x)
    {
        a.clear();
        while(x) a.push_back(x%10),x/=10;
        return dfs(a.size()-1,f(),1);
    }
    
    int main()
    {
        T = read();
        mem(dp,-1);
        REP(I,1,T)
        {
            A = read(),B = read();
            cout<<"Case #"<<I<<": ";
            cout<<solve(B)<<endl;
        }
        return 0;
    }
    
    展开全文
  • 数位DP入门入门

    2019-06-11 11:20:28
    数位DP本质: 记忆化搜索 基本模板: int dfs(int pos,int limit,int lead,int dig,int sum) { int ans=0; if(pos==0)return sum; if(!limit&&lead&&dp[pos][sum]!=-1) return dp[pos][sum]; ...
  • HDU 2089 不要62: 题目大意是给你一个区间,让你统计这个区间里不包含 4 和 62 的数字的个数。 最朴素的思路是: 对于每个区间 [l, r],遍历所有在区间 [l, r] 里的数字,然后检查每个数字是不是合法(没有 4 和...
  • 数位DP入门+数位DP模板

    千次阅读 2019-05-01 11:25:44
    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每...
  • HDU 2089 不要62(数位DP入门

    万次阅读 2014-11-03 10:21:29
    题目链接:Click here~~ 题意: 统计区间 [a,b] 中不含 4 和 62 的数字有多少个。...dp[len][1] 表示长度为 len 的数字不含 4 和 62 但首不为 2 的个数。 状态转移方程为:dp[i][0] = 8 * dp[i-1][0] +
  • ACM题集以及各种总结大全!

    万次阅读 多人点赞 2015-06-08 19:30:41
    各种专题大全,精心整理,发上来供大家专题训练使用!
  • 动态规划之状态压缩dp入门

    万次阅读 多人点赞 2015-02-04 16:02:19
    为了更好的理解状压dp,首先介绍运算相关的知识。 1.’&’符号,x&y,会将两个十进制在二进制下进行与运算,然后返回其十进制下的值。例如3(11)&2(10)=2(10)。 2.’|’符号,x|y,会将两个十进制在二进制下...
  • 状态压缩DP入门

    万次阅读 多人点赞 2011-08-09 11:40:33
    我们知道,用DP解决一个问题的时候很重要的一环就是状态的表示,一般来说,一个数组即可保存状态。但是有这样的一些题目,它们具有DP问题的特性,但是状态中所包含的信息过多,如果要用数组来保存状态的话需要四维...
  • ACM动态规划总结(by utobe67)

    千次阅读 多人点赞 2015-05-14 20:50:17
    动态规划一直是ACM竞赛中的重点, 也是难点(对于我这种水平),因为该算法时间效率高,代码量少,多元性强、灵活度高,主要考察思维能力、建模抽象能力。学了这么久动态规划,虽然还只是个菜菜= =,但还是想总结...
  • 都能看懂的LIS(最长上升子序列)问题

    万次阅读 多人点赞 2020-05-05 14:29:37
    LIS问题介绍: 首先来说一下什么是LIS问题: 有一个长为n的数列a0, a1, ......, a(n-1)。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列,该问题被称为最长...
  • 状态压缩dp入门 (poj3254 Corn Fields)

    万次阅读 多人点赞 2014-04-28 19:10:49
    题意:给出一个n行m列的草地,1表示肥沃,0表示贫瘠,现在要把一些牛放在肥沃的草地上,但是要求所有牛不能相邻,问你有多少种放法。 ...分析:假如我们知道第 i-1 行的所有的可以放的情况,那么对于第 i 行的...
  • Hrbust 题目列表【700题】-个人整理

    千次阅读 多人点赞 2016-08-20 17:05:22
    1004、【入门dp 1005、【思维】序列定和 1006、【进阶】二分查找、好题 1007、【新手】A-B 1008、【新手】水题 1009、【新手】水题 1010、【新手】水题 1011、【新手】水题 1012、【入门】广搜 1015、【新手】...
  • Arduino基础入门篇17—四数码管的驱动

    万次阅读 多人点赞 2019-11-04 14:56:56
    本篇介绍四数码管的使用,通过数码管库驱动四数码管从0开始累加显示数字。
  • ACM题集以及各种总结大全

    千次阅读 多人点赞 2016-11-01 20:50:37
    ACM题集以及各种总结大全! 虽然退役了,但是整理一下,供小弟小妹们以后切题方便一些,但由于近来考试太多,... 一.ACM入门 关于ACM 百度百科连接 杭州电子科技大学(hdu)ACM题目 连接 关于acm的帮助 连接 北京大
  • 不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 29117 Accepted Submission(s): 10217 ...杭州人称那些傻乎乎粘嗒嗒的人为62(音
  • 疯狂的暑假学习之 汇编入门学习笔记 (七)—— dp,div,dup 参考: 《汇编语言》 王爽 第8章 1. bx、si、di、和 bp 8086CPU只有4个寄存器可以用 “[...]” 中进行单元寻址。 bp:除了默认的段地址是ss,其他与...
  • 文章目录前言一.什么是动态规划二.动态规划术语三.简单递归问题四.经典背包问题五....数位DP8.1原理8.2实战8.2.1 数字游戏8.2.2 其他数位DP问题(思路和代码详解)九.状压DP9.1原理9.2位运算基础9.3实战9.3.1
1 2 3 4 5 ... 20
收藏数 4,695
精华内容 1,878
热门标签
关键字:

数位dp入门