The sequence is defined by
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
From the first \(n\) terms \(S_n=(s_0,s_1,\dots,s_{n-1})\), two players alternately take either the leftmost or the rightmost remaining term. Both players are optimal and want to maximize their own final total. Let \(G(n)\) denote the first player's total. The implementations verify the checkpoints
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
A direct dynamic program on all intervals would be far too expensive for large \(n\), so the solution compresses the game mathematically before using the eventual periodicity of the recurrence.
The solution has three layers. First, rewrite the game in terms of score difference instead of absolute totals. Second, compress local peaks, which turns the sequence into a much simpler reduced form. Third, use the fact that the modular recurrence eventually becomes periodic, so large \(n\) can be handled by evaluating only a small calibration prefix and one full aligned cycle block.
For any finite sequence \(X=(x_1,\dots,x_m)\), let \(D(X)\) be the optimal score difference
$$D(X)=\text{(first player's total)}-\text{(second player's total)}.$$
If the current player chooses the left end, the opponent then faces \((x_2,\dots,x_m)\); if the current player chooses the right end, the opponent then faces \((x_1,\dots,x_{m-1})\). Therefore
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
with \(D(\varnothing)=0\).
If \(\Sigma(X)=x_1+\cdots+x_m\), then the first player's score on \(X\) is
$$F(X)=\frac{\Sigma(X)+D(X)}{2}.$$
So for \(S_n\) it is enough to compute the ordinary sum and the optimal difference \(D(S_n)\).
Consider three consecutive values \((a,b,c)\) with \(b\ge a\) and \(b\ge c\). For a two-term game we have
$$D(a,b)=b-a,\qquad D(b,c)=b-c.$$
Substituting those into the recurrence for three terms gives
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$$
So whenever the middle term is a local maximum, the triple behaves, from the viewpoint of score difference, exactly like the single value \(a-b+c\). The implementations scan from left to right, keep a reduced stack, and repeatedly apply this identity to the rightmost triple until no such peak remains.
This is the key compression step: many terms disappear, but the optimal difference of the processed prefix stays unchanged.
After all possible reductions, every interior term is strictly smaller than at least one neighbor. That means the reduced sequence has no local maxima. Such a sequence must be monotone or have a single valley: it can go down and later go up, but it cannot go up and then down without creating a removable peak.
For a valley-shaped sequence, the larger of the two exposed ends is always an optimal move. Once that larger end is removed, the remaining sequence is still valley-shaped, so the same reasoning applies again.
Therefore, if the reduced sequence is \(w_1,\dots,w_t\), then the optimal difference is obtained by the greedy alternating sum produced by repeatedly taking the larger end:
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
Combining this with the original unreduced total sum yields \(G(n)\).
The update rule uses arithmetic modulo \(10^9+7\), so every term lies in a finite set. Because the next value depends only on the current value, the sequence must eventually repeat a state and then continue periodically forever.
Write \(p\) for the length of the nonrepeating prefix and \(c\) for the cycle length. Then
$$s_{k+c}=s_k\qquad\text{for all }k\ge p.$$
If \(n\) is not very large, evaluating the explicit prefix is sufficient. For huge \(n\), however, we must exploit the periodic tail without constructing all \(n\) terms.
Assume \(n>p\), and let
$$r=(n-p)\bmod c.$$
Take the anchor prefix consisting of the first \(p+r\) terms. This stops at a fixed phase inside the cycle. Now append the next full cycle starting from exactly that same phase. That extra block has length \(c\), ends at the same phase where it started, and therefore puts the reduced game state back into the same structural position.
Let \(A_r\) be the first-player score of the anchor prefix, and let \(B_r\) be the first-player score after appending one such full aligned cycle block. Because every additional aligned full cycle starts and ends at the same phase, each one contributes the same increment \(B_r-A_r\). If
$$k=\frac{n-(p+r)}{c},$$
then the score is affine in the number of full blocks:
$$G(n)=A_r+k(B_r-A_r).$$
This is the acceleration that makes \(n=10^8\) feasible.
The first four terms are
$$0,\ 45,\ 2070,\ 4284945.$$
They are strictly increasing, so no local-peak reduction occurs. On such a sequence, the larger exposed end is always taken first, so the alternating difference is
$$D(S_4)=4284945-2070+45-0=4282920.$$
The total sum is
$$\Sigma(S_4)=0+45+2070+4284945=4287060.$$
Hence
$$G(4)=\frac{4287060+4282920}{2}=4284990,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations first generate sequence values until the first repeated state appears. A hash table maps each encountered value to its first position, which immediately yields the preperiod length and the cycle length.
To evaluate a concrete finite prefix, the implementation performs one pass over the terms. During that pass it accumulates the ordinary sum and simultaneously maintains the reduced stack obtained by repeatedly collapsing rightmost local peaks. After the scan, a two-pointer pass over the ends of the reduced structure computes the greedy alternating difference.
For large \(n\), the implementation evaluates only two calibration inputs: the anchor prefix and the anchor prefix followed by one aligned full cycle block. Their difference is the fixed gain per additional full cycle, so the final result is recovered by one multiplication and one addition rather than by simulating the whole sequence.
Let \(L=p+c\) be the number of generated terms needed to detect the first repeat. Cycle detection costs \(O(L)\) time and \(O(L)\) memory. Evaluating a concrete prefix of length at most \(p+2c\) is also linear, because each term is pushed once and can be removed by the reduction at most once. Thus the full method runs in \(O(p+c)\) time and uses \(O(p+c)\) memory, instead of \(O(n)\).
Die Folge ist definiert durch
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
Aus den ersten \(n\) Termen \(S_n=(s_0,s_1,\dots,s_{n-1})\) spielen zwei Spieler ein Enden-Spiel: In jedem Zug wird entweder der linke oder der rechte Randwert genommen. Beide spielen optimal und maximieren ihre eigene Endsumme. Sei \(G(n)\) die Summe des ersten Spielers. Die Implementierungen prüfen die Kontrollwerte
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
Ein direktes Intervall-DP wäre für große \(n\) viel zu teuer. Deshalb komprimiert die Lösung zuerst die Spielstruktur und nutzt danach die Periodizität der modularen Rekursion.
Die Methode hat drei Ebenen. Zuerst formuliert man das Spiel über die optimale Punktedifferenz statt über die absoluten Summen. Danach werden lokale Gipfel wegkomprimiert; dadurch entsteht eine stark vereinfachte reduzierte Folge. Zum Schluss nutzt man, dass die rekursiv erzeugte Folge ab einem gewissen Punkt periodisch wird, sodass für große \(n\) nur ein kurzer Kalibrierabschnitt und ein kompletter ausgerichteter Zyklusblock ausgewertet werden müssen.
Für eine endliche Folge \(X=(x_1,\dots,x_m)\) sei \(D(X)\) die optimale Differenz
$$D(X)=\text{(Summe des ersten Spielers)}-\text{(Summe des zweiten Spielers)}.$$
Wählt der aktuelle Spieler links, dann spielt der Gegner optimal auf \((x_2,\dots,x_m)\). Wählt er rechts, dann spielt der Gegner optimal auf \((x_1,\dots,x_{m-1})\). Also gilt
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
mit \(D(\varnothing)=0\).
Bezeichnet \(\Sigma(X)=x_1+\cdots+x_m\) die Gesamtsumme, dann ist die Summe des ersten Spielers
$$F(X)=\frac{\Sigma(X)+D(X)}{2}.$$
Für \(S_n\) genügt es daher, die gewöhnliche Summe und die optimale Differenz \(D(S_n)\) effizient zu bestimmen.
Betrachte drei aufeinanderfolgende Werte \((a,b,c)\) mit \(b\ge a\) und \(b\ge c\). Für zwei Werte gilt
$$D(a,b)=b-a,\qquad D(b,c)=b-c.$$
Setzt man das in die Dreier-Rekursion ein, erhält man
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$$
Ist also der mittlere Wert ein lokales Maximum, dann verhält sich das Tripel für die Punktedifferenz genau wie der Einzelwert \(a-b+c\). Die Implementierungen lesen die Folge von links nach rechts ein, halten einen reduzierten Stapel und wenden diese Identität wiederholt auf das rechte Ende an, bis kein solcher Gipfel mehr existiert.
Damit verschwinden viele Werte, ohne dass sich die optimale Differenz des bereits verarbeiteten Präfixes ändert.
Nach allen möglichen Reduktionen ist jeder innere Term kleiner als mindestens einer seiner Nachbarn. Die reduzierte Folge hat also keine lokalen Maxima. Solch eine Folge ist monoton oder besitzt genau eine Talform: sie darf erst fallen und später steigen, aber nicht erst steigen und dann wieder fallen, denn das würde einen entfernbaren Gipfel erzeugen.
Für eine talförmige Folge ist das größere der beiden freiliegenden Enden immer ein optimaler Zug. Nach dem Entfernen dieses Endes bleibt wieder eine talförmige Folge übrig, also greift dasselbe Argument induktiv erneut.
Ist die reduzierte Folge \(w_1,\dots,w_t\), dann ergibt sich die optimale Differenz als alternierende Greedy-Summe, die durch wiederholtes Wählen des größeren Endes entsteht:
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
Zusammen mit der unreduzierten Gesamtsumme erhält man daraus \(G(n)\).
Die Aktualisierung erfolgt modulo \(10^9+7\), also liegen alle Werte in einer endlichen Menge. Da der nächste Wert nur vom aktuellen abhängt, muss irgendwann ein bereits gesehener Zustand wieder auftreten; danach läuft die Folge periodisch weiter.
Sei \(p\) die Länge des nichtperiodischen Anfangsstücks und \(c\) die Zykluslänge. Dann gilt
$$s_{k+c}=s_k\qquad\text{für alle }k\ge p.$$
Für kleine \(n\) genügt die explizite Auswertung des benötigten Präfixes. Für sehr große \(n\) muss jedoch der periodische Schwanz ohne vollständige Konstruktion ausgenutzt werden.
Nehmen wir \(n>p\) und setzen
$$r=(n-p)\bmod c.$$
Betrachte das Ankerpräfix aus den ersten \(p+r\) Termen. Es endet an einer festen Phase innerhalb des Zyklus. Hängt man nun genau den nächsten vollen Zyklus an, beginnend an derselben Phase, so hat dieser Zusatzblock Länge \(c\), endet wieder in derselben Phase und bringt den reduzierten Spielzustand in dieselbe strukturelle Lage zurück.
Sei \(A_r\) die Summe des ersten Spielers auf dem Ankerpräfix und \(B_r\) die Summe nach dem Anhängen eines solchen vollen ausgerichteten Zyklusblocks. Jeder weitere ausgerichtete volle Zyklus liefert dann denselben Zuwachs \(B_r-A_r\). Mit
$$k=\frac{n-(p+r)}{c}$$
folgt die affine Formel
$$G(n)=A_r+k(B_r-A_r).$$
Genau diese Beobachtung macht Werte der Größenordnung \(10^8\) handhabbar.
Die ersten vier Werte lauten
$$0,\ 45,\ 2070,\ 4284945.$$
Die Folge ist streng wachsend, daher tritt keine lokale Gipfelreduktion auf. Beim Enden-Spiel wird also immer zuerst das größere sichtbare Ende genommen, und die alternierende Differenz ist
$$D(S_4)=4284945-2070+45-0=4282920.$$
Die Gesamtsumme ist
$$\Sigma(S_4)=0+45+2070+4284945=4287060.$$
Damit ergibt sich
$$G(4)=\frac{4287060+4282920}{2}=4284990,$$
genau der Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst Folgenglieder, bis erstmals ein bereits gesehener Zustand wieder erscheint. Eine Hashtabelle speichert zu jedem Wert seine erste Position und liefert damit sofort Vorperiode und Periodenlänge.
Zur Auswertung eines konkreten endlichen Präfixes wird einmal linear über die Werte gelaufen. Dabei wird einerseits die gewöhnliche Summe akkumuliert und andererseits der reduzierte Stapel gepflegt, auf dem lokale Gipfel am rechten Rand sofort zusammengezogen werden. Anschließend bestimmt ein Zwei-Zeiger-Durchlauf über die beiden Enden dieser reduzierten Struktur die alternierende Greedy-Differenz.
Für große \(n\) werden nur zwei Kalibrierfälle berechnet: das Ankerpräfix und das Ankerpräfix plus ein voller ausgerichteter Zyklusblock. Deren Differenz ist der feste Gewinn pro weiterem vollen Zyklus, sodass statt einer vollständigen Simulation nur noch eine Multiplikation und eine Addition nötig sind.
Sei \(L=p+c\) die Anzahl erzeugter Werte bis zum ersten Wiederauftreten. Die Zykluserkennung benötigt \(O(L)\) Zeit und \(O(L)\) Speicher. Auch die Auswertung eines konkreten Präfixes der Länge höchstens \(p+2c\) ist linear, weil jeder Term genau einmal auf den Stapel gelegt und höchstens einmal wieder durch Reduktion entfernt wird. Insgesamt läuft die Methode also in \(O(p+c)\) Zeit bei \(O(p+c)\) Speicher statt in \(O(n)\).
Dizi şu bağıntıyla tanımlanır:
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
İlk \(n\) terimden oluşan \(S_n=(s_0,s_1,\dots,s_{n-1})\) dizisinde iki oyuncu sırayla ya soldaki ya da sağdaki ucu seçer. Her iki oyuncu da kusursuz oynar ve kendi toplamını en büyük yapmak ister. Birinci oyuncunun toplamı \(G(n)\) ile gösterilsin. Uygulamalar şu kontrol değerlerini doğrular:
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
Bütün aralıklar üzerinde klasik bir dinamik program büyük \(n\) için fazla pahalıdır. Bu yüzden çözüm önce oyunun matematiksel yapısını sıkıştırır, sonra da modüler tekrarın getirdiği çevrimi kullanır.
Yöntem üç katmandan oluşur. Önce mutlak skor yerine skor farkı üzerinden düşünürüz. Sonra yerel tepe noktalarını eşdeğer tek değerlere indirgeriz; böylece dizi çok daha basit bir indirgenmiş biçime dönüşür. Son olarak, üretilen dizinin bir süre sonra çevrime girmesini kullanarak büyük \(n\) için yalnızca kısa bir sabitleme öneki ve faza hizalı tek bir tam çevrim bloğunu değerlendiririz.
Sonlu bir \(X=(x_1,\dots,x_m)\) dizisi için \(D(X)\), en iyi oyunda oluşan fark olsun:
$$D(X)=\text{(birinci oyuncunun toplamı)}-\text{(ikinci oyuncunun toplamı)}.$$
Sıradaki oyuncu soldan alırsa rakibi \((x_2,\dots,x_m)\) üzerinde oynar; sağdan alırsa rakibi \((x_1,\dots,x_{m-1})\) üzerinde oynar. Bu yüzden
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
ve \(D(\varnothing)=0\) olur.
\(\Sigma(X)=x_1+\cdots+x_m\) toplamını yazarsak, birinci oyuncunun skoru
$$F(X)=\frac{\Sigma(X)+D(X)}{2}$$
şeklindedir. Dolayısıyla \(S_n\) için yapılması gereken şey, toplamı ve \(D(S_n)\) farkını hızlı hesaplamaktır.
\((a,b,c)\) ardışık üçlüsünde \(b\ge a\) ve \(b\ge c\) olsun. İki eleman için
$$D(a,b)=b-a,\qquad D(b,c)=b-c$$
olur. Bunu üç elemanlı bağıntıya koyarsak
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c$$
elde edilir. Yani ortadaki terim yerel maksimumsa, bu üçlü skor farkı açısından tam olarak tek değer \(a-b+c\) gibi davranır. Uygulamalar soldan sağa ilerler, indirgenmiş bir yığın tutar ve sağ uçtaki üçlü böyle bir tepe oluşturduğu sürece bu özdeşliği tekrar tekrar uygular.
Böylece çok sayıda terim silinir ama işlenmiş öneğin optimal farkı değişmez.
Bütün mümkün indirgemelerden sonra içte kalan her eleman komşularının en az birinden küçüktür. Yani indirgenmiş dizide iç yerel maksimum yoktur. Böyle bir dizi ya monoton olur ya da tek bir vadi biçimindedir: önce azalabilir, sonra artabilir; fakat artıp sonra azalırsa ortada yeniden kaldırılabilecek bir tepe oluşurdu.
Vadi biçimli bir dizide görünen iki uçtan büyük olanı seçmek her zaman optimaldir. Bu uç kaldırıldığında kalan kısım yine vadi biçimli olur; dolayısıyla aynı mantık adım adım devam eder.
İndirgenmiş dizi \(w_1,\dots,w_t\) ise optimal fark, büyük ucu tekrar tekrar seçerek oluşan işaret dönüşümlü toplamdır:
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
Bunu özgün toplamla birleştirince \(G(n)\) bulunur.
Güncelleme işlemi \(10^9+7\) modunda yapıldığı için tüm değerler sonlu bir kümenin içindedir. Bir sonraki değer yalnızca mevcut değere bağlı olduğundan, dizi sonunda daha önce görülen bir duruma geri dönmek zorundadır; o andan sonra da sonsuza kadar çevrimli gider.
Başlangıçtaki çevrimsiz kısmın uzunluğuna \(p\), çevrim uzunluğuna \(c\) diyelim. O zaman
$$s_{k+c}=s_k\qquad\text{tüm }k\ge p\text{ için}$$
geçerlidir. Küçük \(n\) için gerekli öneği doğrudan üretmek yeterlidir; çok büyük \(n\) için ise çevrimli kuyruğu tümüyle kurmadan kullanmak gerekir.
\(n>p\) olduğunu varsayalım ve
$$r=(n-p)\bmod c$$
tanımını yapalım. İlk \(p+r\) terimden oluşan bir sabitleme öneği alalım. Bu önek çevrim içinde belirli bir fazda biter. Şimdi tam olarak bu fazdan başlayan bir tam çevrim bloğu ekleyelim. Bu ek bloğun uzunluğu \(c\)'dir, yine aynı fazda biter ve indirgenmiş oyun durumunu yapısal olarak aynı noktaya geri getirir.
Bu sabitleme öneğinin birinci oyuncu skoru \(A_r\), bir tam hizalı çevrim bloğu eklendikten sonraki skor ise \(B_r\) olsun. Her yeni tam hizalı çevrim aynı artışı, yani \(B_r-A_r\) farkını verir. Eğer
$$k=\frac{n-(p+r)}{c}$$
ise skor doğrusal-affin biçimde büyür:
$$G(n)=A_r+k(B_r-A_r).$$
\(10^8\) ölçeğindeki girdi bunun sayesinde hesaplanabilir hale gelir.
İlk dört terim
$$0,\ 45,\ 2070,\ 4284945$$
şeklindedir. Dizi sıkı biçimde arttığı için yerel tepe indirgemesi oluşmaz. Uçlardan alma oyununda büyük uç her tur seçilir ve işaret dönüşümlü fark
$$D(S_4)=4284945-2070+45-0=4282920$$
olur. Toplam ise
$$\Sigma(S_4)=0+45+2070+4284945=4287060$$
olduğundan
$$G(4)=\frac{4287060+4282920}{2}=4284990$$
elde edilir; bu da kontrol değeriyle tam uyumludur.
C++, Python ve Java uygulamaları önce ilk tekrar eden durum ortaya çıkana kadar diziyi üretir. Görülen her değer için ilk konumu bir karma tabloya yazıldığı için çevrim öncesi uzunluk ve çevrim uzunluğu doğrudan bulunur.
Belirli bir sonlu öneği değerlendirmek için uygulama terimler üzerinden tek geçiş yapar. Bu geçişte normal toplam birikir ve aynı anda sağ uçta yerel tepe gördükçe bunları birleştiren indirgenmiş yığın korunur. Tarama bitince iki uç üzerinde çalışan iki işaretçi, büyük ucu sırayla seçerek işaret dönüşümlü farkı hesaplar.
Büyük \(n\) için tüm önek maddeselleştirilmez. Bunun yerine yalnızca sabitleme öneği ve bu öneğe fazı aynı olan bir tam çevrim bloğu eklenmiş hali değerlendirilir. Bu iki skor arasındaki fark, kalan her tam çevrim için sabit katkıdır; böylece sonuç tam simülasyon yerine tek bir çarpma ve toplama ile bulunur.
\(L=p+c\), ilk tekrarın bulunması için üretilen terim sayısı olsun. Çevrim tespiti \(O(L)\) zaman ve \(O(L)\) bellek ister. Uzunluğu en fazla \(p+2c\) olan somut bir öneğin değerlendirilmesi de lineerdir; çünkü her terim yığına bir kez eklenir ve en fazla bir kez indirgeme ile silinir. Sonuç olarak tüm yöntem \(O(p+c)\) zamanda ve \(O(p+c)\) bellekte çalışır; \(O(n)\) tam simülasyon gerekmez.
La sucesión está definida por
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
Con los primeros \(n\) términos \(S_n=(s_0,s_1,\dots,s_{n-1})\), dos jugadores toman alternativamente el término más a la izquierda o el más a la derecha. Ambos juegan de forma óptima y quieren maximizar su suma final. Denotemos por \(G(n)\) la suma del primer jugador. Las implementaciones verifican los puntos de control
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
Un programa dinámico directo sobre todos los intervalos sería demasiado costoso para valores grandes de \(n\). Por eso la solución primero comprime la estructura matemática del juego y luego aprovecha que la recurrencia modular acaba siendo periódica.
La idea tiene tres niveles. Primero se reescribe el juego en términos de diferencia de puntuación en lugar de totales absolutos. Después se eliminan picos locales, lo que transforma la secuencia en una forma reducida mucho más simple. Finalmente se usa la periodicidad eventual de la recurrencia para tratar valores grandes de \(n\) con solo un prefijo de calibración y un bloque cíclico completo alineado.
Para una secuencia finita \(X=(x_1,\dots,x_m)\), sea \(D(X)\) la diferencia óptima
$$D(X)=\text{(suma del primer jugador)}-\text{(suma del segundo jugador)}.$$
Si el jugador actual toma el extremo izquierdo, el oponente juega sobre \((x_2,\dots,x_m)\); si toma el derecho, el oponente juega sobre \((x_1,\dots,x_{m-1})\). Por tanto,
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
con \(D(\varnothing)=0\).
Si \(\Sigma(X)=x_1+\cdots+x_m\), entonces la puntuación del primer jugador es
$$F(X)=\frac{\Sigma(X)+D(X)}{2}.$$
Así que para \(S_n\) basta con calcular la suma total y la diferencia óptima \(D(S_n)\).
Consideremos tres valores consecutivos \((a,b,c)\) con \(b\ge a\) y \(b\ge c\). Para dos términos se tiene
$$D(a,b)=b-a,\qquad D(b,c)=b-c.$$
Al sustituir esto en la recurrencia de tres términos, obtenemos
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$$
Por lo tanto, cuando el término central es un máximo local, el triple se comporta, desde el punto de vista de la diferencia óptima, exactamente como el valor único \(a-b+c\). Las implementaciones recorren la secuencia de izquierda a derecha, mantienen una pila reducida y aplican repetidamente esta identidad sobre el triple del extremo derecho mientras siga existiendo un pico de ese tipo.
Muchos términos desaparecen, pero la diferencia óptima del prefijo procesado no cambia.
Después de todas las reducciones posibles, cada término interior es menor que al menos uno de sus vecinos. Eso significa que la secuencia reducida no tiene máximos locales. Una secuencia así es monótona o tiene una sola forma de valle: puede bajar y luego subir, pero no subir y después bajar sin crear un pico reducible.
En una secuencia con forma de valle, siempre es óptimo elegir el mayor de los dos extremos visibles. Tras retirar ese extremo, la secuencia restante sigue teniendo forma de valle, así que el mismo argumento se aplica por inducción.
Si la secuencia reducida es \(w_1,\dots,w_t\), la diferencia óptima queda dada por la suma alternada que produce esa estrategia codiciosa sobre los extremos:
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
Combinando esto con la suma total original se recupera \(G(n)\).
La actualización se hace módulo \(10^9+7\), de modo que todos los valores pertenecen a un conjunto finito. Como el siguiente término depende solo del término actual, la sucesión debe repetir tarde o temprano un estado ya visto; a partir de ahí continúa periódicamente.
Llamemos \(p\) a la longitud del prefijo no periódico y \(c\) a la longitud del ciclo. Entonces
$$s_{k+c}=s_k\qquad\text{para todo }k\ge p.$$
Si \(n\) es pequeño, basta con construir el prefijo explícito. Si \(n\) es enorme, hay que explotar la cola periódica sin materializar los \(n\) términos completos.
Supongamos \(n>p\) y definamos
$$r=(n-p)\bmod c.$$
Tomamos como ancla el prefijo de longitud \(p+r\). Ese prefijo termina en una fase fija dentro del ciclo. A continuación añadimos el siguiente ciclo completo empezando exactamente en esa misma fase. Ese bloque extra tiene longitud \(c\), termina en la misma fase en la que empezó y deja el estado reducido del juego en la misma posición estructural.
Sea \(A_r\) la puntuación del primer jugador en el prefijo ancla, y sea \(B_r\) la puntuación después de añadir un bloque cíclico completo alineado. Cada bloque adicional del mismo tipo aporta entonces el mismo incremento \(B_r-A_r\). Si
$$k=\frac{n-(p+r)}{c},$$
la puntuación crece de forma afín:
$$G(n)=A_r+k(B_r-A_r).$$
Esa es la aceleración que permite llegar cómodamente a \(n=10^8\).
Los cuatro primeros términos son
$$0,\ 45,\ 2070,\ 4284945.$$
Como son estrictamente crecientes, no aparece ninguna reducción por pico local. En consecuencia, la estrategia de elegir el extremo mayor produce la diferencia alternada
$$D(S_4)=4284945-2070+45-0=4282920.$$
La suma total vale
$$\Sigma(S_4)=0+45+2070+4284945=4287060,$$
y por tanto
$$G(4)=\frac{4287060+4282920}{2}=4284990,$$
exactamente el valor de control utilizado por las implementaciones.
Las implementaciones en C++, Python y Java generan primero términos de la sucesión hasta encontrar la primera repetición de estado. Una tabla hash guarda la primera posición de cada valor y de ahí se obtienen directamente la longitud del prefijo no periódico y la longitud del ciclo.
Para evaluar un prefijo finito concreto, la implementación hace una sola pasada. En esa pasada acumula la suma ordinaria y, al mismo tiempo, mantiene la pila reducida que resulta de colapsar picos locales en el extremo derecho. Al terminar, un recorrido con dos punteros sobre los extremos de la estructura reducida calcula la diferencia alternada codiciosa.
Para valores grandes de \(n\), no se construye todo el prefijo. Solo se evalúan dos casos de calibración: el prefijo ancla y el prefijo ancla más un bloque cíclico completo alineado. La diferencia entre ambos es la ganancia fija por cada ciclo adicional, así que el resultado final se obtiene con una multiplicación y una suma.
Sea \(L=p+c\) el número de términos necesarios para detectar la primera repetición. La detección del ciclo cuesta \(O(L)\) tiempo y \(O(L)\) memoria. Evaluar un prefijo concreto de longitud a lo sumo \(p+2c\) también es lineal, porque cada término entra una vez en la pila y puede desaparecer como mucho una vez por reducción. En conjunto, el método requiere \(O(p+c)\) tiempo y \(O(p+c)\) memoria, en lugar de \(O(n)\).
数列由下面的递推式给出：
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
取前 \(n\) 项形成序列 \(S_n=(s_0,s_1,\dots,s_{n-1})\)。两名玩家轮流从当前序列的最左端或最右端取走一个数，双方都采用最优策略，并且都希望自己的最终总和尽量大。记先手玩家得到的总和为 \(G(n)\)。实现中验证的检查点为
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
如果直接对所有区间做动态规划，规模一大就完全不可行。因此解法先对博弈本身做数学压缩，再利用该模递推最终进入循环这一事实，把超大的 \(n\) 变成一个很小的校准问题。
整个思路可以分成三层。第一层把“先手最终拿到多少”改写成“双方最优差值是多少”。第二层利用一个局部恒等式，把中间的局部峰值不断压缩成单个数，从而得到结构非常简单的约化序列。第三层利用递推序列最终周期化的性质，只计算一个锚定前缀和一个与其相位对齐的完整周期块，就能推出任意大的 \(n\) 的答案。
对于任意有限序列 \(X=(x_1,\dots,x_m)\)，定义 \(D(X)\) 为双方都最优时的得分差：
$$D(X)=\text{先手总分}-\text{后手总分}.$$
如果当前玩家取左端，那么对手接下来面对的是 \((x_2,\dots,x_m)\)；如果取右端，那么对手面对的是 \((x_1,\dots,x_{m-1})\)。因此有标准递推式
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
并且边界条件是 \(D(\varnothing)=0\)。
若记总和为 \(\Sigma(X)=x_1+\cdots+x_m\)，那么先手在序列 \(X\) 上的最终得分就是
$$F(X)=\frac{\Sigma(X)+D(X)}{2}.$$
这说明真正需要高效计算的是两个量：原始序列的普通总和，以及最优分差 \(D(S_n)\)。
考虑三个连续数 \((a,b,c)\)，并且满足 \(b\ge a\) 且 \(b\ge c\)，也就是中间项是一个局部峰值。对两个数的情形，分差显然是
$$D(a,b)=b-a,\qquad D(b,c)=b-c.$$
把它们代入三项情形的递推式，可以得到
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$$
也就是说，只要中间项不小于两边，这个三元组在“最优分差”的意义下，和单个数 \(a-b+c\) 完全等价。实现正是利用这个恒等式，从左到右扫描数据，并在一个约化栈的右端反复检查：只要最后三个数形成这样的局部峰值，就把它们压成一个新值。
这样做会删除很多项，但已经处理过的前缀在最优分差意义下保持不变。换句话说，压缩改变了表示形式，却没有改变博弈价值。
把所有可压缩的峰值都处理完以后，约化序列中的任何内部元素都不可能同时大于等于左右两个邻居。于是它不会再出现内部局部最大值。这种序列的形状非常受限：要么单调，要么先下降后上升，也就是至多只有一个“谷底”。
原因很简单。如果它先上升后下降，就会在拐点附近形成一个内部峰值，而这正是上一条规则可以继续压缩的情形，所以与“已经完全约化”矛盾。
对这种“谷形”序列，最优策略会大幅简化。当前玩家总是取两端里较大的那个就是最优的；取走之后，剩下的序列仍然保持谷形，因此同样的判断可以继续使用。于是如果约化序列记为 \(w_1,\dots,w_t\)，那么最优分差就是不断从两端取较大值时得到的交错和：
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
最后再与原始总和一起代入 \(F(X)=\frac{\Sigma(X)+D(X)}{2}\)，就得到先手得分。
递推是在模 \(10^9+7\) 的意义下进行的，所以每一项都只可能取有限个值。并且下一项完全由当前项决定，因此一旦某个值第二次出现，后面的发展就会与上次完全相同，从而进入循环。
记非周期前缀长度为 \(p\)，周期长度为 \(c\)。那么对所有 \(k\ge p\)，都有
$$s_{k+c}=s_k.$$
如果 \(n\) 不大，显式生成需要的前缀即可。但对于非常大的 \(n\)，关键在于只利用这一周期结构，而不是把前 \(n\) 项全部展开出来。
设 \(n>p\)，并定义
$$r=(n-p)\bmod c.$$
先取一个锚定前缀，它包含前 \(p+r\) 项。这样做的好处是：这个前缀恰好停在周期中的某个固定相位上。接下来再追加一个完整周期，但要求从同一个相位开始。这个追加块长度正好是 \(c\)，结束时又回到同一相位，因此它把约化过程带回到相同的结构状态。
设锚定前缀的先手得分为 \(A_r\)，锚定前缀再加上一个同相位完整周期块后的先手得分为 \(B_r\)。由于每多加一个这样的完整周期块，起点相位和终点相位都相同，所以它对约化状态的影响每次都一样，因而先手得分的增量恒为 \(B_r-A_r\)。令
$$k=\frac{n-(p+r)}{c},$$
那么总得分满足线性仿射公式
$$G(n)=A_r+k(B_r-A_r).$$
这一步正是把超大规模输入压缩成常数次有限计算的核心。
前四项是
$$0,\ 45,\ 2070,\ 4284945.$$
它们严格递增，所以不会触发局部峰值压缩。于是约化序列就是原序列本身。在这种情况下，最优策略就是每一步都取两端较大的那个，因此分差为
$$D(S_4)=4284945-2070+45-0=4282920.$$
原始总和为
$$\Sigma(S_4)=0+45+2070+4284945=4287060,$$
所以
$$G(4)=\frac{4287060+4282920}{2}=4284990,$$
恰好与实现中的检查点一致。
C++、Python 和 Java 实现首先不断生成递推项，直到第一次遇到重复状态。它们用哈希表记录每个值首次出现的位置，因此一旦重复出现，就能立刻得到非周期前缀长度和周期长度。
在计算某个具体有限前缀的得分时，实现只做一次线性扫描。在扫描过程中，一边累加原始总和，一边维护右端可继续压缩的约化栈。扫描完成后，再用双指针从约化结构的两端向中间推进，每一步都取较大的端点，从而得到前面数学部分所说的交错分差。
面对很大的 \(n\) 时，实现并不会把整段前缀都构造出来，而是只计算两个校准对象：锚定前缀，以及“锚定前缀加上一个同相位完整周期块”。这两个结果的差值就是每增加一个完整周期块所贡献的固定增量，最终答案只需一次乘法和一次加法即可得到。
设 \(L=p+c\) 为检测到第一次重复之前需要生成的项数。周期检测的时间复杂度是 \(O(L)\)，空间复杂度也是 \(O(L)\)。随后真正需要计算的有限输入长度最多只到 \(p+2c\)，而对这样一个前缀做约化和双端扫描仍然是线性的，因为每个元素只会入栈一次，并且至多被压缩删除一次。所以整体复杂度是 \(O(p+c)\) 时间和 \(O(p+c)\) 空间，而不是直接模拟前 \(n\) 项所需的 \(O(n)\)。
Последовательность задаётся рекуррентно формулой
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
Из первых \(n\) членов строится последовательность \(S_n=(s_0,s_1,\dots,s_{n-1})\). Два игрока по очереди берут либо левый, либо правый крайний элемент. Оба играют оптимально и максимизируют собственную итоговую сумму. Пусть \(G(n)\) обозначает сумму первого игрока. Реализации проверяют контрольные значения
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
Прямое динамическое программирование по всем отрезкам для больших \(n\) слишком дорого. Поэтому решение сначала сжимает игровую структуру, а затем использует тот факт, что последовательность по модулю со временем становится периодической.
Метод состоит из трёх идей. Сначала удобнее считать не абсолютный выигрыш первого игрока, а оптимальную разность очков. Затем локальные пики последовательно сворачиваются в эквивалентные одиночные значения, и последовательность принимает значительно более простую редуцированную форму. Наконец, периодичность хвоста позволяет заменить огромный префикс двумя небольшими калибровочными вычислениями.
Для любой конечной последовательности \(X=(x_1,\dots,x_m)\) обозначим через \(D(X)\) оптимальную разность
$$D(X)=\text{сумма первого игрока}-\text{сумма второго игрока}.$$
Если текущий игрок берёт левый конец, соперник затем играет на \((x_2,\dots,x_m)\). Если берётся правый конец, соперник играет на \((x_1,\dots,x_{m-1})\). Значит, выполняется рекурсия
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
а базовый случай равен \(D(\varnothing)=0\).
Если \(\Sigma(X)=x_1+\cdots+x_m\), то сумма первого игрока на \(X\) выражается как
$$F(X)=\frac{\Sigma(X)+D(X)}{2}.$$
Следовательно, для \(S_n\) достаточно эффективно вычислить обычную сумму и оптимальную разность \(D(S_n)\).
Рассмотрим тройку последовательных значений \((a,b,c)\), где \(b\ge a\) и \(b\ge c\). Для последовательности из двух элементов имеем
$$D(a,b)=b-a,\qquad D(b,c)=b-c.$$
Подставляя это в формулу для трёх элементов, получаем
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$$
Значит, если средний элемент является локальным максимумом, то вся тройка с точки зрения оптимальной разности полностью эквивалентна одному числу \(a-b+c\). Реализации читают значения слева направо, поддерживают редуцированный стек и многократно применяют это тождество к правому концу, пока там существует такой пик.
Тем самым можно удалить большое число элементов, не изменяя оптимальную разность уже обработанного префикса.
После всех возможных свёрток любой внутренний элемент редуцированной последовательности меньше хотя бы одного из соседей. Значит, внутренних локальных максимумов больше нет. Такая последовательность либо монотонна, либо имеет форму одной впадины: она может сначала убывать, а затем возрастать, но не может сначала возрастать, а потом убывать, иначе снова возник бы устранимый пик.
Для последовательности такой формы оптимальный ход всегда состоит в выборе большего из двух открытых концов. После удаления этого конца оставшаяся часть снова имеет ту же форму, поэтому рассуждение повторяется по индукции.
Если редуцированная последовательность равна \(w_1,\dots,w_t\), то оптимальная разность вычисляется как знакопеременная жадная сумма, получаемая при последовательном выборе большего конца:
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
Соединив эту величину с исходной суммой, мы получаем \(G(n)\).
Переход выполняется по модулю \(10^9+7\), то есть все значения лежат в конечном множестве. Следующее значение зависит только от текущего, поэтому рано или поздно одно и то же состояние встретится повторно, после чего последовательность войдёт в цикл.
Обозначим через \(p\) длину допериодической части, а через \(c\) длину цикла. Тогда
$$s_{k+c}=s_k\qquad\text{для всех }k\ge p.$$
Если \(n\) невелико, можно просто построить нужный префикс. Для очень больших \(n\) нужно использовать периодический хвост без явного построения всех членов.
Пусть \(n>p\), и положим
$$r=(n-p)\bmod c.$$
Возьмём якорный префикс длины \(p+r\). Он заканчивается в фиксированной фазе цикла. Теперь добавим следующий полный цикл, начиная ровно с этой же фазы. Такой дополнительный блок имеет длину \(c\), заканчивается в той же фазе и возвращает редуцированное состояние игры в ту же структурную позицию.
Пусть \(A_r\) - сумма первого игрока на якорном префиксе, а \(B_r\) - сумма первого игрока после добавления одного полного согласованного циклического блока. Тогда каждый следующий такой блок добавляет одну и ту же величину \(B_r-A_r\). Если
$$k=\frac{n-(p+r)}{c},$$
то итоговая формула имеет аффинный вид
$$G(n)=A_r+k(B_r-A_r).$$
Именно это делает доступными значения масштаба \(10^8\).
Первые четыре члена равны
$$0,\ 45,\ 2070,\ 4284945.$$
Они строго возрастают, поэтому свёртка локальных пиков не применяется. Значит, оптимальная разность получается простым выбором большего конца на каждом ходу:
$$D(S_4)=4284945-2070+45-0=4282920.$$
Сумма всех четырёх чисел равна
$$\Sigma(S_4)=0+45+2070+4284945=4287060,$$
и потому
$$G(4)=\frac{4287060+4282920}{2}=4284990,$$
что точно совпадает с контрольной проверкой.
Реализации на C++, Python и Java сначала генерируют значения, пока не встретится первое повторное состояние. Хеш-таблица хранит первую позицию каждого значения, поэтому длины допериодической части и цикла определяются сразу после первого повтора.
Чтобы оценить конкретный конечный префикс, реализация делает один линейный проход. Во время этого прохода накапливается обычная сумма и одновременно поддерживается редуцированный стек, у которого на правом конце сразу сворачиваются локальные пики. Затем два указателя проходят по концам редуцированной структуры и вычисляют знакопеременную жадную разность.
Для больших \(n\) весь префикс не материализуется. Вычисляются только два калибровочных случая: якорный префикс и якорный префикс плюс один полный циклический блок в той же фазе. Их разность и есть фиксированная прибавка на каждый следующий полный цикл.
Пусть \(L=p+c\) - число сгенерированных значений до первого повтора. Поиск цикла требует \(O(L)\) времени и \(O(L)\) памяти. Оценка конкретного префикса длины не более \(p+2c\) тоже линейна, так как каждый элемент добавляется в стек один раз и может быть удалён свёрткой не более одного раза. Следовательно, весь метод работает за \(O(p+c)\) времени и использует \(O(p+c)\) памяти вместо прямого \(O(n)\).
تُعرَّف المتتالية بالعلاقة
$$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$$
نأخذ أول \(n\) حدًا فنحصل على المتتالية \(S_n=(s_0,s_1,\dots,s_{n-1})\). بعد ذلك يتناوب لاعبان على أخذ الحد الأيسر أو الحد الأيمن من الجزء المتبقي. كلاهما يلعب لعبًا مثاليًا ويحاول تعظيم مجموع نقاطه النهائي. لنرمز إلى مجموع اللاعب الأول بالرمز \(G(n)\). التحققات المستخدمة في التنفيذ هي
$$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$$
البرمجة الديناميكية المباشرة على جميع الفواصل مكلفة جدًا عندما يكون \(n\) كبيرًا. لذلك يعتمد الحل على ضغط البنية الرياضية للعبة أولًا، ثم على استغلال حقيقة أن المتتالية المولدة بتكرار معياري تصبح دورية في النهاية.
تقوم الفكرة على ثلاث طبقات. أولًا نعيد صياغة اللعبة بدلالة فرق النقاط بدلًا من المجموع المطلق. ثانيًا نحذف القمم المحلية بتحويلها إلى قيم مفردة مكافئة، فينتج عن ذلك تسلسل مختزل أبسط بكثير. ثالثًا نستفيد من أن الذيل يصبح دوريًا، فنكتفي بحساب بادئة مرجعية قصيرة وكتلة دورية كاملة مصفوفة على الطور نفسه.
لكل متتالية منتهية \(X=(x_1,\dots,x_m)\)، نعرّف \(D(X)\) على أنه فرق النقاط الأمثل:
$$D(X)=P_1(X)-P_2(X).$$
إذا أخذ اللاعب الحالي الطرف الأيسر، فإن الخصم سيلعب على \((x_2,\dots,x_m)\). وإذا أخذ الطرف الأيمن، فإن الخصم سيلعب على \((x_1,\dots,x_{m-1})\). لذلك نحصل على العلاقة
$$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$$
مع الشرط الابتدائي \(D(\varnothing)=0\).
إذا كانت \(\Sigma(X)=x_1+\cdots+x_m\) هي المجموع الكلي، فإن نتيجة اللاعب الأول على \(X\) تساوي
$$F(X)=\frac{\Sigma(X)+D(X)}{2}.$$
إذًا يكفي لنا في الحالة \(S_n\) أن نحسب المجموع العادي وفرق النقاط الأمثل \(D(S_n)\).
لننظر إلى ثلاثية متتالية \((a,b,c)\) بحيث \(b\ge a\) و\(b\ge c\)، أي إن العنصر الأوسط يمثل قمة محلية. في حالة عنصرين فقط لدينا
$$D(a,b)=b-a,\qquad D(b,c)=b-c.$$
وبتعويض ذلك في صيغة الثلاثة عناصر نحصل على
$$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$$
هذا يعني أن الثلاثية، ما دام العنصر الأوسط فيها أكبر أو مساويًا للطرفين، تكافئ تمامًا القيمة المفردة \(a-b+c\) من حيث فرق النقاط الأمثل. لذلك تقوم التطبيقات بالمسح من اليسار إلى اليمين، وتحافظ على مكدس مختزل، وتطبق هذه الهوية مرارًا على الثلاثية الأخيرة ما دامت تشكل قمة محلية.
النتيجة هي اختفاء كثير من الحدود، مع بقاء قيمة اللعبة على البادئة المعالجة كما هي.
بعد تنفيذ جميع الاختزالات الممكنة، لا يعود هناك عنصر داخلي أكبر أو مساويًا لكل من جاريه. لذلك يصبح التسلسل المختزل بلا قمم داخلية. وهذا يفرض شكلًا بسيطًا جدًا: إما أن يكون رتيبًا، أو يهبط ثم يصعد مرة واحدة، أي على هيئة وادٍ واحد.
إذا كان التسلسل على شكل وادٍ، فإن أخذ الطرف الأكبر بين الطرفين الظاهرين يكون دائمًا حركة مثلى. وبعد إزالة ذلك الطرف تبقى متتالية لها الشكل نفسه، فيمكن تكرار الحجة بالاستقراء.
وعليه، إذا كانت المتتالية المختزلة هي \(w_1,\dots,w_t\)، فإن فرق النقاط الأمثل يعطى بالمجموع المتناوب الناتج من اختيار الطرف الأكبر في كل مرة:
$$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$$
وبضم هذا الفرق إلى المجموع الأصلي نحصل على \(G(n)\).
لأن التحديث يتم بترديد \(10^9+7\)، فإن جميع القيم تنتمي إلى مجموعة منتهية. وبما أن الحد التالي يعتمد فقط على الحد الحالي، فلا بد أن تتكرر حالة سابقة في وقت ما، وعندها تدخل المتتالية في دورة.
لنرمز بطول المقدمة غير الدورية إلى \(p\)، وبطول الدورة إلى \(c\). عندئذ
$$s_{k+c}=s_k\qquad (k\ge p).$$
إذا كان \(n\) صغيرًا، يكفي توليد البادئة المطلوبة صراحة. أما إذا كان \(n\) ضخمًا، فيجب استخدام هذا الذيل الدوري من دون بناء جميع الحدود حتى الموضع \(n\).
افترض أن \(n>p\)، ولنعرف
$$r=(n-p)\bmod c.$$
نأخذ بادئة مرجعية طولها \(p+r\). هذه البادئة تنتهي عند طور محدد داخل الدورة. ثم نضيف بعدها دورة كاملة تبدأ من الطور نفسه. هذه الكتلة الإضافية طولها \(c\)، وتنتهي في الطور ذاته، ولذلك تعيد الحالة المختزلة للعبة إلى البنية نفسها.
إذا رمزنا إلى نتيجة اللاعب الأول على البادئة المرجعية بـ \(A_r\)، وإلى نتيجته بعد إضافة دورة كاملة مصطفة على الطور نفسه بـ \(B_r\)، فإن كل دورة إضافية من هذا النوع تضيف المقدار الثابت نفسه \(B_r-A_r\). وإذا كان
$$k=\frac{n-(p+r)}{c},$$
فإن النتيجة النهائية تحقق العلاقة الخطية التآلفية
$$G(n)=A_r+k(B_r-A_r).$$
وهذه هي النقطة التي تجعل قيمًا بحجم \(10^8\) ممكنة الحساب عمليًا.
أول أربعة حدود هي
$$0,\ 45,\ 2070,\ 4284945.$$
وهي متزايدة تمامًا، لذلك لا يحدث أي اختزال لقمة محلية. ومن ثم فإن الاستراتيجية المثلى تختار الطرف الأكبر في كل مرة، فيكون فرق النقاط
$$D(S_4)=4284945-2070+45-0=4282920.$$
أما المجموع الكلي فهو
$$\Sigma(S_4)=0+45+2070+4284945=4287060,$$
وبالتالي
$$G(4)=\frac{4287060+4282920}{2}=4284990,$$
وهو يطابق قيمة التحقق المذكورة في التنفيذ.
تبدأ تطبيقات C++ وPython وJava بتوليد حدود المتتالية إلى أن يظهر أول تكرار لحالة سابقة. ويُستخدم جدول تجزئة لتخزين أول موضع ظهر فيه كل عدد، ومن ذلك نستخرج مباشرة طول المقدمة غير الدورية وطول الدورة.
ولحساب نتيجة أي بادئة منتهية، تنفذ الشيفرة مرورًا خطيًا واحدًا على القيم. أثناء هذا المرور تجمع المجموع العادي وتحافظ في الوقت نفسه على المكدس المختزل الذي يضغط القمم المحلية في الجهة اليمنى فور ظهورها. وبعد انتهاء المرور، يستخدم التنفيذ مؤشرين على طرفي البنية المختزلة لاستخراج فرق النقاط المتناوب بالطريقة الجشعة.
أما عندما يكون \(n\) كبيرًا جدًا، فلا تُبنى البادئة كاملة. بدلًا من ذلك تُحسب حالتان فقط: البادئة المرجعية، ثم البادئة المرجعية نفسها بعد إضافة دورة كاملة مصطفة على الطور نفسه. الفرق بين النتيجتين هو الزيادة الثابتة لكل دورة إضافية كاملة.
إذا كان \(L=p+c\) هو عدد الحدود المولدة حتى أول تكرار، فإن اكتشاف الدورة يحتاج إلى \(O(L)\) زمنًا و\(O(L)\) ذاكرة. كما أن تقييم بادئة ملموسة طولها لا يتجاوز \(p+2c\) يبقى خطيًا أيضًا، لأن كل حد يدخل المكدس مرة واحدة ويزال بالاختزال مرة واحدة على الأكثر. لذلك تعمل الطريقة كلها بزمن \(O(p+c)\) وذاكرة \(O(p+c)\)، بدلًا من زمن \(O(n)\) للمحاكاة المباشرة.