C&E 题解 建议在博客园中查看。 先从 Easy Version 看起。首先，根据期望的线性性，我们可以分别计算每个  操作之后的期望值。设  表示恰好操作  次的概率，易知 。设  表示整数  修改  次以后的值，设  表示经过  次操作以后  的期望值，则   容易在  时间内计算，我们接下来主要关注 。如果对每个  暴力计算，则时间复杂度为 ，无法接受。 如何优化？观察修改的式子，发现有一项是 ，这启示我们可以只关心  的较低位。具体来说，设  是满足  的最大整数（即  二进制下的最高位）， 表示  的较低  位的值，。可以发现：。感性理解，较高位不参与修改操作，可以在一开始...