喜讯，我写的文章不仅精选了，还上热门榜了，感谢各位看客

-1-此文的诞生过程

这次的排位赛（#7）的最后一题我在那想了半天，最后才想起来还有数位DP这一回事，于是提交，AC。
在比赛结束后，本来想着去题库找找题目练，结果却发现根本没有“数位DP”这一知识点，于是便有了这篇文章。

0-开始前的准备

本文须读者对一些普通的DP基础（如线性DP）有一定了解，并有一定基础。
如果连DP是什么都不知道，出门左转DP详解

1-数位DP解析

1.1- 数位DP的定义

"数位DP"，顾名思义就是一些关于数论，数位，运算的DP。
或者，你也可以理解为这是一种对一个整数位数的记忆化搜索。

1.2-数位DP的常用题型及时间复杂度

数位DP一般用于“给你一个$[l,r]$的区间，求此区间里有多少个符合条件的数（条件任意）/数和/数字出现数/平方……”，"对于一个（或多个）数字$N$，求此数字的……（随机而变）"，这种题目的$r,N$一般都是$\ge 10^{12}$的，此时朴素的枚举不管是什么机子都会爆那当然，所以这就要用数位DP了。数位DP的主要思想大概是：

先采用前缀和思想，将求解$[l,r]$这个区间内的满足约束的数的数量，转化为$[0,r]$满足约束的数量 - 区间$[0,l-1]$满足约束的数量数位，然后将数字区间$[l,r]$中的数拆分为一个个数位，对于此数位进行数位上的$dfs$。

数位：指如个位、十位、百位等，单个数码（比如十进制，此处就是指$0-9$）在数中所占据的一个位置。

时间复杂度大致为$O(RN)$，这里的$R$指的是进制，$N$指的是数字的位数（一般情况下，$R \in{[2,10,16]},12 \le N \le 1000$）。

1.3-数位DP的流程

#include <bits/stdc++.h>
using namespace std;
int *[N],dp[N][N][2][……]……，……;//*:存n的数组，dp:记忆化/dp用(维数任意，但一般>=4;数字任意)
long long dfs(int pos,int cnt,bool limit,……){//pos:位数，cnt:题目限制数的数量/当前数的[按题目要求自定义]，limit:判断当前的极限（后边有用）
    long long ans=0;
    ……//自定义
    if (pos==len){
        ……//自定义
        return ……;//自定义
    }
    ……//自定义
    if (dp[pos][cnt][limit][……]……!=-1){
        return dp[pos][cnt][limit][……]……;//记忆化搜索
    }
    for (int i=0;i<=(limit?*[pos]:9);++i){//枚举当前位的所有可能数字
         ……//自定义
         ans+=dfs(pos+1,……,limit && ……,……);//自定义
    }
    dp[pos][cnt][limit][……]……=ans;//记忆
    return ans;//返回
}
long long f(long long x){//x一般代指r
    len=0;
    memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);//初始化
    while (x){
        *[len++]=x%10;
        x/=10;
    }//放入n
    reverse(*,*+len);//这里由于之前插入在*数组的n是倒序的，所以要反转一下
    ……//自定义
    return dfs(……);//自定义
}
int main(){
    ……//自定义
}

$\divideontimes:$如果以上内容还没有懂得话，那就多看几遍。

2-Problems

由于ACGO上没有题，所以选了一些洛谷题

2.1-洛谷P2602

数位DP模板题，注意要判断前导零的情况。
Code:

#include <bits/stdc++.h>
using namespace std;
long long *[101],dp[50][50][50][50],len,digit;//digit:判断的数字
long long dfs(int pos,int cnt,bool limit,bool lold){
    long long ans=0;
    if (pos==len){
        return cnt;
    }
    else if (dp[pos][cnt][limit][lold]!=-1){
        return dp[pos][cnt][limit][lold];
    }
    for (int i=0;i<=(limit?*[pos]:9);++i){
        if (lold && i==0){
            ans+=dfs(pos+1,cnt,limit && i==*[pos],1);//如果有前导零，则cnt不加
        }else{
            ans+=dfs(pos+1,cnt+(i==digit),limit && i==*[pos],0);
        }
    }
    dp[pos][cnt][limit][lold]=ans;
    return ans;
}
long long f(long long x){
    len=0;
    memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);
    while (x){
        *[len++]=x%10;
        x/=10;
    }
    reverse(*,*+len);
    return dfs(0,0,1,1);
}
int main(){
    long long x,y;
    cin>>x>>y;
    for (int i=0;i<=9;++i){
        digit=i;
        long long l=f(x-1),r=f(y);
        cout<<r-l<<" ";
    }
}

2.2-洛谷-P4999

