Problem #150
Fun with Expectation
Consider an array of n numbers where each element can be any non negative x bit number ( 0 to 2^x - 1 ) with equal probability. Let F(n,x) be the expected value of the sum of bitwise xor of all possible subsequences of the array.
Eg. Consider the array {1,2,3} .
Sum of xor of all possible subsequences of this array = 1 + 2 + 3 + 1^2 + 1^3 + 2^3 + 1^2^3 = 1 + 2 + 3 + 2 + 1 + 3 + 0 = 12.
Note: ^ is the bitwise xor operation here.
F(2,2) = 4.5
Enter your answer as floor( F(29,30) + F(30,29) ) .