a[0]
a[1]
a[2]
a[3]
变换之后
A[0]=a[0]+a[1]+a[2]+a[3]
A[1]=a[0]-a[1]+a[2]-a[3]
A[2]=a[0]+a[1]-a[2]-a[3]
A[3]=a[0]-a[1]-a[2]+a[3]
A[i]中a[j]项,符号取决于 (i&j) 中1的个数,偶数个是+1,奇数个是-1
A[0]=a[0]+a[1]+a[2]+a[3]
A[1]=a[0]-a[1]+a[2]-a[3]
A[2]=a[0]+a[1]-a[2]-a[3]
A[3]=a[0]-a[1]-a[2]+a[3]
B[0]=b[0]+b[1]+b[2]+b[3]
B[1]=b[0]-b[1]+b[2]-b[3]
B[2]=b[0]+b[1]-b[2]-b[3]
B[3]=b[0]-b[1]-b[2]+b[3]
C[0] = A[0] * B[0]
C[1] = A[1] * B[1]
C[2] = A[2] * B[2]
C[3] = A[3] * B[3]
c[0] = (C[0] + C[1] + C[2] + C[3]) / 4
c[1] = (C[0] - C[1] + C[2] - C[3]) / 4
c[2] = (C[0] + C[1] - C[2] - C[3]) / 4
c[3] = (C[0] - C[1] - C[2] + C[3]) / 4
a[0]
a[1]
a[2]
a[3]
a[0]+a[1]
a[0]-a[1]
a[2]+a[3]
a[2]-a[3]
(a[0]+a[1])+(a[2]+a[3])
(a[0]-a[1])+(a[2]-a[3])
(a[0]+a[1])-(a[2]+a[3])
(a[0]-a[1])-(a[2]-a[3])
a
b
a
b+a
a+b
a-b
(a+b) + (a-b) = 2a
(a+b) - (a-b) = 2b
Minimum Maximum Identity
max(a, b) = a + b - min(a, b)
E[max(a, b)] = E[a] + E[b] - E[min(a, b)]
每过1秒
A发生概率是0.3
B发生概率是0.4
问发生A事件期望多少秒 1/0.3 = 10/3 不发生A的概率是0.7
问发生B事件期望多少秒 1/0.4 = 2.5 不发生B的概率是0.6
既不发生A,也不发生B的概率是 0.42
1秒中发生A或B的概率是0.58
问发生A和B事件中较早的一个期望多少秒 1/0.58
问发生A和B事件中较晚的一个期望多少秒 E[max(a, b)]
第0位变成1
第1位变成1
....
第n-1位变成1
我们希望求
E[max(第i位变成1的时间)]
=
枚举所有大小为1的子集
ans += E[变1的时间]
枚举所有大小为2的子集
ans -= E[变1的时间]
枚举所有大小为3的子集
ans += E[变1的时间]