数位dp学习笔记
目录数位dp
定义：
...好像就是对数位进行dp，统计方案数。
题型特征：
通常会有10组左右的询问，每一次询问你较大（1e18左右）的区间内满足某个条件的数的数量。
dp设计：
dp一般会有2到4维。
- 通常情况下，第一维i表示现在这个n位数把最大的i位确定了。
- 第二位用于存放受限限制的某种信息。例如要是题要求你找有关gcd的东西，就开一维来存储这个信息。
- 第三位是个bool数（当然用记忆化搜索的话就可以不用开这一维，但也要记录）用于记录当前是否达到了最大值。
这里解释一下为甚要开第三维，比如要求你找的区间是1到114514,但是你在第一位就不能够填9这么大的数字。但是呢，要是没满足这个条件的话，例如我第三位填的3，我后面就可以填9了。 - 第四位是bool数，视情况而定要不要加入，主要是为了判断前导零的影响，例如114514我第一位填0是可以的，但是会不会影响到受限制的那个信息呢？有可能呢,所以就相当于一种小型分类讨论吧。
- 当然你还可以开更多的维度，作用同“2”
dp转移
dp常利用记忆化搜索老解决。建议看着以下例题及代码注释进行理解。
例题：BZOJ 3679
这一道题很明显符合特征，我把我的代码呈现一下。
ll dfs(int pos, ll multi, bool head, bool limit) //limit的时候，要判断是否填数字刚好在上限，head的时候，我们需要考虑到前导零
{
if(multi > N) return 0;//超过限定范围，没必要继续下去了（肯定不会贡献）
if(mp[multi] == 0) mp[multi] = ++cnt;//（special)因为数字之积的值域较大，但是真正能乘出来组成的数字较少，利用map来离散化，这个不是模板部分，这是这道题的一个特殊点
if(pos <= 0) return multi > 0 && multi <= N;//进行统计，因为这道题的满足条件就是这个，所以直接判断就好。有的题还要专门写个函数来搞他。
if(head && !limit && dp[pos][mp[multi]] != -1) return dp[pos][mp[multi]];//记忆化搜索，记得前两个条件也要加上
ll ans = 0;
int num = limit?digit[pos]:9;//填的数字在上限时，最多只能填到区间的上限的这一位的值，否则的话0-9随便取
for(int i=0; i<=num; i++)
{
if(i == 0)//这下面都是小型的分类讨论，主要是在后面两个bool数的决定上。
{
if(head) ans += dfs(pos - 1, multi * i, true, limit && i == num);
else ans += dfs(pos - 1, 0, false, limit && i == num);
}
else
{
if(head) ans += dfs(pos - 1, multi * i, true, limit && i == num);
else ans += dfs(pos - 1, i, true, limit && i == num);
}
}
if(!limit && head) dp[pos][mp[multi]] = ans;//记忆化，记得前两个条件
return ans;
}
ll solve(ll x)//这里的x是上届的这个数
{
int pos = 0;
while(x)//找到上届的这个数的每一位具体是什么，用于对第一个bool数进行满足
{
digit[++pos] = x%10;
x /= 10;
}
return dfs(pos, 0, false, true);
}
其他的题型除了第二维会有大幅度变化外没有大多区别，这边建议不会设计状态的话就看看题解。
因为第二维有可能设计状态压缩什么的，这又是另一个范畴了。