Subtask 1

Let's solve the problem ~N~ times, once for each starting room.

Define ~dp[i][j][k]~ as the probability of Josh arriving at the ~j~-th room with a dizziness of ~k~, after traversing ~i~ hallways. Then, the answer is ~\sum_{j=1}^N \sum_{k=0}^{63} dp[L][j][k] \times k~.

We can easily calculate the dp values if we compute them in increasing order of the number of hallways traversed. After calculating ~dp[i][j][k]~, for all ~1 \le x \le N, j \ne x~, we will increment ~dp[i+1][x][k \mathbin| d_{j, x}]~ by ~\frac{dp[i][j][k]}{N-1}~. Here, ~|~ denotes the bitwise or operator.

Time complexity: ~\mathcal{O}(N^3 \times \max(d_{i, j}) \times L)~

Subtask 2

Observe that the bitwise or operation is independent for each bit. If we define ~E(x)~ as the expected final dizziness starting from room ~x~, and we define ~P(x, b)~ as the probability of the ~b~-th bit being set in the final dizziness starting from room ~x~, then by the linearity of expectation, we have ~E(x) = \sum_{b=0}^{29} P(x, b) \times 2^b~. We will now focus on computing the probabilities for each bit independently, and then combine our computations at the end using this formula.

Let us only consider the ~b~-th bit.

At any point in time, Josh's state can be represented by his current room, and whether his current dizziness has the ~b~-th set. This gives us ~2N~ states, which we can label from ~1~ to ~2N~. If Josh is in the ~x~-th room with the ~b~-th bit set, let us label it with the ~(2x-1)~-th state. If Josh is in the ~x~-th room with the ~b~-th bit not set, let us label it with the ~(2x)~-th state.

Define ~Q(x, y, z)~ as the probability of being in the ~y~-th state after traversing ~z~ hallways, starting from the ~x~-th state.

Let us define matrix ~A~ such that ~A_{i, j}~ is ~\frac{1}{N-1}~ if it is possible to move from the ~i~-th state to the ~j~-state by traversing exactly one hallway, and ~0~ otherwise. Then, we can see that:

$$\displaystyle \begin{bmatrix} Q(1, 1, z+1) & Q(1, 2, z+1) & \dots & Q(1, 2N-1, z+1) & Q(1, 2N, z+1) \\ Q(2, 1, z+1) & Q(2, 2, z+1) & \dots & Q(2, 2N-1, z+1) & Q(2, 2N, z+1) \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ Q(2N-1, 1, z+1) & Q(2N-1, 2, z+1) & \dots & Q(2N-1, 2N-1, z+1) & Q(2N-1, 2N, z+1) \\ Q(2N, 1, z+1) & Q(2N, 2, z+1) & \dots & Q(2N, 2N-1, z+1) & Q(2N, 2N, z+1) \end{bmatrix} = \begin{bmatrix} Q(1, 1, z) & Q(1, 2, z) & \dots & Q(1, 2N-1, z) & Q(1, 2N, z) \\ Q(2, 1, z) & Q(2, 2, z) & \dots & Q(2, 2N-1, z) & Q(2, 2N, z) \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ Q(2N-1, 1, z) & Q(2N-1, 2, z) & \dots & Q(2N-1, 2N-1, z) & Q(2N-1, 2N, z) \\ Q(2N, 1, z) & Q(2N, 2, z) & \dots & Q(2N, 2N-1, z) & Q(2N, 2N, z) \end{bmatrix} A$$

Hence, we have:

$$\displaystyle \begin{bmatrix} Q(1, 1, z) & Q(1, 2, z) & \dots & Q(1, 2N-1, z) & Q(1, 2N, z) \\ Q(2, 1, z) & Q(2, 2, z) & \dots & Q(2, 2N-1, z) & Q(2, 2N, z) \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ Q(2N-1, 1, z) & Q(2N-1, 2, z) & \dots & Q(2N-1, 2N-1, z) & Q(2N-1, 2N, z) \\ Q(2N, 1, z) & Q(2N, 2, z) & \dots & Q(2N, 2N-1, z) & Q(2N, 2N, z) \end{bmatrix} = \begin{bmatrix} Q(1, 1, 0) & Q(1, 2, 0) & \dots & Q(1, 2N-1, 0) & Q(1, 2N, 0) \\ Q(2, 1, 0) & Q(2, 2, 0) & \dots & Q(2, 2N-1, 0) & Q(2, 2N, 0) \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ Q(2N-1, 1, 0) & Q(2N-1, 2, 0) & \dots & Q(2N-1, 2N-1, 0) & Q(2N-1, 2N, 0) \\ Q(2N, 1, 0) & Q(2N, 2, 0) & \dots & Q(2N, 2N-1, 0) & Q(2N, 2N, 0) \end{bmatrix} A^z$$

Recall that ~Q(i, i, 0) = 1~ and ~Q(i, j, 0) = 0~ for ~i \ne j~. This means that the matrix to the left on the right hand side is actually just the identity matrix, so we can ignore it. Therefore, we can compute:

$$\displaystyle \begin{bmatrix} Q(1, 1, z) & Q(1, 2, z) & \dots & Q(1, 2N-1, z) & Q(1, 2N, z) \\ Q(2, 1, z) & Q(2, 2, z) & \dots & Q(2, 2N-1, z) & Q(2, 2N, z) \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ Q(2N-1, 1, z) & Q(2N-1, 2, z) & \dots & Q(2N-1, 2N-1, z) & Q(2N-1, 2N, z) \\ Q(2N, 1, z) & Q(2N, 2, z) & \dots & Q(2N, 2N-1, z) & Q(2N, 2N, z) \end{bmatrix} = A^z$$

We can compute this quickly using binary exponentiation.

Then, we have ~P(x, b) = \sum_{i=1}^N Q(2x, 2i-1, L)~, so we can also compute ~P(x, b)~ quickly for all ~x~. After computing our matrix exponentiation for each bit ~b~, we can combine our results to determine the final answer.

Time complexity: ~\mathcal{O}(N^3 \times \log(\max(d_{i, j})) \times \log L)~ (with a bad constant factor)

Subtask 3

Observe that for any bit ~b~, once it is set, the final dizziness must always have bit ~b~ set.

Therefore, we can reduce the number of states from ~2N~ to ~N+1~; we can have ~N~ states representing that Josh is in a particular room with the current bit unset, and another state representing that the current bit is already set.

We can generate a similar matrix and transitions as to before. The exact details are left as an exercise to the reader. As we essentially halve the number of rows and columns in our matrices, the constant factor improves by a factor of about ~8~.

Time complexity: ~\mathcal{O}(N^3 \times \log(\max(d_{i, j})) \times \log L)~ (with a good constant factor)