数位DP - Blog

通常的数位dp可以写成如下形式：

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));
    }
}

无注释版：

int a[20];
long long dp[20][state];
long long dfs(int pos,/*state变量*/,bool lead,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++)
    {
        if() ...
        else if()...
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos])
    }
    if(!limit && !lead) dp[pos][state]=ans;
    return ans;
}
long long solve(long long x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,/*一系列状态 */,true,true);
}
int main()
{
    long long le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}

HDU2089

题意：

不吉利的数字为所有含有4或62的号码。对于每个整数对，输出一个不含有不吉利数字的统计个数。

思路：

$dp[pos][pre]$：长度为pos的前一位是否为6的不含有不吉利数字的个数。

代码：

int p[10];
int dp[10][2];
int dfs(int pos,int pre,int state,bool limit)
{
    if(pos==-1)return 1;
    if(!limit&&dp[pos][state]!=-1)return dp[pos][state];
    int up=limit?p[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        if(i==4)continue;
        if(i==2&&pre==6)continue;
        ans+=dfs(pos-1,i,i==6?1:0,limit&&i==p[pos]);
    }
    if(!limit)dp[pos][state]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        p[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,0,true);
}
int main()
{
    int l,r;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d%d",&l,&r)!=EOF)
    {
        if(l==0&&r==0)break;
        printf("%d\n",solve(r)-solve(l-1));
    }
    return 0;
}

HDU3652

题意：

给出一个n，求比n小的包含13且能被13整除的数字个数。

思路：

