The task is to count rotationally distinct valid colourings of a two-row loop of length \(n\) using \(k\) colours, modulo \(M=1000004321\). A direct search over all full loops is hopeless for the target input, so the implementation scans the loop one column at a time and remembers only the local boundary information needed to continue a legal colouring.
The admissible local patterns are exactly those encoded by the transition system: a colour region may continue horizontally on the top row or the bottom row for at most three columns, or a column may be a single vertical monochromatic domino. Ordinary columns have different top and bottom colours, while a vertical domino has equal top and bottom colours. A simultaneous restart of both rows is allowed only immediately after a vertical domino, which is how the automaton excludes forbidden four-corner junctions.
Let \(F_k(n)\) denote the number of rotational classes of valid colourings of length \(n\). The solution has three layers: encode local legality with a finite automaton, turn rooted colourings into matrix traces, and then quotient by rotation with Burnside's lemma.
Walk around the loop column by column and record a state
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
Here \(r_t,r_b\in\{0,1,2\}\) are the numbers of future columns still occupied by the current top and bottom horizontal runs after the present column, \(c_t,c_b\) are the current colours, and \(p\in\{0,1\}\) marks whether the current column is a vertical monochromatic domino.
The validity conditions are
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b.$$
So the state space is finite, with
$$S=9k(k-1)+k=k(9k-8)$$
valid states.
From each state, the next column is determined by simple local continuation rules.
If \(r_t>0\) and \(r_b>0\), both horizontal runs continue, so the next state is obtained by decrementing both remainders. If exactly one row has ended, the unfinished row keeps its colour while the finished row starts a new run of length \(1\), \(2\), or \(3\), with a colour different from both its left neighbour and its vertical neighbour in the new column.
If both rows have ended, a fresh colour may create a vertical domino. Two independent new horizontal runs may also start, but only when the previous column was vertical; this is the local rule that removes four-corner meetings. These legal moves form a directed graph. Let \(A\) be its adjacency matrix.
A rooted colouring of length \(m\) that closes consistently after exactly \(m\) columns corresponds to a closed walk of length \(m\) in the state graph. Therefore the rooted count is
$$T_m=\operatorname{tr}(A^m).$$
This trace counts closed walks because the diagonal entries of \(A^m\) count returns to the same state after \(m\) steps. Since \(A\) is a finite matrix, the sequence \((T_m)\) satisfies a linear recurrence modulo \(M\).
The implementation first computes a prefix
$$T_0,T_1,T_2,\dots$$
by repeatedly multiplying the current matrix power by the sparse transition graph and taking the trace after each step. Once enough terms are available, Berlekamp-Massey reconstructs the shortest recurrence
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
After that, very large indices can be evaluated quickly using binary exponentiation in the recurrence algebra, so the huge target value of \(n\) is reduced to a logarithmic-time query in \(n\).
The loop is cyclic, so rooted colourings that differ only by a rotation represent the same final object. Burnside's lemma gives
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s),$$
where \(\operatorname{Fix}(s)\) is the number of colourings fixed by rotation through \(s\) columns. A colouring fixed by that rotation has period \(\gcd(n,s)\), hence
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}.$$
Grouping rotations by their order yields the divisor form used in the program:
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
For a loop of length \(3\), there are exactly three rotations. The identity fixes all rooted colourings of period \(3\), contributing \(T_3\). The other two rotations both force period \(1\), so each contributes \(T_1\). Therefore
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
This is a clean small example of the divisor formula, because \(3\) is prime. For \(k=4\), the implementation checks that
$$F_4(3)=104,$$
which is exactly the expected Burnside average for that case.
The C++, Python, and Java implementations all follow the same pipeline. First they enumerate every valid boundary state and build the directed adjacency list of legal next states. This adjacency list is the sparse representation of the transfer matrix.
Next they start from the identity matrix, repeatedly apply one more transition step, and record the traces \(T_0,T_1,\dots\). Once the trace sequence is long enough, they recover a minimal linear recurrence modulo \(M\) and keep the initial values needed to seed that recurrence.
Finally they factor \(n\), enumerate all divisors together with their Euler totient weights, evaluate \(T_{n/d}\) from the recurrence for each divisor \(d\), sum
$$\varphi(d)\,T_{n/d},$$
and multiply by the modular inverse of \(n\). The published answer is that Burnside average modulo \(M\).
Let \(S\) be the number of states, \(E\) the number of directed transitions, and \(L\) the recovered recurrence order. Building the automaton takes \(O(S+E)\) time and memory.
If a prefix of \(m\) trace values is generated, the repeated dense-by-sparse matrix updates cost roughly \(O(mSE)\) time and \(O(S^2+E)\) memory, because the current matrix power is stored explicitly while the transition graph is sparse.
Recovering a recurrence from a prefix of length \(O(L)\) is quadratic in \(L\) in the standard Berlekamp-Massey formulation. After that, each large-index query \(T_x\) costs \(O(L^2\log x)\), and the final Burnside sum needs one such query for each divisor of \(n\). Thus the cyclic count after recurrence discovery is
$$O\bigl(\tau(n)L^2\log n\bigr),$$
plus the comparatively small cost of factoring \(n\) and enumerating its divisors.
Gesucht ist die Anzahl rotationsverschiedener gültiger Färbungen einer zweizeiligen Schleife der Länge \(n\) mit \(k\) Farben, modulo \(M=1000004321\). Eine direkte Enumeration aller vollständigen Schleifen ist für die Zielwerte unmöglich. Deshalb liest die Implementierung die Schleife spaltenweise und speichert nur die lokale Randinformation, die für die Fortsetzung einer zulässigen Färbung nötig ist.
Die zulässigen lokalen Muster sind genau die, die im Zustandsautomaten kodiert sind: Eine Farbregion kann auf der oberen oder unteren Zeile horizontal über höchstens drei Spalten weiterlaufen, oder eine Spalte kann ein einzelner vertikaler monochromer Domino sein. In gewöhnlichen Spalten sind obere und untere Farbe verschieden, bei einem vertikalen Domino sind sie gleich. Ein gleichzeitiger Neustart beider Zeilen ist nur direkt nach einem vertikalen Domino erlaubt; genau so schließt der Automat die verbotenen Vier-Ecken-Situationen aus.
Sei \(F_k(n)\) die Anzahl der Rotationsklassen gültiger Färbungen der Länge \(n\). Die Lösung hat drei Schichten: lokale Zulässigkeit durch einen endlichen Automaten, verwurzelte Färbungen über Matrixspuren, und anschließend das Herausdividieren der Rotationssymmetrie mit dem Lemma von Burnside.
Wir laufen die Schleife Spalte für Spalte ab und speichern einen Zustand
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
Dabei sind \(r_t,r_b\in\{0,1,2\}\) die Anzahlen zukünftiger Spalten, die nach der aktuellen Spalte noch von den laufenden horizontalen Segmenten oben bzw. unten belegt werden, \(c_t,c_b\) sind die aktuellen Farben, und \(p\in\{0,1\}\) markiert, ob die aktuelle Spalte ein vertikaler monochromer Domino ist.
Die Gültigkeitsbedingungen lauten
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b.$$
Damit ist der Zustandsraum endlich, und die Zahl der gültigen Zustände ist
$$S=9k(k-1)+k=k(9k-8).$$
Aus jedem Zustand ergibt sich die nächste Spalte durch einfache lokale Fortsetzungsregeln.
Falls \(r_t>0\) und \(r_b>0\), laufen beide horizontalen Segmente weiter; man dekrementiert also beide Restlängen. Falls genau eine Zeile endet, behält die andere ihre Farbe, während die beendete Zeile ein neues Segment der Länge \(1\), \(2\) oder \(3\) beginnt, dessen Farbe sowohl vom linken Nachbarn als auch vom vertikalen Nachbarn in der neuen Spalte verschieden sein muss.
Wenn beide Zeilen gleichzeitig enden, darf eine neue Farbe einen vertikalen Domino bilden. Zwei unabhängige neue horizontale Segmente dürfen ebenfalls starten, aber nur dann, wenn die vorherige Spalte vertikal war; das ist genau die lokale Regel, die Vier-Ecken-Treffpunkte verhindert. Diese zulässigen Schritte bilden einen gerichteten Graphen. Seine Adjazenzmatrix sei \(A\).
Eine verwurzelte Färbung der Länge \(m\), die nach genau \(m\) Spalten konsistent schließt, entspricht einem geschlossenen Weg der Länge \(m\) im Zustandsgraphen. Daher ist die Anzahl verwurzelter Färbungen
$$T_m=\operatorname{tr}(A^m).$$
Die Spur zählt geschlossene Wege, weil die Diagonaleinträge von \(A^m\) genau die Rückkehr in denselben Zustand nach \(m\) Schritten erfassen. Da \(A\) endlichdimensional ist, erfüllt die Folge \((T_m)\) modulo \(M\) eine lineare Rekurrenz.
Die Implementierung berechnet zunächst ein Präfix
$$T_0,T_1,T_2,\dots$$
durch wiederholtes Anwenden eines weiteren Übergangsschritts auf die aktuelle Matrixpotenz und anschließende Spurbildung. Sobald genügend Terme vorliegen, rekonstruiert Berlekamp-Massey die kürzeste Rekurrenz
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
Danach lassen sich sehr große Indizes schnell per binärer Exponentiation in der Rekurrenzalgebra auswerten. Das riesige Ziel-\(n\) wird so auf eine logarithmische Anfrage in \(n\) reduziert.
Die Schleife ist zyklisch, daher beschreiben verwurzelte Färbungen, die sich nur durch Rotation unterscheiden, dasselbe Endobjekt. Burnside liefert
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s),$$
wobei \(\operatorname{Fix}(s)\) die Anzahl der Färbungen ist, die unter einer Rotation um \(s\) Spalten invariant bleiben. Eine solche Färbung hat Periode \(\gcd(n,s)\), also
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}.$$
Fasst man Rotationen nach ihrer Ordnung zusammen, erhält man die im Programm verwendete Divisorenform
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
Für eine Schleife der Länge \(3\) gibt es genau drei Rotationen. Die Identität fixiert alle verwurzelten Färbungen mit Periode \(3\) und trägt \(T_3\) bei. Die beiden nichttrivialen Rotationen erzwingen beide Periode \(1\) und tragen daher jeweils \(T_1\) bei. Somit gilt
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
Das ist ein besonders sauberes Beispiel der Divisorenformel, weil \(3\) prim ist. Für \(k=4\) prüft die Implementierung den Kontrollwert
$$F_4(3)=104,$$
und genau dieser Burnside-Mittelwert tritt dort auf.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst enumerieren sie alle gültigen Randzustände und bauen daraus die gerichtete Adjazenzliste aller zulässigen Folgezustände. Diese Adjazenzliste ist die spärliche Darstellung der Übergangsmatrix.
Danach starten sie mit der Einheitsmatrix, wenden wiederholt einen weiteren Übergangsschritt an und protokollieren die Spuren \(T_0,T_1,\dots\). Sobald die Spurenfolge lang genug ist, rekonstruieren sie eine minimale lineare Rekurrenz modulo \(M\) und speichern die dazugehörigen Anfangswerte.
Zum Schluss wird \(n\) faktorisiert, alle Divisoren werden zusammen mit ihren Totienten-Gewichten erzeugt, für jeden Divisor \(d\) wird \(T_{n/d}\) aus der Rekurrenz ausgewertet, dann wird
$$\varphi(d)\,T_{n/d}$$
aufsummiert und mit dem modularen Inversen von \(n\) multipliziert. Das veröffentlichte Ergebnis ist genau dieser Burnside-Mittelwert modulo \(M\).
Seien \(S\) die Anzahl der Zustände, \(E\) die Anzahl der gerichteten Übergänge und \(L\) die gefundene Rekurrenzordnung. Der Aufbau des Automaten benötigt \(O(S+E)\) Zeit und Speicher.
Wenn ein Präfix aus \(m\) Spurwerten erzeugt wird, kosten die wiederholten Dense-gegen-Sparse-Matrixupdates ungefähr \(O(mSE)\) Zeit und \(O(S^2+E)\) Speicher, weil die aktuelle Matrixpotenz explizit gehalten wird, der Übergangsgraph aber spärlich bleibt.
Die Rekurrenzrekonstruktion aus einem Präfix der Länge \(O(L)\) ist in der Standardformulierung von Berlekamp-Massey quadratisch in \(L\). Danach kostet jede Anfrage \(T_x\) für großen Index \(O(L^2\log x)\), und die abschließende Burnside-Summe benötigt eine solche Anfrage für jeden Divisor von \(n\). Nach dem Lernen der Rekurrenz kostet die zyklische Zählung also
$$O\bigl(\tau(n)L^2\log n\bigr),$$
zuzüglich der vergleichsweise kleinen Kosten für Faktorisierung und Divisorenerzeugung.
Amaç, uzunluğu \(n\) olan iki satırlı bir döngünün \(k\) renkle yapılabilen geçerli boyamalarının dönmeye göre farklı sınıflarını, \(M=1000004321\) modunda saymaktır. Tüm döngüleri doğrudan taramak hedef girdide imkansız olduğundan, uygulama döngüyü sütun sütun ilerletir ve yalnızca geçerli bir boyamayı sürdürmek için gereken yerel sınır bilgisini tutar.
İzin verilen yerel desenler tam olarak geçiş sisteminin kodladıklarıdır: bir renk bölgesi üst satırda ya da alt satırda yatay olarak en fazla üç sütun devam edebilir veya bir sütun tek başına düşey, tek renkli bir domino olabilir. Normal sütunlarda üst ve alt renkler farklıdır; düşey dominoda ise aynıdır. Her iki satırın aynı anda yeniden başlamasına yalnızca bir düşey dominodan hemen sonra izin verilir; otomatanın yasakladığı dört köşe birleşimleri bu kuralla engellenir.
\(F_k(n)\), uzunluğu \(n\) olan geçerli boyamaların dönme sınıfı sayısı olsun. Çözüm üç katmandan oluşur: yerel geçerliliği sonlu bir otomatla kodlamak, köklü boyamaları matris izleriyle saymak ve sonra dönme simetrisini Burnside Lemması ile bölümlemek.
Döngü boyunca sütun sütun ilerleyip şu durumu kaydedelim:
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
Burada \(r_t,r_b\in\{0,1,2\}\), mevcut sütundan sonra üst ve alt yatay koşuların kaplayacağı gelecekteki sütun sayılarıdır. \(c_t,c_b\) güncel renklerdir. \(p\in\{0,1\}\) ise mevcut sütunun düşey, tek renkli bir domino olup olmadığını gösterir.
Geçerlilik koşulları
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b$$
şeklindedir. Böylece durum uzayı sonludur ve geçerli durum sayısı
$$S=9k(k-1)+k=k(9k-8)$$
olur.
Her durumdan sonraki sütun basit yerel devam kurallarıyla belirlenir.
Eğer \(r_t>0\) ve \(r_b>0\) ise iki yatay koşu da devam eder; dolayısıyla her iki kalan değer bir azaltılır. Eğer yalnızca bir satır bitmişse, diğer satır rengini korur; biten satır ise \(1\), \(2\) veya \(3\) uzunluğunda yeni bir koşu başlatır. Bu yeni rengin hem soldaki komşudan hem de aynı sütundaki dikey komşudan farklı olması gerekir.
Her iki satır aynı anda bitmişse, yeni bir renk düşey domino oluşturabilir. İki bağımsız yeni yatay koşunun birlikte başlamasına da izin vardır, fakat yalnızca önceki sütun düşey domino ise; dört köşe temaslarını ortadan kaldıran yerel kural budur. Bu geçerli adımlar yönlü bir grafik oluşturur. Bu grafiğin komşuluk matrisi \(A\) olsun.
Uzunluğu \(m\) olan ve tam \(m\) sütun sonra tutarlı biçimde kapanan bir köklü boyama, durum grafiğinde uzunluğu \(m\) olan kapalı bir yürüyüşe karşılık gelir. Bu yüzden köklü sayım
$$T_m=\operatorname{tr}(A^m)$$
olur. İz formülü doğrudur; çünkü \(A^m\) matrisinin köşegeni, \(m\) adım sonra aynı duruma geri dönen yürüyüşleri sayar. \(A\) sonlu boyutlu olduğundan \((T_m)\) dizisi de modulo \(M\) altında lineer bir rekürans sağlar.
Uygulama önce
$$T_0,T_1,T_2,\dots$$
önekini üretir; bunu da mevcut matris kuvvetine her adımda bir geçiş daha uygulayıp ardından izi alarak yapar. Yeterli terim oluşunca Berlekamp-Massey, en kısa reküransı kurar:
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
Bundan sonra çok büyük indisler, rekürans cebirinde ikili üs alma ile hızlı hesaplanır. Böylece çok büyük \(n\) değeri, \(n\) içinde logaritmik süreli bir sorguya dönüşür.
Döngü çevrimseldir; bu yüzden yalnızca dönme ile farklılaşan köklü boyamalar aynı nihai nesneyi verir. Burnside Lemması
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s)$$
der. Burada \(\operatorname{Fix}(s)\), \(s\) sütun döndürmeye sabit kalan boyama sayısıdır. Böyle bir boyamanın periyodu \(\gcd(n,s)\) olduğundan
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}$$
elde edilir. Dönmeleri mertebelerine göre gruplayınca programdaki bölen formu çıkar:
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
Uzunluğu \(3\) olan bir döngü için tam üç dönme vardır. Özdeşlik dönüşümü periyodu \(3\) olan tüm köklü boyamaları sabit bırakır ve \(T_3\) katkısı yapar. Öteki iki dönme ise periyodu \(1\) zorunlu kılar; dolayısıyla her biri \(T_1\) katkısı verir. Sonuç:
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
\(3\) asal olduğu için bölen formülünün temiz bir küçük örneğidir. \(k=4\) için uygulamanın doğrulama değeri
$$F_4(3)=104$$
olup Burnside ortalamasıyla tam uyumludur.
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce tüm geçerli sınır durumları çıkarılır ve bunlardan izin verilen bir sonraki durumların yönlü komşuluk listesi oluşturulur. Bu liste, geçiş matrisinin seyrek gösterimidir.
Daha sonra birim matris ile başlanır, her adımda bir geçiş daha uygulanır ve \(T_0,T_1,\dots\) izleri kaydedilir. İz dizisi yeterince uzayınca modulo \(M\) altında minimal lineer rekürans bulunur ve bu reküransın başlangıç değerleri saklanır.
Son adımda \(n\) çarpanlarına ayrılır, tüm bölenler Euler totient ağırlıklarıyla birlikte üretilir, her bölen \(d\) için \(T_{n/d}\) reküranstan hesaplanır, ardından
$$\varphi(d)\,T_{n/d}$$
toplanır ve sonuç \(n\)'in modüler tersiyle çarpılır. Yayınlanan cevap, tam olarak bu Burnside ortalamasının \(M\) modundaki değeridir.
\(S\) durum sayısı, \(E\) yönlü geçiş sayısı ve \(L\) bulunan rekürans mertebesi olsun. Otomatı kurmanın zaman ve bellek maliyeti \(O(S+E)\)'dir.
Eğer uzunluğu \(m\) olan bir iz öneki üretilirse, yoğun-seyrek matris güncellemelerinin toplam maliyeti yaklaşık \(O(mSE)\) zaman ve \(O(S^2+E)\) bellek olur; çünkü mevcut matris kuvveti açıkça tutulurken geçiş grafiği seyrektir.
Uzunluğu \(O(L)\) olan bir önekten rekürans çıkarmak, standart Berlekamp-Massey formülasyonunda \(L\) cinsinden kareseldir. Daha sonra büyük indisli her \(T_x\) sorgusu \(O(L^2\log x)\) sürer ve son Burnside toplamı \(n\)'in her böleni için bir böyle sorgu ister. Rekürans öğrenildikten sonraki çevrimsel sayım maliyeti bu yüzden
$$O\bigl(\tau(n)L^2\log n\bigr)$$
olur; buna ek olarak çarpanlara ayırma ve bölen üretiminin görece küçük maliyeti vardır.
Hay que contar las coloraciones válidas, distintas salvo rotación, de un lazo de dos filas y longitud \(n\) usando \(k\) colores, módulo \(M=1000004321\). Una búsqueda directa sobre todos los lazos completos sería inviable para la entrada real, así que la implementación recorre la figura columna por columna y conserva solo la información local de frontera necesaria para seguir una coloración legal.
Los patrones locales permitidos son exactamente los que codifica el sistema de transiciones: una región de color puede continuar horizontalmente en la fila superior o en la inferior durante como máximo tres columnas, o bien una columna puede ser un dominó vertical monocromático. En una columna ordinaria los colores superior e inferior son distintos; en un dominó vertical son iguales. Reiniciar ambas filas a la vez solo está permitido inmediatamente después de un dominó vertical, y esa es precisamente la regla local que evita las uniones prohibidas de cuatro esquinas.
Sea \(F_k(n)\) el número de clases por rotación de las coloraciones válidas de longitud \(n\). La estrategia tiene tres capas: codificar la legalidad local con un autómata finito, convertir las coloraciones enraizadas en trazas de matrices y luego eliminar la simetría de rotación mediante el lema de Burnside.
Recorremos el lazo columna por columna y registramos un estado
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
Aquí \(r_t,r_b\in\{0,1,2\}\) son las cantidades de columnas futuras que todavía ocuparán los segmentos horizontales actuales de la fila superior e inferior después de la columna presente; \(c_t,c_b\) son los colores actuales; y \(p\in\{0,1\}\) indica si la columna actual es un dominó vertical monocromático.
Las condiciones de validez son
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b.$$
Por tanto, el espacio de estados es finito y el número de estados válidos es
$$S=9k(k-1)+k=k(9k-8).$$
Desde cada estado, la siguiente columna queda determinada por reglas locales muy simples.
Si \(r_t>0\) y \(r_b>0\), ambos segmentos horizontales continúan, así que se decrementan los dos restos. Si solo una fila ha terminado, la otra conserva su color y la fila terminada inicia un nuevo segmento de longitud \(1\), \(2\) o \(3\), con un color distinto tanto del vecino de la izquierda como del vecino vertical en la nueva columna.
Si ambas filas han terminado, un color nuevo puede formar un dominó vertical. También pueden arrancar dos segmentos horizontales independientes, pero solo si la columna anterior era vertical; esa es la regla local que elimina los encuentros de cuatro esquinas. Estos movimientos legales forman un grafo dirigido. Su matriz de adyacencia será \(A\).
Una coloración enraizada de longitud \(m\) que se cierra de manera consistente tras exactamente \(m\) columnas corresponde a un paseo cerrado de longitud \(m\) en el grafo de estados. Por eso el conteo enraizado es
$$T_m=\operatorname{tr}(A^m).$$
La traza cuenta paseos cerrados porque las entradas diagonales de \(A^m\) registran los retornos al mismo estado después de \(m\) pasos. Como \(A\) es una matriz finita, la sucesión \((T_m)\) satisface una recurrencia lineal módulo \(M\).
La implementación calcula primero un prefijo
$$T_0,T_1,T_2,\dots$$
repitiendo una multiplicación adicional por el grafo de transición y tomando la traza tras cada paso. Cuando ya hay suficientes términos, Berlekamp-Massey reconstruye la recurrencia mínima
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
Después de eso, cualquier índice enorme puede evaluarse con rapidez mediante exponenciación binaria dentro del álgebra de la recurrencia, de modo que el valor gigantesco de \(n\) deja de ser un obstáculo.
El lazo es cíclico, así que dos coloraciones enraizadas que solo difieren por una rotación representan el mismo objeto final. El lema de Burnside dice
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s),$$
donde \(\operatorname{Fix}(s)\) es el número de coloraciones fijas por la rotación de \(s\) columnas. Una coloración fija por esa rotación tiene periodo \(\gcd(n,s)\), por lo que
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}.$$
Agrupando las rotaciones por su orden se obtiene la forma por divisores que usa el programa:
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
Para un lazo de longitud \(3\) hay exactamente tres rotaciones. La identidad fija todas las coloraciones enraizadas de periodo \(3\) y aporta \(T_3\). Las otras dos rotaciones fuerzan periodo \(1\), así que cada una aporta \(T_1\). Por tanto,
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
Es un ejemplo pequeño especialmente limpio de la fórmula por divisores porque \(3\) es primo. Para \(k=4\), la implementación comprueba que
$$F_4(3)=104,$$
que es exactamente el promedio de Burnside esperado en ese caso.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero enumeran todos los estados de frontera válidos y construyen la lista dirigida de estados siguientes permitidos. Esa lista es la representación dispersa de la matriz de transferencia.
Después comienzan con la matriz identidad, aplican repetidamente un paso de transición adicional y guardan las trazas \(T_0,T_1,\dots\). Cuando la secuencia ya es suficientemente larga, recuperan una recurrencia lineal mínima módulo \(M\) y guardan los valores iniciales necesarios para usarla.
Por último factorizan \(n\), enumeran todos sus divisores junto con sus pesos \(\varphi(d)\), evalúan \(T_{n/d}\) a partir de la recurrencia para cada divisor \(d\), suman
$$\varphi(d)\,T_{n/d},$$
y multiplican por el inverso modular de \(n\). La respuesta publicada es exactamente ese promedio de Burnside módulo \(M\).
Sean \(S\) el número de estados, \(E\) el número de transiciones dirigidas y \(L\) el orden de la recurrencia recuperada. Construir el autómata cuesta \(O(S+E)\) en tiempo y memoria.
Si se genera un prefijo de \(m\) valores de la traza, las actualizaciones repetidas de matriz densa por grafo disperso cuestan aproximadamente \(O(mSE)\) tiempo y \(O(S^2+E)\) memoria, porque la potencia actual de la matriz se almacena explícitamente mientras el grafo de transiciones sigue siendo disperso.
Recuperar una recurrencia a partir de un prefijo de longitud \(O(L)\) es cuadrático en \(L\) en la formulación estándar de Berlekamp-Massey. Después, cada consulta grande \(T_x\) cuesta \(O(L^2\log x)\), y la suma final de Burnside necesita una consulta de ese tipo por cada divisor de \(n\). Por tanto, tras descubrir la recurrencia, el coste de la cuenta cíclica es
$$O\bigl(\tau(n)L^2\log n\bigr),$$
más el coste relativamente pequeño de factorizar \(n\) y enumerar sus divisores.
目标是计算一个长度为 \(n\) 的两行环形结构在 \(k\) 种颜色下的有效着色数，并且把旋转视为同一种方案，结果对 \(M=1000004321\) 取模。对完整环直接暴力枚举在目标输入上完全不可行，因此实现采用逐列扫描，只保留继续扩展合法着色所必需的局部边界信息。
允许的局部图样正是转移系统所编码的那些情形：某个颜色块可以在上排或下排沿水平方向继续延伸，长度最多再持续三列；或者某一列可以是一个上下同色的竖直单色多米诺。普通列要求上下颜色不同，而竖直多米诺要求上下颜色相同。只有在前一列是竖直多米诺时，才允许上下两排同时重新开始新的水平色段，这正是自动机用来排除“四角同时相遇”这种非法局面的规则。
记 \(F_k(n)\) 为长度为 \(n\) 的有效着色在旋转同构意义下的个数。整个解法分成三层：先用有限状态自动机描述局部合法性，再把有根着色转化为矩阵迹，最后用 Burnside 引理消去旋转对称。
沿着环一列一列前进，并记录状态
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
其中 \(r_t,r_b\in\{0,1,2\}\) 表示在当前列之后，上排和下排当前水平色段还会继续占据多少个未来列；\(c_t,c_b\) 是当前列的上色和下色；\(p\in\{0,1\}\) 表示当前列是否为一个竖直单色多米诺。
状态合法性满足
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b.$$
因此状态空间是有限的，合法状态总数为
$$S=9k(k-1)+k=k(9k-8).$$
从每个状态出发，下一列由简单的局部延伸规则决定。
如果 \(r_t>0\) 且 \(r_b>0\)，说明上下两个水平色段都还没有结束，那么下一步只是把两个剩余长度都减一。若只有一排结束，另一排保持原颜色继续，而结束的那一排必须开始一个长度为 \(1\)、\(2\) 或 \(3\) 的新色段，并且新颜色既不能等于左侧相邻颜色，也不能等于新列中与它垂直相邻的颜色。
若上下两排同时结束，那么可以用一个新颜色开始一个竖直多米诺。也可以同时开始两个彼此独立的水平新段，但这只有在前一列是竖直多米诺时才允许；这条局部规则就是程序中避免四角汇合的关键。所有这些合法移动构成一个有向图，记其邻接矩阵为 \(A\)。
一个长度为 \(m\) 的有根着色，如果在走完恰好 \(m\) 列之后能够和起点状态一致地闭合，那么它就对应于状态图中的一条长度为 \(m\) 的闭路。因此有根计数为
$$T_m=\operatorname{tr}(A^m).$$
这里使用迹的原因是：\(A^m\) 的对角元恰好统计从某个状态出发，经过 \(m\) 步又回到同一状态的走法数。由于 \(A\) 是有限维矩阵，序列 \((T_m)\) 在模 \(M\) 意义下必然满足一个线性递推。
实现先显式计算一个前缀
$$T_0,T_1,T_2,\dots$$
方法是不断把当前矩阵幂再乘一次稀疏转移图，并在每一步取迹。只要前缀足够长，就可以用 Berlekamp-Massey 算法恢复最短递推式
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
有了这个递推以后，就可以在递推代数中使用二进制快速幂来求任意巨大的指标 \(T_x\)。因此真正困难的超大 \(n\) 被压缩成一个关于 \(\log n\) 的查询问题。
环形对象没有固定起点，因此只差一个整体旋转的两个有根着色应该算作同一种最终方案。Burnside 引理给出
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s),$$
其中 \(\operatorname{Fix}(s)\) 表示被旋转 \(s\) 列后仍保持不变的着色数量。若某个着色在该旋转下不变，则它的周期必须是 \(\gcd(n,s)\)，于是
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}.$$
再把所有旋转按其阶进行分组，就得到程序实际使用的约数形式：
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
当环长 \(n=3\) 时，总共有三种旋转。恒等旋转固定所有周期为 \(3\) 的有根着色，因此贡献 \(T_3\)。另外两个非平凡旋转都会强迫着色具有周期 \(1\)，所以各自贡献 \(T_1\)。因此
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
因为 \(3\) 是素数，所以这是约数公式的一个非常干净的小例子。对 \(k=4\) 而言，实现中的校验值是
$$F_4(3)=104,$$
这正好符合上面的 Burnside 平均结构。
C++、Python 和 Java 实现遵循同一条流程。首先枚举全部合法的边界状态，并建立每个状态可以转移到哪些后继状态的有向邻接表。这张邻接表就是转移矩阵的稀疏表示。
接着从单位矩阵开始，不断再执行一步转移，同时记录迹序列 \(T_0,T_1,\dots\)。当这个序列足够长时，就在模 \(M\) 下恢复最小线性递推，并保存驱动该递推所需的初始项。
最后对 \(n\) 做质因数分解，枚举所有约数以及对应的欧拉函数权重，对每个约数 \(d\) 通过递推快速求出 \(T_{n/d}\)，累加
$$\varphi(d)\,T_{n/d},$$
再乘上 \(n\) 在模 \(M\) 下的逆元。最终输出的就是这个 Burnside 平均值。
设 \(S\) 为状态数，\(E\) 为有向转移边数，\(L\) 为恢复出来的递推阶数。建立自动机的时间和空间复杂度都是 \(O(S+E)\)。
如果需要生成长度为 \(m\) 的迹前缀，那么反复执行“稠密矩阵乘稀疏图”的更新，大致需要 \(O(mSE)\) 时间和 \(O(S^2+E)\) 空间，因为当前矩阵幂是显式存储的，而转移图保持稀疏。
从长度为 \(O(L)\) 的前缀中恢复递推，在标准的 Berlekamp-Massey 形式下对 \(L\) 是二次复杂度。之后每次求一个大指标 \(T_x\) 需要 \(O(L^2\log x)\)，而最终的 Burnside 求和要对 \(n\) 的每个约数做一次这样的查询。因此在递推建立之后，环形计数的主成本是
$$O\bigl(\tau(n)L^2\log n\bigr),$$
再加上对 \(n\) 分解和枚举约数的较小开销。
Нужно посчитать число корректных раскрасок двухстрочной циклической ленты длины \(n\) в \(k\) цветов с точностью до поворота, по модулю \(M=1000004321\). Полный перебор всех замкнутых раскрасок для целевого входа нереален, поэтому реализация проходит цикл по столбцам и хранит только ту локальную информацию о границе, которая необходима для продолжения допустимой раскраски.
Допустимые локальные конфигурации в точности совпадают с теми, которые зашиты в системе переходов: цветная область может продолжаться по верхней или нижней строке горизонтально не более чем на три столбца, либо столбец может быть отдельным вертикальным одноцветным домино. В обычном столбце верхний и нижний цвета различны, а в вертикальном домино они совпадают. Одновременный старт новых горизонтальных участков в обеих строках разрешается только сразу после вертикального домино; именно это локальное правило исключает запрещенные встречи четырех углов.
Обозначим через \(F_k(n)\) число классов корректных раскрасок длины \(n\) по вращению. Решение состоит из трех уровней: локальная допустимость кодируется конечным автоматом, корневые раскраски считаются через следы матриц, а затем симметрия по вращению убирается леммой Бёрнсайда.
Идем по циклу столбец за столбцом и записываем состояние
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
Здесь \(r_t,r_b\in\{0,1,2\}\) показывают, сколько будущих столбцов после текущего еще займут текущие горизонтальные участки сверху и снизу, \(c_t,c_b\) — текущие цвета, а \(p\in\{0,1\}\) отмечает, является ли текущий столбец вертикальным одноцветным домино.
Условия допустимости имеют вид
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b.$$
Следовательно, пространство состояний конечно, и число допустимых состояний равно
$$S=9k(k-1)+k=k(9k-8).$$
Следующий столбец из каждого состояния определяется простыми локальными правилами продолжения.
Если \(r_t>0\) и \(r_b>0\), оба горизонтальных участка продолжаются, то есть оба остатка уменьшаются на единицу. Если закончилась только одна строка, то другая сохраняет свой цвет, а завершившаяся строка начинает новый участок длины \(1\), \(2\) или \(3\), причем новый цвет должен отличаться и от левого соседа, и от вертикального соседа в новом столбце.
Если закончились обе строки, новый цвет может образовать вертикальное домино. Можно также одновременно начать два независимых горизонтальных участка, но только если предыдущий столбец был вертикальным; именно так исключаются четырехугольные точки встречи. Все допустимые ходы образуют ориентированный граф. Обозначим его матрицу смежности через \(A\).
Корневая раскраска длины \(m\), которая корректно замыкается ровно через \(m\) столбцов, соответствует замкнутому пути длины \(m\) в графе состояний. Поэтому число корневых раскрасок равно
$$T_m=\operatorname{tr}(A^m).$$
След появляется естественно: диагональные элементы \(A^m\) считают способы вернуться в то же состояние за \(m\) шагов. Поскольку \(A\) имеет конечный размер, последовательность \((T_m)\) удовлетворяет линейной рекуррентности по модулю \(M\).
Сначала реализация вычисляет префикс
$$T_0,T_1,T_2,\dots$$
путем последовательного домножения текущей степени матрицы на разреженный граф переходов и взятия следа после каждого шага. Когда членов становится достаточно, алгоритм Берлекэмпа-Мэсси восстанавливает кратчайшую рекуррентность
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
После этого значения с очень большими индексами вычисляются быстро при помощи двоичного возведения в степень в алгебре рекуррентности, так что огромный параметр \(n\) перестает быть проблемой.
Цикл не имеет выделенного начала, поэтому две корневые раскраски, отличающиеся только поворотом, задают один и тот же итоговый объект. Лемма Бёрнсайда дает
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s),$$
где \(\operatorname{Fix}(s)\) — число раскрасок, инвариантных относительно поворота на \(s\) столбцов. Такая раскраска должна иметь период \(\gcd(n,s)\), значит
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}.$$
Если сгруппировать повороты по их порядку, получается формула по делителям, которую и использует программа:
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
Для цикла длины \(3\) существует ровно три поворота. Тождественный поворот фиксирует все корневые раскраски периода \(3\) и дает вклад \(T_3\). Два нетривиальных поворота заставляют раскраску иметь период \(1\), поэтому каждый из них дает вклад \(T_1\). Следовательно,
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
Поскольку \(3\) простое, это очень наглядный пример формулы по делителям. Для \(k=4\) реализация проверяет значение
$$F_4(3)=104,$$
и оно в точности совпадает с соответствующим средним Бёрнсайда.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала они перечисляют все допустимые граничные состояния и строят ориентированный список смежности всех легальных переходов. Этот список смежности является разреженным представлением матрицы переходов.
Затем они стартуют с единичной матрицы, многократно добавляют еще один шаг перехода и записывают следы \(T_0,T_1,\dots\). Когда последовательность становится достаточно длинной, из нее восстанавливается минимальная линейная рекуррентность по модулю \(M\), а нужные начальные значения сохраняются.
После этого число \(n\) раскладывается на простые множители, перечисляются все делители вместе с весами \(\varphi(d)\), для каждого делителя \(d\) по рекуррентности вычисляется \(T_{n/d}\), затем суммируется
$$\varphi(d)\,T_{n/d},$$
и результат умножается на обратный по модулю элемент к \(n\). Именно это среднее Бёрнсайда и выводится как ответ.
Пусть \(S\) — число состояний, \(E\) — число ориентированных переходов, а \(L\) — порядок найденной рекуррентности. Построение автомата требует \(O(S+E)\) времени и памяти.
Если генерируется префикс из \(m\) значений следа, то последовательные обновления вида «плотная матрица против разреженного графа» стоят примерно \(O(mSE)\) времени и \(O(S^2+E)\) памяти, потому что текущая степень матрицы хранится явно, а граф переходов остается разреженным.
Восстановление рекуррентности по префиксу длины \(O(L)\) в стандартной формулировке Берлекэмпа-Мэсси квадратично по \(L\). После этого каждый запрос \(T_x\) для большого индекса стоит \(O(L^2\log x)\), а финальная сумма Бёрнсайда требует по одному такому запросу на каждый делитель \(n\). Поэтому после нахождения рекуррентности основная стоимость циклического подсчета равна
$$O\bigl(\tau(n)L^2\log n\bigr),$$
плюс сравнительно небольшие затраты на факторизацию \(n\) и перечисление его делителей.
المطلوب هو عدّ التلوينات الصحيحة المميزة حتى الدوران لحلقة من صفين وطولها \(n\) باستخدام \(k\) ألوان، مع أخذ الناتج بترديد \(M=1000004321\). الفحص المباشر لكل الحلقات الممكنة غير عملي تمامًا عند قيمة الإدخال المستهدفة، لذلك تعتمد الشيفرة على المرور عمودًا بعد عمود والاحتفاظ فقط بمعلومة الحدّ المحلية اللازمة لمتابعة تلوين قانوني.
الأنماط المحلية المسموح بها هي بالضبط ما يشفّره نظام الانتقالات: يمكن لمنطقة لونية أن تمتد أفقيًا في الصف العلوي أو السفلي لمسافة لا تزيد على ثلاثة أعمدة، أو يمكن أن يكون العمود قطعة دومينو عمودية أحادية اللون. في العمود العادي يجب أن يختلف اللونان العلوي والسفلي، بينما في الدومينو العمودي يجب أن يتساويا. ولا يُسمح ببدء مقطعين أفقيين جديدين معًا إلا مباشرة بعد دومينو عمودي، وهذه هي القاعدة المحلية التي تستبعد مواضع التقاء الزوايا الأربع الممنوعة.
لنرمز بـ \(F_k(n)\) إلى عدد فئات التلوين الصحيحة ذات الطول \(n\) بعد اعتبار الدوران تماثلًا. يتكون الحل من ثلاث طبقات: تمثيل الشرعية المحلية بأوتومات منتهٍ، ثم عدّ التلوينات المؤصّلة بواسطة آثار المصفوفات، ثم حذف تماثل الدوران بواسطة لمّة Burnside.
نمر حول الحلقة عمودًا بعد عمود ونسجل الحالة
$$\bigl(r_t,r_b,p,c_t,c_b\bigr).$$
هنا \(r_t,r_b\in\{0,1,2\}\) يمثلان عدد الأعمدة المستقبلية التي ستبقى مشغولة بعد العمود الحالي بواسطة المقطعين الأفقيين الجاريين في الأعلى والأسفل، و\(c_t,c_b\) هما اللونان الحاليان، أما \(p\in\{0,1\}\) فيشير إلى ما إذا كان العمود الحالي دومينو عموديًا أحادي اللون.
شروط الصحة هي
$$p=0 \implies c_t\ne c_b,$$
$$p=1 \implies r_t=r_b=0 \land c_t=c_b.$$
وبذلك يكون فضاء الحالات منتهيًا، وعدد الحالات الصحيحة يساوي
$$S=9k(k-1)+k=k(9k-8).$$
يُحدد العمود التالي من كل حالة بواسطة قواعد متابعة محلية بسيطة.
إذا كان \(r_t>0\) و\(r_b>0\)، فهذا يعني أن المقطعين الأفقيين ما زالا مستمرين، لذا ننقص الباقيين معًا. وإذا انتهى صف واحد فقط، فإن الصف الآخر يحتفظ بلونه، بينما يبدأ الصف المنتهي مقطعًا جديدًا بطول \(1\) أو \(2\) أو \(3\)، ويجب أن يكون لونه مختلفًا عن الجار الأيسر وعن الجار العمودي في العمود الجديد.
أما إذا انتهى الصفان معًا، فيجوز للون جديد أن يصنع دومينو عموديًا. كما يجوز أيضًا بدء مقطعين أفقيين مستقلين معًا، لكن فقط إذا كان العمود السابق عموديًا؛ وهذه هي القاعدة المحلية التي تمنع التقاء أربع زوايا في نقطة واحدة. تشكل هذه الحركات المسموح بها رسمًا بيانيًا موجهًا، ولنرمز إلى مصفوفة مجاورته بـ \(A\).
كل تلوين مؤصّل بطول \(m\) يُغلق بصورة متسقة بعد \(m\) أعمدة بالضبط يقابل مسارًا مغلقًا طوله \(m\) في رسم الحالات. لذلك يكون عدد التلوينات المؤصّلة
$$T_m=\operatorname{tr}(A^m).$$
ويظهر الأثر هنا لأن العناصر القطرية في \(A^m\) تعدّ طرق الرجوع إلى الحالة نفسها بعد \(m\) خطوة. وبما أن \(A\) مصفوفة منتهية البعد، فإن المتتالية \((T_m)\) تحقق علاقة عودية خطية بترديد \(M\).
تقوم الشيفرة أولًا بحساب بادئة من الشكل
$$T_0,T_1,T_2,\dots$$
عن طريق ضرب القوة الحالية للمصفوفة مرة إضافية في مخطط الانتقالات المتناثر ثم أخذ الأثر بعد كل خطوة. وبعد توفر عدد كاف من الحدود، تعيد خوارزمية Berlekamp-Massey بناء أقصر علاقة عودية
$$T_{m+L}=c_1T_{m+L-1}+c_2T_{m+L-2}+\cdots+c_LT_m \pmod M.$$
بعد ذلك يمكن حساب الحدود ذات الفهارس الضخمة بسرعة باستخدام الأسّ الثنائي داخل جبر العلاقة العودية، وبذلك تتحول قيمة \(n\) الهائلة إلى استعلام لوغاريتمي في \(n\).
الحلقة كائن دوري، لذا فإن تلوينين مؤصّلين لا يختلفان إلا بدوران يمثلان الشيء النهائي نفسه. تعطي لمّة Burnside الصيغة
$$F_k(n)=\frac{1}{n}\sum_{s=0}^{n-1}\operatorname{Fix}(s),$$
حيث \(\operatorname{Fix}(s)\) هو عدد التلوينات التي تبقى ثابتة تحت دوران مقداره \(s\) أعمدة. وإذا ثبت التلوين تحت هذا الدوران فلابد أن تكون دوريته \(\gcd(n,s)\)، ومن ثم
$$\operatorname{Fix}(s)=T_{\gcd(n,s)}.$$
وعند تجميع الدورانات بحسب رتبها نحصل على صيغة القواسم المستعملة في البرنامج:
$$F_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,T_{n/d}\pmod M.$$
عندما يكون طول الحلقة \(3\)، يوجد ثلاثة دورانات فقط. دوران الهوية يثبت كل التلوينات المؤصّلة ذات الدورية \(3\)، ولذلك يساهم بمقدار \(T_3\). أما الدورانان غير التافهين فيفرضان دورية مقدارها \(1\)، فيسهم كل واحد منهما بمقدار \(T_1\). وعليه
$$F_k(3)=\frac{T_3+2T_1}{3}.$$
وهذا مثال صغير ونظيف على صيغة القواسم لأن \(3\) عدد أولي. وعند \(k=4\) تتحقق الشيفرة من أن
$$F_4(3)=104,$$
وهو بالضبط متوسط Burnside المتوقع في هذه الحالة.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا تُحصي جميع حالات الحدّ الصحيحة وتبني قائمة مجاورة موجهة لكل الحالات التالية المسموح بها. هذه القائمة هي التمثيل المتناثر لمصفوفة الانتقال.
ثم تبدأ من مصفوفة الوحدة، وتضيف خطوة انتقال واحدة في كل مرة، وتسجل آثار المصفوفات \(T_0,T_1,\dots\). وعندما تصبح المتتالية طويلة بما يكفي، تستخرج علاقة عودية خطية دنيا بترديد \(M\) وتحتفظ بالقيم الابتدائية اللازمة لها.
أخيرًا يُفكك \(n\) إلى عوامله الأولية، وتُولد جميع قواسِمه مع أوزان دالة أويلر \(\varphi(d)\)، ثم يُحسب \(T_{n/d}\) من العلاقة العودية لكل قاسم \(d\)، ويُجمع المقدار
$$\varphi(d)\,T_{n/d},$$
ثم يُضرب الناتج في المعكوس الضربي لـ \(n\) بترديد \(M\). والجواب النهائي المنشور هو هذا المتوسط نفسه.
ليكن \(S\) عدد الحالات و\(E\) عدد الانتقالات الموجهة و\(L\) رتبة العلاقة العودية المستخرجة. بناء الأوتومات يكلف \(O(S+E)\) زمنًا وذاكرة.
إذا جرى توليد بادئة طولها \(m\) من قيم الأثر، فإن تحديثات المصفوفة الكثيفة مقابل الرسم المتناثر تكلف تقريبًا \(O(mSE)\) زمنًا و\(O(S^2+E)\) ذاكرة، لأن قوة المصفوفة الحالية تُخزن صراحة بينما يبقى مخطط الانتقالات متناثرًا.
استخراج العلاقة العودية من بادئة طولها \(O(L)\) يكون تربيعيًا في \(L\) في الصياغة القياسية لـ Berlekamp-Massey. وبعد ذلك تصبح كل قيمة كبيرة \(T_x\) بكلفة \(O(L^2\log x)\)، وتحتاج صيغة Burnside النهائية إلى مثل هذا التقييم لكل قاسم من قواسم \(n\). لذلك، بعد تعلم العلاقة العودية، تكون كلفة العدّ الدوري
$$O\bigl(\tau(n)L^2\log n\bigr),$$
إضافة إلى الكلفة الأصغر نسبيًا لتحليل \(n\) إلى عوامل أولية وتوليد القواسم.