Detailed mathematical approach

Problem Summary

There are \(n\) players arranged in their initial rank order. Each day a match is played between adjacent ranks. If the higher-ranked player wins, the order and all overtake counts are unchanged. If the lower-ranked player wins, the two adjacent players swap, and the winner's overtake count increases by \(1\). After exactly \(k\) days the final order must again be the initial order, and \(F(n,k)\) counts how many overtake-count vectors can occur.

The important observation is that the non-overtake matches are pure idle steps. They can be inserted anywhere without changing either the order or the count vector. Therefore only the sequence of actual overtakes matters, and because every overtake is an adjacent transposition, returning to the identity permutation requires an even number of overtakes. The implementation writes \(E=\lfloor k/2\rfloor\) and counts all feasible count vectors with at most \(E\) paired crossings.

Mathematical Approach

From overtakes to pair crossings

Consider two fixed players \(i\) and \(j\), with \(i\) initially above \(j\). Their relative order can change only when they are adjacent and one overtakes the other. Since the final order is again the initial order, this pair must cross an even number of times. If it crosses \(2m_{ij}\) times, then \(j\) overtakes \(i\) exactly \(m_{ij}\) times while moving upward, and \(i\) overtakes \(j\) exactly \(m_{ij}\) times while moving back downward.

Thus every closed overtake history determines a loopless multigraph on the \(n\) players: put \(m_{ij}\) edges between players \(i\) and \(j\). The overtake count of player \(i\) is exactly the degree of vertex \(i\). If the total number of edges is \(e\), then the total number of actual overtakes is \(2e\), so a \(k\)-day schedule can realize any vector that is realizable with \(e\le E=\lfloor k/2\rfloor\).

Why positive players form contiguous runs

Adjacent swaps impose a one-dimensional restriction. If two players interact, then every player initially between them must at some point lie inside the same moving block. Therefore the non-zero entries of a feasible degree vector decompose into disjoint contiguous runs. A run of length \(1\) is impossible: a single isolated player cannot overtake anyone and return while all neighbours have zero count.

So a feasible vector is built from zero gaps and positive runs of lengths \(\ell\ge 2\). Each run represents one connected component of the crossing multigraph on a consecutive block of players. This is exactly the decomposition used by the dynamic program: append a zero, or append a positive run of length \(\ell\) after a zero-separated prefix.

Counting one positive run

For one run of length \(\ell\) using \(e\) graph edges, we need positive degrees

$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$

A loopless multigraph with \(e\) edges cannot have one vertex degree greater than \(e\), because every incident edge contributes one degree to that vertex and one degree elsewhere. Conversely, for positive integer sequences the condition

$\max_i a_i\le e$

is sufficient for a loopless multigraph realization on the run. Hence the number of possible degree sequences for a run is the number of positive compositions of \(2e\) into \(\ell\) parts, excluding those with one part greater than \(e\). Since at most one part can exceed \(e\), this gives

$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}.$

This is the formula implemented in run_count_table. The first binomial counts all positive compositions; the second term subtracts the cases where a specified component is too large.

Dynamic programming over prefixes

Let \(T(i,e)\) be the number of feasible vectors on the first \(i\) players whose crossing multigraph has exactly \(e\) edges. The code also keeps \(Z(i,e)\), the number of such vectors whose last entry is zero. This makes it easy to enforce that two positive runs are separated by at least one zero.

The transition is:

$Z(i,e)=T(i-1,e),$

because appending a zero to a length \(i-1\) vector gives a length \(i\) vector ending in zero. Then a final positive run of length \(\ell\ge 2\) can be appended after a zero-ending prefix:

$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$

The base case is \(T(0,0)=Z(0,0)=1\). After all \(n\) players have been processed, the desired count for a day limit \(k\) is cumulative:

$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$

Polynomial tail for the large target

The direct DP is small in \(n\), but \(E=4567891/2\) is too large to iterate up to. The run formula \(R(\ell,e)\) is a polynomial in \(e\) of degree \(\ell-1\), and the prefix recurrence is made from additions and convolutions of these polynomial pieces. For fixed \(n\), the cumulative function

$A_n(E)=\sum_{e=0}^{E}T(n,e)$

agrees, from \(E\ge n-1\) onward, with a polynomial of degree \(n\). The program computes \(A_n(E)\) only for the \(n+1\) consecutive values

$E=n-1,\;n,\;\ldots,\;2n-1,$

takes finite differences, and evaluates the Newton forward expansion

$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$

The target modulus is not prime, so the large binomial values are not computed by modular inverses. Instead, the implementation cancels the small denominator factors against the numerator factors over the integers, then multiplies the remaining factors modulo \(1234567891\).

How the Code Works

The C++, Python, and Java programs first build binomial tables for the small range needed by the DP. They compute all \(R(\ell,e)\), run the prefix dynamic program up to \(E=2n-1\) for the target \(n=123\), and form the cumulative values. Then they take finite differences beginning at \(E=n-1\) and evaluate the degree-\(n\) polynomial at \(E=\lfloor4567891/2\rfloor\).

The validation block is deliberately stronger than just checking the two examples. For \(2\le n\le5\), it compares the DP against a brute-force search of adjacent-swap states for small \(E\). It also checks \(F(3,4)=8\), \(F(12,34)=2457178250\), and verifies the polynomial continuation against directly computed values for several small \(n\).

Complexity Analysis

The DP only needs \(E_{\max}=2n-1\) for the polynomial interpolation stage. The run table costs \(O(n^2E_{\max})\) arithmetic after binomial precomputation, and the prefix DP costs \(O(n^2E_{\max}^2)\) in this direct implementation. With \(n=123\) and \(E_{\max}=245\), this is practical.

The final large value of \(k\) affects only \(n+1\) modular binomial evaluations of order at most \(n\). The algorithm never iterates through millions of days and never enumerates permutations for the target instance.

References

1. Problem page: Project Euler 996
2. Adjacent transposition: Wikipedia - Adjacent transposition
3. Degree sequence: Wikipedia - Degree in graph theory
4. Finite difference: Wikipedia - Finite difference
5. Dynamic programming: Wikipedia - Dynamic programming