防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本防剧透文本
-1-此文的诞生过程
在几个月的排位赛（#7）时，最后一题我在那想了半天，最后才想起来还有数位DP这一回事，于是提交，AC。
在比赛结束后，本来想着去题库找找题目练，结果却发现根本没有“数位DP”这一知识点，于是便有了这篇文章。
0-开始前的准备
本文须读者对一些普通的DP基础（如线性DP）有一定了解，并有一定基础。
如果连DP是什么都不知道，出门左转DP详解
1-数位DP解析
1.1- 数位DP的定义
"数位DP"，顾名思义就是一些关于数论，数位，运算的DP。
或者，你也可以理解为这是一种对一个整数位数的记忆化搜索。
1.2-数位DP的常用题型及时间复杂度
数位DP一般用于“给你一个[l,r][l,r][l,r]的区间，求此区间里有多少个符合条件的数（条件任意）/数和/数字出现数/平方……”，"对于一个（或多个）数字NNN，求此数字的……（随机而变）"，这种题目的r,Nr,Nr,N一般都是≥1012\ge 10^{12}≥1012的，此时朴素的枚举不管是什么机子都会爆那当然，所以这就要用数位DP了。数位DP的主要思想大概是：
> 先采用前缀和思想，将求解[l,r][l,r][l,r]这个区间内的满足约束的数的数量，转化为[0,r][0,r][0,r]满足约束的数量 - 区间[0,l−1][0,l-1][0,l−1]满足约束的数量数位，然后将数字区间[l,r][l,r][l,r]中的数拆分为一个个数位，对于此数位进行数位上的dfsdfsdfs。
>
> > 数位：指如个位、十位、百位等，单个数码（比如十进制，此处就是指0−90-90−9）在数中所占据的一个位置。
时间复杂度大致为O(RN)O(RN)O(RN)，这里的RRR指的是进制，NNN指的是数字的位数（一般情况下，R∈[2,10,16],12≤N≤1000R \in{[2,10,16]},12 \le N \le 1000R∈[2,10,16],12≤N≤1000）。
1.3-数位DP的流程
⋇:\divideontimes:⋇:如果以上内容还没有懂得话，那就多看几遍。
2-PROBLEMS
由于ACGO上没有题，所以选了一些洛谷题
2.1-洛谷P2602
数位DP模板题，注意要判断前导零的情况。
Code:
2.2-洛谷-P4999
这题简单求总数，算是双倍经验了
正解我就不贴了（前边改改就行），还是看一下我同机房大神写的偏解吧（也能AC,原理？鬼才知道）
Code
(作者说：看不懂？问kimi/chat GPT4去)
2.3-洛谷P1831
我们可以枚举支点的位置，对于每个满足条件的数，它所对应的支点是唯一的，原因是如果将支点右移，左边减去右边的差将严格单调增加。statestatestate表示力矩和（支点左边加支点右边），所以当state<0state<0state<0时，当前这个数不满足以iii为支点成为杠杆数的情况，返回000。但当state=0state=0state=0时并不能就ans+1ans +1ans+1了，因为当前枚举的位置可能还没枚举完。
枚举好支点，问题就转化为：求[1,x][1,x][1,x]中，以第iii位为支点的杠杆数的个数。
Code:
2.4-ACGO-(排位赛#7)T6
很简单，cnt记录此数有多少个非零位，等pos到len时在判断
Code:
（注：代码部分的*是A,望周知）
3-结尾
数位DP的讲解到此结束了，很高兴大家能听我讲解。
下次再会（别走，我写了这么多，能否给个精选/赞/回复）
最后，打个我们团的链接：
中国团，大佬都在里边
