CF2086E 题解

首先，容易发现 $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)$ 左右。