In a double round-robin with \(n\) teams, each pair meets twice. A win gives \(2\) points, a draw gives \(1\) point to each team, and a loss gives \(0\) points. Let \(F(n)\) be the number of distinct final point multisets, so two outcomes are identified when they differ only by permuting team labels. The task is to compute \(F(100)\) modulo \(10^9+7\).
Write the sorted final scores as
$$s_1\le s_2\le \cdots \le s_n,$$
and define
$$V=4(n-1),\qquad S=2n(n-1).$$
The whole problem becomes: count the nondecreasing integer sequences \((s_1,\dots,s_n)\) that can arise from the tournament and whose total sum is \(S\).
For each ordered pair of distinct teams \((i,j)\), let \(a_{ij}\) be the total number of points that team \(i\) earns from its two matches against team \(j\). Then
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
Every value \(0,1,2,3,4\) is genuinely attainable in two ordinary matches: lose-lose, lose-draw, split or double-draw, draw-win, and win-win. Therefore no information is lost by collapsing the two games between a pair into a single 4-point split.
The total score of team \(i\) is then
$$s_i=\sum_{j\ne i} a_{ij},$$
so automatically
$$0\le s_i\le 4(n-1)=V.$$
Since every unordered pair contributes exactly \(4\) points in total, the global sum is fixed:
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
Now look at the \(i\) weakest teams in the sorted list. Their internal matches already contribute
$$4\binom{i}{2}=2i(i-1)$$
points, so their prefix sum must satisfy
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$$
These inequalities are clearly necessary. The implementations rely on the standard score-sequence characterization for this 4-point pair model: after sorting, the total-sum condition and all prefix lower bounds are also sufficient. Because every integer split from \(0\) to \(4\) can be realized by two actual matches, counting valid score multisets is exactly counting sequences satisfying
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
Let \(D_i(v,t)\) be the number of nondecreasing prefixes \((s_1,\dots,s_i)\) such that the last value is \(v\), the prefix sum is \(t\), and every prefix of length at most \(i\) already satisfies the inequality from Step 2.
Equivalently, \(D_i(v,t)\) counts the legal partial score lists of length \(i\) with
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
The base layer is
$$D_1(v,v)=1\qquad(0\le v\le V),$$
because a one-term nondecreasing prefix is determined once its value is chosen. The final total \(S\) is enforced only at the end.
Suppose a legal prefix of length \(i-1\) ends at value \(u\) and has total \(t\). Appending a new value \(v\) keeps the sequence nondecreasing exactly when
$$u\le v.$$
The new total becomes \(t+v\), and the new prefix of length \(i\) is legal only if the \(i\)-th prefix bound is met:
$$t+v\ge 2i(i-1).$$
Therefore the recurrence is
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$$
with the understanding that states violating \(t+v\le S\) or the lower bound are discarded.
For fixed \(i\) and \(t\), the recurrence asks for many sums of the form \(\sum_{u=0}^{v}D_{i-1}(u,t)\). Those are prefix sums in the variable \(v\), so we can sweep \(v=0,1,\dots,V\) once and maintain
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t).$$
Then
$$D_i(v,t+v)=P_{i-1}(v,t).$$
This removes an extra factor from the transition cost: each state update becomes \(O(1)\) amortized instead of summing over all smaller last values from scratch.
At the end we only want full score lists whose total sum is exactly \(S\). The last score \(v\) may be anything between \(0\) and \(V\), so the answer is
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$$
This is exactly the quantity accumulated by the program.
With two teams there is only one pair, so exactly \(4\) total points are distributed. Here
$$V=4,\qquad S=4.$$
The sorted score sequences summing to \(4\) are
$$ (0,4),\qquad (1,3),\qquad (2,2). $$
All three satisfy the prefix condition for \(i=1\), which is trivial. They are also all realizable:
\((0,4)\) comes from two losses by one team, \((1,3)\) comes from one loss and one draw, and \((2,2)\) comes from two draws or one win each. Hence
$$F(2)=3,$$
matching the small checkpoint used by the implementation.
The C++, Python, and Java implementations never simulate individual matches. Instead, they count sorted score sequences directly. They precompute the fixed bounds \(V=4(n-1)\) and \(S=2n(n-1)\), then store one dynamic-programming layer for the current prefix length and one for the next prefix length.
Each layer is a flattened table indexed by the last chosen score \(v\) and the current prefix sum \(t\). For every prefix length \(i\), the implementation clears the next layer, computes the lower bound \(2i(i-1)\), and then loops over all possible previous totals \(t\). While scanning \(v=0\) to \(V\), it keeps a running cumulative count of all previous states whose last value is at most \(v\). Whenever the new total \(t+v\) is within range and satisfies the prefix inequality, that cumulative value is written into the next layer. After processing all \(i\), the implementation sums the states whose total is exactly \(S\) and returns the result modulo \(10^9+7\).
Let \(V=4(n-1)\) and \(S=2n(n-1)\). The outer loop runs over \(i=2,\dots,n\), and inside it the implementation scans every pair \((t,v)\) once. Therefore the running time is
$$O(nSV)=O(n^4).$$
Only two DP layers of size \((V+1)(S+1)\) are stored, so the memory usage is
$$O(SV)=O(n^3).$$
In einer Doppelrunde mit \(n\) Teams spielt jedes Paar zweimal gegeneinander. Ein Sieg bringt \(2\) Punkte, ein Unentschieden \(1\) Punkt für jedes Team und eine Niederlage \(0\) Punkte. Sei \(F(n)\) die Anzahl der verschiedenen Endpunkt-Multimengen, also der Endstände bis auf Permutation der Teamnamen. Gesucht ist \(F(100)\) modulo \(10^9+7\).
Wir schreiben die sortierten Endpunktzahlen als
$$s_1\le s_2\le \cdots \le s_n,$$
und setzen
$$V=4(n-1),\qquad S=2n(n-1).$$
Damit reduziert sich die Aufgabe darauf, die nicht fallenden ganzzahligen Folgen \((s_1,\dots,s_n)\) mit Turnierstruktur und Gesamtsumme \(S\) zu zählen.
Für ein geordnetes Paar verschiedener Teams \((i,j)\) bezeichne \(a_{ij}\) die Gesamtpunktzahl, die Team \(i\) aus den beiden Spielen gegen Team \(j\) holt. Dann gilt
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
Jeder Wert \(0,1,2,3,4\) ist in zwei gewöhnlichen Spielen wirklich erreichbar: zweimal verlieren, verlieren plus Remis, geteilte Siege oder zwei Remis, Remis plus Sieg, zweimal gewinnen. Deshalb geht keine Information verloren, wenn man die beiden Spiele eines Paares zu einer einzigen 4-Punkte-Aufteilung zusammenfasst.
Die Gesamtpunktzahl von Team \(i\) ist dann
$$s_i=\sum_{j\ne i} a_{ij},$$
also automatisch
$$0\le s_i\le 4(n-1)=V.$$
Da jedes ungeordnete Paar insgesamt genau \(4\) Punkte erzeugt, ist die Gesamtsumme fest:
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
Betrachtet man nun die \(i\) schwächsten Teams in der sortierten Liste, dann liefern ihre internen Spiele bereits
$$4\binom{i}{2}=2i(i-1)$$
Punkte. Daher muss ihre Präfixsumme erfüllen
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$$
Diese Ungleichungen sind offensichtlich notwendig. Die Implementierungen benutzen die Standardcharakterisierung von Score-Sequenzen für dieses 4-Punkte-Paarmodell: Nach der Sortierung sind die Bedingung an die Gesamtsumme und alle unteren Präfixschranken auch hinreichend. Weil jede ganzzahlige Aufteilung von \(0\) bis \(4\) durch zwei echte Spiele realisiert werden kann, zählt man also genau die Folgen mit
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
Sei \(D_i(v,t)\) die Anzahl der nicht fallenden Präfixe \((s_1,\dots,s_i)\), deren letzter Wert \(v\) ist, deren Präfixsumme \(t\) beträgt und deren Präfixe der Längen bis \(i\) bereits die Ungleichung aus Schritt 2 erfüllen.
Anders gesagt zählt \(D_i(v,t)\) die zulässigen partiellen Punktlisten der Länge \(i\) mit
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
Die Basisschicht lautet
$$D_1(v,v)=1\qquad(0\le v\le V),$$
denn ein eintermiges nicht fallendes Präfix ist festgelegt, sobald sein Wert gewählt ist. Die Endsumme \(S\) wird erst ganz am Schluss erzwungen.
Angenommen, ein zulässiges Präfix der Länge \(i-1\) endet mit \(u\) und hat Summe \(t\). Wenn man einen neuen Wert \(v\) anhängt, bleibt die Folge genau dann nicht fallend, wenn
$$u\le v.$$
Die neue Summe ist dann \(t+v\), und das neue Präfix der Länge \(i\) ist nur zulässig, wenn die \(i\)-te Präfixschranke erfüllt ist:
$$t+v\ge 2i(i-1).$$
Damit erhält man die Rekursion
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$$
wobei Zustände mit \(t+v>S\) oder unterhalb der Schranke verworfen werden.
Für feste \(i\) und \(t\) benötigt die Rekursion viele Summen der Form \(\sum_{u=0}^{v}D_{i-1}(u,t)\). Das sind Präfixsummen in der Variablen \(v\). Man kann also \(v=0,1,\dots,V\) einmal durchlaufen und dabei
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t)$$
fortlaufend pflegen. Dann gilt
$$D_i(v,t+v)=P_{i-1}(v,t).$$
Dadurch verschwindet ein zusätzlicher Faktor aus der Übergangskostenrechnung: Jede Aktualisierung kostet amortisiert nur \(O(1)\).
Am Ende interessieren nur vollständige Punktfolgen mit Gesamtsumme genau \(S\). Der letzte Wert \(v\) kann beliebig zwischen \(0\) und \(V\) liegen, also ist
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$$
Genau diese Größe akkumuliert das Programm.
Bei zwei Teams gibt es nur ein einziges Paar, also werden insgesamt genau \(4\) Punkte verteilt. Hier ist
$$V=4,\qquad S=4.$$
Die sortierten Punktfolgen mit Summe \(4\) sind
$$ (0,4),\qquad (1,3),\qquad (2,2). $$
Alle drei erfüllen die Präfixbedingung für \(i=1\), die trivial ist. Außerdem sind sie alle realisierbar:
\((0,4)\) entsteht durch zwei Niederlagen eines Teams, \((1,3)\) durch Niederlage plus Remis, und \((2,2)\) durch zwei Remis oder je einen Sieg. Also gilt
$$F(2)=3,$$
genau wie beim kleinen Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen simulieren keine einzelnen Spiele. Stattdessen zählen sie die sortierten Punktfolgen direkt. Zuerst werden die festen Schranken \(V=4(n-1)\) und \(S=2n(n-1)\) berechnet, danach wird eine DP-Schicht für die aktuelle Präfixlänge und eine zweite für die nächste Präfixlänge gespeichert.
Jede Schicht ist eine abgeflachte Tabelle über dem letzten gewählten Wert \(v\) und der aktuellen Präfixsumme \(t\). Für jede Präfixlänge \(i\) wird die nächste Schicht geleert, die Untergrenze \(2i(i-1)\) bestimmt und dann über alle möglichen bisherigen Summen \(t\) iteriert. Während \(v=0\) bis \(V\) durchlaufen wird, hält die Implementierung eine laufende kumulative Summe aller vorherigen Zustände mit letztem Wert höchstens \(v\). Immer wenn die neue Summe \(t+v\) im Bereich liegt und die Präfixungleichung erfüllt, wird dieser kumulative Wert in die nächste Schicht geschrieben. Nach allen \(i\) werden die Zustände mit Gesamtsumme genau \(S\) aufsummiert, und das Ergebnis wird modulo \(10^9+7\) zurückgegeben.
Mit \(V=4(n-1)\) und \(S=2n(n-1)\) läuft die äußere Schleife über \(i=2,\dots,n\), und im Inneren wird jedes Paar \((t,v)\) genau einmal betrachtet. Daher beträgt die Laufzeit
$$O(nSV)=O(n^4).$$
Gespeichert werden nur zwei DP-Schichten der Größe \((V+1)(S+1)\), also ist der Speicherbedarf
$$O(SV)=O(n^3).$$
\(n\) takımlı çift devreli bir ligde her takım çifti iki kez karşılaşır. Galibiyet \(2\) puan, beraberlik iki takıma da \(1\) puan, mağlubiyet \(0\) puan getirir. \(F(n)\), takım isimleri göz ardı edildiğinde oluşabilen farklı final puan çokluklarının sayısı olsun. Amaç \(F(100)\) değerini \(10^9+7\) modunda hesaplamaktır.
Sıralanmış toplam puanları
$$s_1\le s_2\le \cdots \le s_n,$$
şeklinde yazalım ve
$$V=4(n-1),\qquad S=2n(n-1)$$
tanımlarını yapalım. Böylece problem, turnuva koşullarından gelebilen ve toplamı \(S\) olan, küçükten büyüğe sıralı tamsayı dizilerini saymaya dönüşür.
Farklı iki takımın sıralı çifti \((i,j)\) için, \(a_{ij}\) değerini takım \(i\)'nin takım \(j\)'ye karşı oynadığı iki maçtan topladığı toplam puan olarak tanımlayalım. O zaman
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
\(0,1,2,3,4\) değerlerinin her biri iki normal maçla gerçekten elde edilebilir: iki mağlubiyet, mağlubiyet artı beraberlik, paylaşılan galibiyet ya da iki beraberlik, beraberlik artı galibiyet ve iki galibiyet. Dolayısıyla bir takım çiftinin iki maçını tek bir 4 puanlık paylaşım olarak düşünmek bilgi kaybına yol açmaz.
Takım \(i\)'nin toplam puanı
$$s_i=\sum_{j\ne i} a_{ij}$$
olur; bu yüzden otomatik olarak
$$0\le s_i\le 4(n-1)=V$$
sağlanır.
Her sırasız takım çifti toplamda tam \(4\) puan ürettiği için tüm ligin toplam puanı sabittir:
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
Şimdi sıralı listedeki en düşük puanlı \(i\) takıma bakalım. Bu takımlar kendi aralarındaki maçlardan zaten
$$4\binom{i}{2}=2i(i-1)$$
puan üretir. Bu nedenle önek toplamı
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n)$$
olmak zorundadır.
Bu eşitsizlikler açıkça gereklidir. Uygulamalar, bu 4 puanlı eşleşme modeli için standart skor-dizisi karakterizasyonunu kullanır: sıra küçükten büyüğe sabitlendikten sonra toplam puan koşulu ve tüm önek alt sınırları aynı zamanda yeterlidir. Çünkü \(0\) ile \(4\) arasındaki her tamsayı paylaşım iki gerçek maçla üretilebilir. Dolayısıyla saymamız gereken diziler tam olarak
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
koşullarını sağlayan dizilerdir.
\(D_i(v,t)\), son değeri \(v\) olan, önek toplamı \(t\) olan ve uzunluğu \(i\)'ye kadar olan tüm önekleri Adım 2'deki eşitsizliği sağlayan sıralı kısmi dizilerin sayısı olsun.
Yani \(D_i(v,t)\), şu koşulları sağlayan geçerli kısmi skor listelerini sayar:
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
Başlangıç katmanı
$$D_1(v,v)=1\qquad(0\le v\le V)$$
şeklindedir; çünkü tek elemanlı sıralı bir önek, değeri seçildiğinde tamamen belirlenmiş olur. Son toplam \(S\) koşulu ise yalnızca en sonda uygulanır.
Uzunluğu \(i-1\) olan geçerli bir önekin son değeri \(u\), toplamı da \(t\) olsun. Buna yeni bir \(v\) değeri eklersek, dizinin sıralı kalması için gerekli ve yeterli koşul
$$u\le v$$
olur. Yeni toplam \(t+v\)'dir ve uzunluğu \(i\) olan yeni önek ancak \(i\). önek alt sınırı sağlanıyorsa geçerlidir:
$$t+v\ge 2i(i-1).$$
Böylece geçiş denklemi
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t)$$
olur. \(t+v>S\) olan veya alt sınırı geçemeyen durumlar doğrudan elenir.
Sabit \(i\) ve \(t\) için geçişte sürekli \(\sum_{u=0}^{v}D_{i-1}(u,t)\) biçiminde toplamlar gerekir. Bunlar \(v\) değişkenine göre önek toplamlarıdır. Bu yüzden \(v=0,1,\dots,V\) boyunca tek bir tarama yapıp
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t)$$
değerini elde tutmak yeterlidir. O zaman
$$D_i(v,t+v)=P_{i-1}(v,t)$$
olur. Böylece her hücre güncellemesi amortize \(O(1)\) zamana iner.
Son aşamada yalnızca toplamı tam olarak \(S\) olan tam skor listeleri gerekir. Son değer \(v\), \(0\) ile \(V\) arasında herhangi bir şey olabilir. Bu yüzden cevap
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}$$
şeklindedir. Programın topladığı büyüklük tam olarak budur.
İki takım olduğunda sadece tek bir eşleşme çifti vardır ve toplam tam \(4\) puan dağıtılır. Bu durumda
$$V=4,\qquad S=4.$$
Toplamı \(4\) olan sıralı puan dizileri
$$ (0,4),\qquad (1,3),\qquad (2,2) $$
şeklindedir. Üçü de \(i=1\) için önemsiz olan önek koşulunu sağlar. Ayrıca üçü de gerçekten mümkündür:
\((0,4)\) bir takımın iki kez kaybetmesiyle, \((1,3)\) bir mağlubiyet ve bir beraberlikle, \((2,2)\) ise iki beraberlik veya takımların birer kez kazanmasıyla oluşur. Dolayısıyla
$$F(2)=3,$$
ve bu sonuç uygulamadaki küçük kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları tek tek maçları simüle etmez. Onun yerine sıralı puan dizilerini doğrudan sayarlar. Önce sabit sınırlar \(V=4(n-1)\) ve \(S=2n(n-1)\) hesaplanır; sonra mevcut önek uzunluğu için bir DP katmanı ve bir sonraki önek uzunluğu için ikinci bir katman tutulur.
Her katman, son seçilen puan \(v\) ile o ana kadarki önek toplamı \(t\) üzerinden indekslenen düzleştirilmiş bir tablodur. Her \(i\) için sonraki katman sıfırlanır, \(2i(i-1)\) alt sınırı hesaplanır ve tüm önceki toplamlar \(t\) üzerinde dönülür. \(v=0\)'dan \(V\)'ye taranırken, önceki katmandaki son değeri en fazla \(v\) olan tüm durumların kümülatif toplamı elde tutulur. Yeni toplam \(t+v\) aralıkta kaldığında ve önek eşitsizliğini sağladığında bu kümülatif sayı sonraki katmana yazılır. Bütün uzunluklar işlendiğinde toplamı tam \(S\) olan durumlar toplanır ve sonuç \(10^9+7\) modunda döndürülür.
\(V=4(n-1)\) ve \(S=2n(n-1)\) için dış döngü \(i=2,\dots,n\) boyunca çalışır; içte de her \((t,v)\) çifti bir kez işlenir. Bu yüzden zaman karmaşıklığı
$$O(nSV)=O(n^4)$$
olur. Yalnızca \((V+1)(S+1)\) boyutunda iki DP katmanı tutulduğu için bellek kullanımı
$$O(SV)=O(n^3)$$
seviyesindedir.
En una liga todos-contra-todos a doble vuelta con \(n\) equipos, cada pareja de equipos se enfrenta dos veces. Una victoria vale \(2\) puntos, un empate da \(1\) punto a cada equipo y una derrota vale \(0\). Sea \(F(n)\) el número de multiconjuntos finales de puntos distintos, es decir, los resultados finales identificando distribuciones que solo difieren por permutar las etiquetas de los equipos. El objetivo es calcular \(F(100)\) módulo \(10^9+7\).
Escribimos las puntuaciones finales ordenadas como
$$s_1\le s_2\le \cdots \le s_n,$$
y definimos
$$V=4(n-1),\qquad S=2n(n-1).$$
Así, todo el problema consiste en contar las sucesiones enteras no decrecientes \((s_1,\dots,s_n)\) que pueden aparecer en el torneo y cuya suma total es \(S\).
Para cada par ordenado de equipos distintos \((i,j)\), sea \(a_{ij}\) el número total de puntos que el equipo \(i\) obtiene en sus dos partidos contra el equipo \(j\). Entonces
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
Cada valor \(0,1,2,3,4\) es realmente posible en dos partidos normales: perder ambos, perder uno y empatar uno, repartirse una victoria cada uno o empatar ambos, empatar uno y ganar uno, o ganar ambos. Por tanto, comprimir los dos partidos entre una pareja en un único reparto de 4 puntos no pierde información.
La puntuación total del equipo \(i\) es
$$s_i=\sum_{j\ne i} a_{ij},$$
de modo que necesariamente
$$0\le s_i\le 4(n-1)=V.$$
Como cada pareja no ordenada aporta exactamente \(4\) puntos en total, la suma global queda fijada:
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
Ahora consideremos los \(i\) equipos más débiles en la lista ordenada. Solo sus partidos internos ya producen
$$4\binom{i}{2}=2i(i-1)$$
puntos, así que su suma prefijo debe cumplir
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$$
Estas desigualdades son claramente necesarias. Las implementaciones usan la caracterización estándar de secuencias de puntuación para este modelo de parejas con 4 puntos: una vez ordenada la sucesión, la condición de suma total y todas las cotas inferiores sobre prefijos también son suficientes. Como cualquier reparto entero de \(0\) a \(4\) puede realizarse mediante dos partidos reales, basta contar exactamente las sucesiones que satisfacen
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
Sea \(D_i(v,t)\) el número de prefijos no decrecientes \((s_1,\dots,s_i)\) cuyo último valor es \(v\), cuya suma parcial es \(t\) y cuyos prefijos de longitud hasta \(i\) ya satisfacen la desigualdad del Paso 2.
En otras palabras, \(D_i(v,t)\) cuenta las listas parciales válidas de longitud \(i\) con
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
La capa base es
$$D_1(v,v)=1\qquad(0\le v\le V),$$
porque un prefijo no decreciente de un solo término queda completamente determinado al elegir su valor. La suma final \(S\) solo se impone al final.
Supongamos que un prefijo válido de longitud \(i-1\) termina en \(u\) y tiene suma \(t\). Si añadimos un nuevo valor \(v\), la sucesión sigue siendo no decreciente exactamente cuando
$$u\le v.$$
La nueva suma pasa a ser \(t+v\), y el nuevo prefijo de longitud \(i\) solo es legal si satisface la cota del prefijo \(i\):
$$t+v\ge 2i(i-1).$$
Por tanto, la recurrencia es
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$$
entendiendo que los estados con \(t+v>S\) o por debajo de la cota se descartan.
Para \(i\) y \(t\) fijos, la recurrencia pide muchas sumas del tipo \(\sum_{u=0}^{v}D_{i-1}(u,t)\). Esas son sumas prefijo en la variable \(v\), así que basta recorrer \(v=0,1,\dots,V\) una sola vez manteniendo
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t).$$
Entonces
$$D_i(v,t+v)=P_{i-1}(v,t).$$
Con esto desaparece un factor adicional en el coste de la transición: cada actualización pasa a costar \(O(1)\) amortizado.
Al final solo interesan las listas completas cuya suma total sea exactamente \(S\). El último valor \(v\) puede ser cualquiera entre \(0\) y \(V\), de modo que la respuesta es
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$$
Esa es precisamente la cantidad que acumula el programa.
Con dos equipos solo existe una pareja, así que se reparten exactamente \(4\) puntos. En este caso
$$V=4,\qquad S=4.$$
Las secuencias ordenadas que suman \(4\) son
$$ (0,4),\qquad (1,3),\qquad (2,2). $$
Las tres satisfacen la condición de prefijo para \(i=1\), que es trivial. Además, las tres son realizables:
\((0,4)\) corresponde a dos derrotas de un equipo, \((1,3)\) a una derrota y un empate, y \((2,2)\) a dos empates o a una victoria para cada equipo. Por tanto
$$F(2)=3,$$
de acuerdo con la pequeña comprobación usada por la implementación.
Las implementaciones en C++, Python y Java no simulan los partidos individualmente. En lugar de eso cuentan directamente las secuencias ordenadas de puntuaciones. Primero calculan los límites fijos \(V=4(n-1)\) y \(S=2n(n-1)\), y luego mantienen una capa de programación dinámica para la longitud de prefijo actual y otra para la siguiente.
Cada capa se guarda como una tabla aplanada indexada por la última puntuación elegida \(v\) y la suma parcial actual \(t\). Para cada longitud \(i\), la implementación limpia la siguiente capa, calcula la cota inferior \(2i(i-1)\) y recorre todos los totales previos posibles \(t\). Mientras barre \(v=0\) hasta \(V\), mantiene una suma acumulada de todos los estados anteriores cuya última puntuación es como máximo \(v\). Siempre que el nuevo total \(t+v\) está dentro del rango y satisface la desigualdad de prefijo, ese valor acumulado se escribe en la capa siguiente. Después de procesar todos los \(i\), se suman los estados con total exacto \(S\) y se devuelve el resultado módulo \(10^9+7\).
Con \(V=4(n-1)\) y \(S=2n(n-1)\), el bucle exterior recorre \(i=2,\dots,n\), y dentro se visita cada par \((t,v)\) una sola vez. Por ello el tiempo total es
$$O(nSV)=O(n^4).$$
Solo se almacenan dos capas de tamaño \((V+1)(S+1)\), así que la memoria utilizada es
$$O(SV)=O(n^3).$$
在一个有 \(n\) 支队伍的双循环赛中，每一对队伍要交手两次。胜一场得 \(2\) 分，平局双方各得 \(1\) 分，负一场得 \(0\) 分。记 \(F(n)\) 为所有不同最终总分多重集合的数量，也就是说，如果两个结果只是在队伍标签的排列上不同，就视为同一种结果。题目要求计算 \(F(100)\bmod (10^9+7)\)。
把最终总分按从小到大排序，记为
$$s_1\le s_2\le \cdots \le s_n,$$
并设
$$V=4(n-1),\qquad S=2n(n-1).$$
这样一来，整个问题就变成了：有多少个非降整数序列 \((s_1,\dots,s_n)\) 既能来自这种赛制，又满足总和恰好等于 \(S\)。
对任意两个不同的队伍 \(i\) 与 \(j\)，设 \(a_{ij}\) 表示队伍 \(i\) 在和队伍 \(j\) 的两场比赛中一共拿到多少分。那么
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
这里的 \(0,1,2,3,4\) 每一个值都确实能由两场普通比赛实现出来：两负、负加平、一胜一负或两平、平加胜、两胜。因此，把两场比赛压缩成一个“总共 4 分如何在两队之间分配”的模型不会丢失任何与最终总分有关的信息。
于是队伍 \(i\) 的总分就是
$$s_i=\sum_{j\ne i} a_{ij},$$
从而自动得到
$$0\le s_i\le 4(n-1)=V.$$
由于每一对无序队伍总共一定贡献 \(4\) 分，所以全局总分被完全固定：
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
现在考虑排在最前面的 \(i\) 支弱队。它们彼此之间的比赛本身就已经贡献了
$$4\binom{i}{2}=2i(i-1)$$
分，因此这 \(i\) 个数的前缀和必须满足
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$$
这些不等式显然是必要条件。实现所依据的关键事实是：对于这种“每一对队伍总共分配 4 分”的模型，在排序之后，“总和固定”加上“所有前缀和下界”同时也是充分条件。原因在于，每个整数分配 \(0,1,2,3,4\) 都能回译成两场真实比赛，所以不存在额外的隐藏约束。于是我们真正要数的正是满足下列条件的序列：
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
设 \(D_i(v,t)\) 表示满足以下条件的非降前缀 \((s_1,\dots,s_i)\) 的个数：最后一个值等于 \(v\)，前缀和等于 \(t\)，并且所有长度不超过 \(i\) 的前缀都已经满足步骤 2 中的不等式。
换句话说，\(D_i(v,t)\) 统计的是长度为 \(i\) 的合法部分得分表，其中
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
初始层是
$$D_1(v,v)=1\qquad(0\le v\le V),$$
因为长度为 \(1\) 的非降前缀一旦指定其唯一的值，就被完全确定了。真正的总分约束 \(S\) 只在最后提取答案时才强制要求。
假设某个长度为 \(i-1\) 的合法前缀最后一个值是 \(u\)，当前总和是 \(t\)。如果我们在末尾追加一个新值 \(v\)，要保持非降顺序，充要条件就是
$$u\le v.$$
新的前缀和变为 \(t+v\)。与此同时，长度为 \(i\) 的新前缀还必须满足第 \(i\) 个前缀下界：
$$t+v\ge 2i(i-1).$$
因此递推关系是
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$$
当然，若 \(t+v>S\) 或者不满足下界，该状态就直接丢弃。
对固定的 \(i\) 和 \(t\) 而言，上式会反复用到 \(\sum_{u=0}^{v}D_{i-1}(u,t)\) 这样的部分和。这正是关于 \(v\) 的前缀和，因此可以按 \(v=0,1,\dots,V\) 扫描一遍，同时维护
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t).$$
于是有
$$D_i(v,t+v)=P_{i-1}(v,t).$$
这一步就是代码中的核心优化。原本每个状态都要再向前求和，现在只需在扫描过程中维护一个累计值，所以单次更新变成了摊还 \(O(1)\)。
最后我们只关心长度为 \(n\)、总和恰好等于 \(S\) 的完整序列。最后一个值 \(v\) 可以在 \(0\) 到 \(V\) 之间取任意值，因此
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$$
程序最终累加的正是这个表达式。
当 \(n=2\) 时，只有一对队伍，所以总共正好分配 \(4\) 分。此时
$$V=4,\qquad S=4.$$
总和为 \(4\) 的有序非降序列只有
$$ (0,4),\qquad (1,3),\qquad (2,2). $$
这三个序列都满足 \(i=1\) 时的前缀条件，而该条件本身是平凡的。它们也都确实可实现：
\((0,4)\) 对应一支队伍两场全败，\((1,3)\) 对应一负一平，\((2,2)\) 对应两平或者双方各赢一场。因此
$$F(2)=3,$$
这与实现中使用的小规模校验完全一致。
C++、Python 和 Java 的实现都没有去枚举具体比赛结果，而是直接计数排好序的总分序列。它们先计算固定边界 \(V=4(n-1)\) 与 \(S=2n(n-1)\)，然后维护两层动态规划数组：一层表示当前前缀长度，另一层表示下一步要写入的新层。
每一层都可以看成一个以“最后一个分数 \(v\)”和“当前前缀和 \(t\)”为坐标的表，只是为了效率被压平成一维数组。对每个前缀长度 \(i\)，实现会先清空下一层，算出下界 \(2i(i-1)\)，再遍历所有可能的旧总和 \(t\)。在固定 \(t\) 的情况下，它按 \(v=0\) 到 \(V\) 依次扫描，同时维护“上一层中最后一个值不超过 \(v\) 的所有状态数之和”。只要新的总和 \(t+v\) 没超界并且满足前缀约束，这个累计值就写入下一层对应的位置。全部长度处理完以后，把总和正好等于 \(S\) 的所有状态加起来，并对 \(10^9+7\) 取模。
设 \(V=4(n-1)\)、\(S=2n(n-1)\)。外层循环遍历 \(i=2,\dots,n\)，而在每一层里，所有 \((t,v)\) 组合都会被扫描一次。因此总时间复杂度为
$$O(nSV)=O(n^4).$$
由于只保留两层大小为 \((V+1)(S+1)\) 的动态规划表，空间复杂度为
$$O(SV)=O(n^3).$$
В двойном круговом турнире с \(n\) командами каждая пара команд играет два матча. Победа дает \(2\) очка, ничья дает каждой команде по \(1\) очку, поражение дает \(0\). Обозначим через \(F(n)\) число различных итоговых мультимножеств очков, то есть считаем два результата одинаковыми, если они отличаются только перестановкой названий команд. Нужно вычислить \(F(100)\) по модулю \(10^9+7\).
Отсортируем итоговые очки по неубыванию:
$$s_1\le s_2\le \cdots \le s_n,$$
и введем обозначения
$$V=4(n-1),\qquad S=2n(n-1).$$
Тогда задача сводится к подсчету неубывающих целочисленных последовательностей \((s_1,\dots,s_n)\), которые могут возникнуть в таком турнире и имеют суммарный вес \(S\).
Для упорядоченной пары различных команд \((i,j)\) обозначим через \(a_{ij}\) суммарное число очков, набранных командой \(i\) в двух матчах против команды \(j\). Тогда
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
Каждое значение \(0,1,2,3,4\) действительно достижимо двумя обычными матчами: два поражения, поражение плюс ничья, обмен победами или две ничьи, ничья плюс победа, две победы. Поэтому с точки зрения итоговых очков можно без потери информации заменить две игры между парой команд одним распределением 4 очков.
Тогда суммарный счет команды \(i\) равен
$$s_i=\sum_{j\ne i} a_{ij},$$
и автоматически выполняется
$$0\le s_i\le 4(n-1)=V.$$
Поскольку каждая неупорядоченная пара команд в сумме дает ровно \(4\) очка, глобальная сумма фиксирована:
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
Рассмотрим теперь \(i\) самых слабых команд в отсортированном списке. Только их внутренние матчи уже дают
$$4\binom{i}{2}=2i(i-1)$$
очков, поэтому их префиксная сумма обязана удовлетворять условию
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$$
Эти неравенства очевидно необходимы. Реализации используют стандартную характеристику score-sequence для такой 4-очковой модели пар: после сортировки условия на полную сумму и все нижние оценки префиксов оказываются также достаточными. Поскольку любое целое разбиение от \(0\) до \(4\) можно реализовать двумя реальными матчами, нам нужно считать в точности последовательности, удовлетворяющие
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
Пусть \(D_i(v,t)\) обозначает число неубывающих префиксов \((s_1,\dots,s_i)\), у которых последний элемент равен \(v\), сумма префикса равна \(t\), и каждый префикс длины не больше \(i\) уже удовлетворяет неравенству из шага 2.
Иначе говоря, \(D_i(v,t)\) считает допустимые частичные списки очков длины \(i\), для которых
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
Базовый слой имеет вид
$$D_1(v,v)=1\qquad(0\le v\le V),$$
потому что префикс из одного элемента полностью определяется выбором этого элемента. Ограничение на конечную сумму \(S\) накладывается только в самом конце.
Пусть допустимый префикс длины \(i-1\) оканчивается значением \(u\) и имеет сумму \(t\). Если дописать справа новое значение \(v\), то неубывание сохранится тогда и только тогда, когда
$$u\le v.$$
Новая сумма равна \(t+v\), а новый префикс длины \(i\) допустим только при выполнении нижней границы для \(i\)-го префикса:
$$t+v\ge 2i(i-1).$$
Следовательно, получаем рекуррентную формулу
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$$
при этом состояния с \(t+v>S\) или ниже допустимой границы просто отбрасываются.
При фиксированных \(i\) и \(t\) в рекуррентной формуле многократно появляются суммы вида \(\sum_{u=0}^{v}D_{i-1}(u,t)\). Это обычные префиксные суммы по переменной \(v\), поэтому можно один раз пройти \(v=0,1,\dots,V\) и поддерживать
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t).$$
Тогда
$$D_i(v,t+v)=P_{i-1}(v,t).$$
Именно эта идея используется в программе, чтобы каждое обновление выполнялось за амортизированное \(O(1)\), а не за отдельную сумму по всем меньшим последним значениям.
В конце нас интересуют только полные последовательности длины \(n\) с суммой ровно \(S\). Последнее значение \(v\) может быть любым от \(0\) до \(V\), поэтому
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$$
Именно эту величину программа и суммирует.
При \(n=2\) есть только одна пара команд, значит распределяется ровно \(4\) очка. Здесь
$$V=4,\qquad S=4.$$
Отсортированные последовательности, сумма которых равна \(4\), таковы:
$$ (0,4),\qquad (1,3),\qquad (2,2). $$
Все три удовлетворяют префиксному условию для \(i=1\), которое тривиально. Все три также реализуемы:
\((0,4)\) получается из двух поражений одной команды, \((1,3)\) — из поражения и ничьей, а \((2,2)\) — из двух ничьих или по одной победе у каждой команды. Следовательно,
$$F(2)=3,$$
что совпадает с малой проверкой в реализации.
Реализации на C++, Python и Java не перебирают отдельные матчи. Вместо этого они напрямую считают отсортированные последовательности очков. Сначала вычисляются фиксированные границы \(V=4(n-1)\) и \(S=2n(n-1)\), после чего хранится один слой динамики для текущей длины префикса и один слой для следующей.
Каждый слой хранится как уплощенная таблица, индексируемая последним выбранным значением \(v\) и текущей префиксной суммой \(t\). Для каждой длины \(i\) следующая таблица обнуляется, вычисляется нижняя граница \(2i(i-1)\), и затем перебираются все возможные прежние суммы \(t\). Пока программа сканирует \(v=0,1,\dots,V\), она поддерживает накопленное число всех состояний предыдущего слоя, у которых последний элемент не превосходит \(v\). Если новая сумма \(t+v\) не выходит за пределы и удовлетворяет префиксному ограничению, это накопленное значение записывается в следующий слой. После обработки всех длин суммируются состояния с общей суммой ровно \(S\), и результат возвращается по модулю \(10^9+7\).
При \(V=4(n-1)\) и \(S=2n(n-1)\) внешний цикл проходит по \(i=2,\dots,n\), а внутри один раз посещается каждая пара \((t,v)\). Поэтому время работы равно
$$O(nSV)=O(n^4).$$
Хранятся только два слоя размера \((V+1)(S+1)\), так что память составляет
$$O(SV)=O(n^3).$$
في دوري ذهاب وإياب يضم \(n\) فرق، يلتقي كل زوج من الفرق مرتين. الفوز يمنح \(2\) نقطة، والتعادل يمنح كل فريق \(1\) نقطة، والخسارة تمنح \(0\) نقطة. نرمز بـ \(F(n)\) إلى عدد متعددات المجموعات المختلفة للنقاط النهائية، أي إن نتيجتين تعدان متماثلتين إذا اختلفتا فقط في تبديل أسماء الفرق. المطلوب هو حساب \(F(100)\) بترديد \(10^9+7\).
لنرتب المجاميع النهائية تصاعديًا بالشكل
$$s_1\le s_2\le \cdots \le s_n,$$
ولنعرّف
$$V=4(n-1),\qquad S=2n(n-1).$$
عندها تتحول المسألة إلى عدّ جميع المتتاليات الصحيحة غير المتناقصة \((s_1,\dots,s_n)\) التي يمكن أن تنتج من هذه البطولة ويكون مجموعها الكلي مساويًا لـ \(S\).
لكل زوج مرتب من الفرق المختلفة \((i,j)\)، لنعرف \(a_{ij}\) بأنه مجموع النقاط التي يحصل عليها الفريق \(i\) من المباراتين أمام الفريق \(j\). عندئذٍ
$$a_{ij}\in\{0,1,2,3,4\},\qquad a_{ij}+a_{ji}=4.$$
وكل قيمة من \(0\) إلى \(4\) قابلة للتحقق فعلاً في مباراتين عاديتين: خسارتان، خسارة وتعادل، فوز لكل فريق أو تعادلان، تعادل وفوز، أو فوزان. لذلك فإن ضغط المباراتين بين كل زوج إلى عملية توزيع واحدة لـ \(4\) نقاط لا يضيّع أي معلومة تخص المجاميع النهائية.
ومن ثم فإن مجموع نقاط الفريق \(i\) يساوي
$$s_i=\sum_{j\ne i} a_{ij},$$
ومن هنا نحصل تلقائيًا على
$$0\le s_i\le 4(n-1)=V.$$
بما أن كل زوج غير مرتب من الفرق يساهم دائمًا بما مجموعه \(4\) نقاط، فإن المجموع الكلي ثابت ويساوي
$$\sum_{i=1}^{n} s_i = 4\binom{n}{2}=2n(n-1)=S.$$
لننظر الآن إلى أضعف \(i\) فرق في القائمة المرتبة. المباريات الداخلية بينها فقط تنتج أصلًا
$$4\binom{i}{2}=2i(i-1)$$
نقطة، ولذلك يجب أن يحقق مجموعها الابتدائي الشرط
$$\sum_{j=1}^{i} s_j \ge 2i(i-1)\qquad(1\le i\le n).$$
هذه المتراجحات ضرورية بوضوح. وتعتمد التطبيقات على الوصف القياسي لمتتاليات الدرجات في هذا النموذج ذي الأربع نقاط لكل زوج: بعد ترتيب المتتالية، يصبح شرط المجموع الكلي مع جميع الحدود الدنيا للبوادئ كافيًا أيضًا. وبما أن كل تقسيم صحيح من \(0\) إلى \(4\) يمكن تحقيقه بواسطة مباراتين فعليتين، فإن ما نعدّه بالضبط هو جميع المتتاليات التي تحقق
$$0\le s_1\le \cdots \le s_n\le V,\qquad \sum_{i=1}^{n}s_i=S,\qquad \sum_{j=1}^{i}s_j\ge 2i(i-1)\qquad(1\le i\le n).$$
لنعرّف \(D_i(v,t)\) على أنه عدد البوادئ غير المتناقصة \((s_1,\dots,s_i)\) التي يكون آخر عنصر فيها مساويًا لـ \(v\)، ويكون مجموعها الجزئي مساويًا لـ \(t\)، وتكون جميع بوادئها حتى الطول \(i\) محققة للمتراجحة الواردة في الخطوة 2.
أي أن \(D_i(v,t)\) يعد القوائم الجزئية الصالحة من الطول \(i\) التي تحقق
$$s_i=v,\qquad \sum_{j=1}^{i}s_j=t.$$
أما طبقة البداية فهي
$$D_1(v,v)=1\qquad(0\le v\le V),$$
لأن البادئة ذات العنصر الواحد تتحدد بالكامل بمجرد اختيار قيمتها. شرط المجموع النهائي \(S\) لا يُفرض إلا عند استخراج الجواب في النهاية.
افترض أن لدينا بادئة صالحة بطول \(i-1\) تنتهي بالقيمة \(u\) ومجموعها \(t\). إذا ألحقنا بها قيمة جديدة \(v\)، فإن بقاء الترتيب غير المتناقص يكافئ الشرط
$$u\le v.$$
ويصبح المجموع الجديد \(t+v\)، ولا تكون البادئة الجديدة ذات الطول \(i\) صالحة إلا إذا حققت حد البادئة رقم \(i\):
$$t+v\ge 2i(i-1).$$
وبالتالي نحصل على العلاقة العودية
$$D_i(v,t+v)=\sum_{u=0}^{v} D_{i-1}(u,t),$$
مع إسقاط أي حالة فيها \(t+v>S\) أو لا تحقق الحد الأدنى المطلوب.
عند تثبيت \(i\) و\(t\)، تتكرر في العلاقة السابقة مجاميع من الشكل \(\sum_{u=0}^{v}D_{i-1}(u,t)\). وهذه مجرد مجاميع بادئة بالنسبة للمتغير \(v\)، لذا يمكننا مسح \(v=0,1,\dots,V\) مرة واحدة مع الحفاظ على
$$P_{i-1}(v,t)=\sum_{u=0}^{v} D_{i-1}(u,t).$$
وعندها يصبح
$$D_i(v,t+v)=P_{i-1}(v,t).$$
وهذه هي الفكرة الأساسية في التحسين البرمجي: بدل إعادة جمع جميع القيم الأصغر من جديد في كل مرة، يكفي تحديث مجموع تراكمي واحد، فتغدو كلفة كل حالة \(O(1)\) بالقيمة المتوسطة.
في النهاية نهتم فقط بالمتتاليات الكاملة ذات الطول \(n\) والتي يكون مجموعها الكلي مساويًا تمامًا لـ \(S\). ويمكن أن تكون القيمة الأخيرة \(v\) أي عدد بين \(0\) و\(V\)، لذا فإن
$$F(n)=\sum_{v=0}^{V} D_n(v,S)\pmod{10^9+7}.$$
وهذه هي الكمية التي يجمعها البرنامج في النهاية.
عندما يكون \(n=2\)، لا يوجد إلا زوج واحد من الفرق، وبالتالي يتم توزيع \(4\) نقاط فقط. في هذه الحالة
$$V=4,\qquad S=4.$$
والمتتاليات المرتبة التي مجموعها \(4\) هي
$$ (0,4),\qquad (1,3),\qquad (2,2). $$
وكل واحدة منها تحقق شرط البادئة عند \(i=1\)، وهو شرط بسيط هنا. كما أن الثلاث كلها قابلة للتحقيق:
\((0,4)\) تنتج من خسارتين لفريق واحد، و\((1,3)\) من خسارة وتعادل، و\((2,2)\) من تعادلين أو من فوز لكل فريق. إذن
$$F(2)=3,$$
وهو نفس التحقق الصغير الذي تستخدمه العملية البرمجية.
تطبيقات C++ وPython وJava لا تحاكي المباريات فرديًا. بدلاً من ذلك، فهي تعدّ متتاليات النقاط المرتبة مباشرة. أولًا تحسب الحدود الثابتة \(V=4(n-1)\) و\(S=2n(n-1)\)، ثم تحتفظ بطبقة برمجة ديناميكية للطول الحالي للبادئة وطبقة ثانية للطول التالي.
كل طبقة مخزنة على شكل جدول مفلطح مفهرس بالقيمة الأخيرة \(v\) وبالمجموع الجزئي الحالي \(t\). ولكل طول \(i\)، تقوم الشيفرة بتصفير الطبقة التالية، ثم تحسب الحد الأدنى \(2i(i-1)\)، ثم تمر على جميع المجاميع السابقة الممكنة \(t\). وأثناء المسح على \(v=0\) حتى \(V\)، تحافظ على مجموع تراكمي لكل الحالات السابقة التي لا تتجاوز قيمتها الأخيرة \(v\). فإذا كان المجموع الجديد \(t+v\) ضمن المجال ويحقق متراجحة البادئة، تُكتب هذه القيمة التراكمية في الطبقة التالية. وبعد اكتمال جميع الأطوال، تُجمع الحالات التي يساوي مجموعها الكلي \(S\) ويُعاد الجواب بترديد \(10^9+7\).
إذا كان \(V=4(n-1)\) و\(S=2n(n-1)\)، فإن الحلقة الخارجية تمر على \(i=2,\dots,n\)، وداخلها يُمسح كل زوج \((t,v)\) مرة واحدة. لذا يكون الزمن الكلي
$$O(nSV)=O(n^4).$$
وبما أن المخزن هو طبقتان فقط بحجم \((V+1)(S+1)\)، فإن استهلاك الذاكرة يساوي
$$O(SV)=O(n^3).$$