Как решить такую задачу на матожидание lightoj 1284

Тупое решение такое : матожидание линейна, поэтому для каждой клетки можно посчитать отдельно. Используя формулу Бернули , матожидание для одной клетки найдем. А ответ для задачи это сумма всех ячеек.код

UPD: ACCEPTED. Решил за O(X * Y * Z * log(k) * T) . Мне кажеться не должно было проходит из за double. Для одной клетки считаем матожидание с помощью возведение матрицу в степень.code

Задача : ~~~~~ You are given a 3D grid, which has dimensions X, Y and Z. Each of the X x Y x Z cells contains a light. Initially all lights are off. You will have K turns. In each of the K turns,

1. You select a cell A randomly from the grid,
2. You select a cell B randomly from the grid and
3. Toggle the states of all the bulbs bounded by cell A and cell B, i.e. make all the ON lights OFF and make all the OFF lights ON which are bounded by A and B. To be clear, consider cell A is (x1, y1, z1) and cell B is (x2, y2, z2). Then you have to toggle all the bulbs in grid cell (x, y, z) where min(x1, x2) ≤ x ≤ max(x1, x2), min(y1, y2) ≤ y ≤ max(y1, y2) and min(z1, z2) ≤ z ≤ max(z1, z2).

Your task is to find the expected number of lights to be ON after K turns. Input Input starts with an integer T (≤ 50), denoting the number of test cases. Each case starts with a line containing four integers X, Y, Z (1 ≤ X, Y, Z ≤ 100) and K (0 ≤ K ≤ 10000). ~~~~~