Detailed mathematical approach

Problem Summary

Let \(f(n,m)\) denote the number of constrained permutations of sizes \(0,1,\dots,n\) whose inversion count is at most \(m\). The task in Problem 631 is to evaluate

$f(10^{18},40)\pmod{10^9+7}.$

A direct enumeration is hopeless: the length bound is astronomically large, and even the unrestricted number of permutations grows far too quickly. The successful approach is to build permutations incrementally, keep only the structural data that still affects future insertions, and use the fact that the process stabilizes once the length is slightly larger than the inversion budget.

Mathematical Approach

The C++, Python, and Java implementations all use the same idea: grow a valid permutation by inserting the new maximum element and summarize every partial permutation by a compact DP state.

Step 1: Build by inserting the new maximum

Suppose a valid constrained permutation of length \(\ell-1\) has already been formed. To obtain length \(\ell\), insert the value \(\ell\). The implementations parameterize this insertion by the number \(i\) of new inversions created at that step, so

$0 \le i \le \ell-1.$

If the remaining inversion budget before insertion is \(r\), then after using contribution \(i\) it becomes

$r' = r-i.$

Therefore every legal transition must satisfy \(i \le r\), and the raw upper bound is always

$i \lt \min(r+1,\ell).$

This observation turns the inversion condition into a local update rule.

Step 2: Compress the history into two structural boundaries

When the new maximum is inserted, the relative order of all older entries stays unchanged. So any newly created forbidden configuration must involve the new maximum itself. That means the entire past can be compressed into two integers in addition to the remaining budget \(r\):

\(a\), the smallest future inversion contribution still allowed by the 132-type restriction;

\(b\), a switching threshold that separates the two structural cases induced by the 21-type restriction.

A partial permutation is therefore represented by the triple

$ (r,a,b). $

Two partial permutations with the same triple have the same legal future extensions, so there is no need to store the full permutation explicitly.

Step 3: Transition rule for one insertion

At length \(\ell\), a state \((r,a,b)\) may choose any

$a \le i \lt \min(r+1,\ell).$

The next state is determined by whether the chosen insertion contribution lies before or after the threshold \(b\):

$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$

$i \ge b \Longrightarrow (r-i,\ a,\ i).$

The first branch tightens the future lower bound and shifts the threshold one step to the right. The second branch preserves the current lower bound and replaces the threshold by the chosen contribution. These two cases are the full combinatorial engine of the solver.

Step 4: Count exact lengths and cumulative totals

Let \(S_\ell(m)\) be the number of valid constrained permutations of exact length \(\ell\) with inversion budget \(m\). After \(\ell\) insertion steps, the DP layer stores exactly these objects, partitioned by state. Since each legal transition creates exactly one valid permutation of the next length, the cumulative quantity required by the problem is

$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$

where the initial \(1\) is the empty permutation. The running total maintained by the implementations is precisely this cumulative count.

Step 5: Why the large-\(n\) regime becomes linear

The remaining budget always satisfies \(0 \le r \le m\), so \(i\) can never exceed \(m\). Once

$\ell \ge m+2,$

the length cap is irrelevant, because \(\min(r+1,\ell)=r+1\). From that point onward, the transition rules depend only on the finite state \((r,a,b)\), not on the actual value of \(\ell\). The exact-length counts therefore enter a stable regime in which each additional length contributes the same amount \(g\) modulo \(10^9+7\). Thus

$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$

The C++, Python, and Java implementations use this cutoff, and the C++ implementation also performs an explicit one-step check that the layer total has stabilized at the boundary.

Worked Example: the case \(m=0\)

If \(m=0\), then every insertion must use

$i=0.$

So each length has exactly one legal extension: the new maximum is inserted in the unique way that creates no new inversions. Therefore

$S_\ell(0)=1 \qquad (\ell \ge 1),$

and hence

$f(n,0)=1+n.$

In particular,

$f(2,0)=3,$

which matches the checkpoint used by the implementations. The same implementations also reproduce the additional checks \(f(4,5)=32\) and \(f(10,25)=294400\).

How the Code Works

The implementation fixes the modulus \(10^9+7\), the target budget \(m=40\), and the target length \(n=10^{18}\). It stores the DP over triples \((r,a,b)\) in flattened arrays, using one array for the current layer and one for the next. The initial layer contains only the empty permutation with full remaining budget and neutral structural boundaries.

For each length from \(1\) through \(\min(n,m+2)\), the implementation scans every reachable state, enumerates every admissible value of \(i\), adds the state count to the cumulative answer, and sends that count to the next state dictated by the two-branch transition rule. All arithmetic is reduced modulo \(10^9+7\).

If \(n \le m+2\), this explicit DP already yields the final answer. Otherwise the implementation sums the stabilized last layer to obtain \(g\), then appends the linear tail \((n-(m+2))g\) modulo \(10^9+7\). The C++ implementation additionally computes one more layer to confirm that the stabilized layer total is unchanged.

Complexity Analysis

The remaining-budget coordinate has \(m+1\) possibilities, and each structural boundary ranges over \(O(m)\) values after the process is truncated at length \(m+2\). So the DP uses \(O(m^3)\) states and \(O(m^3)\) memory. For one fixed layer, each state can try up to \(O(m)\) insertion contributions, giving a straightforward worst-case bound of \(O(m^4)\) work per layer. Since only \(O(m)\) layers are processed explicitly, the overall worst-case time bound is \(O(m^5)\). With \(m=40\), this is easily practical, and after stabilization the dependence on the huge parameter \(n\) drops to \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=631
2. Inversions in permutations: Wikipedia - Inversion (discrete mathematics)
3. Permutation patterns: Wikipedia - Permutation pattern
4. Dynamic programming: Wikipedia - Dynamic programming
5. Finite-state machines: Wikipedia - Finite-state machine