一个利用随机在记忆化算法中进行卡常的技巧

· · 个人记录

使用记忆化算法时，有时会遇到由于空间限制较小，状态过多无法记忆化，或者需要使用 map/umap/hashtable 等数据结构记忆化，时间无法承受的问题。

这时，我们希望寻找一种方法，可以在减小对用于记忆化的数据结构的访问（这同时减少了时间和空间常数，甚至可以减小空间复杂度）的同时，不影响时间复杂度。

考虑以一定概率 p 进行当前状态的记忆化，设总状态数为 n，那么空间复杂度即为 O(np)，若每个状态能转移到的状态个数不多，那么对时间常数的影响并不大。如果能转移到的状态个数极少，甚至可以继续采用以 p 的概率访问记忆化结构，可以将访问记忆化结构的次数也乘上 p，例子见下。

例题：CF1806E（认为 n,q 同阶）

对于本题，直接对于暴力过程记忆化，若使用 umap，时间和空间复杂度均为 O(n\sqrt{n})，且访问记忆化数据结构（umap）时常数较大，不能稳定通过。

那么可以采用上文的随机化算法，以 p 的概率记忆化，空间复杂度降低为 O(np\sqrt{n})，每次向上暴力跳的次数期望增加 O(\dfrac{1}{p^2})，总的时间复杂度为 O(n\sqrt{n}+\dfrac{n}{p^2})，但访问 umap 的次数降低为 O(np\sqrt{n}+\dfrac{n}{p})，显著减小了常数，取 p=n^{-\frac{1}{6}},n^{-\frac{1}{4}} 等均有不错表现。

老虎油