Set \(s_0=290797\), define
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1,$$
and build the initial box-ball configuration as the infinite binary word
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
where \(1\) denotes an occupied box and \(0\) an empty box. One BBS turn moves each ball once, from left to right, to the nearest empty box on its right. After sufficiently many turns the configuration separates into stable occupied blocks with lengths \(L_1,\dots,L_m\), and the target quantity is
$$\sum_{j=1}^{m} L_j^2.$$
A standard invariant of the box-ball system is obtained by repeatedly deleting every adjacent pattern \(10\), with all deletions in a given round performed simultaneously and with the infinite tail of zeros already present on the right. Let \(N_r\) be the number of pairs deleted in elimination round \(r\).
The stable soliton lengths form the conjugate partition of these row counts. Equivalently,
$$N_r=\#\{j:L_j\ge r\}.$$
This identity is the key reduction: once the numbers \(N_r\) are known, the final occupied block lengths are known as well. The number of blocks of exact length \(r\) is therefore
$$N_r-N_{r+1}.$$
Geometrically, each final block of length \(\ell\) contributes one cell to each of the first \(\ell\) elimination rows, so the Ferrers diagram of the stable blocks has row lengths \(N_1,N_2,\dots\).
The implementations compute the elimination rounds without physically deleting symbols. Scan the binary word from left to right and keep a stack of unmatched occupied boxes. For each unmatched \(1\), store the largest elimination round of any matched pair nested inside it.
When an occupied box is read, push \(0\): at that moment no inner pair has been formed yet. When an empty box is read, it matches the most recent unmatched occupied box. If the stored maximum for that occupied box is \(d\), then all nested pairs vanish by round \(d\), so the outer pair becomes adjacent exactly one round later. Its elimination round is therefore
$$d+1.$$
After recording one more pair in round \(d+1\), this value must influence the nearest unmatched occupied box on the left, because that box now contains a nested structure whose maximum round may have increased. Thus the new value is propagated leftward by a max-update on the stack top.
This is the same recurrence as parenthesis matching with nesting depth: a pair disappears one round after everything strictly inside it has disappeared. At the end of the explicit word, the infinite zero tail is handled by draining the remaining stack in the same way.
The initial state is given as alternating run lengths, so the algorithm never materializes a full turn-by-turn BBS trajectory. For an occupied run of length \(\ell\), it pushes \(\ell\) zeros onto the stack. For an empty run of length \(\ell\), it performs up to \(\ell\) closures, stopping early if no unmatched occupied box remains.
Because every \(t_k\) lies in \(\{1,\dots,64\}\), each generated run costs only \(O(1)\) work, and the complete computation is just a streaming pass over the pseudorandom sequence.
Once the counts \(N_r\) are available, the sum of squares follows from the elementary identity
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
Summing over all stable blocks and exchanging the order of summation gives
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}.$$
Now substitute \(N_r=\#\{j:L_j\ge r\}\) to obtain the exact formula used by the implementations:
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
Consider the small run encoding \([2,2,2,1,2]\). It represents the infinite word
$$110011011\,0^\infty.$$
Repeated \(10\)-elimination removes \(3\) pairs in the first round, \(2\) in the second, and \(1\) in the third. Hence
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
The exact multiplicities are
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1,$$
so the stable occupied blocks have lengths \([1,2,3]\).
For the \(11\)-run sample from the problem statement, the stable lengths are \([1,3,10,24,51,75]\). Therefore \(N_r\) is piecewise constant:
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
Substituting these row counts into the boxed identity yields
$$\sum_{r\ge 1}(2r-1)N_r=8912,$$
which matches the sample value exactly.
The C++, Python, and Java implementations all stream the pseudorandom generator, alternate between occupied and empty runs, and maintain the same stack invariant. Every closure contributes one unit to the appropriate elimination round, and a final drain accounts for the infinite empty tail. After that single pass, the implementations evaluate \(\sum_{r\ge 1}(2r-1)N_r\) directly from the stored round counts. No explicit simulation of many BBS turns is performed.
Let \(B\) be the total number of occupied boxes in the encoded initial state. Each occupied box is pushed onto the stack once and popped once, so the total stack work is \(O(B)\). The round-count array has length equal to the largest elimination round encountered. Thus the memory usage is \(O(H+D)\), where \(H\) is the maximum active stack height and \(D\) the maximum round index; both are bounded by \(B\).
Because every run length satisfies \(1\le t_k\le 64\), we also have \(B=O(R)\) for \(R=10^7+1\) generated runs. Therefore the full algorithm is linear in the size of the encoded input and dramatically faster than any direct simulation over many BBS turns.
Setze \(s_0=290797\) und definiere
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1.$$
Daraus entsteht die anfängliche Box-Ball-Konfiguration als unendliches Binärwort
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
wobei \(1\) ein besetztes Feld und \(0\) ein leeres Feld bezeichnet. In einem BBS-Zug wird jeder Ball genau einmal von links nach rechts in das nächste leere Feld rechts von ihm bewegt. Nach genügend vielen Zügen zerfällt die Konfiguration in stabile besetzte Blöcke mit Längen \(L_1,\dots,L_m\), und gesucht ist
$$\sum_{j=1}^{m} L_j^2.$$
Eine Standardinvariante des Box-Ball-Systems erhält man, indem man wiederholt jedes benachbarte Muster \(10\) löscht. Alle Löschungen einer Runde werden gleichzeitig ausgeführt, und der unendliche Nullen-Schwanz rechts ist von Anfang an vorhanden. Sei \(N_r\) die Anzahl der in Eliminationsrunde \(r\) gelöschten Paare.
Die stabilen Solitonlängen bilden die konjugierte Partition dieser Zeilenlängen. Äquivalent dazu gilt
$$N_r=\#\{j:L_j\ge r\}.$$
Damit ist die wesentliche Reduktion erreicht: Kennt man alle \(N_r\), so kennt man auch die endgültigen Blocklängen. Die Anzahl der Blöcke mit exakter Länge \(r\) ist also
$$N_r-N_{r+1}.$$
Geometrisch liefert jeder Endblock der Länge \(\ell\) je eine Zelle in jeder der ersten \(\ell\) Eliminationszeilen; das Ferrers-Diagramm der stabilen Blöcke hat daher Zeilenlängen \(N_1,N_2,\dots\).
Die Implementierungen berechnen die Eliminationsrunden, ohne das Wort wirklich zu verkleinern. Man liest das Binärwort von links nach rechts und hält einen Stack nicht zugeordneter besetzter Felder. Zu jedem noch offenen \(1\)-Eintrag speichert man die größte Eliminationsrunde eines vollständig darin verschachtelten Paares.
Wird ein besetztes Feld gelesen, so wird \(0\) auf den Stack gelegt: Zu diesem Zeitpunkt existiert noch kein inneres Paar. Wird ein leeres Feld gelesen, so schließt es das zuletzt offene besetzte Feld. Ist der gespeicherte Maximalwert dort \(d\), dann verschwinden alle verschachtelten Paare spätestens in Runde \(d\), also wird das äußere Paar genau eine Runde später benachbart. Seine Eliminationsrunde ist daher
$$d+1.$$
Nachdem dieses Paar gezählt wurde, muss dieser Wert auf das nächste offene besetzte Feld links davon per Maximum übertragen werden, denn auch dessen innerer Maximalwert kann dadurch steigen.
Das ist genau dieselbe Rekursion wie bei Klammerpaaren mit Verschachtelung: Ein Paar verschwindet eine Runde nach allem, was strikt in seinem Inneren liegt. Am Ende des expliziten Wortes wird der unendliche Nullen-Schwanz dadurch behandelt, dass der verbleibende Stack vollständig geleert wird.
Der Anfangszustand ist bereits als alternierende Lauflängen codiert, daher muss keine vollständige BBS-Zeitentwicklung materialisiert werden. Für einen besetzten Lauf der Länge \(\ell\) werden \(\ell\) Nullen auf den Stack gelegt. Für einen leeren Lauf der Länge \(\ell\) werden bis zu \(\ell\) Abschlüsse ausgeführt, wobei frühzeitig abgebrochen wird, wenn kein offenes besetztes Feld mehr existiert.
Da stets \(t_k\in\{1,\dots,64\}\) gilt, kostet jeder erzeugte Lauf nur \(O(1)\) Arbeit. Die gesamte Rechnung ist also ein einziger Streaming-Durchlauf über die pseudorandom erzeugte Folge.
Sobald die Werte \(N_r\) vorliegen, folgt die Quadratsumme aus der elementaren Identität
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
Über alle stabilen Blöcke summiert und umgeordnet ergibt das
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}.$$
Mit \(N_r=\#\{j:L_j\ge r\}\) erhält man genau die im Programm verwendete Formel:
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
Betrachte zunächst die kleine Run-Length-Codierung \([2,2,2,1,2]\). Sie entspricht dem unendlichen Wort
$$110011011\,0^\infty.$$
Die wiederholte \(10\)-Elimination entfernt in der ersten Runde \(3\) Paare, in der zweiten \(2\) und in der dritten \(1\). Also gilt
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
Die exakten Multiplizitäten sind damit
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1,$$
also bestehen die stabilen besetzten Blöcke aus den Längen \([1,2,3]\).
Für das \(11\)-Run-Beispiel aus der Aufgabenstellung lauten die stabilen Längen \([1,3,10,24,51,75]\). Damit ist \(N_r\) stückweise konstant:
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
Einsetzen in die Box-Formel liefert
$$\sum_{r\ge 1}(2r-1)N_r=8912,$$
genau den Beispielwert.
Die C++-, Python- und Java-Implementierungen erzeugen die Pseudorandom-Folge fortlaufend, wechseln zwischen besetzten und leeren Läufen und pflegen dabei dieselbe Stack-Invariante. Jeder Abschluss erhöht den Zähler der passenden Eliminationsrunde um eins, und das abschließende Leeren des Stacks berücksichtigt den unendlichen leeren Schwanz. Danach wird \(\sum_{r\ge 1}(2r-1)N_r\) direkt aus den gespeicherten Rundenzahlen ausgewertet. Eine explizite Simulation vieler BBS-Züge findet nicht statt.
Sei \(B\) die Gesamtzahl besetzter Felder im kodierten Anfangszustand. Jedes besetzte Feld wird genau einmal auf den Stack gelegt und genau einmal wieder entfernt, also kostet die gesamte Stack-Arbeit \(O(B)\). Das Zählerarray für die Eliminationsrunden hat Länge gleich der größten tatsächlich auftretenden Runde. Damit beträgt der Speicherverbrauch \(O(H+D)\), wobei \(H\) die maximale aktive Stackhöhe und \(D\) der größte Rundindex ist; beide sind durch \(B\) beschränkt.
Da jede Lauflänge \(1\le t_k\le 64\) erfüllt und \(R=10^7+1\) Läufe erzeugt werden, gilt außerdem \(B=O(R)\). Das gesamte Verfahren ist somit linear in der Größe der kodierten Eingabe und erheblich schneller als jede direkte Simulation über viele BBS-Züge.
\(s_0=290797\) alınsın ve
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1$$
tanımlansın. Başlangıç kutu-top sistemi şu sonsuz ikili kelimeyle verilir:
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
burada \(1\) dolu kutuyu, \(0\) boş kutuyu gösterir. Bir BBS turunda her top soldan sağa doğru tam bir kez hareket eder ve sağındaki en yakın boş kutuya gider. Yeterince çok turdan sonra yapı, uzunlukları \(L_1,\dots,L_m\) olan kararlı dolu bloklara ayrılır. İstenen değer
$$\sum_{j=1}^{m} L_j^2$$
toplamıdır.
Box-ball sisteminin standart değişmezlerinden biri, bitişik her \(10\) desenini tekrar tekrar silerek elde edilir. Aynı turdaki silmeler eşzamanlı yapılır ve sağdaki sonsuz sıfır kuyruğu baştan beri mevcut kabul edilir. \(N_r\), eliminasyonun \(r\). turunda silinen çift sayısı olsun.
Kararlı soliton uzunlukları, bu satır sayılarının eşlenik partition'ını verir. Eşdeğer ifade şudur:
$$N_r=\#\{j:L_j\ge r\}.$$
Ana indirgeme budur: tüm \(N_r\) değerleri biliniyorsa, son dolu blok uzunlukları da bilinir. Tam uzunluğu \(r\) olan blok sayısı bu yüzden
$$N_r-N_{r+1}$$
olur. Ferrers diyagramı açısından bakılırsa, uzunluğu \(\ell\) olan her son blok ilk \(\ell\) satırın her birine bir hücre katkısı yapar; dolayısıyla satır uzunlukları tam olarak \(N_1,N_2,\dots\) olur.
Uygulamalar bu eliminasyon turlarını sembolleri gerçekten silmeden hesaplar. İkili kelime soldan sağa taranır ve henüz eşleşmemiş dolu kutular için bir yığın tutulur. Her açık \(1\) için, tamamen onun içinde kalan eşleşmiş çiftlerin en büyük eliminasyon turu saklanır.
Yeni bir dolu kutu görüldüğünde yığına \(0\) itilir; çünkü henüz içinde kapanmış bir çift yoktur. Boş kutu görüldüğünde ise en son açılmış dolu kutuyla eşleşir. Bu dolu kutu için saklanan en büyük değer \(d\) ise, içerideki tüm çiftler en geç \(d\). turda kaybolur; dıştaki çift tam bir tur sonra bitişik hale gelir. Bu nedenle onun eliminasyon turu
$$d+1$$
olur. Ardından bu değer soldaki en yakın açık dolu kutuya maksimum alınarak aktarılır; çünkü artık onun iç yapısındaki en büyük tur artmış olabilir.
Bu, iç içe parantezlerdeki aynı özyinelemeli kuraldır: bir çift, içinde kalan her şey kaybolduktan bir tur sonra yok olur. Açıkça yazılmış kelime bittiğinde, sağdaki sonsuz sıfır kuyruğu kalan yığını tamamen boşaltarak hesaba katılır.
Başlangıç durumu zaten art arda gelen koşu uzunluklarıyla verildiği için tam BBS evrimini oluşturmaya gerek yoktur. Uzunluğu \(\ell\) olan dolu bir koşu için yığına \(\ell\) adet sıfır itilir. Uzunluğu \(\ell\) olan boş koşu için en fazla \(\ell\) kapanış yapılır; açık dolu kutu kalmamışsa erken durulur.
Her \(t_k\) değeri \(\{1,\dots,64\}\) kümesinde olduğundan her koşunun maliyeti \(O(1)\) olur. Böylece tüm hesap, sözde rastgele diziyi akış halinde işleyen tek bir geçiştir.
\(N_r\) değerleri elde edildikten sonra kareler toplamı şu basit özdeşlikten gelir:
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
Bunu tüm kararlı bloklar üzerinde toplayıp toplamların yerini değiştirirsek
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}$$
elde edilir. Şimdi \(N_r=\#\{j:L_j\ge r\}\) yerine yazınca uygulamaların kullandığı tam formül çıkar:
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
Küçük bir örnek olarak \([2,2,2,1,2]\) koşu kodlamasını alalım. Bu, şu sonsuz kelimeye karşılık gelir:
$$110011011\,0^\infty.$$
Tekrarlı \(10\)-eliminasyon birinci turda \(3\), ikinci turda \(2\), üçüncü turda \(1\) çift siler. Yani
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
Buna göre tam uzunluk çoklukları
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1$$
olur ve kararlı dolu blok uzunlukları \([1,2,3]\) çıkar.
Problemdeki \(11\) koşuluk örnekte kararlı uzunluklar \([1,3,10,24,51,75]\) biçimindedir. Bu durumda \(N_r\) parça parça sabittir:
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
Bu sayılar kutudaki özdeşliğe yerleştirildiğinde
$$\sum_{r\ge 1}(2r-1)N_r=8912$$
elde edilir; bu da örnek değerle tam olarak uyuşur.
C++, Python ve Java uygulamaları sözde rastgele üreteci akış halinde işler, dolu ve boş koşular arasında dönüşümlü ilerler ve aynı yığın değişmezini korur. Her kapanış ilgili eliminasyon turu sayacını bir artırır; sonda yapılan yığın boşaltma işlemi de sonsuz boş kuyruğu hesaba katar. Bu tek geçiş tamamlandıktan sonra \(\sum_{r\ge 1}(2r-1)N_r\) doğrudan saklanan tur sayılarından hesaplanır. Çok sayıda BBS turunu tek tek simüle etmeye gerek yoktur.
\(B\), kodlanmış başlangıç durumundaki toplam dolu kutu sayısı olsun. Her dolu kutu yığına bir kez itilir ve bir kez çıkarılır; dolayısıyla toplam yığın işi \(O(B)\)'dir. Tur sayacı dizisinin uzunluğu, karşılaşılan en büyük eliminasyon turuna eşittir. Bu nedenle bellek kullanımı \(O(H+D)\) olur; burada \(H\) en büyük aktif yığın yüksekliği, \(D\) ise en büyük tur indeksidir. Her ikisi de \(B\) ile sınırlıdır.
Ayrıca her koşu uzunluğu \(1\le t_k\le 64\) olduğundan ve toplam \(R=10^7+1\) koşu üretildiğinden \(B=O(R)\) yazılabilir. Sonuç olarak yöntem, kodlanmış girdinin boyutunda lineerdir ve çok sayıda BBS turunu doğrudan simüle etmekten çok daha hızlıdır.
Tomamos \(s_0=290797\) y definimos
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1.$$
Con ello se construye la configuración inicial del sistema como la palabra binaria infinita
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
donde \(1\) significa caja ocupada y \(0\) caja vacía. En un turno del BBS cada bola se mueve exactamente una vez, de izquierda a derecha, hasta la caja vacía más cercana a su derecha. Tras suficientes turnos, la configuración se descompone en bloques ocupados estables de longitudes \(L_1,\dots,L_m\), y se pide calcular
$$\sum_{j=1}^{m} L_j^2.$$
Un invariante clásico del box-ball system se obtiene borrando repetidamente cada patrón adyacente \(10\). Todas las eliminaciones de una misma ronda se realizan simultáneamente y la cola infinita de ceros a la derecha se considera presente desde el inicio. Sea \(N_r\) el número de pares eliminados en la ronda \(r\).
Las longitudes de los solitones estables forman la partición conjugada de esos conteos por filas. De forma equivalente,
$$N_r=\#\{j:L_j\ge r\}.$$
Esta identidad es la reducción esencial: si conocemos todos los \(N_r\), entonces conocemos también las longitudes finales. El número de bloques de longitud exacta \(r\) es por tanto
$$N_r-N_{r+1}.$$
Geométricamente, cada bloque final de longitud \(\ell\) aporta una celda a cada una de las primeras \(\ell\) filas, así que el diagrama de Ferrers de los bloques estables tiene longitudes de fila \(N_1,N_2,\dots\).
Las implementaciones calculan las rondas de eliminación sin borrar símbolos de manera explícita. Se recorre la palabra binaria de izquierda a derecha y se mantiene una pila de cajas ocupadas que todavía no han sido emparejadas. Para cada \(1\) abierto se guarda la mayor ronda de eliminación de cualquier par completamente anidado en su interior.
Cuando aparece una caja ocupada, se apila un \(0\): en ese momento no existe ningún par interno. Cuando aparece una caja vacía, se empareja con la caja ocupada no cerrada más reciente. Si el máximo almacenado para esa caja era \(d\), entonces todos los pares internos desaparecen antes o en la ronda \(d\), de modo que el par exterior se vuelve adyacente exactamente una ronda después. Su ronda de eliminación es
$$d+1.$$
Tras contabilizar ese nuevo par, el valor debe propagarse hacia la izquierda mediante un máximo, porque la caja ocupada inmediatamente anterior ahora contiene una estructura interna cuyo máximo puede haber aumentado.
Es la misma recurrencia que en un emparejamiento de paréntesis con anidamiento: un par desaparece una ronda después de que haya desaparecido todo lo que estaba estrictamente dentro. Al terminar la palabra explícita, la cola infinita de ceros se maneja vaciando la pila restante.
El estado inicial ya viene dado como longitudes alternadas de runs, así que no hace falta materializar una historia completa del BBS. Para un run ocupado de longitud \(\ell\), se apilan \(\ell\) ceros. Para un run vacío de longitud \(\ell\), se realizan hasta \(\ell\) cierres, deteniéndose antes si ya no queda ninguna caja ocupada sin emparejar.
Como siempre se cumple \(t_k\in\{1,\dots,64\}\), cada run generado cuesta solo \(O(1)\), y el cálculo completo es una pasada en streaming sobre la sucesión pseudoaleatoria.
Una vez conocidos los valores \(N_r\), la suma de cuadrados se obtiene de la identidad elemental
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
Al sumar sobre todos los bloques estables e intercambiar el orden de la suma, se obtiene
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}.$$
Sustituyendo \(N_r=\#\{j:L_j\ge r\}\) llegamos a la fórmula exacta utilizada por las implementaciones:
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
Consideremos primero la codificación \([2,2,2,1,2]\). Representa la palabra infinita
$$110011011\,0^\infty.$$
La eliminación repetida de \(10\) borra \(3\) pares en la primera ronda, \(2\) en la segunda y \(1\) en la tercera. Por tanto,
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
Las multiplicidades exactas son
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1,$$
y las longitudes estables resultan ser \([1,2,3]\).
En la muestra de \(11\) runs del enunciado, las longitudes estables son \([1,3,10,24,51,75]\). Entonces \(N_r\) es constante por tramos:
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
Al sustituir estos valores en la identidad anterior, se obtiene
$$\sum_{r\ge 1}(2r-1)N_r=8912,$$
que coincide exactamente con el valor de la muestra.
Las implementaciones en C++, Python y Java generan la sucesión pseudoaleatoria en streaming, alternan entre runs ocupados y vacíos y mantienen el mismo invariante de pila. Cada cierre añade una unidad al contador de la ronda de eliminación correspondiente, y el vaciado final de la pila incorpora la cola infinita de cajas vacías. Terminada esa única pasada, la cantidad \(\sum_{r\ge 1}(2r-1)N_r\) se evalúa directamente a partir de los conteos almacenados. No se simulan muchos turnos del BBS de forma explícita.
Sea \(B\) el número total de cajas ocupadas en el estado inicial codificado. Cada caja ocupada se inserta una vez en la pila y se extrae una vez, así que el trabajo total de pila es \(O(B)\). El arreglo de conteos por ronda tiene longitud igual a la ronda máxima realmente alcanzada. Por ello, el uso de memoria es \(O(H+D)\), donde \(H\) es la altura máxima de la pila activa y \(D\) el mayor índice de ronda; ambos están acotados por \(B\).
Como además cada run satisface \(1\le t_k\le 64\) y se generan \(R=10^7+1\) runs, también se tiene \(B=O(R)\). En consecuencia, el método completo es lineal en el tamaño de la entrada codificada y mucho más eficiente que simular directamente una gran cantidad de turnos del BBS.
取 \(s_0=290797\)，并定义
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1.$$
初始 box-ball 配置可写成无限二进制串
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
其中 \(1\) 表示有球，\(0\) 表示空盒。一次 BBS 操作按从左到右的顺序让每个球恰好移动一次，移到其右侧最近的空盒中。经过足够多轮之后，系统会分解成稳定的连续占用块，其长度记为 \(L_1,\dots,L_m\)。目标是计算
$$\sum_{j=1}^{m} L_j^2.$$
Box-ball system 的一个标准不变量来自反复删除相邻的 \(10\) 模式。同一轮中的删除同时进行，并且右侧的无限零尾巴从一开始就存在。记 \(N_r\) 为第 \(r\) 轮消去的配对数。
稳定 soliton 的长度正好构成这些行计数的共轭分拆。等价地，
$$N_r=\#\{j:L_j\ge r\}.$$
这一步是核心化简：只要知道所有 \(N_r\)，最终块长就随之确定。长度恰好为 \(r\) 的稳定块个数因此等于
$$N_r-N_{r+1}.$$
从 Ferrers 图的角度看，长度为 \(\ell\) 的每个最终块都会向前 \(\ell\) 行各贡献一个单元格，所以稳定块的行长度正是 \(N_1,N_2,\dots\)。
实现并不会真的反复删除字符串中的字符。它从左到右扫描二进制串，并维护一个“尚未匹配的占用盒”栈。对每个尚未闭合的 \(1\)，栈里记录完全嵌套在它内部的已匹配对中，最大的消去轮数。
读到占用盒时，就把 \(0\) 压栈，因为此时内部还没有任何已完成的配对。读到空盒时，它会和最近的未匹配占用盒配对。如果该占用盒保存的最大值是 \(d\)，说明所有内部配对都会在第 \(d\) 轮之前消失，于是外层配对会在下一轮第一次变成相邻，所以它的消去轮数就是
$$d+1.$$
记录完这个配对之后，还要把这个值用取最大值的方式向左传播到下一个未匹配的占用盒，因为它所包围的内部结构最大轮数可能已经增加。
这与带嵌套的括号匹配是同一个递推：一个外层配对会在其内部所有内容全部消失后一轮被删除。显式给出的有限部分扫描结束后，通过清空剩余栈即可处理右侧无限零尾巴。
初始状态本来就是交替的 run-length 编码，因此不需要构造整条 BBS 演化轨迹。对长度为 \(\ell\) 的占用段，向栈中压入 \(\ell\) 个零；对长度为 \(\ell\) 的空段，最多执行 \(\ell\) 次闭合，如果此时已没有未匹配的占用盒，就提前停止。
由于每个 \(t_k\) 都落在 \(\{1,\dots,64\}\) 中，每个 run 的处理代价都是 \(O(1)\)。整个计算因此只是对伪随机序列的一次流式扫描。
得到 \(N_r\) 之后，平方和来自基本恒等式
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
对所有稳定块求和并交换求和顺序，可得
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}.$$
再代入 \(N_r=\#\{j:L_j\ge r\}\)，就得到实现中直接使用的公式：
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
先看一个小例子 \([2,2,2,1,2]\)。它对应的无限串是
$$110011011\,0^\infty.$$
反复执行 \(10\)-消去时，第一轮删去 \(3\) 对，第二轮删去 \(2\) 对，第三轮删去 \(1\) 对，因此
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
于是精确长度的重数为
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1,$$
所以稳定占用块长度就是 \([1,2,3]\)。
题目给出的 \(11\) 个 runs 的样例，其稳定块长度为 \([1,3,10,24,51,75]\)。因此 \(N_r\) 是分段常数：
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
把这些值代入上面的公式得到
$$\sum_{r\ge 1}(2r-1)N_r=8912,$$
与样例答案完全一致。
C++、Python 和 Java 实现都以流式方式生成伪随机 run 长度，在占用段与空段之间交替前进，并维护同一个栈不变量。每次闭合都会让对应消去轮数的计数加一，最后清空栈则负责处理右侧无限空盒尾巴。完成这一趟扫描后，实现直接根据保存的轮数计数计算 \(\sum_{r\ge 1}(2r-1)N_r\)。整个过程不需要逐轮模拟大量 BBS 演化。
设 \(B\) 为编码后的初始状态中球的总数。每个球只会入栈一次、出栈一次，因此总的栈操作是 \(O(B)\)。按轮计数的数组长度等于实际出现的最大消去轮数，所以内存复杂度为 \(O(H+D)\)，其中 \(H\) 是栈的最大活动高度，\(D\) 是最大轮编号；两者都不超过 \(B\)。
又因为每个 run 满足 \(1\le t_k\le 64\)，而总共有 \(R=10^7+1\) 个 runs，所以 \(B=O(R)\)。因此整个算法对编码输入规模是线性的，远快于显式模拟许多轮 BBS。
Положим \(s_0=290797\) и определим
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1.$$
Начальная конфигурация box-ball system задаётся бесконечным двоичным словом
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
где \(1\) означает занятую коробку, а \(0\) пустую. За один ход BBS каждый шар перемещается ровно один раз, слева направо, в ближайшую пустую коробку справа. После достаточно большого числа ходов конфигурация распадается на устойчивые занятые блоки длины \(L_1,\dots,L_m\). Требуется вычислить
$$\sum_{j=1}^{m} L_j^2.$$
Стандартный инвариант box-ball system получается так: мы многократно удаляем каждый соседний шаблон \(10\). Все удаления в рамках одного раунда выполняются одновременно, а бесконечный хвост нулей справа считается присутствующим с самого начала. Пусть \(N_r\) обозначает число пар, удалённых на \(r\)-м раунде.
Длины устойчивых солитонов образуют сопряжённое разбиение к этим длинам строк. Эквивалентная запись такова:
$$N_r=\#\{j:L_j\ge r\}.$$
Это и есть главное упрощение: зная все \(N_r\), мы автоматически знаем и финальные длины блоков. Число блоков точной длины \(r\) равно
$$N_r-N_{r+1}.$$
Геометрически каждый конечный блок длины \(\ell\) добавляет по одной клетке в каждую из первых \(\ell\) строк, поэтому Ferrers-диаграмма устойчивых блоков имеет длины строк \(N_1,N_2,\dots\).
Реализации вычисляют номера раундов, не удаляя символы буквально. Двоичное слово сканируется слева направо, а в стеке хранятся ещё не сопоставленные занятые клетки. Для каждой открытой единицы запоминается максимальный номер раунда среди всех пар, полностью вложенных внутрь неё.
Когда читается занятая клетка, в стек помещается \(0\): пока внутри неё нет ни одной готовой пары. Когда читается пустая клетка, она сопоставляется с последней не закрытой занятой клеткой. Если сохранённый максимум для этой клетки равен \(d\), то все внутренние пары исчезают не позднее раунда \(d\), значит внешняя пара станет соседней ровно на один раунд позже. Её номер равен
$$d+1.$$
После учёта этой пары значение нужно передать ближайшей открытой единице слева через операцию максимума, потому что максимальный номер вложенной структуры мог увеличиться и для неё.
Это та же рекурсия, что и для вложенных скобок: внешняя пара исчезает через один раунд после того, как исчезло всё строго внутри неё. После конца явной части слова бесконечный хвост нулей обрабатывается простым опустошением оставшегося стека.
Начальное состояние уже задано чередующимися длинами серий, поэтому строить полную историю BBS не нужно. Для занятой серии длины \(\ell\) алгоритм помещает в стек \(\ell\) нулей. Для пустой серии длины \(\ell\) он выполняет до \(\ell\) закрытий, останавливаясь раньше, если открытых занятых клеток больше нет.
Поскольку всегда \(t_k\in\{1,\dots,64\}\), каждая серия обрабатывается за \(O(1)\), а вся задача решается одним потоковым проходом по псевдослучайной последовательности.
Когда значения \(N_r\) уже известны, сумма квадратов следует из элементарной формулы
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
Суммируя по всем устойчивым блокам и меняя порядок суммирования, получаем
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}.$$
Подставляя \(N_r=\#\{j:L_j\ge r\}\), получаем точную формулу, которую используют реализации:
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
Рассмотрим маленький пример \([2,2,2,1,2]\). Он задаёт бесконечное слово
$$110011011\,0^\infty.$$
Повторная \(10\)-элиминация удаляет \(3\) пары в первом раунде, \(2\) во втором и \(1\) в третьем. Значит,
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
Точные кратности длин равны
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1,$$
поэтому устойчивые занятые блоки имеют длины \([1,2,3]\).
Для образца из \(11\) серий в условии финальные длины равны \([1,3,10,24,51,75]\). Тогда функция \(N_r\) кусочно постоянна:
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
Подстановка в формулу даёт
$$\sum_{r\ge 1}(2r-1)N_r=8912,$$
что точно совпадает с образцом.
Реализации на C++, Python и Java потоково генерируют псевдослучайные длины серий, чередуют занятые и пустые серии и поддерживают один и тот же стековый инвариант. Каждое закрытие увеличивает счётчик соответствующего раунда элиминации на единицу, а финальное опустошение стека учитывает бесконечный хвост пустых коробок. После этого единственного прохода величина \(\sum_{r\ge 1}(2r-1)N_r\) вычисляется напрямую из накопленных счётчиков. Никакой явной симуляции большого числа ходов BBS не требуется.
Пусть \(B\) обозначает общее число занятых коробок в закодированном начальном состоянии. Каждая занятая коробка один раз помещается в стек и один раз извлекается из него, так что суммарная стековая работа равна \(O(B)\). Массив счётчиков раундов имеет длину, равную максимальному реально встреченному раунду. Следовательно, память равна \(O(H+D)\), где \(H\) это максимальная активная высота стека, а \(D\) максимальный номер раунда; оба значения ограничены сверху числом \(B\).
Поскольку каждая длина серии удовлетворяет \(1\le t_k\le 64\), а число сгенерированных серий равно \(R=10^7+1\), получаем также \(B=O(R)\). Поэтому весь метод линеен по размеру закодированного входа и несравнимо эффективнее прямой симуляции большого количества ходов BBS.
نأخذ \(s_0=290797\) ونعرّف
$$s_{k+1}=s_k^2 \bmod 50515093,\qquad t_k=(s_k \bmod 64)+1.$$
عندئذ تصبح الحالة الابتدائية لنظام الصناديق والكرات هي الكلمة الثنائية اللانهائية
$$W=1^{t_0}0^{t_1}1^{t_2}0^{t_3}\cdots 1^{t_{10^7}}0^\infty,$$
حيث تمثل \(1\) صندوقاً مشغولاً و\(0\) صندوقاً فارغاً. في كل جولة من BBS تتحرك كل كرة مرة واحدة فقط، من اليسار إلى اليمين، إلى أقرب صندوق فارغ يقع على يمينها. وبعد عدد كاف من الجولات تتحلل البنية إلى كتل مشغولة مستقرة أطوالها \(L_1,\dots,L_m\)، والمطلوب حساب
$$\sum_{j=1}^{m} L_j^2.$$
هناك ثابت معروف في box-ball system يُستخرج عبر حذف كل ظهور متجاور للنمط \(10\) بشكل متكرر. جميع الحذوفات في الجولة الواحدة تُنفذ في الوقت نفسه، مع اعتبار ذيل لا نهائي من الأصفار على اليمين موجوداً منذ البداية. ولتكن \(N_r\) عدد الأزواج المحذوفة في الجولة \(r\).
أطوال السوليتونات المستقرة تعطي التقسيم المرافق لهذه الأعداد الصفية. وبصورة مكافئة:
$$N_r=\#\{j:L_j\ge r\}.$$
وهذه هي الفكرة الأساسية: إذا عرفنا جميع القيم \(N_r\)، فإن أطوال الكتل النهائية تصبح معلومة فوراً. ومن ثم فإن عدد الكتل ذات الطول الدقيق \(r\) يساوي
$$N_r-N_{r+1}.$$
هندسياً، كل كتلة نهائية طولها \(\ell\) تضيف خلية واحدة إلى كل واحد من الصفوف \(\ell\) الأولى، ولذلك فإن أطوال صفوف مخطط Ferrers هي بالضبط \(N_1,N_2,\dots\).
التنفيذ لا يحذف الرموز فعلياً. بدلاً من ذلك يتم مسح الكلمة الثنائية من اليسار إلى اليمين مع الاحتفاظ بمكدس للصناديق المشغولة التي لم تُطابق بعد. ولكل \(1\) مفتوح نخزّن أكبر رقم جولة لأي زوج مُطابق يقع بالكامل داخل هذا الموضع.
عند قراءة صندوق مشغول جديد نضع \(0\) على المكدس، لأنه لا توجد بعد أي أزواج داخلية. وعند قراءة صندوق فارغ فإنه يطابق أحدث صندوق مشغول غير مغلق. إذا كانت أكبر جولة مخزنة لذلك الصندوق هي \(d\)، فهذا يعني أن كل الأزواج الداخلية تختفي في الجولة \(d\) أو قبلها، وبالتالي يصبح الزوج الخارجي متجاوراً بعد جولة واحدة إضافية. إذن رقم جولته هو
$$d+1.$$
وبعد تسجيل هذا الزوج يجب تمرير هذه القيمة يساراً عبر أخذ القيمة العظمى مع العنصر الأعلى الجديد في المكدس، لأن البنية الداخلية للصندوق المشغول السابق قد أصبحت أعمق.
هذه هي نفس علاقة العودية في المطابقة المتداخلة للأقواس: الزوج الخارجي يختفي بعد جولة واحدة من اختفاء كل ما يقع بداخله تماماً. وعند نهاية الجزء الصريح من الكلمة، يُعالَج ذيل الأصفار اللانهائي بإفراغ المكدس المتبقي بالطريقة نفسها.
الحالة الابتدائية معطاة أصلاً على شكل أطوال مقاطع متعاقبة، لذلك لا حاجة لبناء التاريخ الكامل لحركات BBS. إذا كان لدينا مقطع مشغول طوله \(\ell\)، فإننا نضيف \(\ell\) صفراً إلى المكدس. وإذا كان لدينا مقطع فارغ طوله \(\ell\)، فإننا ننفذ حتى \(\ell\) عمليات إغلاق، مع التوقف مبكراً إذا لم تعد هناك صناديق مشغولة غير مطابقة.
ولأن كل \(t_k\) يقع دائماً في المجموعة \(\{1,\dots,64\}\)، فإن كلفة كل مقطع هي \(O(1)\)، وبذلك تصبح العملية كلها مروراً تدفقياً واحداً فوق المتتالية شبه العشوائية.
بعد الحصول على القيم \(N_r\)، يأتي مجموع المربعات من الهوية الأساسية
$$\ell^2=\sum_{r=1}^{\ell}(2r-1).$$
وبجمعها على جميع الكتل المستقرة وتبديل ترتيب الجمع نحصل على
$$\sum_{j=1}^{m}L_j^2=\sum_{j=1}^{m}\sum_{r=1}^{L_j}(2r-1)=\sum_{r\ge 1}(2r-1)\#\{j:L_j\ge r\}.$$
ثم نعوّض \(N_r=\#\{j:L_j\ge r\}\) فنصل إلى الصيغة الدقيقة التي تستخدمها التطبيقات:
$$\boxed{\sum_{j=1}^{m}L_j^2=\sum_{r\ge 1}(2r-1)N_r.}$$
لنأخذ المثال الصغير \([2,2,2,1,2]\). هذا المثال يمثل الكلمة اللانهائية
$$110011011\,0^\infty.$$
الحذف المتكرر للنمط \(10\) يزيل \(3\) أزواج في الجولة الأولى، و\(2\) في الجولة الثانية، و\(1\) في الجولة الثالثة. لذلك
$$N_1=3,\qquad N_2=2,\qquad N_3=1.$$
ومن ثم تكون المضاعفات الدقيقة للأطوال
$$N_1-N_2=1,\qquad N_2-N_3=1,\qquad N_3-N_4=1,$$
فتكون أطوال الكتل المستقرة هي \([1,2,3]\).
أما في عينة المسألة ذات المقاطع الأحد عشر، فإن الأطوال المستقرة هي \([1,3,10,24,51,75]\). لذلك تكون \(N_r\) ثابتة على مقاطع:
$$N_r=\begin{cases} 6,& r=1,\\ 5,& 2\le r\le 3,\\ 4,& 4\le r\le 10,\\ 3,& 11\le r\le 24,\\ 2,& 25\le r\le 51,\\ 1,& 52\le r\le 75,\\ 0,& r\ge 76. \end{cases}$$
وبالتعويض في الهوية السابقة نحصل على
$$\sum_{r\ge 1}(2r-1)N_r=8912,$$
وهو تماماً مقدار العينة.
تقوم تطبيقات C++ وPython وJava بتوليد أطوال المقاطع شبه العشوائية على نحو تدفقي، وتتنقل بالتناوب بين المقاطع المشغولة والفارغة، وتحافظ على نفس ثابت المكدس. كل عملية إغلاق تزيد العداد الموافق لجولة الحذف المناسبة بمقدار واحد، أما الإفراغ النهائي للمكدس فيمثل الذيل اللانهائي من الصناديق الفارغة. وبعد هذه التمريرة الوحيدة يُحسب المقدار \(\sum_{r\ge 1}(2r-1)N_r\) مباشرة من العدادات المخزنة. لا توجد أي محاكاة صريحة لجولات كثيرة من BBS.
لتكن \(B\) هي الكمية الكلية للصناديق المشغولة في الحالة الابتدائية المرمزة. كل صندوق مشغول يدخل المكدس مرة واحدة ويخرج منه مرة واحدة، لذلك يكون مجموع عمل المكدس \(O(B)\). أما مصفوفة عدادات الجولات فطولها يساوي أكبر جولة حذف تظهر فعلياً. ومن ثم يكون استهلاك الذاكرة \(O(H+D)\)، حيث \(H\) هو أكبر ارتفاع فعّال للمكدس و\(D\) هو أكبر رقم جولة؛ وكلاهما محدود من أعلى بواسطة \(B\).
وبما أن كل طول مقطع يحقق \(1\le t_k\le 64\)، ومع وجود \(R=10^7+1\) مقطعاً مولداً، نحصل أيضاً على \(B=O(R)\). لذلك فالخوارزمية كلها خطية في حجم الإدخال المرمز، وأسرع بكثير من أي محاكاة مباشرة لعدد كبير من جولات BBS.