数位DP

CatWing · 2025-08-19 16:53:54 · 算法·理论

哦梅林的电脑啊，之前我竟然没总结

数位DP主要用于解决求在一段区间 [l,r] 内满足约束条件的数之和（平方、数量）的问题

数位DP大致思想是，先用前缀和转化为求解区间 [1,r]-[1,l-1]，再逐位拆分，用 dfs 记忆化搜索遍历每一位统计答案

其实还有一种利用for循环的迭代法，但是 dfs 法更好写代码，且思路清晰，所以统一使用搜索

现通过一到具体例题入门 （别急一会入坟）

例1：P4999

题面

首先要有一个函数，负责把一个数拆成多个十进制位，这样存储数组的最低位就是原数的最高位

然后开始搜索，我们要有一个参数 x 表示当前搜索到哪个位置，因为要从高位开始，所以初始 x 为最大值

现在要求区间 [0,n] 的数字和，当位置为 i，假设当前位的数字为 a_i，则对于当前这一位能填的数的范围，有如下情况：

1. 前面填的数全是原数 （当前数受到限制只能填 0 ~ a_i）：

   ①这一位也填 a_i，则后面的数也受到限制

   ②这一位填 0 ~ a_i-1，则后面的数可以随便填

2. 前面有位置填的非原数 （当前位可以随便填 0 ~ 9）：后面的都随便填了

不妨设一个参数 e，e=1 代表当前数有限制，e=0 代表无限制，只有先前填好的位置上所有的位置都等于 a 数组，e 才为 1（当然 e 初始为 1）

当 x=0 时，所有数位都填完了，所以要返回当前的数字和，那么还要有一个参数 sum 累加

这就是朴素的dfs思路，时间复杂度为 O(10^{len})（len 为原数数位），有点惊人，所以要使用记忆化

我们来考虑当前的答案和什么状态有关，首先肯定是 x，然后再是之前的数填了些什么，所以还有一个 sum

至于为什么没有 e ：

#include <bits/stdc++.h>
using namespace std;
int a[20];
long long f[20][200],mod = 1e9 + 7;
long long dfs(int x,long long sum,int e)
{
    if(x == 0)
    {
        return sum;
    }
    if(f[x][sum] != 0 && e == 0)
    {
        return f[x][sum];
    }
    int b = (e == 1 ? a[x] : 9);
    long long ans = 0;
    for(int i = 0;i <= b;i++)
    {
        ans = (ans + dfs(x - 1,sum + i,e == 1 && i == b)) % mod;
    }
    if(e == 0)
    {
        f[x][sum] = ans;
    }
    return ans;
}
long long fun(long long n)
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 10;
        n /= 10;
    }
    return dfs(cnt,0,1);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",(fun(r) - fun(l - 1) + mod) % mod);
    }
    return 0;
}

说完这道题先别急，注意到上题有三个参数 x,sum,e，为了使这种DP更加套路化（好写），归纳一下常见的参数：

• > 对一个集合的数在数位上的出现次数的奇偶性有要求时，其二进制形式就可以表示每个数出现的奇偶性

例2：P2602

题面

因为包含 0 的出现次数，所以参数加上 e2

因为题目要求出每个数字的出现次数，故分别用dfs求

设记忆化数组状态为 f_{x,sum}，表示在没有前导零且填入数组无限制时，填到位置 i，已经填了 sum 个数字 k，数字 k 的总个数，因为体现在 [x+1,len] 的约束条件只有 k 的个数

大致思路清晰了，看看细节：

1. 只有在当前也填 0 且 e2=1 时，才是前导零
3. 找 0 个数时特判前导零
4. 对于答案的处理，不放让记录答案的数组先加上 [1,r] 之间 0 ~ 9 的出现次数，再减掉 [1,l-1] 之间的（具体看代码）
5. 每次计算不同数字的出现个数时，初始化一遍 f 数组
6. 开long long

