algorithm - 表达的期望值

Question

如何在 P/Q 中找到表达式的期望值

Given:
N integers
2 Operators, 'Bitwise OR' & '+'

我们可以使用每个连续整数之间具有相等概率的两个运算符中的任何一个来形成表达式。

目前，我想到的解决方案是使用运算符生成所有可能的表达式，然后使用每个表达式的值我可以计算出它的期望值。

但是随着 N 的增长，这种方法失效了。有没有其他在时间复杂度方面更有效的替代方案？

Note: For this question: 'Bitwise OR' has higher priority than '+' operator.

There can be at max 10^5 integers.

例子:

Input
1 2 3

Output
19/4

不同的方式是:

1+2+3 = 6

1+2|3 = 4

1|2+3 = 6

1|2|3 = 3

所有这些方式的概率 = 1/4

因此预期值为 19/4

Answer 1

重要的观察是每个 + 将其左右部分拆分为可以独立处理的部分。

设数字数组为a[1…N]。定义 f(i) 为从 a[i…N] 获得的期望值。我们要查找的是f(1)。

请注意，[i…N] 中的第一个 + 符号将以 1/的概率出现在第 i 个元素之后2 和 i+1 概率 1/4 的元素等等。只需找到元素的按位或直到 + 并添加剩余部分的期望值。

这样我们就有了递归

f(i) = sum_{j = i to N-1} (or(a[i…j]) + f(j+1))/(2^(j-i+1) )
+ 或(a[i…N])/(2^(N-i))

这应该很容易高效地实现而不会出错。

对于示例数组[1,2,3]:

• f(3) = or(a[3…3]) = 3
• f(2) = (或(a[2…2])+f(3))/2 + 或(a[2…3])/2 = 5/2 + 3/2 = 4<
• f(1) = (or(a[1…1])+f(2))/2 + (or(a[1…2])+f(3))/4 + or(a[ 1…3])/4 = 5/2 + 6/4 + 3/4 = 19/4

如预期的那样，答案是 19/4。