Problem: Not So Random
这道题是2016年 Google 校招 APAC Test 的其中一题，也是2016年5月13日Google在北大宣讲会的 Mock Interview Part 的范例题：
There is a certain “random number generator” (RNG) which takes one nonnegative integer as input and generates another nonnegative integer as output. But you know that the RNG is really not very random at all! It uses a fixed number K, and always performs one of the following three operations:
- with probability A/100: return the bitwise AND of the input and K
- with probability B/100: return the bitwise OR of the input and K
- with probability C/100: return the bitwise XOR of the input and K (You may assume that the RNG is truly random in the way that it chooses the operation each time, based on the values of A, B, and C.)
You have N copies of this RNG, and you have arranged them in series such that output from one machine will be the input for the next machine in the series. If > you provide X as an input to the first machine, what will be the expected value of the output of the final machine in the series?
Input
The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which all the bitwise operations will be performed (on every machine), and 100 times the probabilities of the bitwise AND, OR, and XOR operations.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the expected value of the final output. y will be considered correct if it is within an absolute or relative error of 10^-9 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Limits
1 ≤ T ≤ 50.
0 ≤ A ≤ 100.
0 ≤ B ≤ 100.
0 ≤ C ≤ 100.
A+B+C = 100.
Small dataset
1 ≤ N ≤ 10.
0 ≤ X ≤ 10^4.
0 ≤ K ≤ 10^4.
Large dataset
1 ≤ N ≤ 10^5.
0 ≤ X ≤ 10^9.
0 ≤ K ≤ 10^9.
Sample
| Input | Output |
|---|---|
| 3 | |
| 1 5 5 10 50 40 | Case #1: 3.0000000000 |
| 2 5 5 10 50 40 | Case #2: 3.6000000000 |
| 10 15 21 70 20 10 | Case #3: 15.6850579098 |
In sample test case #1, the final output will be 5 if AND or OR happens and 0 if XOR happens. So the probability of getting 5 is (0.1 + 0.5) and the probability of getting 0 is 0.4. So the expected final output is 5 * 0.6 + 0 * 0.4 = 3.
In sample test case #2, the final output will be 5 with probability 0.72, and 0 otherwise.
位运算
首先理一下题意，把N个RNG串起来，求最后输出结果的期望值。这里很容易注意到，RNG内部的操作（与、或、异或）都是位运算，而一个二进制整数的期望可以用每一位比特的期望乘以所在位的权重计算得到，那么本题就可以简化为只考虑单个比特在系统内的流程来得到单个比特位的期望值。
单个RNG
只考虑一个bit的话，X和K的值组合只有4种，可以列出下面的操作结果表：
| A | B | C |
|---|---|---|
| 0 & 0 = 0 | 0 | 0 = 0 | 0 ^ 0 = 0 |
| 0 & 1 = 0 | 0 | 0 = 1 | 0 ^ 1 = 1 |
| 1 & 0 = 0 | 0 | 0 = 1 | 1 ^ 0 = 1 |
| 1 & 1 = 1 | 1 | 1 = 1 | 1 ^ 1 = 0 |
注意到这里虽然有A、B、C三种可能性，但是输入和输出都是0和1，是不是可以尝试一下用转移矩阵来做呢？
因为输入是X、输出是0或1，而K是相对固定的、每个RNG的K值都相同。因此，对照上面的结果表分别计算K=0和K=1时的转移矩阵：
k = 0:
[ 100 , 0 ]
[ A , B+C ]
k = 1:
[ A , B + C ]
[ C , A + B ]
（即k=1，输入为0时，输出A%为0、(B+C)%为1；输入为1时，输出C%为0，(A+B)%为1）
这样，我们就将RNG内部当作了一个黑箱，将内部的三种操作简化成了输入输出的转移矩阵。
多个RNG串联
有了单个RNG的转移矩阵，K值又不变，就可以分别计算K=0和K=1时多个RNG的串联结果了，将N-1个矩阵相乘即可。
转移矩阵的定义：
/**
* 使用double是因为题意要求输出结果精度达到10^-9
*/
private static class Matrix {
private double a, b, c, d;
public Matrix(double a, double b, double c, double d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
}
矩阵的乘法：
private static Matrix multiply(Matrix m1, Matrix m2) {
double a = (m1.a * m2.a + m1.b * m2.c) / 100;
double b = (m1.a * m2.b + m1.b * m2.d) / 100;
double c = (m1.c * m2.a + m1.d * m2.c) / 100;
double d = (m1.c * m2.b + m1.d * m2.d) / 100;
return new Matrix(a, b, c, d);
}
矩阵相乘：
Matrix bitZero = new Matrix(100, 0, A, B + C);
Matrix bitOne = new Matrix(A, B + C, C, A + B);
Matrix bitZeroAfterK = bitZero;
Matrix bitOneAfterK = bitOne;
for (int n = 1; n < N; n++) {
// Maybe some Fast-Matrix-Multiplication will do it faster.
bitZeroAfterK = multiply(bitZeroAfterK, bitZero);
bitOneAfterK = multiply(bitOneAfterK, bitOne);
}
这样，得到系统完整的转移矩阵后，通过判断每一位bit的X和K的值，带入矩阵求出结果每一位bit的概率和期望，加权相加即可得到最后结果：
double result = 0;
for (int i = 31; i >= 0; i--) {
result *= 2;
Matrix matrix = isLastZero(K, i) ? bitZeroAfterK : bitOneAfterK;
double chanceOfOne = (isLastZero(X, i) ? matrix.b : matrix.d) / 100;
result += chanceOfOne;
}
print(t, result);
完整的代码见我的Github：company/google/NotSoRandom.java
优化方案
考虑到本题的时间复杂度与X和K的大小无关，那么主要耗时的部分是这N-1个矩阵的乘法，是不是可以使用矩阵的快速乘法（例如Strassen算法）来进一步优化时间消耗，不过我怀疑这个算法对2x2的矩阵能有多大的优化空间，我这里偷懒就没再继续研究了-。-