Detailed mathematical approach

Problem Summary

For lengths \(N=2^m\), the problem asks for the 1-based lexicographic rank of the special unpredictable permutation of \(\{1,\dots,N\}\), reduced modulo \(10^9+7\). A brute-force comparison against all \(N!\) permutations is impossible once \(m\) is large, so the solution follows the recursive structure of the permutation itself and carries its Lehmer code along the same recursion.

Mathematical Approach

Write the target permutation as

$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$

using zero-based positions. Let \(L_N(i)\) be the Lehmer digit at position \(i\), meaning the number of later entries smaller than \(P_N(i)\). Then the 1-based lexicographic rank is

$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$

The central task is therefore to update \(P_N\) and \(L_N\) together when the size doubles.

Step 1: Seed permutation and Lehmer code

The recursive construction starts from the first nontrivial power of two, namely \(N=4\):

$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$

The smaller cases \(N=2\) and \(N=4\) have direct known ranks, so the implementations can begin from this seed. Two boundary facts are already visible and remain true after every doubling step:

$P_N(0)=1,\qquad P_N(N-1)=N.$

These identities make the bridge positions in the next stage especially simple.

Step 2: Doubling rule for the permutation

Assume \(P_N\) is known. The permutation of size \(2N\) is built by sending most old values to odd or even numbers:

$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$

$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$

$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$

So the old prefix becomes odd values, most of the new suffix becomes even values, and two bridge positions connect the two blocks. Because \(P_N(0)=1\) and \(P_N(N-1)=N\), the same boundary pattern propagates:

$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$

Step 3: Lehmer digits for the old prefix

Take a position \(0\le i\le N-2\). Its new value is \(2P_N(i)-1\), which is odd. Among later odd values, the relative order is exactly the same as in the old permutation, so the old inversion count \(L_N(i)\) is still present.

There is one extra source of smaller entries: all even numbers

$2,4,\dots,2P_N(i)-2$

are smaller than \(2P_N(i)-1\), and after doubling they all lie to the right of position \(i\). The number of such even values is \(P_N(i)-1\). Therefore

$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$

This is the key identity that lets the rank information grow without recomputing inversion counts from scratch.

Step 4: Lehmer digits for the bridge and suffix

The bridge position \(N-1\) contains \(2P_N(0)=2\). Since the value \(1\) is fixed at the far left, there is no smaller value anywhere to the right, hence

$L_{2N}(N-1)=0.$

The next bridge position \(N\) contains \(2P_N(N-1)-1=2N-1\). To its right there are \(N-1\) even values, and only \(2N\) is larger, so exactly \(N-2\) of them are smaller:

$L_{2N}(N)=N-2.$

For the remaining suffix positions \(N+j\) with \(1\le j\le N-1\), everything to the right is also even, and multiplying values by \(2\) preserves order. So those Lehmer digits are copied unchanged:

$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$

Step 5: Worked example from \(4\) to \(8\)

Starting from

$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0],$

the doubling rule gives

$P_8=[1,5,3,2,7,6,4,8].$

Using the formulas above, the Lehmer digits become

$L_8=[0,3,1,0,2,1,0,0].$

Now evaluate the factorial expansion:

$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$

This matches the checkpoint used by the implementations and confirms that the recursive Lehmer update is correct.

Step 6: Final quantity for the problem size

Repeat the doubling step until \(N=2^m\). At that point the target permutation and its entire Lehmer code are already known, so the required answer is simply

$R_{2^m}\bmod (10^9+7).$

No search over permutations is required. The recursion itself contains all of the combinatorial structure needed for the final rank.

How the Code Works

The C++, Python, and Java implementations follow the same recipe. They handle the tiny powers of two directly, initialize the seed permutation and seed Lehmer digits for length \(4\), and then double the arrays until the requested size is reached. During each doubling step, the new even suffix is written first, the two bridge entries are inserted next, and the old prefix is updated in place at the end. The right-to-left write order is important because the old values are still needed while the new stage is being assembled.

Once the target length has been built, the implementation computes the lexicographic rank from the Lehmer code. It scans from right to left, maintaining the current factorial weight modulo \(10^9+7\), so it never has to store large factorials explicitly. The same pattern appears in all three language versions, differing only in syntax.

Complexity Analysis

Let \(N=2^m\). The recursive construction touches each array entry only a constant number of times across the sequence of sizes \(4,8,16,\dots,N\). The total work is therefore

$4+8+16+\cdots+N=O(N).$

The final rank accumulation from the Lehmer code is another linear pass. Hence the complete running time is \(O(N)=O(2^m)\), and the memory usage is \(O(N)\) because the permutation and Lehmer arrays both have length \(N\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=720
2. Lehmer code: Wikipedia - Lehmer code
3. Factorial number system: Wikipedia - Factorial number system
4. Lexicographical order: Wikipedia - Lexicographical order
5. Permutation: Wikipedia - Permutation