浅谈数位 DP

zhangjinxuan

浅谈数位 DP

Update Logs:
- [2024/11/26 23:00] 完成了未完成的部分。

更好的阅读体验。

本文章的作者与上处链接所指向的文章的作者是同一个人。

前言

---

本文全方面讲解了数位 DP 从基础的计数到入土的拓展（例如自动机、进退位和偏序），我认为我至少比 OI-wiki 写得好，但总有缺漏或错误之处，欢迎大佬指出。

这里我专门整理了一个数位 DP 专题的题单，欢迎收藏。

声明：请勿搬运。

引言

---

此处部分参考于 OI-wiki。

数位 DP 的题目一般是如下情形：

- 在一个区间范围内统计一些东西。

在区间范围很小的时候，显然可以暴力枚举，但是当区间范围很大的时候，就要使用数位 DP 优化。

为什么数位 DP 就能优化这一点呢？数位 DP 的核心思想大概就是，对于很多个数字，他们都有可能存在相同的贡献，比如在 P2602（分别统计一个范围内所有数位的出现次数） 一题中，数字 $12345$ 和数字 $54321$，$3$ 都在百位出现了 $2$ 次，如果统计的区间范围足够大，那么这个数字会更多，所以我们就可以使用计数的方法优化。

而 DP 是什么呢？比方说一道题目要统计 $1\sim n$ 的所有数字的数位和的和，会发现 $123456$ 和 $123457$ 这两个数字他们都有一个共同的前缀，这种前缀只有在暴力枚举的时候会增加复杂度，而 DP 就不会存在这一点。

因而，数位 DP 大概也就有两种分类，并且细分为多种写法：

- 数位计数。
        - 纯数位计数。
        - 拆分区间范围。
- 数位 DP。
        - 纯 DP
        - 枚举 LCP + DP。

更复杂的情况会在对应的位置讲解，不过不管怎样，都需要考察选手对于数位的深刻理解能力。

下文会介绍所有常用的数位 DP 写法，并且介绍部分简单的拓展。

希望您能在阅读下文之前评分和收藏，谢谢！

                               
登录/注册后可看大图

zhangjinxuan

纯胡说，没什么东西

zhangjinxuan

@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山

柿子饼同学

想起来之前做过的一个比较恶心的
CF1194G
哎, 退役了

#include <bits/stdc++.h>
using namespace std;

/*
    首先把 x / y
    换成  k*dx / k*dy
    枚举的是 x 和 y, 但是我们必须保证 k 相同, 并且 x, y 分别被 dx, dy 整除
    于是乎我们状态中存下来 前 pos 位的 x, y 分别除以 dx, dy 的余数, 再存 x, y 中出现的数字
    答案就是 余数都是 0 并且出现数字符合题意的状态的答案之和

    举个栗子:
    这个竖式的答案是 k, 我们按位枚举 k 的位数(这样保证了 k 相同), 现在 k 这一位是 i 
       ______________
    dx )  A   B   j ...这里是 x 的位置, 在做除法, 枚举 x 的这一位为 j
        _________
    上一次的余数 = rx 
    那么这次的余数就是 (rx*10 + j) - i*dx, 这个余数要在 [0, dx) 的范围
    再用状压把这次出现的数位 j 打上去即可
*/

const int N = 102;
const int P = 998244353;

// f(pos, sx, sy, rx, ry) 代表前 pos 位, x, y 带有的数字状态, x, y 除以 dx, dy 的余数
int f[N][16][16][10][10];
string s;
int num[N], n;
int dx, dy;
int ans;
// 分数值一样的一起算, 不然会算重
// 情况最多的是 1/2 = 2/4 = 3/6 = 4/8 共 4 组
// tot 是组数
int choice[2][4], tot;

// type == 0 表示是 x, type == 1 表示是 y
int Add(int st, int d, int type){
    for(int i = 0; i < tot; i++){
        if(choice[type][i] == d){
            st |= (1 << i);
            return st;
        }
    }
    return st;
}

int dfs(int pos, int sx, int sy, int rx, int ry, bool lim){
    if(pos == n + 1){
        // 没有余数, 并且 x 中出现 dx, y 中出现了 dy
        if(!rx && !ry && (sx & sy)) return 1;
        return 0;
    }

    auto& cur = f[pos][sx][sy][rx][ry];

    if(!lim && ~cur) return cur;

    int res = 0;
    int up = 9;
    int newrx, newry;
    if(lim) up = num[pos];

    // 枚举 k 的数位(竖式答案), x / dx == y / dy == k
    for(int ki = 0; ki < 10; ki++){

        // 枚举 x 的数位(竖式被除数)
        for(int xi = 0; xi <= up; xi++){
            newrx = (rx*10 + xi) - ki*dx;

            if(newrx < 0) continue;
            if(newrx >= dx) break;

            // 枚举 y 的数位, 流程是一样的
            // y 比 x 小, 所以不用管
            for(int yi = 0; yi < 10; yi++){
                newry = (ry*10 + yi) - ki*dy;

                if(newry < 0) continue;
                if(newry >= dy) break;

                res = (res + dfs(pos + 1, Add(sx, xi, 0), Add(sy, yi, 1), newrx, newry, lim && (xi == up))) % P;
            }
        }
    }

    if(!lim) cur = res;
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> s;
    n = s.size();
    for(int i = 1; i <= n; i++){
        num[i] = s[i - 1] - '0';
    }

    // dx == dy 的情况, 这时每个数都满足条件, ans += num
    for(int i = 1; i <= n; i++){
        ans = (ans*10 + num[i]) % P;
    }

    // 强制令 x > y (即 dx > dy), 这样只需要满足 x <= n 就行了
    for(int i = 1; i < 10; i++){
        for(int j = 1; j < i; j++){
            if(__gcd(i, j) != 1) continue;

            memset(f, -1, sizeof(f));
            for(tot = 0; tot < 4; tot++){
                if(i*(tot + 1) > 9) break;
                choice[0][tot] = i*(tot + 1);
                choice[1][tot] = j*(tot + 1);
            }
            dx = i, dy = j;

            long long w = (dfs(1, 0, 0, 0, 0, 1)*2ll) % P;

            ans = (ans + w) % P;
        }
    }

    cout << ans;
    
    return 0;
}

柿子饼同学

noip分数线怎么还变高了...
哎这下完了

tommyyu

zhangjinxuan 发表于 2024-12-7 10:37
@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山

退役了开始搞化竞了

sfqxx

失踪人口回归

baimups

失踪人口回归

zyx2012

NB!!

123456qax

谢谢

123456qax

谢谢

OKMY

6

学习编程中的Ben

厉害！！！

123456qax

谢谢

6bingame

感谢分享，看不懂嘻嘻

zhangjinxuan

1

Ewan-Ahiouy

zhangjinxuan 发表于 2024-12-7 10:37
@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山

sry来晚啦~

sfqxx

顶一顶

trinityee

方少恒

学习一下