#include <bits/stdc++.h>
using namespace std;
int a[15],k;
long long f[15][15],z[15];
long long dfs(int x,int sum,int e1,int e2)
{
    if(x == 0)
    {
        return sum;
    }
    if(e1 == 0 && e2 == 0 && f[x][sum] != -1)
    {
        return f[x][sum];
    }
    int b = (e1 == 1 ? a[x] : 9);
    long long ans = 0;
    for(int i = 0;i <= b;i++)
    {
        int c = sum + (k == i);
        if(i == 0 && e2 == 1)
        {
            c = 0;
        }
        ans += dfs(x - 1,c,e1 == 1 && i == b,e2 == 1 && i == 0);
    }
    if(e1 == 0 && e2 == 0)
    {
        f[x][sum] = ans;
    }
    return ans;
}
void fun(long long n,int v)//v表示这次得出的数值加还是减
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 10;
        n /= 10;
    }
    for(int i = 0;i <= 9;i++)
    {
        memset(f,-1,sizeof(f));
        k = i;
        z[i] += v * dfs(cnt,0,1,1);
    }
}
int main()
{
    long long l,r;
    scanf("%lld%lld",&l,&r);
    fun(r,1);
    fun(l - 1,-1);
    for(int i = 0;i <= 9;i++)
    {
        printf("%lld ",z[i]);
    }
    return 0;
}

例3：P2657

题面

最经典的题了，题目对相邻的数有要求，显然要加上参数 l，它的初值不能是 0,-1，因为这会导致 0,1 不能填，可以设为 -3

考虑 f 的状态，此时对于 [x+1,len] 的状态只有 l，所以状态为 f_{x,l}

现在考虑前导零对于下一次dfs的影响，如果仍为前导零，那么 l 的值是不能变的，否则变为 i

注意此题dfs参数不需要有 sum 了，因为问的是windy数个数，所以 x=0 直接返回 1 即可

#include <bits/stdc++.h>
using namespace std;
int a[15],f[15][15];
int dfs(int x,int e1,int e2,int l)
{
    if(x == 0)
    {
        return 1;
    }
    if(f[x][l] != -1 && e1 == 0 && e2 == 0)
    {
        return f[x][l];
    }
    int b = (e1 == 1 ? a[x] : 9),ans = 0;
    for(int i = 0;i <= b;i++)
    {
        if(e2 == 1)
        {
            ans += dfs(x - 1,e1 == 1 && i == b,e2 == 1 && i == 0,i == 0 ? l : i);
        }
        else if(abs(l - i) >= 2)
        {
            ans += dfs(x - 1,e1 == 1 && i == b,0,i);
        }
    }
    if(e1 == 0 && e2 == 0)
    {
        f[x][l] = ans;
    }
    return ans;
}
int fun(int n)
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 10;
        n /= 10;
    }
    return dfs(cnt,1,1,-3);
}
int main()
{
    memset(f,-1,sizeof(f));
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d",fun(r) - fun(l - 1));
    return 0;
}

例4：P4317

P4317

考虑拆成二进制，然后遍历每一位，参数只需要 x,sum,e 即可

DP状态为 f_{x,sum}，表示位置 x 且已经填了 sum 个 1，1 的总个数是多少

统计答案时，ans 初值设为 1，每次相乘，这里dfs直接遍历到下一位即可，无需分类讨论

这里有坑，如果 x=0，返回值应该是 max(sum,1)，因为每个数的二进制至少有一个 1

#include <bits/stdc++.h>
using namespace std;
int a[60];
long long f[60][60],mod = 10000007;
long long dfs(int x,long long sum,int e)
{
    if(x == 0)
    {
        return max(sum,1ll);//坑
    }
    if(f[x][sum] != -1 && e == 0)
    {
        return f[x][sum];
    }
    int b = (e == 1 ? a[x] : 1);
    long long ans = 1;
    for(int i = 0;i <= b;i++)
    {
        ans = (ans * dfs(x - 1,sum + (i == 1),e == 1 && i == b)) % mod;
    }
    if(e == 0)
    {
        f[x][sum] = ans;
    }
    return ans;
}
long long fun(long long n)
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 2;
        n /= 2;
    }
    return dfs(cnt,0,1);
}
int main()
{
    memset(f,-1,sizeof(f));
    long long n;
    scanf("%lld",&n);
    printf("%lld",fun(n));
    return 0;
}

