CF2086E 题解

zhangbo1000 · 2025-04-28 17:45:16 · 题解

首先，容易发现 10^{18} 以内的 Zebra-like number 就 30 个，设从小到大第 i 个为 a_i，由定义易得 a_i=4a_{i-1}+1。

然后发现问题：用大的 a_i 总是不劣的，因为我们省掉了 4\times a_{i-1}，而“去掉”1 带来的影响无非就是拆掉一个 a_j 换成 4\times a_{j-1}。

所以“计算一个数的 zebra value”这个问题具有贪心性质。

考虑记忆化搜索，设 v_{i,j} 表示 i 以内 zebra value 为 j 的数的个数，那么设 a_x 为小于 i 的最大的 Zebra-like number，则 v_{i,j}=v_{i-a_x,j-1}+v_{a_x,j}，这个式子的含义是：[a_x,i] 以内的数的 zebra value 可以先贪心的除去一个最大值，变为 [0,i-a_x] 内的数，再加一，其余的数直接递归处理。a_x 不会小于 \frac{i}{4}，a_x-1={4a_{x-1}}，所以两次递归后 i 必然缩小最少 \frac{1}{4}，递归层数是 O(\log n) 的，理论上能卡到 O(r\log r) 直接 10^{20} TLE 飞，但实际上完全跑不满，再加上记忆化，实际快的飞起，卡满在 CF 评测机上大概 60\operatorname{ms}。

代码及评测记录。

关于复杂度

“跑不满”当然是一个很不严谨的说法，所以接下来让我们具体证一下。

首先，根据上面的贪心性质，易知一个数最多由 30\times 4=120 个 Zebra-like number 组成（实际上这个界也不满），更严谨的说，是 O(\log V) 个（其中 V 为值域），因为这个界内最多 O(\log V) 个 Zebra-like number，一个数中每个不超过 4 次。

所以 k 的（有意义的）范围是 O(\log V) 的，具体多少就不算了。

对于 v_{a_x-1,j}，我们一旦算出了所有 v_{a_x-1,j}，这部分就 O(1) 了，所以我们每次实际上相当于只往一侧递归，x,j 的范围又是 O(\log V) 的，所以我们的总复杂度实际上控制在了 O(\log ^2V) 左右。