Detailed mathematical approach

Problem Summary

Start from the identity permutation

$A^{(0)}=(0,1,2,\dots,n-1).$

Let the reversal endpoints be

$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$

and for each step \(j=0,1,\dots,k-1\), reverse the closed interval

$\left[\min(a_j,b_j),\max(a_j,b_j)\right],$

then update

$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$

The target is the weighted sum

$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$

The challenge is that \(n\) is enormous, so the final permutation cannot be built element by element.

Mathematical Approach

The implementation succeeds by tracking only the large monotone blocks created by the reversals, not the individual entries. Those blocks always remain simple arithmetic progressions with common difference \(+1\) or \(-1\).

Step 1: The reversal intervals can be generated online

The endpoints satisfy a Fibonacci-like recurrence modulo \(n\):

$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$

So the \(j\)-th reversal interval is known as soon as the \((j-1)\)-st step finishes. No table of all intervals is needed. Starting from \((1,1)\), the unreduced pairs are

$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $

which shows why consecutive Fibonacci numbers keep appearing behind the modular updates.

Step 2: The permutation stays piecewise arithmetic

Call a block a run if it has the form

$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$

Initially the whole permutation is one increasing run:

$B(0,1,n).$

Now reverse any subarray of a sequence that is already a concatenation of such runs. Only the two boundary runs may need to be cut. Every interior run is reversed as a whole block, and the reverse of

$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$

is again an arithmetic run, namely

$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x,$

which simply flips the sign of the step. Therefore the representation is invariant under every operation.

Step 3: Each reversal creates only constant new structure

Because only the two boundary runs can be split, a single reversal creates at most two new runs. If we start with one real run, then after \(k\) reversals the number of real runs is at most

$2k+1.$

This is the crucial compression: the permutation has length \(n\), but its description has size only \(O(k)\). A self-adjusting sequence tree can therefore manage the whole process efficiently.

Step 4: A whole run contributes by closed formulas

Suppose a run occupies positions \(p,p+1,\dots,p+\delta\), where \(\delta=\ell-1\). Define the standard sums

$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$

If the run is increasing, its values are \(x,x+1,\dots,x+\delta\), so

$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$

If the run is decreasing, its values are \(x,x-1,\dots,x-\delta\), so

$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$

Thus the final weighted sum can be accumulated run by run, without expanding the full permutation.

Step 5: Worked Example: \(R(5,4)=27\)

Take \(n=5\). The intervals come from the endpoint sequence

$ (1,1)\to(2,3)\to(0,3)\to(3,1). $

Now apply the reversals:

$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$

Therefore

$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all use the same fast idea: store the permutation as an ordered collection of maximal runs inside an implicit sequence tree. Each node records the first and last value of one run, a lazy reversal flag, and the total number of array positions represented by its subtree.

For every reversal, the implementation locates the two boundary positions by rank, splits a boundary run only if the cut lands inside it, isolates the middle interval, and marks that interval as reversed. Laziness is enough because reversing a concatenation of runs only requires two effects: reverse the order of the blocks and flip the direction inside each block.

After all \(k\) steps, an in-order traversal visits the runs from left to right. The current starting index of each run is known from subtree sizes, so the formulas from Step 4 give the contribution of the entire run modulo \(10^9\) in constant time.

The Python and Java versions delegate to the same optimized solver logic, so their mathematical behavior is identical to the C++ implementation.

Complexity Analysis

Let \(m_j\) be the number of runs after \(j\) reversals. Since each reversal adds at most two runs, \(m_j=O(j)\), hence \(m_k=O(k)\). Each operation performs only a constant number of positional searches, local splits, and subtree reversals in an implicit splay tree, giving amortized \(O(\log m_j)\) time per step. Summing over all \(k\) steps yields

$O(k\log k)$

time. The final traversal is linear in the number of runs, so it costs \(O(k)\). The memory usage is also

$O(k),$

because only the compressed run representation is stored.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=680
2. Splay tree: Wikipedia - Splay tree
3. Arithmetic progression: Wikipedia - Arithmetic progression
4. Fibonacci number: Wikipedia - Fibonacci number
5. Square pyramidal number and \(\sum u^2\): Wikipedia - Square pyramidal number