For each \(i=1,\dots,N\), a linear congruential generator produces
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0.$$
Each value is written as a 12-digit decimal string with leading zeros, and every digit \(d\in\{0,\dots,9\}\) is shifted to \(d+1\). That turns the number into a word \(w_i\in\{1,\dots,10\}^{12}\). The problem is not to compare these words lexicographically, but to compare them by the order in which they appear as consecutive windows in a de Bruijn cycle of order 12 on a 10-symbol alphabet. After assigning that de Bruijn rank to every generated value, the values are sorted by rank and we compute
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891},$$
where \(a_{(m)}\) is the \(m\)-th value after sorting by de Bruijn rank.
The whole solution is a ranking problem on words. There are \(10^{12}\) possible length-12 words, so the de Bruijn cycle cannot be built explicitly. Instead, the implementations rank each word directly through necklace representatives, Lyndon words, and a short dynamic program.
Let \(k=10\) and \(n=12\). A standard theorem says that if we concatenate, in lexicographic order, all Lyndon words whose lengths divide \(n\), we obtain a de Bruijn cycle \(B(k,n)\). Cutting that cycle immediately before the window \(1^{12}\) turns the cyclic order into a linear order on all \(10^{12}\) words of length 12.
So every word \(w\in\{1,\dots,10\}^{12}\) has a unique rank \(R(w)\in\{1,\dots,10^{12}\}\): the position at which \(w\) appears as a length-12 window in that linearized cycle. The final sort is performed by this rank.
A word is a necklace if it is lexicographically smallest among all of its cyclic rotations. If a necklace \(\nu\) can be written as
$$\nu=u^{\,n/p},$$
where \(u\) is primitive and Lyndon, then \(p\) is the length of the fundamental block. This number is an important invariant in the code: it tells us how many consecutive windows are contributed by that Lyndon block in the de Bruijn construction.
For instance, \(1^{12}\) has \(p=1\), while \((1,2,1,2,\dots,1,2)\) has \(p=2\). When a necklace is ranked, the computation first counts all completed Lyndon blocks before it, and then steps backward inside its own block by exactly \(p-1\) positions.
Fix a divisor \(d\mid 12\). To count Lyndon words of length \(d\) up to a boundary induced by \(w\), the implementations first replace the boundary by the largest necklace \(\eta_d(w)\) that is not greater than the first \(d\) symbols of \(w\). This is the correct canonical boundary because necklace representatives, not arbitrary rotations, are what index the blocks in the de Bruijn construction.
That replacement is done by repeatedly locating the first place where the current prefix ceases to be necklace-compatible, lowering that symbol by 1, and filling the rest with the maximum symbol 10. The loop stops exactly when the word becomes a necklace.
Once the boundary necklace \(\eta=\eta_d(w)\) is known, the implementations evaluate a counting function \(T_d(w)\). The main table satisfies
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
for \(0\le j<t\). Conceptually, \(B[t,j]\) counts how many completions of remaining length \(t\) are possible once the first \(j\) positions have already matched the boundary necklace. The first term keeps the next symbol equal to the boundary and moves right; the second term chooses a larger symbol and then counts all free continuations.
A second table stores border information: for every relevant suffix, it remembers how much of that suffix also matches a prefix of \(\eta\). This lets the code continue comparisons across the cyclic boundary in constant time instead of rescanning characters. Using those two tables, the implementation accumulates the full value \(T_d(w)\), which counts periodic words compatible with the boundary necklace.
The quantity \(T_d(w)\) still counts periodic objects, so primitive Lyndon words must be isolated by Möbius inversion:
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
Here \(L_d(w)\) is the number of Lyndon words of length \(d\) that do not exceed the boundary induced by \(w\), and \(\mu\) is the Möbius function. The divisor sum removes the overcount coming from smaller primitive words repeated several times.
If \(w\) is itself a necklace, then its de Bruijn rank is
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w).$$
The sum \(\sum d\,L_d(w)\) is the total number of length-12 windows contributed by all eligible Lyndon blocks up to \(w\). The correction \(1-p(w)\) moves from the end of the current block back to the specific window represented by \(w\).
Every non-necklace word is a rotation of a unique necklace. The implementations rotate \(w\) left until the first necklace in its orbit appears; call it \(\nu\). If the rotation does not cross the point where the de Bruijn cycle was cut, then \(R(w)\) is just \(R(\nu)\) plus or minus the corresponding offset inside the same Lyndon block.
The only exceptional family is
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
These are precisely the windows that wrap across the cut between the end of the cycle and the initial word \(1^{12}\). They occupy the last \(t\) positions of the linear order, so
$$R(w)=10^{12}-t+1.$$
A concrete example is \(w=(10,10,1,1,\dots,1)\), which has \(t=2\), hence rank \(10^{12}-1\). This matches the special case handled explicitly in all three implementations.
The C++, Python, and Java implementations follow the same pipeline. They first generate the pseudo-random values, keep each one as a 12-digit object with leading zeros, and map those digits from \(\{0,\dots,9\}\) to the alphabet \(\{1,\dots,10\}\).
Next they precompute the tiny amount of reusable arithmetic: the powers \(10^0,10^1,\dots,10^{12}\) and the Möbius values for \(1,\dots,12\). For every generated word, the implementation decides whether it is already a necklace, finds the appropriate boundary necklace when it is not, evaluates the divisor-based counting formulas, and combines them into the de Bruijn rank \(R(w)\).
After each value has been paired with its rank, the list is sorted by rank. The final pass computes \(F(N)\) exactly for the small validation cases and modulo \(1234567891\) for the full input. The C++ version parallelizes the independent ranking work across threads; the mathematical result is otherwise identical in all three languages.
The alphabet size and word length are fixed: \(k=10\) and \(n=12\). Therefore the ranking work for one value is bounded by a constant amount of computation over the divisors of 12 together with a few \(12\times12\) tables. For \(N\) generated values, the dominant cost is the final sort, so the overall time complexity is \(O(N\log N)\).
The memory usage is \(O(N)\) because the generated values and their ranks must be stored for sorting. The main mathematical achievement is that the algorithm never constructs the de Bruijn cycle of length \(10^{12}\); it reaches the correct position of each word directly through necklace normalization, Möbius inversion, and short dynamic counts.
Für \(i=1,\dots,N\) erzeugt ein linearer Kongruenzgenerator die Folge
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0.$$
Jeder Wert wird als 12-stellige Dezimalzahl mit führenden Nullen geschrieben, und jede Ziffer \(d\in\{0,\dots,9\}\) wird zu \(d+1\) verschoben. So entsteht ein Wort \(w_i\in\{1,\dots,10\}^{12}\). Verglichen werden diese Wörter nicht in gewöhnlicher lexikographischer Ordnung, sondern nach der Reihenfolge, in der sie als 12er-Fenster in einem de-Bruijn-Zyklus der Ordnung 12 über einem Alphabet mit 10 Symbolen auftreten. Nach dieser Rangzahl werden die erzeugten Werte sortiert und dann
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891}$$
berechnet, wobei \(a_{(m)}\) der \(m\)-te Wert in de-Bruijn-Reihenfolge ist.
Die gesamte Lösung ist eine Rangbestimmung auf Wörtern. Es gibt \(10^{12}\) mögliche Wörter der Länge 12, also darf der de-Bruijn-Zyklus niemals explizit aufgebaut werden. Stattdessen berechnen die Implementierungen den Rang eines Wortes direkt über Necklaces, Lyndon-Wörter und eine kleine dynamische Zählung.
Setze \(k=10\) und \(n=12\). Ein klassischer Satz besagt: Verkettet man alle Lyndon-Wörter, deren Längen \(n\) teilen, in lexikographischer Reihenfolge, so erhält man einen de-Bruijn-Zyklus \(B(k,n)\). Schneidet man diesen Zyklus unmittelbar vor dem Fenster \(1^{12}\), wird aus der zyklischen eine lineare Ordnung aller \(10^{12}\) Wörter der Länge 12.
Damit besitzt jedes Wort \(w\in\{1,\dots,10\}^{12}\) genau einen Rang \(R(w)\in\{1,\dots,10^{12}\}\): seine Position als 12er-Fenster in dieser linearen Ordnung. Genau nach diesem Rang wird später sortiert.
Ein Wort heißt Necklace, wenn es unter all seinen zyklischen Rotationen lexikographisch minimal ist. Lässt sich ein Necklace \(\nu\) schreiben als
$$\nu=u^{\,n/p},$$
wobei \(u\) primitiv und Lyndon ist, dann ist \(p\) die Länge des fundamentalen Blocks. Diese Zahl ist die entscheidende Invariante des Verfahrens: Sie sagt, wie viele aufeinanderfolgende Fenster der zugehörige Lyndon-Block in der de-Bruijn-Konstruktion beisteuert.
Beispielsweise hat \(1^{12}\) den Wert \(p=1\), während \((1,2,1,2,\dots,1,2)\) den Wert \(p=2\) hat. Beim Ranken eines Necklaces zählt man zunächst alle vollständig abgeschlossenen Lyndon-Blöcke davor und geht dann innerhalb des aktuellen Blocks genau um \(p-1\) Positionen zurück.
Sei nun \(d\mid 12\). Um Lyndon-Wörter der Länge \(d\) bis zu einer von \(w\) induzierten Schranke zu zählen, ersetzen die Implementierungen diese Schranke zuerst durch das größte Necklace \(\eta_d(w)\), das nicht größer ist als die ersten \(d\) Symbole von \(w\). Das ist die richtige kanonische Schranke, weil in der de-Bruijn-Konstruktion die Blöcke durch Necklace-Repräsentanten und nicht durch beliebige Rotationen indiziert werden.
Praktisch geschieht das so: Man findet die erste Stelle, an der das aktuelle Präfix nicht mehr necklace-kompatibel ist, verringert dieses Symbol um 1 und füllt den Rest mit dem Maximalsymbol 10 auf. Sobald das Ergebnis ein Necklace ist, stoppt die Schleife.
Ist das Schranken-Necklace \(\eta=\eta_d(w)\) bekannt, berechnen die Implementierungen eine Zählfunktion \(T_d(w)\). Die zentrale Tabelle erfüllt
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
für \(0\le j<t\). Inhaltlich zählt \(B[t,j]\), wie viele Fortsetzungen der Restlänge \(t\) möglich sind, nachdem die ersten \(j\) Positionen bereits mit der Schranke übereinstimmen. Der erste Summand hält das nächste Symbol gleich der Schranke; der zweite Summand wählt ein größeres Symbol und lässt danach alle freien Fortsetzungen zu.
Eine zweite Tabelle speichert Randinformationen: Für jedes relevante Suffix merkt sie sich, wie viel davon zugleich Präfix von \(\eta\) ist. So können Vergleiche über die zyklische Grenze hinweg in konstanter Zeit fortgesetzt werden. Aus beiden Tabellen wird schließlich \(T_d(w)\) aufgebaut, also die Zahl der mit der Schranke verträglichen periodischen Wörter.
Die Größe \(T_d(w)\) zählt noch periodische Objekte mit, daher werden die primitiven Lyndon-Wörter per Möbius-Inversion isoliert:
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
Dabei ist \(L_d(w)\) die Anzahl der Lyndon-Wörter der Länge \(d\), die die von \(w\) induzierte Schranke nicht überschreiten, und \(\mu\) ist die Möbius-Funktion. Die Teiler-Summe entfernt exakt die Überzählung, die von kleineren primitiven Wörtern entsteht, welche mehrfach wiederholt wurden.
Ist \(w\) selbst ein Necklace, dann lautet sein de-Bruijn-Rang
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w).$$
Die Summe \(\sum d\,L_d(w)\) ist die gesamte Zahl der 12er-Fenster, die von allen zulässigen Lyndon-Blöcken bis einschließlich \(w\) geliefert werden. Die Korrektur \(1-p(w)\) verschiebt vom Ende des aktuellen Blocks zurück auf das konkrete Fenster \(w\).
Jedes Wort, das kein Necklace ist, ist eine Rotation eines eindeutigen Necklaces. Die Implementierungen rotieren \(w\) nach links, bis das erste Necklace \(\nu\) seiner Bahn erreicht ist. Falls diese Rotation den Schnittpunkt des linearisierten de-Bruijn-Zyklus nicht überquert, erhält man \(R(w)\) aus \(R(\nu)\) durch einen einfachen Positionsversatz innerhalb desselben Lyndon-Blocks.
Die einzige Ausnahmefamilie ist
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
Genau diese Wörter laufen über den Schnitt zwischen dem Ende des Zyklus und dem Anfangswort \(1^{12}\). Sie besetzen die letzten \(t\) Positionen der linearen Ordnung, also gilt
$$R(w)=10^{12}-t+1.$$
Ein konkretes Beispiel ist \(w=(10,10,1,1,\dots,1)\) mit \(t=2\); sein Rang ist daher \(10^{12}-1\). Genau diesen Spezialfall behandeln alle drei Implementierungen explizit.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst erzeugen sie die Pseudozufallswerte, halten jeden Wert als 12-stelliges Objekt mit führenden Nullen fest und interpretieren die Ziffern als Wort über dem Alphabet \(\{1,\dots,10\}\).
Danach werden die wenigen wiederverwendbaren Hilfswerte vorbereitet: die Potenzen \(10^0,10^1,\dots,10^{12}\) sowie die Möbius-Werte für \(1,\dots,12\). Für jedes erzeugte Wort entscheidet die Implementierung, ob es bereits ein Necklace ist, bestimmt gegebenenfalls die passende Schrankenform, wertet die teilerbasierten Zählformeln aus und setzt daraus den de-Bruijn-Rang \(R(w)\) zusammen.
Sobald jeder Wert mit seinem Rang gepaart ist, wird nach diesem Rang sortiert. Im letzten Durchlauf wird \(F(N)\) für die kleinen Validierungsfälle exakt und für die volle Eingabe modulo \(1234567891\) berechnet. Die C++-Version parallelisiert nur die voneinander unabhängigen Rangberechnungen; mathematisch sind alle drei Fassungen identisch.
Alphabetgröße und Wortlänge sind fest: \(k=10\) und \(n=12\). Daher ist die Rangberechnung pro Wert durch eine konstante Menge von Arbeit beschränkt: einige Teiler von 12 und ein paar Tabellen der Größe \(12\times12\). Für \(N\) erzeugte Werte dominiert damit die abschließende Sortierung, also beträgt die gesamte Laufzeit \(O(N\log N)\).
Der Speicherverbrauch ist \(O(N)\), weil die erzeugten Werte zusammen mit ihren Rängen für die Sortierung gespeichert werden müssen. Der entscheidende mathematische Gewinn besteht darin, dass der de-Bruijn-Zyklus der Länge \(10^{12}\) nie explizit gebaut wird; jede Position wird direkt über Necklaces, Möbius-Inversion und kurze dynamische Zählungen bestimmt.
\(i=1,\dots,N\) için doğrusal kongruans üreteci
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0$$
değerlerini üretir. Her değer, baştaki sıfırlar korunarak 12 basamaklı onluk gösterime çevrilir ve her rakam \(d\in\{0,\dots,9\}\) için \(d+1\) alınır. Böylece \(w_i\in\{1,\dots,10\}^{12}\) biçiminde bir kelime elde edilir. Sorudaki sıralama sıradan leksikografik sıralama değildir; her kelime, 10 sembollü ve mertebesi 12 olan bir de Bruijn çevrimi içinde ardışık 12'li pencere olarak göründüğü konuma göre sıralanır. Sonra bu de Bruijn sıralamasına göre düzenlenen değerler için
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891}$$
hesaplanır; burada \(a_{(m)}\), de Bruijn rank'ine göre sıralanmış listenin \(m\). elemanıdır.
Tüm çözüm, kelimeler üzerinde bir rank hesabıdır. Uzunluğu 12 olan olası kelime sayısı \(10^{12}\) olduğundan de Bruijn çevrimini açıkça üretmek mümkün değildir. Bunun yerine uygulamalar her kelimenin konumunu necklace temsilcileri, Lyndon kelimeleri ve küçük bir dinamik program üzerinden doğrudan bulur.
\(k=10\) ve \(n=12\) alalım. Klasik sonuca göre, uzunluğu \(n\)'yi bölen bütün Lyndon kelimeleri leksikografik sırayla art arda yazılırsa \(B(k,n)\) de Bruijn çevrimi elde edilir. Bu çevrimi \(1^{12}\) penceresinden hemen önce kesersek, bütün 12 harfli kelimeler üzerinde doğrusal bir sıra oluşur.
Dolayısıyla her \(w\in\{1,\dots,10\}^{12}\) kelimesinin tek bir rank değeri vardır: \(R(w)\in\{1,\dots,10^{12}\}\). Bu değer, kelimenin kesilmiş de Bruijn çevriminde bir pencere olarak göründüğü pozisyondur ve son sıralama tam olarak buna göre yapılır.
Bir kelime, tüm döngüsel döndürmeleri arasında leksikografik olarak en küçükse necklace olarak adlandırılır. Eğer bir necklace
$$\nu=u^{\,n/p}$$
şeklinde yazılabiliyorsa ve burada \(u\) hem primitive hem de Lyndon ise, \(p\) temel bloğun uzunluğudur. Kodun kullandığı ana değişmezlerden biri budur; çünkü de Bruijn yapısında ilgili Lyndon bloğunun kaç ardışık pencere ürettiğini bu sayı belirler.
Örneğin \(1^{12}\) için \(p=1\) olur, \((1,2,1,2,\dots,1,2)\) içinse \(p=2\) olur. Bir necklace rank edilirken önce ondan önce tamamlanan bütün Lyndon blokları sayılır, sonra da kendi bloğu içinde \(p-1\) adım geri gidilerek gerçek pencere konumuna dönülür.
Şimdi \(d\mid 12\) olsun. Uzunluğu \(d\) olan Lyndon kelimelerini, \(w\)'nin indüklediği bir üst sınıra kadar saymak için uygulamalar önce bu sınırı, \(w\)'nin ilk \(d\) sembolünü aşmayan en büyük necklace \(\eta_d(w)\) ile değiştirir. Bunun nedeni, de Bruijn yapısında blokların keyfi döndürmelerle değil, kanonik necklace temsilcileriyle indekslenmesidir.
Bu dönüşüm şu şekilde yapılır: mevcut önek necklace koşulunu bozduğu ilk noktada ilgili sembol 1 azaltılır, geri kalan bütün konumlar maksimum sembol olan 10 ile doldurulur. Elde edilen kelime necklace olunca döngü durur.
Sınır necklace'i \(\eta=\eta_d(w)\) belirlendikten sonra uygulamalar \(T_d(w)\) adlı bir sayım büyüklüğü hesaplar. Merkezdeki tablo şu yinelemeyi sağlar:
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
burada \(0\le j<t\). Kavramsal olarak \(B[t,j]\), ilk \(j\) konum zaten sınır kelimeyle eşleşmişken, kalan \(t\) uzunluklu kısmın kaç farklı biçimde tamamlanabileceğini sayar. İlk terim bir sonraki sembolü sınırla eşit tutar; ikinci terim daha büyük bir sembol seçip geri kalan kısmı serbest bırakır.
İkinci bir tablo da sınır bilgisi tutar: ilgili her son-ek için, onun ne kadarının aynı zamanda \(\eta\)'nın öneki olduğunu kaydeder. Böylece çevrimsel sınırı aşan karşılaştırmalar her seferinde baştan taranmadan sabit zamanda güncellenir. Bu iki tablo birleştirilince, sınır necklace ile uyumlu periyodik kelimeleri sayan \(T_d(w)\) değeri elde edilir.
\(T_d(w)\) hâlâ periyodik nesneleri de saydığı için primitive Lyndon kelimeleri Möbius terslemesiyle ayırmak gerekir:
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
Burada \(L_d(w)\), \(w\)'nin verdiği sınırı aşmayan uzunluk-\(d\) Lyndon kelimelerinin sayısıdır; \(\mu\) ise Möbius fonksiyonudur. Bölenler üzerindeki bu toplam, daha kısa primitive kelimelerin tekrar edilmesinden gelen fazla sayımı tam olarak siler.
Eğer \(w\) zaten bir necklace ise de Bruijn rank'i
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w)$$
olur. \(\sum d\,L_d(w)\) toplamı, \(w\)'ye kadar olan bütün uygun Lyndon bloklarının ürettiği 12'li pencere sayısını verir. \(1-p(w)\) düzeltmesi ise bizi mevcut bloğun sonundan alıp bizzat \(w\)'nin temsil ettiği pencereye geri taşır.
Necklace olmayan her kelime, tek bir necklace temsilcisinin döndürülmüş hâlidir. Uygulamalar \(w\)'yi sola döndürerek aynı yörüngedeki ilk necklace \(\nu\)'yu bulur. Eğer bu döndürme, de Bruijn çevriminin kesildiği noktayı geçmiyorsa \(R(w)\), \(R(\nu)\) değerinden aynı Lyndon bloğu içindeki uygun ofset kadar kaydırılarak bulunur.
Tek istisna aile şudur:
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
Bunlar çevrimin sonuyla başlangıç kelimesi \(1^{12}\) arasındaki kesimi aşan pencerelerdir. Doğrusal sıranın son \(t\) konumunu kapladıkları için
$$R(w)=10^{12}-t+1$$
olur. Somut bir örnek olarak \(w=(10,10,1,1,\dots,1)\) için \(t=2\) olduğundan rank \(10^{12}-1\)'dir. Üç uygulamadaki özel dal tam olarak bunu hesaplar.
C++, Python ve Java uygulamalarının akışı aynıdır. Önce sözde-rastgele değerler üretilir, her biri baştaki sıfırlar korunarak 12 basamaklı biçimde tutulur ve rakamlar \(\{1,\dots,10\}\) alfabesine dönüştürülür.
Sonra tekrar tekrar kullanılacak küçük aritmetik tablolar hazırlanır: \(10^0,10^1,\dots,10^{12}\) kuvvetleri ve \(1,\dots,12\) için Möbius değerleri. Her kelime için uygulama bunun zaten bir necklace olup olmadığını kontrol eder, gerekirse uygun sınır necklace'ini bulur, bölenler üzerinden gelen sayım formüllerini değerlendirir ve bunları birleştirerek de Bruijn rank'i \(R(w)\)'yi üretir.
Bütün değerler rank ile eşleştirildikten sonra liste bu rank'e göre sıralanır. Son geçişte küçük doğrulama örnekleri için tam sayı toplamı, asıl giriş içinse \(1234567891\) modunda sonuç hesaplanır. C++ sürümü yalnızca bağımsız rank hesaplarını iş parçacıkları arasında paylaştırır; matematiksel içerik üç dilde de aynıdır.
Alfabe boyutu ve kelime uzunluğu sabittir: \(k=10\), \(n=12\). Bu yüzden tek bir değer için rank hesabı, 12'nin bölenleri ve birkaç \(12\times12\) tablo üzerinde yapılan sabit miktarda işten ibarettir. \(N\) adet değer için baskın maliyet son sıralama olduğundan toplam zaman karmaşıklığı \(O(N\log N)\) olur.
Bellek karmaşıklığı \(O(N)\)'dir; çünkü sıralama yapabilmek için üretilen değerler ile bunların rank'leri birlikte saklanır. Asıl matematiksel kazanç, uzunluğu \(10^{12}\) olan de Bruijn çevrimini hiç üretmeden, her kelimenin konumunu necklace normalleştirmesi, Möbius terslemesi ve kısa dinamik sayımlar aracılığıyla doğrudan bulmaktır.
Para \(i=1,\dots,N\), un generador congruencial lineal produce
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0.$$
Cada valor se escribe como una cadena decimal de 12 dígitos con ceros a la izquierda, y cada dígito \(d\in\{0,\dots,9\}\) se reemplaza por \(d+1\). Eso transforma el número en una palabra \(w_i\in\{1,\dots,10\}^{12}\). El problema no ordena estas palabras de forma lexicográfica ordinaria, sino según la posición en la que aparecen como ventanas consecutivas dentro de un ciclo de de Bruijn de orden 12 sobre un alfabeto de 10 símbolos. Una vez asignado ese rango de de Bruijn a cada valor generado, se ordenan los valores por rango y se calcula
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891},$$
donde \(a_{(m)}\) es el \(m\)-ésimo valor después de ordenar por rango de de Bruijn.
Toda la solución es un problema de ranking de palabras. Hay \(10^{12}\) palabras posibles de longitud 12, así que el ciclo completo de de Bruijn no puede construirse explícitamente. En su lugar, las implementaciones calculan la posición de cada palabra directamente mediante representantes necklace, palabras de Lyndon y un programa dinámico pequeño.
Tomemos \(k=10\) y \(n=12\). Un resultado clásico afirma que, si se concatenan en orden lexicográfico todas las palabras de Lyndon cuyas longitudes dividen a \(n\), se obtiene un ciclo de de Bruijn \(B(k,n)\). Si se corta ese ciclo justo antes de la ventana \(1^{12}\), la ordenación cíclica se convierte en una ordenación lineal de todas las palabras de longitud 12.
Por tanto, cada palabra \(w\in\{1,\dots,10\}^{12}\) tiene un rango único \(R(w)\in\{1,\dots,10^{12}\}\): la posición en la que aparece como ventana de longitud 12 en ese ciclo linealizado. Ese es exactamente el orden utilizado al final.
Una palabra es un necklace si es la menor, en sentido lexicográfico, entre todas sus rotaciones cíclicas. Si un necklace \(\nu\) puede escribirse como
$$\nu=u^{\,n/p},$$
con \(u\) primitiva y además palabra de Lyndon, entonces \(p\) es la longitud del bloque fundamental. Ese valor es una invariante clave: indica cuántas ventanas consecutivas aporta ese bloque de Lyndon dentro de la construcción de de Bruijn.
Por ejemplo, \(1^{12}\) tiene \(p=1\), mientras que \((1,2,1,2,\dots,1,2)\) tiene \(p=2\). Al rankear un necklace, primero se cuentan todos los bloques de Lyndon completos que aparecen antes y luego se retrocede \(p-1\) posiciones dentro del bloque actual para obtener la ventana exacta.
Fijemos un divisor \(d\mid 12\). Para contar palabras de Lyndon de longitud \(d\) hasta una cota inducida por \(w\), las implementaciones sustituyen primero esa cota por el mayor necklace \(\eta_d(w)\) que no supera los primeros \(d\) símbolos de \(w\). Esa es la cota canónica correcta, porque la construcción de de Bruijn indexa bloques mediante representantes necklace y no mediante rotaciones arbitrarias.
El proceso es iterativo: se detecta el primer punto donde el prefijo actual deja de ser compatible con la condición de necklace, se reduce ese símbolo en 1 y todo el sufijo restante se rellena con el símbolo máximo 10. La iteración termina exactamente cuando la palabra resultante ya es un necklace.
Una vez fijado el necklace frontera \(\eta=\eta_d(w)\), las implementaciones evalúan una función de conteo \(T_d(w)\). La tabla principal satisface
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
para \(0\le j<t\). Conceptualmente, \(B[t,j]\) cuenta cuántas completaciones de longitud restante \(t\) son posibles cuando las primeras \(j\) posiciones ya coinciden con la frontera. El primer término mantiene el siguiente símbolo igual a la frontera; el segundo elige un símbolo mayor y deja libre el resto.
Una segunda tabla guarda información de borde: para cada sufijo relevante, recuerda qué longitud de ese sufijo coincide también con un prefijo de \(\eta\). Así las comparaciones que cruzan el borde cíclico pueden actualizarse en tiempo constante. Con ambas tablas se obtiene \(T_d(w)\), que cuenta palabras periódicas compatibles con el necklace frontera.
La cantidad \(T_d(w)\) todavía incluye objetos periódicos, por lo que hay que extraer la parte primitiva mediante inversión de Möbius:
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
Aquí \(L_d(w)\) es el número de palabras de Lyndon de longitud \(d\) que no exceden la cota inducida por \(w\), y \(\mu\) es la función de Möbius. La suma sobre divisores elimina exactamente el sobreconteo producido por palabras primitivas más cortas repetidas varias veces.
Si \(w\) ya es un necklace, su rango de de Bruijn viene dado por
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w).$$
La suma \(\sum d\,L_d(w)\) representa el número total de ventanas de longitud 12 aportadas por todos los bloques de Lyndon admisibles hasta \(w\). La corrección \(1-p(w)\) desplaza desde el final del bloque actual hasta la ventana concreta representada por \(w\).
Toda palabra que no sea necklace es una rotación de un necklace único. Las implementaciones rotan \(w\) hacia la izquierda hasta encontrar el primer necklace \(\nu\) de su órbita. Si esa rotación no cruza el punto donde se cortó el ciclo de de Bruijn, entonces \(R(w)\) se obtiene a partir de \(R(\nu)\) aplicando el desplazamiento correspondiente dentro del mismo bloque de Lyndon.
La única familia excepcional es
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
Estas son exactamente las ventanas que cruzan la unión entre el final del ciclo y la palabra inicial \(1^{12}\). Ocupan las últimas \(t\) posiciones del orden lineal, así que
$$R(w)=10^{12}-t+1.$$
Un ejemplo concreto es \(w=(10,10,1,1,\dots,1)\), para la cual \(t=2\), luego el rango es \(10^{12}-1\). Ese es el caso especial que aparece explícitamente en las tres implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero generan los valores pseudoaleatorios, conservan cada uno como objeto decimal de 12 dígitos con ceros iniciales y reinterpretan esos dígitos como letras del alfabeto \(\{1,\dots,10\}\).
Después precalculan la pequeña aritmética reutilizable: las potencias \(10^0,10^1,\dots,10^{12}\) y los valores de Möbius para \(1,\dots,12\). Para cada palabra generada, la implementación decide si ya es un necklace, encuentra en caso contrario el necklace frontera apropiado, evalúa las fórmulas de conteo sobre los divisores de 12 y las combina para producir el rango de de Bruijn \(R(w)\).
Una vez que cada valor está emparejado con su rango, la lista se ordena por ese rango. El último recorrido calcula \(F(N)\) exactamente en los casos pequeños de validación y módulo \(1234567891\) para la entrada completa. La versión en C++ paraleliza el trabajo independiente de ranking; el contenido matemático es el mismo en los tres lenguajes.
El tamaño del alfabeto y la longitud de palabra son fijos: \(k=10\) y \(n=12\). Por eso, el costo de rankear un solo valor está acotado por una cantidad constante de trabajo sobre los divisores de 12 y unas pocas tablas \(12\times12\). Para \(N\) valores generados, el costo dominante es la ordenación final, de modo que el tiempo total es \(O(N\log N)\).
La memoria es \(O(N)\), porque hay que guardar los valores y sus rangos para poder ordenar. La ganancia matemática esencial es que el algoritmo nunca construye el ciclo de de Bruijn de longitud \(10^{12}\); encuentra la posición correcta de cada palabra directamente mediante normalización por necklaces, inversión de Möbius y recuentos dinámicos cortos.
对 \(i=1,\dots,N\)，线性同余生成器产生
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0.$$
每个数都写成保留前导零的 12 位十进制串，再把每个数字 \(d\in\{0,\dots,9\}\) 替换成 \(d+1\)。这样就得到一个字母表为 \(\{1,\dots,10\}\) 的 12 位单词 \(w_i\)。题目要求的排序不是普通字典序，而是把每个单词看成某个 10 元字母表、阶数为 12 的 de Bruijn 环中的一个长度 12 窗口，并按它在该环中出现的位置排序。得到这个 de Bruijn 排名以后，再按排名对生成值排序，并计算
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891},$$
其中 \(a_{(m)}\) 表示按 de Bruijn 排名排序后第 \(m\) 个值。
整个解法本质上是“给单词直接编号”。长度为 12 的单词一共有 \(10^{12}\) 个，不可能真的把完整的 de Bruijn 环展开出来。实现采用的是组合计数方法：先把单词归约到其 necklace 代表，再利用 Lyndon 单词的分块结构和一个很小的动态规划直接算出位置。
记 \(k=10\)、\(n=12\)。经典结论表明：把所有长度整除 \(n\) 的 Lyndon 单词按字典序连接起来，就得到一个 de Bruijn 环 \(B(k,n)\)。如果把这个环在线性化时切在窗口 \(1^{12}\) 的前面，那么所有长度为 12 的单词都会获得一个确定的线性位置。
因此每个 \(w\in\{1,\dots,10\}^{12}\) 都有唯一的排名 \(R(w)\in\{1,\dots,10^{12}\}\)。这个排名就是它作为长度 12 窗口在该线性化 de Bruijn 环中的出现次序，最终排序完全依据这个值进行。
如果一个单词在它的所有循环移位中都是字典序最小的，那么它就是一个 necklace。若某个 necklace \(\nu\) 能写成
$$\nu=u^{\,n/p},$$
其中 \(u\) 既是 primitive，又是 Lyndon 单词，那么 \(p\) 就是基本块的长度。这个 \(p\) 是实现里最重要的不变量之一，因为它告诉我们：在 de Bruijn 构造中，由这个 Lyndon 块贡献的连续窗口恰好有多少个。
例如 \(1^{12}\) 的 \(p=1\)，而 \((1,2,1,2,\dots,1,2)\) 的 \(p=2\)。给一个 necklace 求排名时，先累计它之前所有已经完整结束的 Lyndon 块，再在当前块内部回退 \(p-1\) 个位置，就能落到这个单词本身对应的窗口。
固定一个约数 \(d\mid 12\)。为了统计长度为 \(d\) 的 Lyndon 单词中有多少个不超过由 \(w\) 诱导出的上界，实现先把这个上界替换成 \(\eta_d(w)\)：也就是“不超过 \(w\) 前 \(d\) 个符号的最大 necklace”。这样做的原因是，de Bruijn 构造中的块是按 necklace 代表编号的，而不是按任意旋转版本编号的。
具体做法是反复修正当前候选上界：找到它第一次违反 necklace 条件的位置，把该位置上的符号减 1，然后把后面的所有位置都填成最大符号 10。循环一旦停下，得到的就是所需的规范上界 necklace。
设 \(\eta=\eta_d(w)\) 是上一步得到的边界 necklace。实现接着计算一个计数函数 \(T_d(w)\)。核心动态规划表满足
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
其中 \(0\le j<t\)。从含义上看，\(B[t,j]\) 表示：当前有前 \(j\) 位已经与边界 \(\eta\) 一致，还剩长度 \(t\) 的尾部需要填充时，合法完成方式有多少种。第一项表示下一位仍然与边界相等，于是继续向右比较；第二项表示下一位选得更大，此后剩余部分就可以自由计数。
实现还维护第二张边界表，用来记录“某个相关后缀有多长一段同时也是 \(\eta\) 的前缀”。这样在比较跨越循环边界时，就不必重新扫描字符，而是能常数时间更新状态。两张表组合起来，便得到 \(T_d(w)\)，也就是与边界 necklace 相容的周期性对象的计数。
\(T_d(w)\) 仍然包含了周期重复带来的重复计数，因此必须用 Möbius 反演把 primitive 的 Lyndon 单词单独提取出来：
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
这里 \(L_d(w)\) 表示不超过由 \(w\) 诱导边界的长度 \(d\) 的 Lyndon 单词数量，\(\mu\) 是 Möbius 函数。这个约数求和恰好消除了“更短 primitive 单词重复若干次”带来的多计。
如果 \(w\) 本身已经是 necklace，那么它的 de Bruijn 排名满足
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w).$$
\(\sum d\,L_d(w)\) 统计的是到 \(w\) 为止所有合格 Lyndon 块一共贡献了多少个长度 12 的窗口；而 \(1-p(w)\) 则把位置从当前块的末端拉回到 \(w\) 本身所对应的那个窗口。
每个非 necklace 单词都是某个唯一 necklace 的循环移位。实现会不断把 \(w\) 向左旋转，直到它所在轨道中的第一个 necklace \(\nu\) 出现。如果这个旋转过程没有跨过 de Bruijn 环被切开的那个位置，那么 \(R(w)\) 只需由 \(R(\nu)\) 加上或减去对应的块内偏移量即可得到。
唯一需要单独处理的一族单词是
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
这些单词正好跨越了“环的末尾”和“起始窗口 \(1^{12}\)”之间的切口，因此它们落在线性顺序的最后 \(t\) 个位置。于是
$$R(w)=10^{12}-t+1.$$
一个具体例子是 \(w=(10,10,1,1,\dots,1)\)。此时 \(t=2\)，所以它的排名是 \(10^{12}-1\)。三种语言的实现都显式包含了这个特判。
C++、Python 和 Java 实现采用完全相同的计算流程。首先生成伪随机值，把每个值保留为带前导零的 12 位十进制对象，再把十进制数字重解释成字母表 \(\{1,\dots,10\}\) 上的单词。
接着预计算可以重复利用的小型算术表：\(10^0,10^1,\dots,10^{12}\) 这些幂，以及 \(1,\dots,12\) 的 Möbius 值。对每个生成的单词，实现先判断它是否已经是 necklace；如果不是，就找到合适的边界 necklace；然后对 12 的各个约数执行计数公式，并把这些结果组合成最终的 de Bruijn 排名 \(R(w)\)。
当每个值都与其排名配对后，列表按排名排序。最后一次扫描中，小规模校验样例使用精确整数求和，而正式输入则在模 \(1234567891\) 下计算 \(F(N)\)。C++ 版本把彼此独立的排名工作并行化到多个线程；除此之外，三种语言的数学内容一致。
字母表大小和单词长度都是固定常数：\(k=10\)、\(n=12\)。因此，对单个值求排名所需的工作量是常数级的，只涉及 12 的约数和少量 \(12\times12\) 表。对 \(N\) 个生成值而言，真正占主导的是最后的排序，所以总时间复杂度为 \(O(N\log N)\)。
空间复杂度为 \(O(N)\)，因为排序前必须同时保存所有生成值及其排名。最关键的数学收益在于：算法从不显式构造长度为 \(10^{12}\) 的 de Bruijn 环，而是通过 necklace 规范化、Möbius 反演以及短小的动态计数直接得到每个单词的位置。
Для \(i=1,\dots,N\) линейный конгруэнтный генератор задаёт последовательность
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0.$$
Каждое значение записывается как 12-значная десятичная строка с ведущими нулями, после чего каждая цифра \(d\in\{0,\dots,9\}\) заменяется на \(d+1\). Так получается слово \(w_i\in\{1,\dots,10\}^{12}\). Сравнивать эти слова нужно не по обычному лексикографическому порядку, а по позиции, в которой они встречаются как последовательные окна длины 12 в цикле де Брёйна порядка 12 над алфавитом из 10 символов. После присвоения каждому значению такого ранга значения сортируются по рангу, и вычисляется
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891},$$
где \(a_{(m)}\) обозначает \(m\)-й элемент после сортировки по de Bruijn-рангу.
Вся задача сводится к вычислению ранга слова. Возможных слов длины 12 ровно \(10^{12}\), поэтому строить сам цикл де Брёйна явно нельзя. Вместо этого реализации находят позицию слова напрямую, используя necklace-представители, слова Линдона и небольшой динамический подсчёт.
Положим \(k=10\) и \(n=12\). Классический факт говорит, что если выписать в лексикографическом порядке все слова Линдона, длины которых делят \(n\), и склеить их, то получится цикл де Брёйна \(B(k,n)\). Если разрезать этот цикл непосредственно перед окном \(1^{12}\), циклический порядок превратится в линейный порядок всех слов длины 12.
Следовательно, каждое слово \(w\in\{1,\dots,10\}^{12}\) получает единственный ранг \(R(w)\in\{1,\dots,10^{12}\}\): это позиция, на которой \(w\) встречается как окно длины 12 в линеаризованном цикле. Именно по этому значению потом выполняется сортировка.
Слово называется necklace, если среди всех своих циклических сдвигов оно лексикографически минимально. Если necklace \(\nu\) представим в виде
$$\nu=u^{\,n/p},$$
где \(u\) примитивно и одновременно является словом Линдона, то число \(p\) есть длина фундаментального блока. Это главный инвариант алгоритма: он показывает, сколько подряд идущих окон в de Bruijn-порядке создаёт данный блок Линдона.
Например, для \(1^{12}\) получаем \(p=1\), а для \((1,2,1,2,\dots,1,2)\) имеем \(p=2\). При ранжировании necklace сначала суммируются все завершённые блоки Линдона, стоящие раньше, а затем делается сдвиг назад на \(p-1\) позиций внутри текущего блока, чтобы попасть в окно, соответствующее самому \(\nu\).
Зафиксируем делитель \(d\mid 12\). Чтобы посчитать слова Линдона длины \(d\), не превосходящие границу, заданную словом \(w\), реализации сначала заменяют эту границу на \(\eta_d(w)\): наибольший necklace, не превосходящий первые \(d\) символов \(w\). Это и есть правильная каноническая граница, потому что блоки в de Bruijn-конструкции индексируются necklace-представителями, а не произвольными сдвигами.
Алгоритм такой: находится первая позиция, в которой текущий префикс нарушает necklace-условие, этот символ уменьшается на 1, а весь оставшийся хвост заполняется максимальным символом 10. Как только результат становится necklace, процесс заканчивается.
После того как найден граничный necklace \(\eta=\eta_d(w)\), реализации вычисляют функцию подсчёта \(T_d(w)\). Основная таблица подчиняется рекуррентному соотношению
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
где \(0\le j<t\). По смыслу \(B[t,j]\) считает число допустимых продолжений длины \(t\), если первые \(j\) позиций уже совпали с граничным necklace. Первый член сохраняет равенство со следующей буквой границы, второй выбирает большую букву и после этого считает все свободные продолжения.
Вторая таблица хранит информацию о бордерах: для каждого нужного суффикса она помнит, какая его длина одновременно является префиксом \(\eta\). Благодаря этому сравнения через циклическую границу продолжаются за \(O(1)\), без повторного просмотра символов. Совместно эти таблицы дают величину \(T_d(w)\), то есть число периодических объектов, совместимых с граничным necklace.
Величина \(T_d(w)\) всё ещё учитывает периодические повторения, поэтому примитивная часть выделяется инверсией Мёбиуса:
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
Здесь \(L_d(w)\) означает число слов Линдона длины \(d\), не превосходящих границу, индуцированную \(w\), а \(\mu\) есть функция Мёбиуса. Сумма по делителям точно устраняет переучёт, вызванный тем, что более короткое примитивное слово могло повторяться несколько раз.
Если \(w\) само является necklace, то его de Bruijn-ранг равен
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w).$$
Сумма \(\sum d\,L_d(w)\) есть общее число окон длины 12, внесённых всеми допустимыми блоками Линдона вплоть до \(w\). Поправка \(1-p(w)\) переводит нас с конца текущего блока обратно к конкретному окну, которое соответствует слову \(w\).
Любое слово, не являющееся necklace, есть циклический сдвиг некоторого единственного necklace. Реализации сдвигают \(w\) влево, пока не встретят первый necklace \(\nu\) в его орбите. Если при этом не пересекается точка, где цикл де Брёйна был разрезан, то \(R(w)\) получается из \(R(\nu)\) добавлением или вычитанием нужного смещения внутри того же блока Линдона.
Единственное исключительное семейство имеет вид
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
Именно эти слова переходят через разрез между концом цикла и начальным окном \(1^{12}\). Они занимают последние \(t\) позиций линейного порядка, поэтому
$$R(w)=10^{12}-t+1.$$
Конкретный пример: для \(w=(10,10,1,1,\dots,1)\) имеем \(t=2\), значит ранг равен \(10^{12}-1\). Этот частный случай явно выделен во всех трёх реализациях.
Реализации на C++, Python и Java выполняют один и тот же конвейер. Сначала они генерируют псевдослучайные значения, хранят каждое как 12-значный десятичный объект с ведущими нулями и переинтерпретируют цифры как буквы алфавита \(\{1,\dots,10\}\).
Далее заранее вычисляются небольшие повторно используемые таблицы: степени \(10^0,10^1,\dots,10^{12}\) и значения функции Мёбиуса для \(1,\dots,12\). Для каждого слова реализация определяет, является ли оно уже necklace, при необходимости находит подходящий граничный necklace, вычисляет формулы подсчёта по делителям числа 12 и объединяет их в окончательный de Bruijn-ранг \(R(w)\).
После этого каждое значение уже связано со своим рангом, и массив сортируется по рангу. На заключительном проходе вычисляется \(F(N)\): точно для маленьких проверочных случаев и по модулю \(1234567891\) для полного входа. Версия на C++ лишь распараллеливает независимые вычисления рангов; сама математика во всех трёх языках одинакова.
Размер алфавита и длина слова фиксированы: \(k=10\) и \(n=12\). Поэтому ранжирование одного значения требует лишь константного объёма работы по делителям числа 12 и нескольким таблицам размера \(12\times12\). Для \(N\) элементов доминирует итоговая сортировка, так что общая временная сложность равна \(O(N\log N)\).
Память составляет \(O(N)\), поскольку перед сортировкой нужно хранить все сгенерированные значения вместе с их рангами. Главный математический выигрыш в том, что цикл де Брёйна длины \(10^{12}\) никогда не строится явно; позиция каждого слова определяется напрямую через necklace-нормализацию, инверсию Мёбиуса и короткие динамические подсчёты.
لكل \(i=1,\dots,N\) يولّد المولد التوافقي الخطي القيم
$$a_i \equiv 920461\,a_{i-1}+800217387569 \pmod{10^{12}}, \qquad a_0=0.$$
ثم يُكتب كل عدد على صورة سلسلة عشرية من 12 رقمًا مع الاحتفاظ بالأصفار البادئة، وبعد ذلك تُحوَّل كل خانة \(d\in\{0,\dots,9\}\) إلى \(d+1\). بهذه الطريقة نحصل على كلمة \(w_i\in\{1,\dots,10\}^{12}\). ترتيب هذه الكلمات ليس الترتيب المعجمي المعتاد، بل ترتيب مواضع ظهورها كنوافذ متتالية بطول 12 داخل دورة de Bruijn من الرتبة 12 على أبجدية من 10 رموز. بعد إسناد رتبة de Bruijn لكل قيمة مولَّدة، تُرتَّب القيم بحسب تلك الرتبة ثم نحسب
$$F(N)=\sum_{m=1}^{N} m\,a_{(m)} \pmod{1234567891},$$
حيث \(a_{(m)}\) هو العنصر رقم \(m\) بعد الترتيب وفق رتبة de Bruijn.
الحل كله يدور حول حساب رتبة كلمة مباشرة. عدد الكلمات الممكنة بطول 12 هو \(10^{12}\)، ولذلك لا يمكن توليد دورة de Bruijn كاملة صراحة. بدلاً من ذلك تعتمد الحلول على ممثلات necklace، وعلى كلمات Lyndon، وعلى عدّ ديناميكي صغير للحصول على موضع كل كلمة دون بناء الدورة نفسها.
لنضع \(k=10\) و\(n=12\). هناك نتيجة كلاسيكية تقول إن وصل جميع كلمات Lyndon التي تقسم أطوالها العدد \(n\) بترتيب معجمي يعطي دورة de Bruijn هي \(B(k,n)\). وإذا قُطعت هذه الدورة مباشرة قبل النافذة \(1^{12}\)، فإن الترتيب الدوري يتحول إلى ترتيب خطي على جميع الكلمات ذات الطول 12.
ومن ثم فلكل كلمة \(w\in\{1,\dots,10\}^{12}\) رتبة وحيدة \(R(w)\in\{1,\dots,10^{12}\}\)، وهي الموضع الذي تظهر فيه الكلمة كنافذة بطول 12 داخل هذه الدورة بعد خطيّتها. هذا هو الترتيب الذي تستخدمه الخوارزمية في الفرز النهائي.
تُسمّى الكلمة necklace إذا كانت أصغر معجميًا من جميع دوراناتها الدورية. وإذا أمكن كتابة necklace ما على الصورة
$$\nu=u^{\,n/p},$$
بحيث يكون \(u\) بدائيًا وكلمة Lyndon في الوقت نفسه، فإن \(p\) هو طول الكتلة الأساسية. هذا العدد هو أحد أهم الثوابت البنيوية في الحل، لأنه يحدد عدد النوافذ المتتالية التي تساهم بها تلك الكتلة داخل بناء de Bruijn.
فعلى سبيل المثال، للكلمة \(1^{12}\) القيمة \(p=1\)، أما الكلمة \((1,2,1,2,\dots,1,2)\) فلها \(p=2\). وعند ترتيب necklace ما، تُحسب أولاً جميع كتل Lyndon الكاملة التي تسبقها، ثم يُرجع داخل الكتلة الحالية بمقدار \(p-1\) خطوة للوصول إلى النافذة التي تمثل الكلمة نفسها.
ثبّت قاسمًا \(d\mid 12\). من أجل عدّ كلمات Lyndon ذات الطول \(d\) حتى حد أعلى تستحثه الكلمة \(w\)، تستبدل التطبيقات هذا الحد أولاً بأكبر necklace \(\eta_d(w)\) لا يتجاوز أول \(d\) رموز من \(w\). هذه هي الصورة القانونية الصحيحة، لأن بناء de Bruijn يفهرس الكتل بواسطة ممثلات necklace لا بواسطة دورانات اعتباطية.
تتم هذه الخطوة بصورة تكرارية: يُحدَّد أول موضع يتوقف فيه المقطع الحالي عن التوافق مع شرط necklace، ثم يُنقص ذلك الرمز بمقدار 1، وتُملأ بقية المواضع بالرمز الأعظم 10. تتوقف العملية تمامًا عندما تصبح الكلمة الناتجة necklace فعلية.
بعد تثبيت necklace الحدية \(\eta=\eta_d(w)\)، تحسب التطبيقات كمية عدّ \(T_d(w)\). والجدول الرئيسي يحقق العلاقة
$$B[t,j]=B[t,j+1]+\bigl(k-\eta_{j+1}\bigr)\,B[t-j-1,0], \qquad B[0,0]=1,$$
حيث \(0\le j<t\). من الناحية المفهومية، تحسب \(B[t,j]\) عدد الإكمالات الممكنة ذات الطول الباقي \(t\) عندما تكون أول \(j\) مواضع قد طابقت الحد \(\eta\) بالفعل. الحد الأول يبقي الرمز التالي مساويًا للحد، أما الحد الثاني فيختار رمزًا أكبر ويترك الباقي حرًا للعد.
كما تُبنى أيضًا طاولة ثانية لحفظ معلومات الحدود: فهي تسجل، لكل لاحقة مهمة، كم طول الجزء الذي يطابق في الوقت نفسه بادئة من \(\eta\). وبهذا يمكن متابعة المقارنات التي تعبر الحد الدوري في زمن ثابت من غير إعادة فحص الرموز. وبالاعتماد على الجدولين معًا تتكون القيمة \(T_d(w)\)، أي عدد البنى الدورية المتوافقة مع necklace الحدية.
ما زالت \(T_d(w)\) تتضمن مساهمات دورية مكررة، لذلك تُعزل كلمات Lyndon البدائية بواسطة عكس Möbius:
$$L_d(w)=\frac{1}{d}\sum_{e\mid d}\mu\!\left(\frac{d}{e}\right)T_e(w).$$
هنا تمثل \(L_d(w)\) عدد كلمات Lyndon ذات الطول \(d\) التي لا تتجاوز الحد الذي تفرضه \(w\)، و\(\mu\) هي دالة Möbius. هذه الصيغة على القواسم تزيل بالضبط الزيادة في العد الناتجة من تكرار كلمات بدائية أقصر عدة مرات.
إذا كانت \(w\) نفسها necklace، فإن رتبتها في ترتيب de Bruijn تعطى بـ
$$R(w)=1-p(w)+\sum_{d\mid 12} d\,L_d(w).$$
المجموع \(\sum d\,L_d(w)\) هو العدد الكلي للنوافذ بطول 12 التي تنتجها جميع كتل Lyndon المؤهلة حتى \(w\). أما التصحيح \(1-p(w)\) فيعيد الموضع من نهاية الكتلة الحالية إلى النافذة المحددة التي تمثلها \(w\).
كل كلمة ليست necklace هي دوران لكلمة necklace وحيدة. تقوم التطبيقات بتدوير \(w\) نحو اليسار حتى تظهر أول necklace \(\nu\) في مدارها. وإذا لم يقطع هذا الدوران الموضع الذي جرى عنده شق دورة de Bruijn، فإن \(R(w)\) يُستخلص من \(R(\nu)\) بإضافة أو طرح الإزاحة المناسبة داخل الكتلة نفسها.
العائلة الاستثنائية الوحيدة هي
$$w=(\underbrace{10,\dots,10}_{t},\underbrace{1,\dots,1}_{12-t}), \qquad 1\le t\le 12.$$
فهذه الكلمات بالضبط تعبر موضع القطع بين نهاية الدورة وبداية النافذة \(1^{12}\). ولذلك فهي تشغل آخر \(t\) مواضع من الترتيب الخطي، ومن ثم
$$R(w)=10^{12}-t+1.$$
ومثال ملموس على ذلك \(w=(10,10,1,1,\dots,1)\)، حيث \(t=2\)، فتكون الرتبة \(10^{12}-1\). هذا هو الفرع الخاص الذي يظهر صراحة في جميع التطبيقات الثلاثة.
تتبع تطبيقات ++C وPython وJava المسار نفسه. فهي تولد أولاً القيم شبه العشوائية، وتحفظ كل قيمة على هيئة تمثيل عشري من 12 خانة مع الأصفار البادئة، ثم تعيد تفسير تلك الخانات ككلمة على الأبجدية \(\{1,\dots,10\}\).
بعد ذلك تُحسب مسبقًا الجداول الحسابية الصغيرة التي يعاد استخدامها: القوى \(10^0,10^1,\dots,10^{12}\) وقيم Möbius للأعداد \(1,\dots,12\). ولكل كلمة مولدة، تحدد الخوارزمية هل هي necklace أصلًا، وإن لم تكن كذلك تبحث عن necklace الحدية المناسبة، ثم تقيّم صيغ العد على قواسم 12، وتجمع هذه النتائج للحصول على رتبة de Bruijn النهائية \(R(w)\).
بعد إقران كل قيمة برتبتها، تُرتب القائمة حسب الرتبة. وفي المرور الأخير تُحسب \(F(N)\) بدقة تامة للحالات الصغيرة المستخدمة في التحقق، وباقي المدخلات تُحسب modulo \(1234567891\). نسخة ++C توازي فقط مرحلة حساب الرتب المستقلة؛ أما المضمون الرياضي فهو واحد في اللغات الثلاث.
حجم الأبجدية وطول الكلمة ثابتان: \(k=10\) و\(n=12\). لذلك فإن كلفة ترتيب عنصر واحد محدودة بكمية ثابتة من العمل على قواسم 12 وعلى بضعة جداول بحجم \(12\times12\). ومع وجود \(N\) قيمة مولدة، تصبح الكلفة المسيطرة هي عملية الفرز النهائية، وبالتالي يكون الزمن الكلي \(O(N\log N)\).
أما الذاكرة فهي \(O(N)\)، لأن القيم المولدة ورتبها يجب أن تبقى مخزنة قبل الفرز. والمكسب الرياضي الحاسم هو أن الخوارزمية لا تبني دورة de Bruijn ذات الطول \(10^{12}\) أبدًا، بل تصل مباشرة إلى موضع كل كلمة عبر تطبيع necklace، وعكس Möbius، وعدّ ديناميكي قصير.