例5：P6218

题面

本题的约束条件是 0 的数量和 1 的数量，所以不妨把它们设成DP状态：f_{x,cnt_0,cnt_1} 表示已经填到位置 x，且填了 cnt_0 个 0 和 cnt_1 个 1 的圆数数量

对于dfs参数，显然要有 x,cnt_0,cnt_1,e1，因为此题涉及了 0 的个数，所有也要有 e2

注意一个细节，在 x=0 时，只有 cnt_0 \ge cnt_1 才满足圆数的条件

依旧要特判前导零，这时 0,1 的数量还是 0 不变，因为根本没填

#include <bits/stdc++.h>
using namespace std;
int a[40],f[40][40][40];
int dfs(int x,int cnt0,int cnt1,int e1,int e2)
{
    if(x == 0)
    {
        return cnt0 >= cnt1;
    }
    if(f[x][cnt0][cnt1] != -1 && e1 == 0 && e2 == 0)
    {
        return f[x][cnt0][cnt1];
    }
    int b = (e1 == 1 ? a[x] : 1),ans = 0;
    for(int i = 0;i <= b;i++)
    {
        int c = (e2 == 1 && i == 0),u = cnt0,v = cnt1;
        if(c == 0)
        {
            u += (i == 0);
            v += (i == 1);
        }
        ans += dfs(x - 1,u,v,e1 == 1 && i == b,c);
    }
    if(e1 == 0 && e2 == 0)
    {
        f[x][cnt0][cnt1] = ans;
    }
    return ans;
}
int fun(int n)
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 2;
        n /= 2;
    }
    return dfs(cnt,0,0,1,1);
}
int main()
{
    memset(f,-1,sizeof(f));
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d",fun(r) - fun(l - 1));
    return 0;
}

例6：CF628D

题面

要开始入坟了喵嗷！！

题目中给定的 l,r 特别大，所以干脆用字符串存储，注意在转数组的时候要倒过来

原本的式子 fun(r)-fun(l-1) 出现了高精度减法，有点麻烦，不妨改成 fun(r)-fun(l)+ck(l) 其中 ck(l) 表示检验 l 是否为d-magic数

观察到题目的约束条件有两个，奇偶数位的值和取模后的值，那么 ck 函数直接判断就行了，dfs参数肯定要加入 r 代表当前数 mod m 的值

现在考虑是否需要判断前导零，因为题目中保证 l,r 位数相同，所以如果找到了不合法（位数小）的数，也是 l,r 都有的，相减直接抵消，不用管了

那么DP状态就有了，f_{x,r} 代表位置 x 模 m 等于 r 时d-magic数的个数

在写dfs时，如果当前是偶数位，则只能填 d，否则能填 [0,b] 之间除了 d 以外的所有数

坑点：由于 a 数组中数是反着存的，高位对应的下标更大，所以判断数位时要用 cnt-x+1 而非 x

