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.
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\).
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.
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.
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).$$
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\).
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\).
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.
Es gibt \(n\) Spieler in ihrer ursprünglichen Rangfolge. Jeden Tag spielen zwei benachbarte Ränge gegeneinander. Gewinnt der höher platzierte Spieler, bleiben Reihenfolge und Überholungszähler unverändert. Gewinnt der niedriger platzierte Spieler, tauschen die beiden ihre Plätze, und der Sieger erhält eine zusätzliche Überholung. Nach genau \(k\) Tagen muss die Reihenfolge wieder die Anfangsreihenfolge sein; \(F(n,k)\) zählt die möglichen Vektoren der Überholungszahlen.
Die wichtige Beobachtung ist, dass Spiele ohne Überholung reine Leerlaufschritte sind. Man kann sie beliebig einfügen, ohne Reihenfolge oder Zählvektor zu ändern. Deshalb zählt nur die Folge der tatsächlichen Überholungen. Da jede Überholung eine benachbarte Transposition ist, braucht die Rückkehr zur Identität eine gerade Anzahl solcher Transpositionen. Die Implementierung setzt \(E=\lfloor k/2\rfloor\) und zählt alle möglichen Vektoren mit höchstens \(E\) Paar-Kreuzungen.
Betrachte zwei feste Spieler \(i\) und \(j\), wobei \(i\) anfangs über \(j\) steht. Ihre relative Reihenfolge ändert sich nur, wenn sie benachbart sind und einer den anderen überholt. Da die Endreihenfolge wieder die Anfangsreihenfolge ist, muss dieses Paar eine gerade Anzahl von Malen kreuzen. Kreuzen sie \(2m_{ij}\) Mal, dann überholt \(j\) den Spieler \(i\) genau \(m_{ij}\) Mal aufwärts, und \(i\) überholt \(j\) genau \(m_{ij}\) Mal auf dem Rückweg.
Jede geschlossene Überholungsfolge bestimmt daher einen schleifenlosen Multigraphen auf den \(n\) Spielern: Zwischen \(i\) und \(j\) liegen \(m_{ij}\) Kanten. Die Überholungszahl eines Spielers ist genau sein Grad in diesem Multigraphen. Hat der Multigraph \(e\) Kanten, dann gibt es \(2e\) tatsächliche Überholungen; ein Zeitplan mit \(k\) Tagen kann also jeden Vektor mit \(e\le E=\lfloor k/2\rfloor\) realisieren.
Benachbarte Vertauschungen erzwingen eine eindimensionale Einschränkung. Wenn zwei Spieler miteinander interagieren, muss jeder Spieler, der anfangs zwischen ihnen stand, zeitweise im selben bewegten Block liegen. Daher zerfallen die positiven Einträge eines zulässigen Gradvektors in disjunkte zusammenhängende Läufe. Ein Lauf der Länge \(1\) ist unmöglich: Ein einzelner isolierter Spieler kann niemanden überholen und zurückkehren, während beide Nachbarn Zähler \(0\) haben.
Ein zulässiger Vektor entsteht also aus Nulllücken und positiven Läufen der Länge \(\ell\ge 2\). Jeder Lauf ist eine Zusammenhangskomponente des Kreuzungsmultigraphen auf einem konsekutiven Spielerblock. Genau diese Zerlegung benutzt die DP: entweder wird eine Null angehängt, oder nach einem durch Null getrennten Präfix wird ein positiver Lauf angehängt.
Für einen Lauf der Länge \(\ell\) mit \(e\) Kanten brauchen wir positive Grade
$$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$$
In einem schleifenlosen Multigraphen mit \(e\) Kanten kann kein Grad größer als \(e\) sein, denn jede inzidente Kante liefert einen Gradbeitrag an diesen Knoten und einen weiteren Beitrag an einen anderen Knoten. Umgekehrt ist für positive ganzzahlige Folgen die Bedingung
$$\max_i a_i\le e$$
hinreichend für eine Realisierung als schleifenloser Multigraph auf dem Lauf. Also zählt man positive Kompositionen von \(2e\) in \(\ell\) Teile und entfernt die Fälle, in denen ein Teil größer als \(e\) ist. Da höchstens ein Teil größer als \(e\) sein kann, ergibt sich
$$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}.$$
Dies ist die Formel in run_count_table. Der erste Binomialkoeffizient zählt alle positiven Kompositionen; der zweite Term subtrahiert die Fälle mit einer festgelegten zu großen Komponente.
Sei \(T(i,e)\) die Anzahl zulässiger Vektoren auf den ersten \(i\) Spielern, deren Kreuzungsmultigraph genau \(e\) Kanten hat. Zusätzlich speichert der Code \(Z(i,e)\), die Anzahl solcher Vektoren, deren letzter Eintrag null ist. Damit lässt sich erzwingen, dass zwei positive Läufe durch mindestens eine Null getrennt sind.
Die Übergänge lauten:
$$Z(i,e)=T(i-1,e),$$
denn das Anhängen einer Null an einen Vektor der Länge \(i-1\) ergibt einen Vektor der Länge \(i\), der mit Null endet. Ein positiver Endlauf der Länge \(\ell\ge 2\) kann nach einem nullendenden Präfix angehängt werden:
$$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$$
Der Startwert ist \(T(0,0)=Z(0,0)=1\). Nach der Verarbeitung aller \(n\) Spieler wird kumuliert:
$$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$$
Die DP ist für \(n\) klein genug, aber \(E=4567891/2\) ist zu groß für eine direkte Schleife. Die Formel \(R(\ell,e)\) ist ein Polynom in \(e\) vom Grad \(\ell-1\), und die Präfixrekurrenz besteht aus Additionen und Faltungen solcher Polynomstücke. Für festes \(n\) stimmt die kumulative Funktion
$$A_n(E)=\sum_{e=0}^{E}T(n,e)$$
ab \(E\ge n-1\) mit einem Polynom vom Grad \(n\) überein. Das Programm berechnet nur die \(n+1\) aufeinanderfolgenden Werte
$$E=n-1,\;n,\;\ldots,\;2n-1,$$
nimmt endliche Differenzen und wertet Newtons Vorwärtsformel aus:
$$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$$
Der Zielmodul ist nicht prim, daher werden die großen Binomialwerte nicht mit modularen Inversen berechnet. Stattdessen kürzt die Implementierung die kleinen Nennerfaktoren ganzzahlig gegen die Zählerfaktoren und multipliziert erst danach modulo \(1234567891\).
Die C++-, Python- und Java-Versionen bauen zunächst kleine Binomialtabellen für den DP-Bereich. Sie berechnen alle \(R(\ell,e)\), führen die Präfix-DP bis \(E=2n-1\) für \(n=123\) aus und bilden die kumulativen Werte. Danach berechnen sie die endlichen Differenzen ab \(E=n-1\) und werten das Grad-\(n\)-Polynom bei \(E=\lfloor4567891/2\rfloor\) aus.
Der Validierungsblock prüft mehr als nur die beiden Beispiele. Für \(2\le n\le5\) vergleicht er die DP mit einer Brute-Force-Suche über benachbarte Vertauschungszustände für kleine \(E\). Außerdem prüft er \(F(3,4)=8\), \(F(12,34)=2457178250\), und testet die Polynomfortsetzung gegen direkt berechnete Werte für mehrere kleine \(n\).
Für die Interpolation wird nur \(E_{\max}=2n-1\) benötigt. Die Lauftabelle kostet nach der Binomialvorbereitung \(O(n^2E_{\max})\) Operationen, und die Präfix-DP kostet in dieser direkten Implementierung \(O(n^2E_{\max}^2)\). Für \(n=123\) und \(E_{\max}=245\) ist das praktikabel.
Der große Wert von \(k\) beeinflusst nur \(n+1\) modulare Binomialauswertungen mit Ordnung höchstens \(n\). Der Algorithmus iteriert nicht über Millionen Tage und enumeriert für die Zielinstanz keine Permutationen.
\(n\) oyuncu başlangıçtaki sıralarına göre dizilidir. Her gün bitişik iki sıra arasında bir maç oynanır. Üst sıradaki oyuncu kazanırsa sıra ve overtake sayıları değişmez. Alt sıradaki oyuncu kazanırsa iki oyuncu yer değiştirir ve kazanan oyuncunun overtake sayısı \(1\) artar. Tam \(k\) gün sonunda sıralama yeniden başlangıç sırası olmalıdır; \(F(n,k)\) mümkün overtake-sayı vektörlerinin sayısını verir.
Temel gözlem şudur: overtake olmayan maçlar saf bekleme adımlarıdır. Bunlar herhangi bir yere eklenebilir ve ne sırayı ne de sayı vektörünü değiştirir. Dolayısıyla yalnızca gerçek overtake dizisi önemlidir. Her overtake bitişik bir transpozisyon olduğu için kimlik permütasyonuna dönmek için overtake sayısı çift olmalıdır. Uygulama \(E=\lfloor k/2\rfloor\) yazar ve en fazla \(E\) eşleşmiş geçişle mümkün olan tüm vektörleri sayar.
Başlangıçta \(i\) oyuncusu \(j\)'nin üstünde olsun. Bu iki oyuncunun göreli sırası yalnızca bitişik olduklarında ve biri diğerini geçtiğinde değişir. Son sıra tekrar başlangıç sırası olduğuna göre bu çiftin birbirini kesme sayısı çift olmalıdır. Eğer çift \(2m_{ij}\) kez kesişirse, \(j\) yukarı çıkarken \(i\)'yi tam \(m_{ij}\) kez, \(i\) geri inerken \(j\)'yi tam \(m_{ij}\) kez geçer.
Bu yüzden her kapalı overtake geçmişi \(n\) oyuncu üzerinde döngüsüz bir multigraf belirler: \(i\) ile \(j\) arasına \(m_{ij}\) kenar koyarız. Oyuncu \(i\)'nin overtake sayısı, bu multigraftaki derece değeridir. Toplam kenar sayısı \(e\) ise gerçek overtake sayısı \(2e\)'dir; \(k\) günlük bir program, \(e\le E=\lfloor k/2\rfloor\) olan her vektörü zamanla doldurabilir.
Bitişik takaslar tek boyutlu bir kısıt getirir. İki oyuncu etkileşiyorsa, başlangıçta aralarında bulunan her oyuncu bir noktada aynı hareketli bloğun içinde kalır. Bu nedenle geçerli bir derece vektörünün sıfır olmayan girdileri ayrık bitişik run'lara ayrılır. Uzunluğu \(1\) olan run imkansızdır: izole tek oyuncu, komşularının sayısı sıfırken kimseyi geçip geri dönemez.
Demek ki geçerli vektörler sıfır boşlukları ve uzunluğu \(\ell\ge 2\) olan pozitif run'lardan kurulur. Her run, ardışık bir oyuncu bloğu üzerindeki geçiş multigrafının bir bağlı bileşenidir. Dinamik program tam olarak bu ayrışmayı kullanır: ya bir sıfır eklenir ya da sıfırla ayrılmış bir önekten sonra pozitif bir run eklenir.
Uzunluğu \(\ell\) olan ve \(e\) graf kenarı kullanan bir run için pozitif dereceler gerekir:
$$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$$
\(e\) kenarlı döngüsüz bir multigrafta hiçbir derece \(e\)'den büyük olamaz; çünkü her kenar o düğüme bir derece ve başka bir düğüme de bir derece verir. Tersine, pozitif tamsayı dizileri için
$$\max_i a_i\le e$$
koşulu böyle bir döngüsüz multigraf gerçekleştirmesi için yeterlidir. Dolayısıyla tek run sayısı, \(2e\)'nin \(\ell\) pozitif parçaya ayrılış sayısından bir parçanın \(e\)'den büyük olduğu durumların çıkarılmasıdır. En fazla bir parça \(e\)'den büyük olabileceği için
$$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}$$
elde edilir. Kodda bu formül run_count_table içinde yer alır. İlk binom tüm pozitif kompozisyonları sayar; ikinci terim belirli bir bileşenin fazla büyük olduğu durumları çıkarır.
\(T(i,e)\), ilk \(i\) oyuncu üzerinde tam \(e\) kenarlı geçerli vektörlerin sayısı olsun. Kod ayrıca son girdisi sıfır olan bu tür vektörlerin sayısını \(Z(i,e)\) olarak tutar. Böylece iki pozitif run arasında en az bir sıfır olma koşulu temiz biçimde uygulanır.
Geçişler şöyledir:
$$Z(i,e)=T(i-1,e),$$
çünkü uzunluğu \(i-1\) olan bir vektöre sıfır eklemek, sıfırla biten uzunluk \(i\) vektörü üretir. Sonra uzunluğu \(\ell\ge 2\) olan pozitif bir son run, sıfırla biten bir önekten sonra eklenebilir:
$$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$$
Başlangıç \(T(0,0)=Z(0,0)=1\)'dir. Bütün \(n\) oyuncu işlendikten sonra istenen gün sınırı için kümülatif toplam alınır:
$$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$$
DP, \(n\) için küçüktür; fakat \(E=4567891/2\) değerine kadar doğrudan ilerlemek çok büyüktür. Run formülü \(R(\ell,e)\), \(e\) cinsinden derecesi \(\ell-1\) olan bir polinomdur; önek reküransı da bu polinom parçalarının toplam ve konvolüsyonlarından oluşur. Sabit \(n\) için kümülatif fonksiyon
$$A_n(E)=\sum_{e=0}^{E}T(n,e)$$
\(E\ge n-1\) sonrasında derecesi \(n\) olan bir polinomla çakışır. Program yalnızca ardışık \(n+1\) değeri hesaplar:
$$E=n-1,\;n,\;\ldots,\;2n-1,$$
sonlu farkları alır ve Newton ileri açılımını değerlendirir:
$$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$$
Modül asal olmadığı için büyük binomlar modüler terslerle hesaplanmaz. Uygulama küçük payda çarpanlarını tamsayı düzeyinde pay çarpanlarından sadeleştirir, sonra kalan çarpanları \(1234567891\) modülünde çarpar.
C++, Python ve Java programları önce DP için gereken küçük aralıkta binom tablolarını kurar. Tüm \(R(\ell,e)\) değerlerini hesaplar, hedef \(n=123\) için önek DP'yi \(E=2n-1\)'e kadar çalıştırır ve kümülatif değerleri oluşturur. Sonra \(E=n-1\)'den başlayan sonlu farkları alır ve derece \(n\) polinomu \(E=\lfloor4567891/2\rfloor\) noktasında değerlendirir.
Doğrulama bloğu yalnızca iki örneği kontrol etmekle kalmaz. \(2\le n\le5\) için DP'yi küçük \(E\) değerlerinde bitişik-takas durumlarını brute force dolaşan sayımla karşılaştırır. Ayrıca \(F(3,4)=8\), \(F(12,34)=2457178250\) kontrollerini ve birkaç küçük \(n\) için polinom uzatmasının doğrudan hesaplanan değerlerle uyumunu test eder.
İnterpolasyon için yalnızca \(E_{\max}=2n-1\) gerekir. Run tablosu, binom önhesabından sonra \(O(n^2E_{\max})\) aritmetik işlem ister; önek DP ise bu doğrudan sürümde \(O(n^2E_{\max}^2)\) maliyetindedir. \(n=123\) ve \(E_{\max}=245\) için bu rahatça uygulanabilir.
Büyük \(k\) değeri yalnızca derecesi en fazla \(n\) olan \(n+1\) modüler binom değerlendirmesini etkiler. Algoritma milyonlarca günü dolaşmaz ve hedef örnekte permütasyonları enumerate etmez.
Hay \(n\) jugadores ordenados según su clasificación inicial. Cada día se juega un partido entre dos rangos adyacentes. Si gana el jugador de rango superior, el orden y todos los contadores de adelantamientos no cambian. Si gana el jugador de rango inferior, los dos jugadores intercambian posiciones y el contador del ganador aumenta en \(1\). Después de exactamente \(k\) días el orden final debe volver a ser el inicial, y \(F(n,k)\) cuenta cuántos vectores de contadores pueden aparecer.
La observación clave es que los partidos sin adelantamiento son pasos inactivos. Se pueden insertar en cualquier lugar sin cambiar ni el orden ni el vector de contadores. Por tanto solo importa la secuencia de adelantamientos reales. Como cada adelantamiento es una transposición adyacente, volver a la permutación identidad exige un número par de adelantamientos. La implementación escribe \(E=\lfloor k/2\rfloor\) y cuenta todos los vectores factibles con a lo sumo \(E\) cruces emparejados.
Consideremos dos jugadores fijos \(i\) y \(j\), con \(i\) inicialmente por encima de \(j\). Su orden relativo solo cambia cuando son adyacentes y uno adelanta al otro. Como el orden final vuelve a ser el inicial, este par debe cruzarse un número par de veces. Si se cruza \(2m_{ij}\) veces, entonces \(j\) adelanta a \(i\) exactamente \(m_{ij}\) veces al subir, e \(i\) adelanta a \(j\) exactamente \(m_{ij}\) veces al volver a bajar.
Así, toda historia cerrada de adelantamientos determina un multigrafo sin bucles sobre los \(n\) jugadores: ponemos \(m_{ij}\) aristas entre \(i\) y \(j\). El contador de adelantamientos del jugador \(i\) es exactamente el grado del vértice \(i\). Si el número total de aristas es \(e\), el número real de adelantamientos es \(2e\); por tanto un calendario de \(k\) días puede realizar cualquier vector con \(e\le E=\lfloor k/2\rfloor\).
Los intercambios adyacentes imponen una restricción unidimensional. Si dos jugadores interactúan, todos los jugadores inicialmente situados entre ellos deben entrar en algún momento en el mismo bloque móvil. Por ello las entradas no nulas de un vector factible se descomponen en intervalos contiguos disjuntos. Un intervalo de longitud \(1\) es imposible: un jugador aislado no puede adelantar a alguien y regresar si sus vecinos tienen contador cero.
Un vector factible se construye entonces con huecos de ceros e intervalos positivos de longitud \(\ell\ge 2\). Cada intervalo representa una componente conexa del multigrafo de cruces sobre un bloque consecutivo de jugadores. Esta es exactamente la descomposición usada por la programación dinámica: añadir un cero, o añadir un intervalo positivo después de un prefijo separado por cero.
Para un intervalo de longitud \(\ell\) que usa \(e\) aristas, necesitamos grados positivos
$$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$$
En un multigrafo sin bucles con \(e\) aristas, ningún vértice puede tener grado mayor que \(e\), porque cada arista incidente aporta un grado a ese vértice y otro grado a algún otro vértice. Recíprocamente, para sucesiones positivas de enteros, la condición
$$\max_i a_i\le e$$
es suficiente para una realización por multigrafo sin bucles en el intervalo. Por tanto el número buscado es el de composiciones positivas de \(2e\) en \(\ell\) partes, menos las que tienen una parte mayor que \(e\). Como a lo sumo una parte puede exceder \(e\), se obtiene
$$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}.$$
Esta es la fórmula de run_count_table. El primer binomial cuenta todas las composiciones positivas; el segundo término resta los casos en que una componente especificada es demasiado grande.
Sea \(T(i,e)\) el número de vectores factibles en los primeros \(i\) jugadores cuyo multigrafo de cruces tiene exactamente \(e\) aristas. El código también mantiene \(Z(i,e)\), el número de esos vectores cuyo último elemento es cero. Esto permite exigir que dos intervalos positivos estén separados por al menos un cero.
La transición es:
$$Z(i,e)=T(i-1,e),$$
porque añadir un cero a un vector de longitud \(i-1\) produce un vector de longitud \(i\) que termina en cero. Luego un intervalo positivo final de longitud \(\ell\ge 2\) puede añadirse tras un prefijo que termina en cero:
$$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$$
La base es \(T(0,0)=Z(0,0)=1\). Tras procesar los \(n\) jugadores, se toma la suma acumulada:
$$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$$
La DP es pequeña en \(n\), pero \(E=4567891/2\) es demasiado grande para iterar directamente. La fórmula \(R(\ell,e)\) es un polinomio en \(e\) de grado \(\ell-1\), y la recurrencia de prefijos está formada por sumas y convoluciones de esas piezas polinómicas. Para \(n\) fijo, la función acumulada
$$A_n(E)=\sum_{e=0}^{E}T(n,e)$$
coincide, desde \(E\ge n-1\), con un polinomio de grado \(n\). El programa calcula solo los \(n+1\) valores consecutivos
$$E=n-1,\;n,\;\ldots,\;2n-1,$$
toma diferencias finitas y evalúa la expansión de Newton hacia adelante:
$$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$$
El módulo objetivo no es primo, de modo que los binomios grandes no se calculan con inversos modulares. La implementación cancela los factores pequeños del denominador contra los factores del numerador en enteros, y luego multiplica los factores restantes módulo \(1234567891\).
Los programas en C++, Python y Java construyen primero tablas binomiales pequeñas para el rango de la DP. Calculan todos los \(R(\ell,e)\), ejecutan la DP de prefijos hasta \(E=2n-1\) para \(n=123\), y forman los valores acumulados. Después toman diferencias finitas desde \(E=n-1\) y evalúan el polinomio de grado \(n\) en \(E=\lfloor4567891/2\rfloor\).
El bloque de validación es más fuerte que comprobar solo los dos ejemplos. Para \(2\le n\le5\), compara la DP con una búsqueda exhaustiva de estados por transposiciones adyacentes para \(E\) pequeños. También comprueba \(F(3,4)=8\), \(F(12,34)=2457178250\), y verifica la continuación polinómica frente a valores directos para varios \(n\) pequeños.
La etapa de interpolación solo necesita \(E_{\max}=2n-1\). La tabla de intervalos cuesta \(O(n^2E_{\max})\) operaciones tras precalcular binomios, y la DP de prefijos cuesta \(O(n^2E_{\max}^2)\) en esta implementación directa. Con \(n=123\) y \(E_{\max}=245\), es práctico.
El gran valor de \(k\) solo afecta a \(n+1\) evaluaciones binomiales modulares de orden como máximo \(n\). El algoritmo nunca itera por millones de días ni enumera permutaciones para la instancia objetivo.
有 \(n\) 名网球选手按初始排名排列。每天在相邻排名的两名选手之间进行一场比赛。如果排名较高的选手获胜，顺序和所有超越次数都不变；如果排名较低的选手获胜，两人交换名次，并且获胜者的超越次数增加 \(1\)。经过正好 \(k\) 天后，最终排名必须回到初始排名；\(F(n,k)\) 计算可能出现的超越次数向量数。
关键观察是，没有超越的比赛只是空闲步骤。它们可以插入到任意位置，而不改变排名或计数向量。因此真正重要的是实际超越的序列。每次超越都是一次相邻换位，而回到恒等排列需要偶数次换位。实现令 \(E=\lfloor k/2\rfloor\)，并计算最多 \(E\) 个成对交叉所能产生的所有向量。
考虑两名固定选手 \(i\) 和 \(j\)，其中 \(i\) 初始排名高于 \(j\)。他们的相对顺序只会在两人相邻且一人超越另一人时改变。最终顺序又回到初始顺序，所以这对选手必须交叉偶数次。若他们交叉 \(2m_{ij}\) 次，则 \(j\) 向上时超越 \(i\) 正好 \(m_{ij}\) 次，\(i\) 返回时超越 \(j\) 正好 \(m_{ij}\) 次。
因此每个闭合的超越历史都会确定一个以 \(n\) 名选手为顶点的无环多重图：在 \(i\) 与 \(j\) 之间放 \(m_{ij}\) 条边。选手 \(i\) 的超越次数正好是顶点 \(i\) 的度。如果总边数为 \(e\)，实际超越数就是 \(2e\)；所以 \(k\) 天的赛程可以实现所有 \(e\le E=\lfloor k/2\rfloor\) 的向量。
相邻交换带来一维限制。如果两名选手发生交互，那么初始位于他们之间的所有选手在某个时刻都必须处在同一个移动块中。因此可行度向量中的非零项分解为若干不相交的连续段。长度为 \(1\) 的段不可能出现：单个孤立选手无法在邻居计数为零时超越别人并返回。
所以一个可行向量由零间隔和长度 \(\ell\ge 2\) 的正连续段构成。每个连续段表示一个连续选手块上的交叉多重图连通分量。动态规划正是使用这个分解：要么追加一个零，要么在以零分隔的前缀之后追加一个正段。
对长度为 \(\ell\)、使用 \(e\) 条图边的连续段，需要正度数
$$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$$
在有 \(e\) 条边的无环多重图中，一个顶点的度不能超过 \(e\)，因为每条关联边给该顶点贡献一个度，同时也给别的顶点贡献一个度。反过来，对正整数序列，条件
$$\max_i a_i\le e$$
足以实现为该连续段上的无环多重图。因此一个连续段的数量等于把 \(2e\) 分成 \(\ell\) 个正部分的组合数，再减去某一部分超过 \(e\) 的情形。因为至多有一个部分能超过 \(e\)，所以
$$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}.$$
这就是 run_count_table 中实现的公式。第一个二项式计算所有正组合；第二项减去指定分量过大的情况。
令 \(T(i,e)\) 表示前 \(i\) 名选手上交叉多重图恰有 \(e\) 条边的可行向量数。代码还维护 \(Z(i,e)\)，表示这些向量中最后一个元素为零的数量。这样就能保证两个正连续段之间至少隔着一个零。
转移为：
$$Z(i,e)=T(i-1,e),$$
因为向长度 \(i-1\) 的向量追加一个零，会得到长度 \(i\) 且以零结尾的向量。然后长度 \(\ell\ge 2\) 的末尾正段可以接在以零结尾的前缀之后：
$$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$$
初始条件是 \(T(0,0)=Z(0,0)=1\)。处理完所有 \(n\) 名选手后，答案取累计和：
$$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$$
DP 对 \(n\) 来说很小，但 \(E=4567891/2\) 太大，不能直接迭代。连续段公式 \(R(\ell,e)\) 是关于 \(e\) 的 \(\ell-1\) 次多项式，而前缀递推只由这些多项式片段的加法和卷积构成。对固定 \(n\)，累计函数
$$A_n(E)=\sum_{e=0}^{E}T(n,e)$$
从 \(E\ge n-1\) 开始与一个 \(n\) 次多项式一致。程序只计算连续的 \(n+1\) 个值
$$E=n-1,\;n,\;\ldots,\;2n-1,$$
取有限差分，并使用 Newton 前向展开：
$$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$$
目标模数不是素数，所以大二项式不通过模逆计算。实现先在整数中把小分母因子与分子因子约掉，再把剩余因子在 \(1234567891\) 下相乘。
C++、Python 和 Java 程序先为 DP 所需的小范围建立二项式表。它们计算所有 \(R(\ell,e)\)，对目标 \(n=123\) 运行前缀 DP 到 \(E=2n-1\)，并形成累计值。然后从 \(E=n-1\) 开始取有限差分，并在 \(E=\lfloor4567891/2\rfloor\) 处计算 \(n\) 次多项式。
验证部分不只是检查两个样例。对 \(2\le n\le5\)，它把 DP 与小 \(E\) 下的相邻换位状态暴力搜索进行比较。它还检查 \(F(3,4)=8\)、\(F(12,34)=2457178250\)，并对多个小 \(n\) 验证多项式延拓与直接计算值一致。
插值阶段只需要 \(E_{\max}=2n-1\)。在预计算二项式后，连续段表需要 \(O(n^2E_{\max})\) 次运算；这个直接实现中的前缀 DP 需要 \(O(n^2E_{\max}^2)\)。当 \(n=123\)、\(E_{\max}=245\) 时，这是可行的。
巨大的 \(k\) 只影响 \(n+1\) 个阶数不超过 \(n\) 的模二项式求值。算法不会遍历数百万天，也不会为目标实例枚举排列。
Есть \(n\) теннисистов, расположенных в начальном порядке рейтинга. Каждый день матч проводится между двумя соседними позициями. Если выигрывает игрок с более высоким местом, порядок и все счетчики обгонов не меняются. Если выигрывает игрок с более низким местом, эти два игрока меняются местами, а счетчик победителя увеличивается на \(1\). После ровно \(k\) дней порядок снова должен стать начальным; \(F(n,k)\) считает, сколько векторов счетчиков обгонов может получиться.
Главное наблюдение состоит в том, что матчи без обгона являются чистыми пустыми шагами. Их можно вставлять куда угодно, не меняя ни порядок, ни вектор счетчиков. Поэтому важна только последовательность реальных обгонов. Каждый обгон является соседней транспозицией, а возвращение к тождественной перестановке требует четного числа таких транспозиций. Реализация задает \(E=\lfloor k/2\rfloor\) и считает все допустимые векторы с не более чем \(E\) парными пересечениями.
Рассмотрим двух фиксированных игроков \(i\) и \(j\), где \(i\) изначально выше \(j\). Их относительный порядок меняется только тогда, когда они соседние и один обгоняет другого. Так как конечный порядок снова начальный, эта пара должна пересечься четное число раз. Если она пересекается \(2m_{ij}\) раз, то \(j\) обгоняет \(i\) ровно \(m_{ij}\) раз при движении вверх, а \(i\) обгоняет \(j\) ровно \(m_{ij}\) раз при возврате.
Следовательно, любая замкнутая история обгонов определяет петлесвободный мультиграф на \(n\) игроках: между \(i\) и \(j\) помещается \(m_{ij}\) ребер. Счетчик обгонов игрока \(i\) равен степени вершины \(i\). Если всего ребер \(e\), то реальных обгонов \(2e\); значит, расписание длины \(k\) может реализовать любой вектор с \(e\le E=\lfloor k/2\rfloor\).
Соседние перестановки накладывают одномерное ограничение. Если два игрока взаимодействуют, то каждый игрок, изначально находившийся между ними, в какой-то момент попадает в тот же движущийся блок. Поэтому ненулевые элементы допустимого вектора степеней распадаются на непересекающиеся непрерывные блоки. Блок длины \(1\) невозможен: один изолированный игрок не может кого-то обогнать и вернуться, если у его соседей нулевые счетчики.
Значит, допустимый вектор строится из нулевых промежутков и положительных блоков длины \(\ell\ge 2\). Каждый блок соответствует связной компоненте мультиграфа пересечений на последовательном блоке игроков. Именно это разложение использует динамическая программа: добавить ноль или добавить положительный блок после префикса, отделенного нулем.
Для блока длины \(\ell\), использующего \(e\) ребер графа, нужны положительные степени
$$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$$
В петлесвободном мультиграфе с \(e\) ребрами степень одной вершины не может быть больше \(e\), потому что каждое инцидентное ребро дает один вклад этой вершине и один вклад другой вершине. Обратно, для положительных целочисленных последовательностей условие
$$\max_i a_i\le e$$
достаточно для реализации петлесвободным мультиграфом на блоке. Поэтому число вариантов для блока равно числу положительных композиций \(2e\) на \(\ell\) частей за вычетом случаев, где одна часть больше \(e\). Поскольку больше \(e\) может быть не более одной части, получаем
$$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}.$$
Эта формула реализована в run_count_table. Первый биномиальный коэффициент считает все положительные композиции; второй член вычитает случаи с заданной слишком большой компонентой.
Пусть \(T(i,e)\) - число допустимых векторов на первых \(i\) игроках, чей мультиграф пересечений имеет ровно \(e\) ребер. Код также хранит \(Z(i,e)\), число таких векторов, последний элемент которых равен нулю. Это позволяет гарантировать, что два положительных блока разделены хотя бы одним нулем.
Переход:
$$Z(i,e)=T(i-1,e),$$
потому что добавление нуля к вектору длины \(i-1\) дает вектор длины \(i\), оканчивающийся нулем. Затем конечный положительный блок длины \(\ell\ge 2\) можно добавить после префикса, оканчивающегося нулем:
$$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$$
База равна \(T(0,0)=Z(0,0)=1\). После обработки всех \(n\) игроков берется накопленная сумма:
$$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$$
DP мала по \(n\), но \(E=4567891/2\) слишком велико для прямого перебора. Формула \(R(\ell,e)\) является многочленом по \(e\) степени \(\ell-1\), а префиксная рекурсия состоит из сумм и сверток таких многочленных частей. Для фиксированного \(n\) накопленная функция
$$A_n(E)=\sum_{e=0}^{E}T(n,e)$$
начиная с \(E\ge n-1\), совпадает с многочленом степени \(n\). Программа вычисляет только \(n+1\) последовательных значений
$$E=n-1,\;n,\;\ldots,\;2n-1,$$
берет конечные разности и вычисляет разложение Ньютона вперед:
$$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$$
Целевой модуль не является простым, поэтому большие биномиальные коэффициенты не считаются через обратные по модулю. Реализация сокращает малые множители знаменателя с множителями числителя в целых числах, а затем перемножает оставшиеся множители modulo \(1234567891\).
Версии C++, Python и Java сначала строят биномиальные таблицы для малого диапазона DP. Они вычисляют все \(R(\ell,e)\), запускают префиксную DP до \(E=2n-1\) для целевого \(n=123\), и формируют накопленные значения. Затем берут конечные разности, начиная с \(E=n-1\), и вычисляют многочлен степени \(n\) при \(E=\lfloor4567891/2\rfloor\).
Блок проверки сильнее, чем простая проверка двух примеров. Для \(2\le n\le5\) он сравнивает DP с полным перебором состояний соседних перестановок для малых \(E\). Он также проверяет \(F(3,4)=8\), \(F(12,34)=2457178250\), и сверяет полиномиальное продолжение с прямыми значениями для нескольких малых \(n\).
Для этапа интерполяции нужно только \(E_{\max}=2n-1\). Таблица блоков стоит \(O(n^2E_{\max})\) операций после предварительного вычисления биномиальных коэффициентов, а префиксная DP в этой прямой реализации стоит \(O(n^2E_{\max}^2)\). При \(n=123\) и \(E_{\max}=245\) это практически мало.
Большое значение \(k\) влияет только на \(n+1\) вычислений биномиальных коэффициентов по модулю порядка не выше \(n\). Алгоритм не проходит миллионы дней и не перечисляет перестановки для целевой задачи.
يوجد \(n\) لاعب تنس مرتبين حسب ترتيبهم الابتدائي. في كل يوم تلعب مباراة بين رتبتين متجاورتين. إذا فاز اللاعب الأعلى رتبة، لا يتغير الترتيب ولا تتغير عدادات التجاوز. إذا فاز اللاعب الأدنى رتبة، يتبادل اللاعبان مكانيهما، ويزداد عداد التجاوز للفائز بمقدار \(1\). بعد \(k\) أيام بالضبط يجب أن يعود الترتيب إلى الترتيب الابتدائي؛ وتحسب \(F(n,k)\) عدد متجهات عدادات التجاوز الممكنة.
الملاحظة المهمة هي أن المباريات التي لا يحدث فيها تجاوز هي خطوات خاملة فقط. يمكن إدراجها في أي مكان من دون تغيير الترتيب أو متجه العدادات. لذلك لا يهم إلا تسلسل التجاوزات الفعلية. وبما أن كل تجاوز هو تبديل متجاور، فإن الرجوع إلى الترتيب الأصلي يتطلب عددا زوجيا من التجاوزات. تكتب الخوارزمية \(E=\lfloor k/2\rfloor\)، وتعد كل المتجهات الممكنة بما لا يزيد عن \(E\) تقاطعا مزدوجا.
لننظر إلى لاعبين ثابتين \(i\) و \(j\)، حيث يكون \(i\) أعلى من \(j\) في البداية. لا يتغير ترتيبهما النسبي إلا عندما يكونان متجاورين ويتجاوز أحدهما الآخر. وبما أن الترتيب النهائي هو نفسه الترتيب الابتدائي، فيجب أن يتقاطع هذا الزوج عددا زوجيا من المرات. إذا تقاطعا \(2m_{ij}\) مرة، فإن \(j\) يتجاوز \(i\) بالضبط \(m_{ij}\) مرة أثناء الصعود، و \(i\) يتجاوز \(j\) بالضبط \(m_{ij}\) مرة أثناء الرجوع.
لذلك فإن كل تاريخ مغلق من التجاوزات يحدد رسما متعدد الحواف بلا حلقات على اللاعبين \(n\): نضع \(m_{ij}\) حافة بين \(i\) و \(j\). عداد التجاوز للاعب \(i\) هو تماما درجة الرأس \(i\). إذا كان مجموع الحواف \(e\)، فإن عدد التجاوزات الفعلية هو \(2e\)، ومن ثم يستطيع جدول من \(k\) أيام تحقيق أي متجه له \(e\le E=\lfloor k/2\rfloor\).
التبديلات المتجاورة تفرض قيدا أحادي البعد. إذا تفاعل لاعبان، فإن كل لاعب كان في البداية بينهما يجب أن يدخل في وقت ما داخل الكتلة المتحركة نفسها. لذلك تنقسم القيم غير الصفرية في متجه درجات ممكن إلى مقاطع متجاورة منفصلة. مقطع بطول \(1\) مستحيل: لاعب منفرد لا يستطيع أن يتجاوز أحدا ويعود بينما عدادا جارَيْه يساويان صفرا.
إذن يبنى المتجه الممكن من فجوات صفرية ومقاطع موجبة بطول \(\ell\ge 2\). كل مقطع يمثل مركبة متصلة من رسم التقاطعات على كتلة متتالية من اللاعبين. وهذا بالضبط ما تستعمله البرمجة الديناميكية: إما إضافة صفر، أو إضافة مقطع موجب بعد بادئة مفصولة بصفر.
لمقطع طوله \(\ell\) ويستخدم \(e\) حافة، نحتاج درجات موجبة
$$a_1,a_2,\ldots,a_\ell \ge 1,\qquad a_1+\cdots+a_\ell=2e.$$
في رسم متعدد الحواف بلا حلقات وله \(e\) حافة، لا يمكن أن تتجاوز درجة رأس واحد القيمة \(e\)، لأن كل حافة حادثة تعطي درجة واحدة لهذا الرأس ودرجة أخرى لرأس آخر. وبالعكس، للمتتاليات الصحيحة الموجبة يكون الشرط
$$\max_i a_i\le e$$
كافيا لتحقيقها كرسم متعدد الحواف بلا حلقات على ذلك المقطع. لذلك يكون عدد المقاطع هو عدد تجزئات \(2e\) إلى \(\ell\) أجزاء موجبة، مع حذف الحالات التي يكون فيها جزء واحد أكبر من \(e\). وبما أن جزءا واحدا فقط على الأكثر يمكن أن يتجاوز \(e\)، نحصل على
$$R(\ell,e)=\binom{2e-1}{\ell-1}-\ell\binom{e-1}{\ell-1}.$$
هذه هي الصيغة المنفذة في run_count_table. الحد الأول يعد كل التجزئات الموجبة؛ والحد الثاني يطرح الحالات التي تكون فيها مركبة محددة كبيرة جدا.
ليكن \(T(i,e)\) عدد المتجهات الممكنة على أول \(i\) لاعب، بحيث يكون رسم التقاطعات لها ذا \(e\) حافة بالضبط. يحتفظ الكود أيضا بـ \(Z(i,e)\)، وهو عدد هذه المتجهات التي يكون آخر عنصر فيها صفرا. هذا يجعل فرض وجود صفر على الأقل بين مقطعين موجبين أمرا مباشرا.
الانتقال هو:
$$Z(i,e)=T(i-1,e),$$
لأن إضافة صفر إلى متجه طوله \(i-1\) تعطي متجها طوله \(i\) وينتهي بصفر. ثم يمكن إضافة مقطع موجب أخير بطول \(\ell\ge 2\) بعد بادئة تنتهي بصفر:
$$T(i,e)\;{+}{=}\;Z(i-\ell,e-u)\,R(\ell,u),\qquad 2\le \ell\le i,\;1\le u\le e.$$
حالة البداية هي \(T(0,0)=Z(0,0)=1\). بعد معالجة كل اللاعبين \(n\)، نأخذ المجموع التراكمي:
$$F(n,k)=\sum_{e=0}^{\lfloor k/2\rfloor}T(n,e).$$
البرمجة الديناميكية صغيرة بالنسبة إلى \(n\)، لكن \(E=4567891/2\) أكبر من أن يحسب مباشرة. صيغة المقطع \(R(\ell,e)\) كثيرة حدود في \(e\) من الدرجة \(\ell-1\)، وتكرار البوادئ مكون من جمع وطي لهذه القطع كثيرة الحدود. عند تثبيت \(n\)، فإن الدالة التراكمية
$$A_n(E)=\sum_{e=0}^{E}T(n,e)$$
تتطابق ابتداء من \(E\ge n-1\) مع كثيرة حدود من الدرجة \(n\). يحسب البرنامج فقط \(n+1\) قيمة متتالية:
$$E=n-1,\;n,\;\ldots,\;2n-1,$$
ثم يأخذ الفروق المنتهية ويقيم توسع نيوتن الأمامي:
$$A_n(E)=\sum_{r=0}^{n}\Delta^r A_n(n-1)\binom{E-(n-1)}{r}.$$
المودولو الهدف ليس عددا أوليا، لذلك لا تحسب القيم الثنائية الكبيرة بالمقلوبات المعيارية. بدلا من ذلك تلغي الخوارزمية عوامل المقام الصغيرة مع عوامل البسط على مستوى الأعداد الصحيحة، ثم تضرب العوامل الباقية بترديد \(1234567891\).
تبني برامج C++ و Python و Java أولا جداول ثنائية للمدى الصغير الذي تحتاجه DP. ثم تحسب كل \(R(\ell,e)\)، وتشغل DP للبوادئ حتى \(E=2n-1\) من أجل \(n=123\)، وتكون القيم التراكمية. بعد ذلك تأخذ الفروق المنتهية ابتداء من \(E=n-1\)، وتقيّم كثيرة الحدود من الدرجة \(n\) عند \(E=\lfloor4567891/2\rfloor\).
كتلة التحقق أقوى من مجرد فحص المثالين. من أجل \(2\le n\le5\)، تقارن DP مع بحث شامل في حالات التبديلات المتجاورة لقيم صغيرة من \(E\). كما تتحقق من \(F(3,4)=8\)، و \(F(12,34)=2457178250\)، وتختبر الاستمرار كثير الحدود مقابل قيم مباشرة لعدة قيم صغيرة من \(n\).
مرحلة الاستيفاء تحتاج فقط إلى \(E_{\max}=2n-1\). جدول المقاطع يكلف \(O(n^2E_{\max})\) عملية حسابية بعد التحضير الثنائي، وتكلف DP للبوادئ \(O(n^2E_{\max}^2)\) في هذا التنفيذ المباشر. مع \(n=123\) و \(E_{\max}=245\)، يبقى ذلك عمليا.
القيمة الكبيرة لـ \(k\) تؤثر فقط في \(n+1\) تقييما ثنائيا معياريا من رتبة لا تتجاوز \(n\). لا تمر الخوارزمية على ملايين الأيام ولا تعدد التبديلات في حالة الهدف.