Project Euler 323

题目

Bitwise-OR operations on random integers

Let $y_0, y_1, y_2,\dots$ be a sequence of random unsigned $32$ bit integers (i.e. $0 \le y_i < 2^{32}$, every value equally likely).
For the sequence $x_i$ the following recursion is given:

• $x_0 = 0$ and
• $xi = x{i-1} \mathbf{|} y_{i-1}$, for $i > 0$. ( $\mathbf{|}$ is the bitwise-OR operator)

It can be seen that eventually there will be an index $N$ such that
$x_i = 2^{32} -1$ (a bit-pattern of all ones) for all $i \ge N$.

Find the expected value of $N$. Give your answer rounded to $10$ digits after the decimal point.

解决方案

令$N=32$。

一个观察点：当前状态其实和$y_i$的值没有关系，只和$y_i$的二进制$1$的个数有关系。

因此，我们只考虑$y_i$中还有多少个$0$还没有被翻成$1$。

令$f(i)(i\ge 0)$表示还有$i$个$0$还没被翻成$1$的情况下，全都完成翻转的期望。

那么，状态$i$有$\dfrac{\binom{i}{0}}{2^i}$的概率转换成状态$i$，也就是说，一个比特都没翻转成功；有$\dfrac{\binom{i}{1}}{2^i}$的概率转换成状态$i-1$，也就是说只有一个比特翻转成功了……有$\dfrac{\binom{i}{i}}{2^i}$的概率转换成状态$0$，此时$i$个比特全部成功翻转。那么，我们可以写出如下的式子：

$$f(i)=\sum_{j=0}^i\left(\dfrac{\binom{i}{j}}{2^n}\cdot f(j)\right)+1$$

这是一个有后效性的动态规划方程，因为状态之间形成了循环的依赖（状态$i$依赖于自身）。不过，这种情况下消除后效性很简单。右边有一个项也是$f(i)$，只需要挪到左边消除就可以完成消除后效性，从而正确计算结果。

因此，可以正式写出状态转移方程：

$$f(i)= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &\dfrac{\sum_{j=0}^{i-1}\binom{i}{j}\cdot f(j)+2^i}{2^i-1} & & \text{else} \end{aligned}\right.$$

因此，最终结果为$f(N)$。

代码

from tools import get_pascals_triangle

N = 32
C = get_pascals_triangle(N)
f = [0]
for n in range(1, N + 1):
    f.append(2 ** n)
    for i in range(n):
        f[n] += C[n][i] * f[i]
    f[n] /= 2 ** n - 1
ans = f[N]
print("{:.10f}".format(ans))