#include <bits/stdc++.h>
using namespace std;
string l,r;
int m,d,a[2005],cnt;
long long f[2005][2005],mod = 1e9 + 7;
long long dfs(int x,int sum,int e)
{
    if(x == 0)
    {
        return sum == 0;
    }
    if(f[x][sum] != -1 && e == 0)
    {
        return f[x][sum];
    }
    int b = (e == 1 ? a[x] : 9),y = cnt + 1 - x;
    long long ans = 0;
    if(y % 2 == 0)
    {
        if(d <= b)
        {
            ans = (ans + dfs(x - 1,(sum * 10 + d) % m,e == 1 && d == b)) % mod;
        }
    }
    else
    {
        for(int i = 0;i <= b;i++)
        {
            if(i != d)
            {
                ans = (ans + dfs(x - 1,(sum * 10 + i) % m,e == 1 && i == b)) % mod;
            }
        }
    }
    if(e == 0)
    {
        f[x][sum] = ans;
    }
    return ans;
}
long long fun(string s)
{
    cnt = s.size();
    for(int i = 0;i <= s.size() - 1;i++)
    {
        a[cnt - i] = int(s[i]) - 48;
    }
    return dfs(cnt,0,1);
}
int ck(string s)
{
    int g = 1;
    long long sum = 0;
    for(int i = 0;i <= s.size() - 1;i++)
    {
        int x = int(s[i]) - 48;
        sum = (sum * 10 + x) % m;
        if(i % 2 == 0 && x == d)
        {
            g = 0;
            break;
        }
        if(i % 2 == 1 && x != d)
        {
            g = 0;
            break;
        }
    }
    if(g == 0)
    {
        return 0;
    }
    return sum == 0;
}
int main()
{
    memset(f,-1,sizeof(f));
    cin >> m >> d >> l >> r;
    printf("%lld\n",(fun(r) - fun(l) + ck(l) + mod) % mod);
    return 0;
}

例7：P4124

题面

显然需要维护上一个数字和上上个数字，以及是否已经出现 3 个相邻数字（tl），是否出现 4,8（cnt4,cnt8）

那么 f 数组直接把上述所有的都放进去即可，因为这些都是约束条件

在填数时，如果已经有 8 则不能填 4，有 4 则不能填 8，对于 tl,cnt4,cnt8 的运算都是或运算，因为如果已经达成了后面怎么填都不会影响

题目还要求不能有前导零，于是在 x=cnt 时特判一下

巨大坑点：当区间左端点为 10^{10} 时，不能无脑 fun(l-1)，因为电话号码要求 11 位数，应该变成 fun(r)-fun(l)+1

#include <bits/stdc++.h>
using namespace std;
int a[15],cnt;
long long f[15][15][15][3][3][3];
long long dfs(int x,int l2,int l1,int tl,int cnt4,int cnt8,int e)
{
    if(x == 0)
    {
        return tl == 1;
    }
    if(f[x][l2][l1][tl][cnt4][cnt8] != -1 && e == 0)
    {
        return f[x][l2][l1][tl][cnt4][cnt8];
    }
    int b = (e == 1 ? a[x] : 9),w = 0;
    long long ans = 0;
    if(x == cnt)
    {
        w = 1;
    }
    for(int i = w;i <= b;i++)
    {
        if((i == 4 && cnt8 == 1) || (i == 8 && cnt4 == 1))
        {
            continue;
        }
        ans += dfs(x - 1,l1,i,(tl == 1) || (l2 == l1 && l1 == i),cnt4 | (i == 4),cnt8 | (i == 8),e == 1 && i == b);
    }
    if(e == 0)
    {
        f[x][l2][l1][tl][cnt4][cnt8] = ans;
    }
    return ans;
}
long long fun(long long n)
{
    cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 10;
        n /= 10;
    }
    return dfs(cnt,10,10,0,0,0,1);
}
int main()
{
    memset(f,-1,sizeof(f));
    long long l,r;
    scanf("%lld%lld",&l,&r);
    if(l != 10000000000)
    {
        printf("%lld",fun(r) - fun(l - 1));
    }
    else
    {
        printf("%lld",fun(r) - fun(l) + 1);
    }
    return 0;
}

例8：CF855E

题面

要保证数字的出现次数是偶数次，那么不妨让偶数是 0，奇数是 1，构造一个集合 s，是所有数字的奇偶性构成二进制数的十进制值，那么符合条件的就是 s=0（简单状压）

此题涉及到了 0 的出现次数，所以要有 e2，这有个坑点，当 e2=1,s=0 时全是前导零相当于没填，不能算是一个符合条件的数，要特判掉

DP状态：f_{k,x,s} 表示 k 进制下位置 x 且当前奇偶性为 s 时，数的个数（因为有 10^5 次询问但最多有十种进制，所以加一维优化）

