CF441E Valera and Number - Solution

· · 题解

先把原题的 p 除 100。

简单来说，x 开始，p 概率乘 2，1 - p 概率加 1，求期望末尾 0 个数。

最朴素想法是设 f_{i,\,v} 代表 i 次操作后 x 变为 v 的概率，当然这个状态数超级大，没啥讨论的必要。

- 加 $1$ 至多有两百次，那我直接维护后 $8$ 位即可！ 不过我们的 $x$ 毕竟是一个任意的数，它是完全有可能加一些 $1$ 就产生超过 $8$ 位的进位的。 那我们把 $8$ 位以上连续 $1$ 的个数也加入状态，毕竟显然超过 $8$ 位的进位至多只有一次。 不过这样就要把两个过程拆开来，毕竟这种情况我们默认产生了进位，并且后面没有 $+1$ 把进位产生的这坨 $0$ 顶掉。所以如果超八位进位后还有加 $1$，那么进位产生的这坨 $0$ 对最终末尾 $0$ 的个数当然产生不了影响，于是要设另一个 dp 来转移这种情况。 设 $f_{i,\,j,\,k}$ 代表前 $i$ 次操作使得八位以上末尾连续 $1$ 的个数是 $j$，且末尾八位是 $k$ 的概率。 $g_{i,\,j}$ 代表前 $i$ 次操作，末尾有 $j$ 个零的方案数，强制令 $j > 8$。 写起来会比较复杂，但总之我们容易获得一个 $\Theta(k^3)$ 的做法。 - 考虑时光倒流！ 不难发现我们是越靠后的操作产生的影响越大。比如我们在末尾进行了几次乘 $2$，那么继续往前的加 $1$ 肯定不会对最低位产生影响。 假设我们末尾进行了 $t$ 次乘 $2$，在这坨乘 $2$ 之前我们对 $x$ 产生了 $+w$ 的影响 首先如果 $w$ 是偶数，那么可以看成 $t + 1$ 次乘 $2$ 和前面 $+\frac{w}{2}$ 的的影响。 如果 $w$ 是奇数，显然我们的末尾 $0$ 个数直接就是 $t$ 了。 $f_{i,\,j,\,w}$ 代表进行了末尾 $i$ 次操作，并且结尾有 $j$ 个乘 $2$，在这 $j$ 个乘 $2$ 之前有 $+w$ 的影响。 转移上面直接得出来了，讨论 $w$ 的奇偶性即可。 至于 $w$ 的范围，只有加 $1$ 是能扩展 $w$ 的范围的，至多有 $k$ 次加 $1$。 复杂度 $\Theta(k^3)$。 - 费用提前计算！ 上面这个东西其实可以做得更好，我们为什么要把末尾乘 $2$ 的数量 $j$ 纳入状态，因为我们要在最后乘上一个 $p$ 的 $j$ 次方得到这个状态的概率，但是我们知道期望具有线性性，于是可以把 $j$ 这一维直接去了，直接乘 $p$ 贡献给答案。 大概是个这样的东西： ``` if (j mod 2 == 0) f[i + 1][j / 2] += f[i][j] * p, ans += f[i][j] * p; f[i + 1][j + 1] += f[i][j] * (1 - p); ``` 时间复杂度 $\Theta(k^2)$。