前言
不管从实现方式到智慧程度都是数位 \(\rm{dp}\) 好题, 写一下
思路
首先你发现常规的数位 \(\rm{dp}\) 方法不可以实现
原因是不能对于一个数求出其 \(m(x)\)
容易考虑到逆向思考, 你钦定 \(m(x)\) 的值, 看有多少个 \(x\) 满足此要求
怎么做?
先考虑最简单的情况, 如果从 \([L, len]\) 中的数你可以随便填, 钦定众数为 \(s\) , 怎么计算方案数
显然的是我们需要知道 \([1, L)\) 中, 各个数字出现了多少次, 然后我们再枚举众数 \(s\) 的出现次数 \(j\) 方便处理
知道了之前出现多少次, 我们可以计算出之后每个数字出现的最大限制, 具体的
设 \(i\) 的出现次数为 \(c_i\) , 那么众数在之后出现 \(j - c_s\) 次, 数 \(i\) 在之后最多出现 \(j - c_i - [i > s]\) 次
这个是可以动态规划的, 具体怎么做类似于多重背包, 假设剩下的位数是 \(p\) , 容易得到一组分配 \(x\) , 使得 \(\displaystyle\sum_{j = 0}^{9} x_i = p, x_s = j - c_s , \forall i \neq s, 0 \leq x_i \leq j - c_i - [i > s]\)
最终的方案数就是
\[\frac{p!}{\prod_{i = 0}^{9} x_i!} \]知道了上面的方法, 我们首先用数位 \(\rm{dp}\) 的方式枚举一些位置, 如果其满足
从 \([L, len]\) 中的数你可以随便填
就用上面的方法 \(\mathcal{O} (d |n|^2)\) 的做一次
然后就是注意对于未确定
从 \([L, len]\) 中的数你可以随便填
也就是还在前导 \(0\) 阶段或者还在被约束, 这种情况下就继续递归
递归到最深层就直接暴力计算, 复杂度证明见下
但是这个和上面「对于一个数求出其 \(m(x)\)」本质不是相同的吗? 为什么复杂度正确?
然而并不是, 因为上面的情况, \(\rm{dfs}\) 会出现重复计算, 具体为什么?
你发现数位 \(\rm{dp}\) 的第 \(i\) 位会重复调用第 \(i + 1\) 位的运算, 使其复杂度不正确, 这个题也无法记忆化
但是为什么这种做法下不会出现重复计算呢?
你把数位 \(\rm{dp}\) 的图表示出来
其中红色表示还需要继续计算, 蓝色表示可以直接通过 \(\rm{dp}\) 算出答案
发现原本会重复计算的部分, 都可以直接用 \(\mathcal{O} (d |n|^2)\) 的 \(\rm{dp}\) 做出来, 其中 \(d = 10\) , 表示数字的个数
考虑其最终的复杂度
- 枚举 \(s, j\) : \(\mathcal{O} (d^2)\)
- 每次确定 \(s, j\) 之后, 做 \(\rm{dp}\) 的次数 : 容易证明不超过 \(\mathcal{O} (|n| d)\)
总时间复杂度 \(\mathcal{O} (d^4 |n|^3)\) , 迅速通过
总结
正难则反
一种结合了数位 \(\rm{dp}\) , 在数位 \(\rm{dp}\) 确定了无限制的情况下, 用更快的算法计算出来
本质上是利用了数位 \(\rm{dp}\) 有限制的情况少这一特点