那么每次填数 s 怎么改变呢？位运算yyds！在确保不是前导零的情况下，s^(1<<i)就是让第 i 为奇偶性转变

但有个问题，这个题不知道为什么卡不过去CF的评测，TLE #14，明明和标程一样的思路啊喵！！>.<

#include <bits/stdc++.h>
using namespace std;
int k,a[60];
long long f[15][60][1030];
long long dfs(int x,int s,int e1,int e2)
{
    if(x == 0)
    {
        return s == 0 && e2 == 0;
    }
    if(f[k][x][s] != -1 && e1 == 0 && e2 == 0)
    {
        return f[k][x][s];
    }
    int b = (e1 == 1 ? a[x] : k - 1);
    long long ans = 0;
    for(int i = 0;i <= b;i++)
    {
        int t = 0;
        if(e2 == 0 || i != 0)
        {
            t = s ^ (1 << i);
        }
        ans += dfs(x - 1,t,e1 == 1 && i == b,e2 == 1 && i == 0);
    }
    if(e1 == 0 && e2 == 0)
    {
        f[k][x][s] = ans;
    }
    return ans;
}
long long fun(long long n)
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % k;
        n /= k;
    }
    return dfs(cnt,0,1,1);
}
int main()
{
    memset(f,-1,sizeof(f));
    int q;
    scanf("%d",&q);
    while(q--)
    {
        long long l,r;
        scanf("%d%lld%lld",&k,&l,&r);
        printf("%lld\n",fun(r) - fun(l - 1));
    }
    return 0;
}

例9：SP10606

题面

注意，题目中说的是出现过的奇/偶数数量为偶/奇数，众所周知 0 也是偶数，所以如果只记录数字出现次数会有问题，不妨用两个集合 s1,s2，s1 记录该数字是否出现，s2 记录出现次数奇偶性

更新集合时，显然为s1|(1<<i)和s2|(1<<i)，相应的 f 的状态加一维变成 f_{x,s1,s2}，空间有点大但原题给的是1.46GB

检查是否满足要求稍微复杂一点，对于每个数字，如果出现了（s1&(1<<i)），且为偶数&出现偶数次或为奇数&出现奇数次，就不符合要求

错因：位运算&不能直接判断，要加括号，比如a&b!=0是错误的，写成(a&b)!=0或者a&b即可，这里建议位运算的判断别用等号，判非零直接不写，判零加个!就行

#include <bits/stdc++.h>
using namespace std;
int a[20];
long long f[20][1030][1030];
long long dfs(int x,int s1,int s2,int e1,int e2)
{
    if(x == 0)
    {
        int g = 1;
        for(int i = 0;i <= 9;i++)
        {
            if(s1 & (1 << i))
            {
                if((i % 2 == 0 && !(s2 & (1 << i))) || (i % 2 == 1 && (s2 & (1 << i))))
                {
                    g = 0;
                    break;
                }
            }
        }
        return g == 1 && e2 == 0;
    }
    if(f[x][s1][s2] != -1 && e1 == 0 && e2 == 0)
    {
        return f[x][s1][s2];
    }
    int b = (e1 == 1 ? a[x] : 9);
    long long ans = 0;
    for(int i = 0;i <= b;i++)
    {
        int t1 = 0,t2 = 0;
        if(e2 == 0 || i != 0)
        {
            t1 = s1 | (1 << i);
            t2 = s2 ^ (1 << i);
        }
        ans += dfs(x - 1,t1,t2,e1 == 1 && i == b,e2 == 1 && i == 0);
    }
    if(e1 == 0 && e2 == 0)
    {
        f[x][s1][s2] = ans;
    }
    return ans;
}
long long fun(long long n)
{
    int cnt = 0;
    while(n != 0)
    {
        a[++cnt] = n % 10;
        n /= 10;
    }
    return dfs(cnt,0,0,1,1);
}
int main()
{
    memset(f,-1,sizeof(f));
    int q;
    scanf("%d",&q);
    while(q--)
    {
        long long l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",fun(r) - fun(l - 1));
    }
    return 0;
}

神犇名言：