Solution. CF441E Valera and Number

$+1$ 操作的贡献不好计算，但是由于操作数很少，我们完全可以记录下最低 $\log k$ 位的状态，这样总状态数是 $O(k^3)$ 的，转移 $O(1)$，故总复杂度 $O(k^3)$。

还有一些更聪明的做法。由于 $+1$ 贡献难算，我们可以预支这些 $+1$ 操作，设 $f_{i,j}$ 表示 $i$ 次操作所得到的数 $+j$ 末尾 0 个数的期望（预支 $j$ 次 $+1$ 操作），这样可以做到 $O(k^2)$。

另一种思路是，$+1$ 导致的进位只会影响到前面的位，而对于（未来产生的）后面的位没有影响，所以考虑时光倒流，倒序 dp，一次 $\times 2$ 操作可以视作是锁定了最后一位的值，所以设 $f_{i,j,k}$ 表示 $i$ 次操作，后 $k$ 位被锁定（当然，我们要求后 $k$ 位全是 $0$，否则贡献应当直接算入答案），对前面的数 $+j$ 的概率，而 $k$ 这一维的作用仅在于辅助最后计算答案，所以可以用期望的线性性在每次 $\times 2$ 时直接将贡献算入答案，这样可以省掉一维，复杂度 $O(k^2)$。

其实两种 $O(k^2)$ 做法的本质是相同的，只是顺序不同以及考虑方式有些区别。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。