数位DP

# 数位DP

## 学习计划

2021/1/18 基本知识、思路、例题
2021/1/19 基本例题、习题
2021/1/20 习题、整理

https://blog.csdn.net/tomjobs/article/details/111741760
https://www.lmlphp.com/user/56/article/item/6747/
https://blog.csdn.net/jk211766/article/details/81474632
https://www.luogu.com.cn/blog/virus2017/shuweidp
题单

[HDU2089](http://acm.hdu.edu.cn/showproblem.php?pid=2089)
![0](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120004319.png)
状态：dp[pos][pre][st]
pos：位置
pre：前一位
st：扫到当前位是否已经是满足条件。

[洛谷P2657](https://www.luogu.com.cn/problem/P2657)
![1](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120011440.png)
状态：dp[pos][pre][st]
pos：位置
pre：前一位
st：扫到当前位是否已经不再满足条件。

[洛谷P2602](https://www.luogu.com.cn/problem/P2602)
![2](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120013001.png)
状态：num，dp[pos][st]
num为当前计算的数码
pos：位置
st：扫到当前位数码num已经出现的次数。

[洛谷P3413](https://www.luogu.com.cn/problem/P3413)
![3](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120140100.png)
![4](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120140111.png)

！思路：正难则反！考虑不符合条件的情形：任何一位都不和前两位数字相同。
状态：dp[pos][pre1][pre2][st]

pos：位置
pre1：前一位字符
pre2：前前一位字符
st：当前状态是否已经还满足“任何一位都不和前两位数字相同”
其他问题：
  由于正常数位DP会采用`part(r) - part(l-1)`，但此处需要实现高精度，那么可以考虑只算`part(r)-part(l)`，再单独判断一下`l`。
  由于最后要用`(r-l+1)`减去自己算的才是题目要的答案，而`(r-l+1)`可以先取模再运算。

[洛谷P4127](https://www.luogu.com.cn/problem/P4127)
![5](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120180950.png)
[参考](https://www.luogu.com.cn/blog/virus2017/p4127)
需要记录扫描到当前位置的数位cur_sum和以及原数st。
如何构造状态进行记忆化：
st很大，无法记忆化，因此我们考虑枚举数位和，然后再进入递归求解。
也就是枚举digit_sum，该轮循环进入的dfs求解的是数位和是digit_sum且本身能被digit_sum整除的数的个数。
然后就是不再直接存储st，而是考虑st对digit_sum求模。
递归终止条件是 `if(pos > len) return (st == 0 && cur_sum == digit_sum) ? 1 : 0;` 。

[洛谷P4317](https://www.luogu.com.cn/problem/P4317)
![6](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120201511.png)
注意是连乘！
所以我们考虑先枚举`sum(i)`可能的值，设其为`d`，那么我们每次使用数位dp统计1~N中二进制形式中`1`的个数为`d`的数有多少。然后再快速幂计算总的连乘答案即可。
注意：这题的数位DP中别取模，因为求的是答案表达式中的指数。

[洛谷P4124](https://www.luogu.com.cn/problem/P4124)
![7](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210120213858.png)
dp[pos][pre1][pre2][s3][s4][s8]：
pos：位置
pre1：前一位字符
pre2：前前一位字符
s3：是否已经有三位相邻数字相同
s4：是否出现过数字4
s8：是否出现过数字4

王队长的题单，明天学习
HDU4734
HDU4507
HDU3709
Codeforces55D
Codeforces628D
Codeforces914C

epee_no_front's Notes

导航

最近发表

友情链接