数位DP

-1 前言

源于一次校内NOIP模拟赛的第一题。

那道题是一道非常板的数位DP，可惜我没学过，只能打一个40pts暴力~~，最后甚至暴力都挂了。~~

于是乎学习数位DP，写了这篇笔记。

0 前置知识

无

1 用途

数位DP，顾名思义就是对数字的每一位进行DP的一种算法。一般用于解决具有以下特征的问题：

1. 给定一个区间，令你求区间内满足某一特征的数的个数。

2. 数据范围非常大，暴力枚举会超时。

举一个例子，就比如：

• 我们定义一个同时含有 $1,4,5$ 三个数的数字为hm数，给定区间 $[l,r]$,求给你定区间内hm数的个数。数据保证 $0\leq l\leq r\leq 10^{1145}$。

上面的例子只是作为示范，我也不知道可不可做。

2 原理

数位DP本质上是一种利用DP数组统计情况最后汇总答案的方法。

首先，区间 $[l,r]$ 内的信息不好直接维护，我们可以维护 $[1,l-1]$ 和 $[1,r]$ 内的信息，用类似于前缀和的方法计算出 $[l,r]$ 的信息。

然后，我们预处理一个DP数组 $f_{i,j}$,表示填数填到了第 $i$ 位，并且这一位填的是数字 $j$ 时的可能的符合条件的数字个数。

然后，我们就可以根据 $l,r$ 的每一位来计算了。

3 具体理论

我们以 P13085 [SCOI2009] windy 数（加强版） - 洛谷为例题。

（2025.7.29：已将例题严肃更新为 $n\leq 10^{18}$ 的新版本。）

我们可以按照上述的步骤，先预处理出 $f_{i,j}$ ,来表示有 $i$ 位的数中，当前这一位为 $j$ 的符合条件的数的个数。

然后我们考虑怎么计数。

假设我们现在要处理 $[0,x]$ 区间内的windy数数量， $x$ 的位数为 $k_1$，并且目前填的数有 $k_2$ 位，那么我们考虑：

• 如果 $k_1>k_2$ ，那么我们直接累加 $f_{k_1,0}$ 到 $f_{k_1,9}$ 。

• 如果 $k_1=k_2$ ，那么就要考虑高位限制。

所谓“高位限制”，就是判断这个数之前填的位置有没有填到“最高位”上。我们用 $x_i$ 来表示 $x$ 的第 $i$ 位，“高位限制”也就是判断之前填的位置的数是否都取到了 $x_i$。这是为了保证我们填的数不超过 $x$ 。

举个例子：

假设 $x=114514$ ，我们目前填的数为 $\overline{abcdef}$。

假设 $a=1,b=1,c=3$，那么我们考虑 $d$ 的取值。

答案是任意一个个位数。

因为此时 $c$ 没有取到最高位，所以就没有高位限制。

假设 $a=1,b=1,c=4$，那么我们考虑 d 的取值。

首先，由于 $a,b,c$ 都取到了最高位，所以此时有高位限制，$d$ 最大只能取到 $5$。

其次由于windy数的性质，我们要求 $d\in [1,2] \cup [6,9]$ 。

综上，一定有 $d\in[1,2]$。

高位限制就是这样一个东西。

然后其他的我们就是累加上面所有的结果。

4 实现

上面的东西主要为废话理论知识，接下来我们结合代码讲解。

呃好像没啥可讲的。

直接结合注释看代码吧。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x&-x)
#define elif else if
int read(){
    int f=1,s=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c-'0');c=getchar();}
    return f*s;
}
const int MAXN=15;
int l,r;
int f[114][114];
void init(){//预处理
    for(int i=0;i<=9;++i){
        f[1][i]=1;
    }//一位数的每种情况只有一个符合条件
    for(int i=1;i<MAXN;++i){//枚举位数
        for(int j=0;j<=9;++j){//枚举这一位
            for(int k=0;k<=9;++k){//枚举上一位
                if(abs(j-k)>=2) f[i][j]+=f[i-1][k];//如果符合windy数条件就计数
            }
        }
    }
}
int a[114];
int solve(int x){
    if(x==0)return 0;
    int k=0,ans=0;
    while(x){a[++k]=x%10;x/=10;}//数字转化为数组
    int lst=-2;//记录上一位数
    for(int i=k;i>=1;--i){
        for(int j=(i==k);j<a[i];++j){//j<a[i]，防止高位限制
            if(abs(j-lst)>=2)ans+=f[i][j];//如果每一位符合条件就直接计数
        }
        if(abs(a[i]-lst)<2)break;//最高位不符合限制直接退出
        lst=a[i];//更新上一位数
        if(i==1) ans++;//如果完整填完那么x也是符合条件的数
    }
    for(int i=1;i<k;++i){
        for(int j=1;j<=9;++j){
            ans+=f[i][j];
        }
    }//位数小于k的情况，直接累加所有
    return ans;
}
signed main(){
    init();//初始化
    l=read();//输入
    r=read();  
    printf("%lld",solve(r)-solve(l-1));//输出
} 

5 后记

咕咕咕了两天后还是发出来了，但是写的有点急，等以后再完善一下啥的吧。