对数位dp的一些拙见

这不是一篇介绍数位 d p dp dp的文章，只是我思考后的一些记录，怕以后就忘记了。

由于博主太菜不会组合数学，以下数位 d p dp dp均采用记忆化搜索的方式。

首先最重要的就是状态设计了，正常来说数位 d p dp dp的状态设计需要包含数的结构和状态。

数位 d p dp dp的复杂度可以简单理解为开的数组的大小。

对于数位 d p dp dp有两种理解：

第一种： d p dp dp的状态只与当前数的位数以及要维护的状态有关。在这种理解方式下， d p dp dp状态设计通常为 f [ p o s ] [ s t a t e ] f[pos][state] f[pos][state]，由于状态中并未规定上下界，所以对于每次查询操作，并不需要将其 d p dp dp数组清成 − 1 -1 −1，这样在应对多组查询的时候可能会快一点。在记忆化的时候需要加上 f l a g 1... flag1... flag1...等限制上界的变量是否为 1 1 1，即当前位是否可以选任意数，在多组测试情况下这个方法跑的还可以。当然这个只跑的快只能在维护一个数的时候跑的快，如果你要维护一对数，那么记忆化的时候 f l a g 1 & & f l a g 2 flag1 \And\And flag2 flag1&&flag2才能记忆化，这样的话就会慢很多，导致 T L E TLE TLE，所以当维护两个数及以上的时候最好不要用这种记忆化方式。

写成的代码大概是这样的：

if(f[pos][state]!=-1&&flag) return f[pos][state];
if(flag) f[pos][state]=ans;
return ans;
           

第二种： 在状态中加入 0 / 1 0/1 0/1表示是否达到上界，即上文中的 f l a g 1 , f l a g 2... flag1,flag2... flag1,flag2...，这样的话由于每次询问的数都不同，所以每次都需要将 f f f数组置为 − 1 -1 −1才能记忆化，这样的优点和缺点相比于上面的方式很明显，优点就是这个状态设计能记录 f [ p o s ] [ s t a t e ] [ 0 ] f[pos][state][0] f[pos][state][0]的信息，即如果当前位不能自由选也可以记忆化，而上面的只能记录下来 f [ p o s ] [ s t a t e ] [ 1 ] f[pos][state][1] f[pos][state][1]的信息，只不过我们将最后一维省略了。缺点也比较明显，每次都需要初始化 f f f数组，让后重新 d p dp dp一次，不过也不会太慢。

写成代码大概是这样的：

if(f[pos][state][flag]!=-1) return f[pos][state][flag];
return f[pos][state]=ans;
           

对于前导零：

当涉及到对数的结构特点进行维护的时候就有可能需要维护一个前导零了。比如说求 [ l , r ] [l,r] [l,r]内有多少个数的位数中含 k k k个 0 0 0，这个时候如果不维护一个前导零的话会将如 0010 0010 0010中前面两个 0 0 0也算入答案，这显然是不正确的。

数位 d p dp dp很多题目求贡献的话都是按位或者按照数来求的。

做过的例题：

2020 ICPC 上海 Sum of Log 数位dp + 优化状态

hdu 6899 Xor 数位dp

FZU - 2042 The Mad Mathematician 数位dp + 算贡献

暂时先更这些，后面有更好的理解会补充。