这题简单求总数，算是双倍经验了
正解我就不贴了（前边改改就行），还是看一下我同机房大神写的偏解吧（也能AC,原理？鬼才知道）
Code

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
unsigned long long run(unsigned long long x)
{
    unsigned long long ret=0;
    unsigned long long M = 1e9 + 7;
    unsigned long long m=1;
    while (m<=x) {
        unsigned long long l=x%m;
        int k=(x/m)%10;
        for(long long i=1;i<=9;++i){
            ret += (x/(m*10))*m*i;
           // cout<<"B"<<ret<<endl;
            ret %= M;
        }
       // cout<<"*"<<ret<<endl;
        for(int i=1;i<=k-1;++i){
            ret += m*i;
            ret %= M;
        }
        ret += (l+1)*k;
        ret %= M;
        m *= 10;
        //cout<<m<<" "<<ret<<endl;
    }
    return ret;
}
int main(){
    int t;
    // cout<<run(1e5)<<endl;
    unsigned long long M = 1e9 + 7;
    cin>>t;
    while (t--){
        unsigned long long x,y,sum=0;
        cin>>x>>y;
        unsigned long long l=run(x-1),r=run(y);
        cout<<(M+r-l)%M<<endl;
    }
}

(作者说：看不懂？问kimi/chat GPT4去)

2.3-洛谷P1831

我们可以枚举支点的位置，对于每个满足条件的数，它所对应的支点是唯一的，原因是如果将支点右移，左边减去右边的差将严格单调增加。$state$表示力矩和（支点左边加支点右边），所以当$state<0$时，当前这个数不满足以$i$为支点成为杠杆数的情况，返回$0$。但当$state=0$时并不能就$ans +1$了，因为当前枚举的位置可能还没枚举完。
枚举好支点，问题就转化为：求$[1,x]$中，以第$i$位为支点的杠杆数的个数。
Code:

#include <bits/stdc++.h>
using namespace std;
long long *[101],dp[50][50][2500],len;
long long dfs(int pos,int pront,int mos,bool limit){
    long long tmp=0;
    if (pos==0){
        return mos==0;
    }
    if (mos<0){
        return 0;
    }
    if (!limit && dp[pos][pront][mos]!=-1){
        return dp[pos][pront][mos];
    }
    for (int i=0;i<=(limit?*[pos]:9);i++){
        tmp+=dfs(pos-1,pront,mos+(i*(pos-pront)),limit && (i==(limit?*[pos]:9)));
        //cout<<tmp<<endl;
    }
    if (!limit){
        dp[pos][pront][mos]=tmp;
    }
    return tmp;
}
long long f(long long x){
    len=0;
    long long ans=0;
    memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);
    while (x){
        *[++len]=x%10;
        x/=10;
    }
    for (int i=1;i<=len;i++){
        ans+=dfs(len,i,0,1);
    }
    return ans-len;
}
int main(){
    long long x,y;
    cin>>x>>y;
    long long l=f(x-1),r=f(y);
    cout<<r-l<<endl;
}

2.4-ACGO-(排位赛#7)T6

很简单，cnt记录此数有多少个非零位，等pos到len时在判断
Code:

#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
long long dp[111][111][3][3],len;
int *[111];
int k;
long long dfs(int pos,int cnt,bool limit,bool lold){
    long long ans=0;
    //cout<<pos<<" "<<cnt<<" "<<limit<<" "<<lold<<" "<<*[pos]<<" "<<len<<" "<<k<<" "<<(limit?*[pos]:9)<<endl;
    if (pos==len && cnt==k){
        return 1;
    }else if (pos==len){
    	return 0;
	}else if (dp[pos][cnt][limit][lold]!=-1){
        return dp[pos][cnt][limit][lold]%MOD;
    }
    for (int i=0;i<=(limit?*[pos]:9);++i){
    	//cout<<i<<endl;
        if (lold && i==0){
            ans+=dfs(pos+1,cnt,limit && i==*[pos],1)%MOD;
        }else{
            ans+=dfs(pos+1,cnt+(i!=0),limit && i==*[pos],0)%MOD;
        }
    }
    dp[pos][cnt][limit][lold]=ans;
    return ans%MOD;
}
long long f(string n){
	len=0;
	memset(dp,-1,sizeof dp);
    memset(*,0,sizeof *);
    len=n.size();
    for (int i=0;i<len;++i){
    	*[i]=n[i]-'0';
	}
    return dfs(0,0,1,1)%MOD;
}
int main(){
    int t;
    cin>>t;
    while (t--){
    	k=0;
    	string n;
    	cin>>n>>k;
    	cout<<f(n)%MOD<<endl;
	}
}

（注：代码部分的*是a,望周知）

3-结尾

数位DP的讲解到此结束了，很高兴大家能听我讲解。
下次再会（别走，我写了这么多，能否给个精选/赞/回复）
最后，打个我们团的链接：
中国团，大佬都在里边