Oyler's Geometric Jumps

The solution uses heavy light strategy.

First we fix a size B. For elements x that have frequency k less than B, we use a $O(k^2)$solution. We define dp[i] = count of way to make it to i-th cell with number x (while avoiding cells with value x that are before). Then dp[i] = pre[pos[i]] - $\sum_{j < i}$dp[j] * pre[pos[i] - pos[j]]. Here pre[a] represents count of way to make it from 1 to a without any restrictions. we consider the final cell to have x too when solving for value x.

For elements x that have frequency k greater than B, we use a $O(n\log n)$ solution, we define dp[p] = count of way to make it to position p, skipping x’s. then dp[p] = dp[p-1] + dp[p-2] + dp[p-4] + … (those with x’s are zeroes).

Now the time taken is $O\left(nB + \frac{n^2\log n}{B} \right)$ optimal happens when $B \approx \sqrt{n \log n}$making the solution $O(n \sqrt{n \log n})$