El Toll Caves
Contest: Codeforces Round 438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 3300
Tags: math

The prehistoric caves of El Toll are located in Moià (Barcelona). You have heard that there is a treasure hidden in one of n possible spots in the caves. You assume that each of the spots has probability 1 / n to contain a treasure.

You cannot get into the caves yourself, so you have constructed a robot that can search the caves for treasure. Each day you can instruct the robot to visit exactly k distinct spots in the caves. If none of these spots contain treasure, then the robot will obviously return with empty hands. However, the caves are dark, and the robot may miss the treasure even when visiting the right spot. Formally, if one of the visited spots does contain a treasure, the robot will obtain it with probability 1 / 2, otherwise it will return empty. Each time the robot searches the spot with the treasure, his success probability is independent of all previous tries (that is, the probability to miss the treasure after searching the right spot x times is 1 / 2x).

What is the expected number of days it will take to obtain the treasure if you choose optimal scheduling for the robot? Output the answer as a rational number modulo 109 + 7. Formally, let the answer be an irreducible fraction P / Q, then you have to output $$P \cdot Q^{-1} \bmod (10^9 + 7)$$. It is guaranteed that Q is not divisible by 109 + 7.

Input format:
The first line contains the number of test cases T (1 ≤ T ≤ 1000).

Each of the next T lines contains two integers n and k (1 ≤ k ≤ n ≤ 5·108).

Output format:
For each test case output the answer in a separate line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first case the robot will repeatedly search in the only spot. The expected number of days in this case is 2. Note that in spite of the fact that we know the treasure spot from the start, the robot still has to search there until he succesfully recovers the treasure.

In the second case the answer can be shown to be equal to 7 / 2 if we search the two spots alternatively. In the third case the answer is 25 / 9.

Example input:
3
1 1
2 1
3 2

Example output:
2
500000007
777777786

Editorial:
Let ai, j be the number of times we have checked spot j after i days. Assuming that the spot j contains the treasure, we can see that the expected number of days to find the treasure is $$\sum_{i=0}^{\infty} 2^{-a_{i,j}}$$. Hence the unconditional expectation of the answer is $$\frac{1}{n} \sum_{i=0}^{\infty} \sum_{j=0}^{n-1} 2^{-a_{i,j}}$$. This formula implies that the optimal strategy is to keep the visiting frequencies for all spots as close as possible, since the sum $$\sum_{j=0}^{n-1} 2^{-a_{i,j}}$$ is minimized under $$\sum_{j=0}^{n-1} a_{i,j} = ik$$ when ai, j is the smoothest partition of ik. One implementation of this strategy is to visit spots $${ i k } \operatorname { m o d } n, ( i k + 1 ) \operatorname { m o d } n, \ldots, ( i k + k - 1 ) \operatorname { m o d } n$$ on day i. Note further that this strategy always visits spots in batches of size $$\gcd(n,k)$$, hence we can divide both n and k by their GCD.
Let us now consider an example of n = 8, k = 3. Let Ei be the expected number of days to find the treasure in spot i according to the optimal strategy above. We can see that E3 = E0 + 1, E4 = E1 + 1, ..., E7 = E4 + 1, because a cell j + k is visited on day i iff the cell j was visited on day i - 1. We also have E0 = E5 / 2 + 1 for the same reason except for that the cell 0 was visited on the first day. This argument allows to express, say, E0 as a linear expression of itself, and find the answer in O(n) time. Another approach is to substitute the expressions until we cross the end of the sequence once: E0 = E3 - 1 = E6 - 2 = 2E1 - 4, also E1 = 2E2 - 4, but E2 = E5 - 1 = 2E0 - 3. We have obtained a similar set of linear relations of three spots with difference 2. To reduce to n = 3, k = 2 let us group Ej by $$j \bmod k$$: E0 + E3 + E6 = 3E0 + 3, E1 + E4 + E7 = 3E1 + 3, E2 + E5 = 2E2 + 1. We can see that the total contribution of all Ej for $$j \equiv x \pmod{k}$$ is a linear function in Ex, with coefficients depending on whether $$x \leq n \bmod k$$. The main idea is that we continue this process with a different set of linear equations, effectively obtaining Euclid's algorithm that stores some additional data.
Let us now describe the general solution. Assume that we have a set of variables X0, ..., Xn - 1 satisfying Xi + k = A(Xi) for i + k < n, and Xi + k - n = B(Xi) for i + k ≥ n. Assume further that the answer $$E = \sum_{j=0}^{k-1} S_1(X_j) + \sum_{j=k}^{n-1} S_2(X_j)$$. Let $$k^{\prime} = n \bmod k$$. For j < k', by applying relations A and B successively we obtain $$X_{j+k-k'} = B(A^{\left\lfloor n/k \right\rfloor}(X_j))$$, hence $$X_{j+k'-k} = A^{-\left\lfloor n/k \right\rfloor}(B^{-1}(X_j))$$ for j + k' ≥ k. Similarly, $$X_{j+k'} = A^{-\left\lfloor n/k-1 \right\rfloor} (B^{-1}(X_j))$$ for j + k' < k. Also, $$E = \sum_{j=0}^{k'-1} S_1'(X_j) + \sum_{j=k'}^{k-1} S_2'(X_j)$$, where $$S_1' = S_1 + \sum_{t=1}^{\left\lfloor n/k \right\rfloor} S_2(A^t)$$, $${ S } _ { 2 } ^ { \prime } = { S } _ { 1 } + \sum _ { t = 1 } ^ { \left[ n / k - 1 \right] } { S } _ { 2 } ( A ^ { t } )$$. It follows that the transformation n → k, k → k', $$A \to A^{-\left\lfloor n/k-1 \right\rfloor}(B^{-1}(X_j))$$, $$B \rightarrow A^{-\left[\frac{n}{k}\right]}(B^{-1}(X_{j}))$$, S1 → S'1, S2 → S'2 produces the same answer E.
In the end of this process we have n = 1, k = 0, hence we have a linear equation X0 = A(X0). After finding X0, the answer is S2(X0). The number of reductions of the above type is $${\mathcal {O}}(\log n)$$, with each transformation possible to do in $$O(\log(n/k))$$ time, (S1 → S'1 and S2 → S'2 require fast matrix exponentation). The total number of operations is $${\mathcal {O}}(\log n)$$ per test.