$dp[pos][ext][mod][cur]$$：长度为pos的是否存在13的余数为mod的前一位是否为1的数字个数。 **代码：** <pre><code class="hljs c++">int dp[15][2][15][2]; int a[15]; int dfs(int pos,int ext,int mod,int cur,bool limit) { //printf("%d %d %d %d %d\n",pos,ext,mod,cur,limit); if(pos==-1)return (ext&&mod==0); if(!limit&&dp[pos][ext][mod][cur]!=-1) return dp[pos][ext][mod][cur]; int up=limit?a[pos]:9; int ans=0; for(int i=0;i<=up;i++) ans+=dfs(pos-1,ext||(cur&&i==3),(mod*10+i)%13,i==1,limit&&i==a[pos]); if(!limit)dp[pos][ext][mod][cur]=ans; return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,0,0,0,true); } int main() { int n; memset(dp,-1,sizeof(dp)); while(scanf("%d",&n)!=EOF) printf("%d\n",solve(n)); return 0; }</code></pre> #### BZOJ1026 **题意：** 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。[A,B]总共有多少个windy数？ **思路：** $$dp[pos][pre]$$：长度为len，前面一位为pre的数字个数。注意一下前导零就可以了。 **代码：** <pre><code class="hljs c++">int a[20]; ll dp[20][10]; ll dfs(int pos,int pre,bool lead,bool limit) { //printf("%d %d %d %d\n",pos,pre,lead,limit); if(pos==-1)return 1ll; if(!limit&&!lead&&dp[pos][pre]!=-1)return dp[pos][pre]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++) { if(!lead&&abs(pre-i)<2)continue; ans+=dfs(pos-1,i,lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead)dp[pos][pre]=ans; //printf("%d %d %d:%lld\n",pos,pre,limit,ans); return ans; } ll solve(ll x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,0,true,true); } int main() { ll l,r; scanf("%lld%lld",&l,&r); memset(dp,-1,sizeof(dp)); //printf("%lld\n",solve(r)); printf("%lld\n",solve(r)-solve(l-1)); return 0; }</code></pre> #### CodeForces55D **题意：** 一个正整数是漂亮数，当且仅当它能够被自身的各非零数字整除。求给定范围中有多少个漂亮数。 **思路：** 一个数可以被各位数字整除就相当于可以被各位数字的最大公倍数整除。 $$dp[len][lcm][mod]$$：长度为len的各位数字的最大公倍数为lcm的被2520除余数为mod的数字个数。因为lcm最大可以是2520（0～9的最大公约数），直接开$$19*2520*2520$$会爆，但是可以存在的lcm并没有这么多，所以离散化一下就好了。 **代码：** <pre><code class="hljs c++">int a[20]; ll dp[20][100][2525]; map<int,int>mp; int cnt; int gcd(int a,int b) { if(a<b){int temp;temp=a;a=b;b=temp;} if(b==0)return a; while(a%b){int r=a%b;a=b;b=r;} return b; } int lcm(int a,int b) { if(a==0)return b; if(b==0)return a; return a*b/gcd(a,b); } ll dfs(int pos,int lc,int mod,bool limit) { if(pos==-1)return lc==0||mod%lc==0; int temp; if(!mp[lc])mp[lc]=++cnt; temp=mp[lc]; if(!limit&&dp[pos][temp][mod]!=-1)return dp[pos][temp][mod]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++) ans+=dfs(pos-1,lcm(lc,i),(mod*10+i)%2520,limit&&i==a[pos]); if(!limit)dp[pos][temp][mod]=ans; return ans; } ll solve(ll x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,0,0,true); } int main() { int t; ll l,r; memset(dp,-1,sizeof(dp)); cnt=0; scanf("%d",&t); while(t--) { scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); } return 0; }</code></pre> #### POJ3252 **题意：** 求区间[a,b]中，转换成2进制后，0的个数>=1的个数的数字的个数 **思路：** $$dp[pos][num0][num1]$$：长度为pos的0的个数为num0的1的个数为num1的满足条件的数的个数。注意处理前导0就好了。 **代码：** <pre><code class="hljs c++">int a[100]; ll dp[100][100][100]; ll dfs(int pos,int num0,int num1,bool lead,bool limit) { if(pos==-1)return num0>=num1; if(!limit&&!lead&&dp[pos][num0][num1]!=-1) return dp[pos][num0][num1]; int up=limit?a[pos]:1; ll ans=0; for(int i=0;i<=up;i++) ans+=dfs(pos-1,i==0&&!lead?num0+1:num0,i==1?num1+1:num1,lead&&i==0,limit&&i==a[pos]); //printf("%d %d %d %d:%lld\n",pos,num0,num1,limit,ans); if(!limit&&!lead)dp[pos][num0][num1]=ans; return ans; } ll solve(ll x) { int pos=0; while(x) { a[pos++]=x%2; x/=2; } return dfs(pos-1,0,0,true,true); } int main() { memset(dp,-1,sizeof(dp)); ll l,r; scanf("%lld%lld",&l,&r); //scanf("%lld",&l); //printf("%lld\n",solve(l)); printf("%lld\n",solve(r)-solve(l-1)); return 0; }</code></pre> #### HDU4734 **题意：** 求F(0)~F(B)中,有几个小于等于 F(A)的; 对于数字$$A_nA_{n-1}A_{n-2} ... A_2A_1$$，$$ F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + ... + A_2 * 2 + A_1 * 1$$。 **思路：** 因为有多组，所以F(A)总是在变的，所以这个状态记录就不能只是记录长度为pos的值为val的数字个数，而应该， $$dp[pos][tot]$$：长度为pos的函数值小于tot的数字个数。所以转移就是$$dp[pos][tot]+=dp[pos-1][tot-i*(1<<pos)]$$。 **代码：** <pre><code class="hljs c++">int sum; int pre[20]; int a[20]; int dp[20][10000];//长度为i且小于等于j的数的个数 void calc(int x) { sum=0; int pos=0; while(x) { sum+=x%10*(1<<pos); pos++; x/=10; } //printf("%d\n",sum); } int dfs(int pos,int tot,bool limit) { //printf("%d %d %d\n",pos,tot,limit); if(pos==-1)return tot>=0; if(!limit&&dp[pos][tot]!=-1)return dp[pos][tot]; int up=limit?a[pos]:9; int ans=0; for(int i=0;i<=up;i++) { if(tot-i*(1<<pos)<0)break; ans+=dfs(pos-1,tot-i*(1<<pos),limit&&i==up); } if(!limit)dp[pos][tot]=ans; //printf("%d %d %d:%d\n",pos,tot,limit,ans); return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,sum,true); } int main() { int t; int l,r; memset(dp,-1,sizeof(dp)); scanf("%d",&t); for(int kase=1;kase<=t;kase++) { scanf("%d%d",&l,&r); calc(l); printf("Case #%d: %d\n",kase,solve(r)); } return 0; }</code></pre> #### HDU3709 **题意：** 给定区间[a,b]，求区间内平衡数的个数。所谓平衡数即有一位做平衡点，左右两边数字的力矩相等。 **思路：** 本来是想四维的，结果MLE了。三维也是可以的。 $$dp[d][pos][sum]$$：平衡点为d，长度为pos，力矩和为sum的数字个数。注意重复0的计算要减去。 **代码：** <pre><code class="hljs c++">int a[20]; ll dp[20][20][2000]; int sign; ll dfs(int d,int pos,int sum,bool limit) { //if(d==0)printf("%d %d %d %d %d\n",d,pos,l,r,limit); if(pos==-1)return sum==0; if(!limit&&dp[d][pos][sum]!=-1)return dp[d][pos][sum]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++) { //printf("i=%d %d %d %d %d %d\n",i,d,pos-1,pos<d?l+(d-pos)*i:l,pos>d?r+(pos-d)*i:r,limit&&i==a[pos]); ans+=dfs(d,pos-1,sum+(pos-d)*i,limit&&i==a[pos]); } if(!limit)dp[d][pos][sum]=ans; //if(d==0)printf("%d %d %d %d %d:%lld\n",d,pos,l,r,limit,ans); return ans; } ll solve(ll x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } ll ans=0; sign=0; for(int i=0;i<pos;i++) { ll temp=dfs(i,pos-1,0,true); //printf("%d:%lld\n",i,temp); ans+=temp; } return ans-pos; } int main() { int t; ll l,r; memset(dp,-1,sizeof(dp)); scanf("%d",&t); while(t--) { scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); } return 0; }</code></pre> #### HDU4507 **题意：** 如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关： 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；求在一定区间内和7无关的数字的平方和。 **思路：** $$dp[pos][mod][tot]$$：长度为pos的每位加起来的和的余数为mod的余数为tot的数字。考虑一个例子， 245,213,257，它们的平方和应该这样算： $$245^2+213^2+257^2$ $=(200+45)^2+(200+13)^2(200+57)^2$ $=200^2*3+45^2+13^2+57^2+2*200*(45+13+57)$

所以知道不仅要记录平方和，还要记录个数，和。

然后记忆化搜索就可以了。

代码：

struct node
{
    ll num,sum,sqsum;//个数、和、平方和
}dp[20][10][10];
int a[20];
ll xs[20];
void init()
{
    xs[0]=1;
    for(int i=1;i<=18;i++)
        xs[i]=(xs[i-1]*10)%MOD;
}
node dfs(int pos,int mod,int tot,int pre,bool limit)
{
    //printf("%d %d %d %d\n",pos,mod,tot,limit);
    if(pos==-1)
    {
        node temp;
        if(mod!=0&&tot!=0)
        {
            temp.num=1ll;
            temp.sum=0;
            temp.sqsum=0;
            //printf("%lld %lld %lld\n",temp.num,temp.sum,temp.sqsum);
        }
        else temp.num=temp.sum=temp.sqsum=0;
        return temp;
    }
    if(!limit&&dp[pos][mod][tot].num!=-1)return dp[pos][mod][tot];
    int up=limit?a[pos]:9;
    node ans;
    ans.num=ans.sum=ans.sqsum=0;
    for(int i=0;i<=up;i++)
    {
        if(i==7)continue;
        node temp=dfs(pos-1,(mod+i)%7,(tot*10+i)%7,i,limit&&i==up);
        ans.num=(ans.num+temp.num)%MOD;
        ans.sum=(ans.sum+(temp.num*i*xs[pos]%MOD+temp.sum)%MOD)%MOD;
        ans.sqsum=(ans.sqsum+((i*i*xs[pos]%MOD*xs[pos]%MOD*temp.num%MOD+temp.sqsum)%MOD+2*i*xs[pos]%MOD*temp.sum%MOD)%MOD)%MOD;
    }
    if(!limit)dp[pos][mod][tot]=ans;
    //printf("%d %d %d %d:%lld %lld %lld\n",pos,mod,tot,limit,ans.num,ans.sum,ans.sqsum);
    return ans;
}
node solve(ll x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,0,0,true);
}
int main()
{
    init();
    int t;
    ll l,r;
    scanf("%d",&t);
    for(int i=0;i<20;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<10;k++)
                dp[i][j][k].num=dp[i][j][k].sum=dp[i][j][k].sqsum=-1;
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        //scanf("%lld",&l);
        printf("%lld\n",(solve(r).sqsum-solve(l-1).sqsum+MOD)%MOD);
        //node temp=solve(l);
        //printf("%lld %lld %lld\n",temp.num,temp.sum,temp.sqsum);
    }
    return 0;
}