C&E 题解

建议在博客园中查看。

先从 Easy Version 看起。首先，根据期望的线性性，我们可以分别计算每个 操作之后的期望值。设 表示恰好操作 次的概率，易知 。设 表示整数 修改 次以后的值，设 表示经过 次操作以后 的期望值，则

容易在 时间内计算，我们接下来主要关注 。如果对每个 暴力计算，则时间复杂度为 ，无法接受。

如何优化？观察修改的式子，发现有一项是 ，这启示我们可以只关心 的较低位。具体来说，设 是满足 的最大整数（即 二进制下的最高位）， 表示 的较低 位的值，。可以发现：。感性理解，较高位不参与修改操作，可以在一开始就分离出来。所以只需要对 个值计算 数组，暴力模拟即可，时间复杂度 。代码

对于 Hard Version， 的时间复杂度也无法接受了。我们可以尝试推广先前的做法，即每次修改操作中都把高位分离出来，这样只用考虑低位，而不同的低位只有 个。考虑到 远小于 ，从这个角度出发或许能导出时间复杂度更低的做法。

具体而言，我们考虑对 进行 次修改得到的长度为 的整数序列（包含初始值），设修改 次以后的值为 。我们只保留 的低位，也就是说 。考虑 对 的贡献。显然， 是贡献的一部分。但如何考虑高位的贡献呢？对 进行一次修改，变成 ，但 只保留了低位，高位的贡献丢失了。关键的地方在于：高位的贡献会一直保留，无论之后修改多少次。设 ，即至少修改 次的概率，那么高位的贡献为 。

对 这种转移关系建图，则图中有 个点。由于每个点恰有一条出边，所以图是基环树森林。因此从任意一点出发走 步就能走到环上，我们可以考虑一次性计算环上的某个点的贡献。设从 出发走 步可以走到环，环的长度为 ，途径的路径为

（忽略了后续一直在环上走的过程。）

对于不在环上的点，直接套用公式计算贡献。对于环上的某个点 ，它同时是路径上的第 个点，所以它的贡献为

这里我们要处理 和 的求和。用数学方法导出封闭形式是不好做的，我们只能 递推。对于相同的环长，使用的和是相同的，无需重复求。而根据经典结论，由于环大小的和不超过 ，所以不同的环长只有 种，因此计算这些和的总时间复杂度为 。（题解说环长一定是 的非负整数次幂，根据这个结论时间复杂度为 ，但没有给出证明。）

综上所述，我们在 的时间内解决了问题。代码