A positive integer is called 11-free if its decimal representation does not contain the decimal expansion of any power \(11^k\) with \(k \ge 1\) as a contiguous substring. The forbidden patterns therefore begin with
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
The single digit \(1\) is allowed, because the definition excludes \(11^0\). If \(E(n)\) denotes the \(n\)-th 11-free positive integer in increasing order, the checkpoints \(E(3)=3\), \(E(200)=213\), and \(E(500000)=531563\) confirm the interpretation. The goal is to compute \(E(10^{18})\), so scanning integers one by one is not realistic.
If the final answer has at most \(D\) digits, then only powers of 11 whose decimal length is at most \(D\) can appear as substrings. Write
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$$
The implementation generates these strings directly in decimal form by repeated multiplication by 11, performed on digit strings rather than with a big-integer library. The C++, Python, and Java implementations all use the safe bound \(D=64\), which is much larger than the actual answer length and therefore guarantees that no relevant forbidden pattern is missed.
When we build a number digit by digit, we do not need to remember the whole prefix. We only need the longest suffix of the current prefix that is also a prefix of some forbidden pattern. That information is exactly what an Aho-Corasick automaton stores.
Let \(s_0\) be the root state, and let \(T(s,d)\) be the state reached after appending digit \(d \in \{0,\dots,9\}\). A state is called terminal if some member of \(\mathcal{P}_D\) has already been matched as a substring. Once a terminal state is reached, the number is invalid forever, so every continuation from that state must be discarded.
For every safe automaton state \(s\) and every remaining length \(r\), define \(A(r,s)\) as the number of length-\(r\) digit strings that can be appended without ever entering a terminal state. The empty suffix gives the base case
$$A(0,s)=1.$$
For \(r \ge 1\), every next digit either leads to another safe state or to a forbidden one, so the recurrence is
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ is safe}}.$$
This is a standard digit-DP over automaton states. Leading zeros are handled outside the recurrence, so zeros are allowed inside the suffix. The implementations also cap every count at \(n+1\): once a count is already larger than the target rank, exact values above that threshold are irrelevant for later comparisons.
Let \(C_L\) be the number of valid \(L\)-digit positive integers. Since the first digit cannot be zero,
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ is safe}}.$$
Now process lengths \(L=1,2,3,\dots\) in order. If the current rank \(n\) is larger than \(C_L\), then all valid \(L\)-digit numbers lie before the desired answer, so we subtract \(C_L\) and continue. The first length for which the remaining rank does not exceed \(C_L\) is the length of \(E(n)\).
After the length \(L\) is known, the number is built from left to right. Suppose we are at position \(i\), currently in state \(s\), with remaining rank \(r\). For a candidate digit \(d\), the number of valid completions is
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ is safe}}.$$
If \(r > B_d\), then every valid number starting with that candidate comes before the target, so we replace \(r\) by \(r-B_d\) and try the next digit. Otherwise we fix that digit and move to the next position. For the first position the candidates are \(1,\dots,9\); afterwards they are \(0,\dots,9\).
This works because all shorter lengths were removed first, and among numbers with the same number of digits, lexicographic order is the same as numerical order.
The checkpoint \(E(200)=213\) is a good sanity check for the substring rule. The number \(211\) is excluded because it contains the forbidden substring \(11\), while \(212\) and \(213\) remain admissible. The same automaton-and-DP framework explains all three published checkpoints without any special cases.
The C++, Python, and Java implementations follow the same plan. They first generate all relevant decimal powers of 11 up to the fixed digit bound. They then build the Aho-Corasick automaton, including failure transitions and terminal propagation, so that every digit extension can be checked in constant time. Next they precompute the table \(A(r,s)\) for every remaining length and every safe state. Finally, they use that table twice: once to determine how many digits the target number has, and once more to reconstruct the exact digits of the answer in increasing order.
A practical implementation detail matters here: the counts are stored with saturation at \(n+1\). This preserves every branch decision of the unranking algorithm while preventing overflow in the fixed-width languages.
Let \(D\) be the chosen digit bound, let \(P=|\mathcal{P}_D|\) be the number of generated forbidden powers, and let \(S\) be the number of automaton states. Generating the patterns costs \(O(PD)\) digit operations. Building the automaton costs \(O(S)\) up to the constant alphabet factor 10.
The dominant phase is the dynamic programming table:
$$O(D \cdot S \cdot 10)$$
time and
$$O(D \cdot S)$$
memory. The final reconstruction adds only \(O(D \cdot 10)\) time. This is negligible compared with any brute-force search for the \(10^{18}\)-th valid integer.
Eine positive ganze Zahl heißt 11-frei, wenn ihre Dezimaldarstellung keine Dezimaldarstellung einer Potenz \(11^k\) mit \(k \ge 1\) als zusammenhängende Teilzeichenkette enthält. Die verbotenen Muster beginnen also mit
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
Die einzelne Ziffer \(1\) bleibt erlaubt, weil \(11^0\) ausdrücklich nicht mitgezählt wird. Bezeichnet \(E(n)\) die \(n\)-te 11-freie positive Zahl in aufsteigender Reihenfolge, dann liefern \(E(3)=3\), \(E(200)=213\) und \(E(500000)=531563\) die bekannten Kontrollwerte. Gesucht ist \(E(10^{18})\); eine direkte Enumeration kommt dafür nicht in Frage.
Hat die gesuchte Zahl höchstens \(D\) Stellen, dann können nur solche Potenzen von 11 als Teilstring auftreten, deren Dezimallänge höchstens \(D\) ist. Daher definieren wir
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$$
Die Implementierung erzeugt diese Muster direkt als Dezimalstrings durch wiederholte Multiplikation mit 11 auf Zeichenkettenebene. Alle drei Implementierungen verwenden die sichere Schranke \(D=64\). Diese liegt deutlich über der tatsächlichen Stellenzahl der Antwort, sodass kein relevantes verbotenes Muster verloren geht.
Beim schrittweisen Aufbau einer Zahl muss man nicht den gesamten bisherigen Präfix speichern. Es genügt, den längsten Suffix des aktuellen Präfixes zu kennen, der zugleich Präfix eines verbotenen Musters ist. Genau diese Information hält ein Aho-Corasick-Automat fest.
Sei \(s_0\) der Startzustand und \(T(s,d)\) der Zustand nach dem Anhängen der Ziffer \(d \in \{0,\dots,9\}\). Ein Zustand heißt terminal, wenn bereits eines der Muster aus \(\mathcal{P}_D\) als Teilstring erkannt wurde. Sobald ein terminaler Zustand erreicht ist, ist die Zahl ungültig; spätere Ziffern können das nicht mehr reparieren.
Für jeden sicheren Zustand \(s\) und jede Restlänge \(r\) sei \(A(r,s)\) die Anzahl der \(r\)-stelligen Ziffernfolgen, die angehängt werden können, ohne je einen terminalen Zustand zu erreichen. Für die leere Fortsetzung gilt
$$A(0,s)=1.$$
Für \(r \ge 1\) folgt dann die Rekursion
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ ist sicher}}.$$
Das ist eine klassische Digit-DP auf Automatenzuständen. Führende Nullen werden getrennt behandelt; innerhalb des Reststrings sind Nullen erlaubt. Außerdem sättigen die Implementierungen jeden Zählwert bei \(n+1\). Exakte Werte oberhalb des gesuchten Rangs sind für die spätere Verzweigungslogik nicht mehr nötig.
Sei \(C_L\) die Anzahl aller gültigen positiven \(L\)-stelligen Zahlen. Da die erste Ziffer nicht null sein darf, gilt
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ ist sicher}}.$$
Nun werden die Längen \(L=1,2,3,\dots\) der Reihe nach geprüft. Ist der aktuelle Rang \(n\) größer als \(C_L\), dann liegen alle gültigen \(L\)-stelligen Zahlen vor der gesuchten Zahl; man zieht also \(C_L\) ab und geht zur nächsten Länge weiter. Die erste Länge, für die der verbleibende Rang höchstens \(C_L\) ist, ist die Stellenzahl von \(E(n)\).
Nachdem die Länge \(L\) feststeht, wird die Zahl von links nach rechts aufgebaut. Befinden wir uns an Position \(i\), im Zustand \(s\), mit verbleibendem Rang \(r\), dann liefert eine Kandidatenziffer \(d\) genau
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ ist sicher}}$$
gültige Fortsetzungen. Falls \(r > B_d\), kommen alle Zahlen mit diesem Kandidaten vor dem Ziel; also ersetzt man \(r\) durch \(r-B_d\) und probiert die nächste Ziffer. Andernfalls wird diese Ziffer fixiert und man geht zur nächsten Position über. In der ersten Stelle testet man \(1,\dots,9\), danach \(0,\dots,9\).
Das Verfahren ist korrekt, weil zuerst alle kürzeren Längen ausgeschlossen werden und weil bei gleicher Stellenzahl die lexikographische Ordnung mit der numerischen Ordnung übereinstimmt.
Der Kontrollwert \(E(200)=213\) illustriert die Regel gut. Die Zahl \(211\) ist ungültig, weil sie den verbotenen Teilstring \(11\) enthält, während \(212\) und \(213\) gültig bleiben. Genau dieselbe Automaten- und DP-Logik erklärt alle veröffentlichten Kontrollpunkte ohne Sonderbehandlung.
Die C++-, Python- und Java-Implementierungen folgen demselben Aufbau. Zuerst werden alle relevanten Dezimalpotenzen von 11 bis zur festen Stellenobergrenze erzeugt. Dann wird der Aho-Corasick-Automat samt Fehlkanten und terminaler Propagation aufgebaut, sodass jede Ziffernerweiterung in konstanter Zeit geprüft werden kann. Anschließend wird die Tabelle \(A(r,s)\) für alle Restlängen und sicheren Zustände vorab berechnet. Diese Tabelle wird zweimal verwendet: zunächst zur Bestimmung der richtigen Länge und danach zur Rekonstruktion der exakten Ziffern der gesuchten Zahl.
Wichtig ist die Sättigung bei \(n+1\). Dadurch bleiben alle Vergleiche des Unranking-Verfahrens korrekt, ohne dass in den Sprachen mit fester Wortbreite Überläufe auftreten.
Seien \(D\) die gewählte Stellenobergrenze, \(P=|\mathcal{P}_D|\) die Anzahl der erzeugten verbotenen Potenzen und \(S\) die Anzahl der Automatenzustände. Das Erzeugen der Muster kostet \(O(PD)\) Ziffernoperationen. Der Aufbau des Automaten kostet bis auf den konstanten Alphabetfaktor 10 genau \(O(S)\).
Der dominierende Teil ist die dynamische Programmierung:
$$O(D \cdot S \cdot 10)$$
Zeit und
$$O(D \cdot S)$$
Speicher. Die anschließende Rekonstruktion benötigt nur noch \(O(D \cdot 10)\) Zeit. Gegenüber jeder Brute-Force-Suche nach der \(10^{18}\)-ten gültigen Zahl ist das verschwindend klein.
Bir pozitif tamsayı, ondalık gösterimi içinde \(k \ge 1\) için herhangi bir \(11^k\) kuvvetinin ondalık yazımını bitişik bir alt dize olarak taşımıyorsa 11-free kabul edilir. Yasak desenler şu şekilde başlar:
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
Tek başına \(1\) rakamı serbesttir; çünkü tanım \(11^0\) durumunu dışarıda bırakır. \(E(n)\) artan sıradaki \(n\). 11-free pozitif sayı olsun. \(E(3)=3\), \(E(200)=213\) ve \(E(500000)=531563\) kontrol değerleri bu sıralamayı doğrular. Hedef \(E(10^{18})\) olduğundan, sayıları tek tek denemek pratik değildir.
Cevabın en fazla \(D\) basamaklı olduğunu varsayalım. O zaman yalnızca ondalık uzunluğu en fazla \(D\) olan \(11\) kuvvetleri alt dize olarak görünebilir. Bu yüzden
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}$$
kümesini oluştururuz. Uygulama bu desenleri büyük tamsayı kütüphanesi kullanmadan, ondalık karakter dizilerini 11 ile art arda çarparak üretir. C++, Python ve Java uygulamalarının üçü de güvenli üst sınır olarak \(D=64\) kullanır; bu değer gerçek cevap uzunluğundan çok daha büyüktür.
Sayıyı soldan sağa kurarken tüm öneki saklamamız gerekmez. Sadece mevcut önekin, herhangi bir yasak desenin öneki olan en uzun son ekini bilmek yeterlidir. Aho-Corasick otomatı tam olarak bu bilgiyi tutar.
\(s_0\) kök durum olsun ve \(T(s,d)\), \(d \in \{0,\dots,9\}\) rakamı eklendiğinde gidilen durum olsun. Bir durum, \(\mathcal{P}_D\) içindeki desenlerden biri zaten eşleşmişse terminal kabul edilir. Terminal duruma ulaşıldıktan sonra sayı artık geçersizdir; sonraki basamaklar bunu düzeltemez.
Her güvenli durum \(s\) ve kalan uzunluk \(r\) için \(A(r,s)\), terminal bir duruma hiç girmeden eklenebilecek \(r\) basamaklı dizilerin sayısı olsun. Boş devam için
$$A(0,s)=1$$
olur. \(r \ge 1\) için geçiş denklemi
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ güvenli}}$$
şeklindedir. Bu, otomat durumları üzerinde klasik bir digit-DP kurulumudur. Baştaki sıfır yasağı ayrıca ele alındığı için, bu son eklerde sıfır kullanılabilir. Uygulamalar ayrıca bütün sayımları \(n+1\) değerinde doyuma uğratır; hedef sıradan daha büyük kesin değerleri ayırt etmeye gerek yoktur.
\(C_L\), geçerli \(L\) basamaklı pozitif sayıların sayısı olsun. İlk basamak sıfır olamayacağından
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ güvenli}}$$
elde edilir. Şimdi \(L=1,2,3,\dots\) uzunluklarını sırayla dolaşırız. Eğer mevcut sıra \(n\), \(C_L\) değerinden büyükse bütün geçerli \(L\) basamaklı sayılar hedeften önce gelir; dolayısıyla \(C_L\) çıkarılır ve bir sonraki uzunluğa geçilir. Kalan sıranın ilk kez \(C_L\) değerini aşmadığı uzunluk, \(E(n)\)'in basamak sayısıdır.
Uzunluk \(L\) belirlendikten sonra sayı soldan sağa oluşturulur. Pozisyon \(i\)'de, durum \(s\)'de ve kalan sıra \(r\)'de olduğumuzu varsayalım. Aday rakam \(d\) için geçerli tamamlanma sayısı
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ güvenli}}$$
olur. Eğer \(r > B_d\) ise, bu rakamla başlayan tüm geçerli sayılar hedeften önce gelir; bu yüzden \(r\) değerinden \(B_d\) çıkarılır ve bir sonraki rakam denenir. Aksi halde rakam sabitlenir ve sonraki pozisyona geçilir. İlk pozisyonda \(1,\dots,9\), sonraki pozisyonlarda \(0,\dots,9\) denenir.
Bu yöntem doğrudur; çünkü önce daha kısa tüm uzunluklar elenir ve eşit uzunluklu sayılarda leksikografik sıra ile sayısal sıra aynıdır.
\(E(200)=213\) kontrolü, alt dize kuralını güzel gösterir. \(211\) sayısı, içinde yasak desen \(11\) bulunduğu için atılır; buna karşılık \(212\) ve \(213\) geçerlidir. Aynı otomat ve DP çerçevesi, yayımlanan tüm kontrol noktalarını özel durum kullanmadan açıklar.
C++, Python ve Java uygulamaları aynı planı uygular. Önce sabit basamak sınırına kadar gerekli tüm \(11\) kuvvetleri üretilir. Sonra başarısızlık geçişleri ve terminal yayılımı ile birlikte Aho-Corasick otomatı kurulur; böylece her yeni rakam sabit zamanda kontrol edilebilir. Ardından tüm kalan uzunluklar ve güvenli durumlar için \(A(r,s)\) tablosu önceden hesaplanır. Son adımda bu tablo iki kez kullanılır: önce cevap uzunluğunu bulmak için, sonra da tam sayıyı basamak basamak yeniden kurmak için.
Buradaki önemli uygulama ayrıntısı, sayımların \(n+1\) seviyesinde doyurulmasıdır. Böylece sabit genişlikli dillerde taşma engellenirken, dallanma kararlarının tamamı doğru kalır.
\(D\) seçilen basamak üst sınırı, \(P=|\mathcal{P}_D|\) üretilen yasak kuvvet sayısı ve \(S\) otomat durum sayısı olsun. Desenleri üretmek \(O(PD)\) basamak işlemi gerektirir. Otomatı kurmak, 10 sembollü sabit alfabe çarpanı dışında \(O(S)\) maliyetlidir.
Baskın kısım dinamik programlama tablosudur:
$$O(D \cdot S \cdot 10)$$
zaman ve
$$O(D \cdot S)$$
bellek kullanılır. Nihai yeniden kurma adımı yalnızca \(O(D \cdot 10)\) zaman ekler. Bu, \(10^{18}\). geçerli sayıya brute-force ile ulaşmaya kıyasla çok küçüktür.
Un entero positivo se llama 11-libre si su representación decimal no contiene, como subcadena contigua, la expansión decimal de ninguna potencia \(11^k\) con \(k \ge 1\). Por tanto, los patrones prohibidos comienzan con
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
El dígito aislado \(1\) sí está permitido, porque la definición excluye \(11^0\). Si \(E(n)\) denota el \(n\)-ésimo entero positivo 11-libre en orden creciente, entonces \(E(3)=3\), \(E(200)=213\) y \(E(500000)=531563\) son puntos de control útiles. El objetivo es hallar \(E(10^{18})\), así que enumerar enteros uno a uno es imposible en la práctica.
Si la respuesta final tiene como mucho \(D\) cifras, solo pueden aparecer como subcadenas aquellas potencias de 11 cuya longitud decimal no exceda \(D\). Definimos
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$$
La implementación genera estas cadenas directamente en decimal mediante multiplicaciones sucesivas por 11 sobre cadenas de dígitos, sin depender de una biblioteca de enteros grandes. Las implementaciones en C++, Python y Java usan el límite seguro \(D=64\), claramente superior a la longitud real de la respuesta.
Al construir un número cifra a cifra no hace falta recordar todo el prefijo ya escrito. Basta con recordar el sufijo más largo del prefijo actual que también sea prefijo de algún patrón prohibido. Esa es exactamente la información que mantiene un autómata de Aho-Corasick.
Sea \(s_0\) el estado inicial y \(T(s,d)\) el estado alcanzado al añadir el dígito \(d \in \{0,\dots,9\}\). Un estado es terminal si ya se ha reconocido como subcadena algún elemento de \(\mathcal{P}_D\). Una vez alcanzado un estado terminal, el número deja de ser válido para siempre.
Para cada estado seguro \(s\) y cada longitud restante \(r\), definimos \(A(r,s)\) como el número de cadenas decimales de longitud \(r\) que pueden añadirse sin entrar nunca en un estado terminal. El caso base es
$$A(0,s)=1.$$
Para \(r \ge 1\), la recurrencia queda
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ es seguro}}.$$
Esto es una digit-DP clásica sobre los estados del autómata. Los ceros iniciales se tratan aparte, de modo que dentro del sufijo sí se permite el dígito cero. Además, las implementaciones saturan cada conteo en \(n+1\); por encima del rango buscado ya no hace falta distinguir valores exactos.
Sea \(C_L\) el número de enteros positivos válidos con exactamente \(L\) cifras. Como la primera cifra no puede ser cero,
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ es seguro}}.$$
Ahora recorremos \(L=1,2,3,\dots\). Si el rango actual \(n\) es mayor que \(C_L\), entonces todo el bloque de números válidos de \(L\) cifras queda antes de \(E(n)\); por eso restamos \(C_L\) y seguimos. La primera longitud para la cual el rango restante no supera a \(C_L\) es la longitud de la respuesta.
Una vez conocida la longitud \(L\), construimos el número de izquierda a derecha. Si estamos en la posición \(i\), en el estado \(s\), con rango restante \(r\), entonces para un dígito candidato \(d\) el número de completaciones válidas es
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ es seguro}}.$$
Si \(r > B_d\), entonces todos los números válidos que empiezan con ese candidato quedan antes del objetivo; restamos \(B_d\) a \(r\) y probamos el siguiente dígito. En caso contrario fijamos ese dígito y avanzamos. En la primera posición se prueban \(1,\dots,9\); en las demás, \(0,\dots,9\).
La corrección es inmediata: primero se eliminan todas las longitudes menores, y dentro de una longitud fija el orden lexicográfico coincide con el orden numérico.
El valor \(E(200)=213\) ilustra bien la regla. El número \(211\) se descarta porque contiene la subcadena prohibida \(11\), mientras que \(212\) y \(213\) siguen siendo válidos. El mismo esquema de autómata más DP explica los tres puntos de control publicados sin ninguna excepción adicional.
Las implementaciones en C++, Python y Java siguen exactamente la misma estructura. Primero generan todas las potencias decimales relevantes de 11 hasta el límite fijo de cifras. Después construyen el autómata de Aho-Corasick, incluyendo enlaces de fallo y propagación de estados terminales, para que cada extensión por una cifra pueda validarse en tiempo constante. A continuación precalculan la tabla \(A(r,s)\) para todas las longitudes restantes y todos los estados seguros. Por último usan esa tabla dos veces: una para encontrar la longitud correcta y otra para reconstruir la respuesta cifra a cifra.
Hay además un detalle práctico importante: los conteos se almacenan saturados en \(n+1\). Eso conserva todas las decisiones del proceso de unranking y evita desbordamientos en los lenguajes con enteros de anchura fija.
Sea \(D\) el límite de cifras elegido, \(P=|\mathcal{P}_D|\) el número de potencias prohibidas generadas y \(S\) el número de estados del autómata. Generar los patrones cuesta \(O(PD)\) operaciones sobre dígitos. Construir el autómata cuesta \(O(S)\) salvo por el factor constante del alfabeto decimal.
La fase dominante es la programación dinámica:
$$O(D \cdot S \cdot 10)$$
de tiempo y
$$O(D \cdot S)$$
de memoria. La reconstrucción final añade solo \(O(D \cdot 10)\) tiempo. Es una mejora enorme frente a cualquier búsqueda exhaustiva hasta el \(10^{18}\)-ésimo entero válido.
如果一个正整数的十进制表示中，不含任何 \(k \ge 1\) 时的 \(11^k\) 的十进制写法作为连续子串，就称它为 11-free。因此，最先出现的禁串是
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
单个数字 \(1\) 仍然允许，因为定义明确排除了 \(11^0\)。记 \(E(n)\) 为按从小到大排列时第 \(n\) 个 11-free 正整数，则 \(E(3)=3\)、\(E(200)=213\)、\(E(500000)=531563\) 是已知校验点。题目要求的是 \(E(10^{18})\)，所以不可能逐个枚举整数来求解。
如果最终答案最多有 \(D\) 位，那么只有十进制长度不超过 \(D\) 的 \(11\) 的幂才可能作为子串出现。于是定义
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$$
实现中并没有依赖大整数库，而是直接对十进制字符串反复乘以 11 来生成这些模式。C++、Python 和 Java 实现统一采用安全上界 \(D=64\)。这个上界明显大于真实答案的位数，因此不会漏掉任何相关禁串。
按位构造数字时，并不需要记住整个前缀。只要知道当前前缀的最长后缀，而这个后缀同时又是某个禁串的前缀，就足够了。这正是 Aho-Corasick 自动机所维护的信息。
设 \(s_0\) 为根状态，\(T(s,d)\) 表示在状态 \(s\) 后追加数字 \(d \in \{0,\dots,9\}\) 所到达的状态。如果某个状态意味着已经匹配到了 \(\mathcal{P}_D\) 中的至少一个禁串，就称其为终止状态。一旦进入终止状态，当前数字必定非法，后续追加任何数字都无法挽回。
对每个安全状态 \(s\) 和剩余长度 \(r\)，定义 \(A(r,s)\) 为还能追加的长度为 \(r\) 的数字串个数，并且在追加过程中始终不进入终止状态。空后缀给出边界条件
$$A(0,s)=1.$$
当 \(r \ge 1\) 时，有递推式
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ 安全}}.$$
这就是自动机状态上的典型 digit DP。前导零单独处理，因此这里的“后缀”内部可以出现数字 0。实现还把所有计数截断在 \(n+1\)：一旦某个数量已经超过目标排名，就没有必要继续保存更大的精确值了。
设 \(C_L\) 为所有合法的 \(L\) 位正整数个数。因为首位不能是 0，所以
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ 安全}}.$$
然后按 \(L=1,2,3,\dots\) 依次扫描。如果当前排名 \(n\) 大于 \(C_L\)，说明所有合法的 \(L\) 位数都排在目标之前，于是从 \(n\) 中减去 \(C_L\) 后继续。第一次满足剩余排名不超过 \(C_L\) 的 \(L\)，就是答案的位数。
位数 \(L\) 确定后，从左到右构造答案。假设当前位是位置 \(i\)，自动机状态为 \(s\)，剩余排名为 \(r\)。若候选数字为 \(d\)，则以它开头的合法补全数量为
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ 安全}}.$$
如果 \(r > B_d\)，说明所有以该候选数字开头的合法数都在目标之前，因此令 \(r \leftarrow r-B_d\) 并尝试下一个数字；否则就固定这个数字并进入下一位。第一位只尝试 \(1,\dots,9\)，之后的位置尝试 \(0,\dots,9\)。
该过程之所以正确，是因为更短的长度已经全部提前剔除，而在固定位数下，无前导零的十进制字符串的字典序与数值大小顺序一致。
\(E(200)=213\) 很适合作为直观验证。数字 \(211\) 因为含有禁串 \(11\) 而被排除，但 \(212\) 和 \(213\) 依然合法。三个公开校验点都能由同一套自动机加动态规划的框架自然解释，不需要任何特殊分支。
C++、Python 和 Java 实现采用相同的结构。首先生成固定位数上界以内的所有相关 \(11\) 的十进制幂；然后建立带失败跳转和终止信息传播的 Aho-Corasick 自动机，使得每次扩展一位数字都能在常数时间内判断是否合法；接着预计算所有剩余长度与安全状态对应的 \(A(r,s)\) 表；最后把这张表使用两次，一次用于确定答案位数，一次用于按升序逐位恢复出真正的答案。
其中一个关键工程细节是计数饱和到 \(n+1\)。这样既能保证反排名过程中的比较结果完全正确，又能避免定长整数语言中的溢出问题。
设 \(D\) 为选定的位数上界，\(P=|\mathcal{P}_D|\) 为生成出的禁串数量，\(S\) 为自动机状态数。生成这些模式需要 \(O(PD)\) 次十进制位操作。建立自动机在十进制字母表固定为 10 的前提下是 \(O(S)\)。
主导成本来自动态规划：
$$O(D \cdot S \cdot 10)$$
时间，以及
$$O(D \cdot S)$$
空间。最后的重建步骤只再增加 \(O(D \cdot 10)\) 时间。与暴力搜索第 \(10^{18}\) 个合法整数相比，这个代价非常小。
Положительное целое число называется 11-свободным, если в его десятичной записи не встречается в качестве непрерывной подстроки десятичная запись никакой степени \(11^k\) при \(k \ge 1\). Поэтому запрещённые шаблоны начинаются так:
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
Одиночная цифра \(1\) разрешена, потому что случай \(11^0\) исключён из определения. Пусть \(E(n)\) обозначает \(n\)-е 11-свободное положительное число в возрастающем порядке. Контрольные значения \(E(3)=3\), \(E(200)=213\) и \(E(500000)=531563\) подтверждают это понимание. Нужно найти \(E(10^{18})\), поэтому перебор чисел по одному здесь невозможен.
Если ответ имеет не более \(D\) цифр, то в качестве подстроки могут появиться только те степени 11, чья десятичная длина не превышает \(D\). Обозначим
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$$
Реализация строит эти строки напрямую в десятичной записи, многократно умножая строку цифр на 11, без использования библиотеки длинной арифметики. Во всех трёх реализациях выбран безопасный предел \(D=64\), существенно превосходящий фактическую длину ответа.
При построении числа слева направо не нужно помнить весь уже набранный префикс. Достаточно знать его самый длинный суффикс, который одновременно является префиксом какого-то запрещённого шаблона. Именно эту информацию хранит автомат Ахо-Корасик.
Пусть \(s_0\) — корневое состояние, а \(T(s,d)\) — состояние после добавления цифры \(d \in \{0,\dots,9\}\). Состояние называется терминальным, если уже найдено совпадение с каким-либо элементом \(\mathcal{P}_D\). Попадание в терминальное состояние делает текущее число недопустимым окончательно.
Для каждого безопасного состояния \(s\) и оставшейся длины \(r\) определим \(A(r,s)\) как число десятичных строк длины \(r\), которые можно дописать, ни разу не попав в терминальное состояние. Для пустого продолжения имеем
$$A(0,s)=1.$$
При \(r \ge 1\) выполняется рекуррентное соотношение
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ безопасно}}.$$
Это обычная digit DP по состояниям автомата. Запрет ведущего нуля обрабатывается отдельно, поэтому внутри суффикса нули допустимы. Кроме того, реализации насыщают все значения на уровне \(n+1\): если количество уже больше искомого ранга, то точное значение выше этого порога не нужно.
Пусть \(C_L\) — число всех допустимых положительных чисел длины \(L\). Так как первая цифра не может быть нулём, получаем
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ безопасно}}.$$
Дальше перебираются длины \(L=1,2,3,\dots\). Если текущий ранг \(n\) больше \(C_L\), значит весь блок допустимых \(L\)-значных чисел лежит перед ответом; тогда вычитаем \(C_L\) и переходим к следующей длине. Первая длина, на которой оставшийся ранг не превосходит \(C_L\), и есть длина \(E(n)\).
После определения длины \(L\) число восстанавливается слева направо. Пусть мы находимся в позиции \(i\), в состоянии \(s\), и имеем оставшийся ранг \(r\). Для кандидата \(d\) число допустимых продолжений равно
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ безопасно}}.$$
Если \(r > B_d\), то все допустимые числа, начинающиеся с этого кандидата, расположены раньше цели; значит, нужно заменить \(r\) на \(r-B_d\) и попробовать следующую цифру. Иначе цифра фиксируется, и алгоритм переходит к следующей позиции. На первом месте перебираются \(1,\dots,9\), далее \(0,\dots,9\).
Корректность следует из двух фактов: сначала исключаются все меньшие длины, а внутри фиксированной длины лексикографический порядок совпадает с обычным числовым порядком.
Проверка \(E(200)=213\) хорошо иллюстрирует правило. Число \(211\) исключается, потому что содержит запрещённую подстроку \(11\), а \(212\) и \(213\) остаются допустимыми. Все опубликованные контрольные значения естественно объясняются той же схемой автомата и динамики.
Реализации на C++, Python и Java устроены одинаково. Сначала они генерируют все релевантные десятичные степени 11 до фиксированной границы по числу цифр. Затем строят автомат Ахо-Корасик с переходами по отказам и распространением терминальности, чтобы каждая попытка дописать цифру проверялась за константное время. После этого заранее вычисляется таблица \(A(r,s)\) для всех оставшихся длин и безопасных состояний. Наконец, эта таблица используется дважды: сначала для выбора правильной длины, потом для восстановления точных цифр ответа по возрастанию.
Важная инженерная деталь состоит в насыщении значений на уровне \(n+1\). Это полностью сохраняет правильность всех сравнений в процедуре unranking и одновременно предотвращает переполнение в языках с фиксированной разрядностью.
Пусть \(D\) — выбранная граница по числу цифр, \(P=|\mathcal{P}_D|\) — число сгенерированных запрещённых степеней, а \(S\) — число состояний автомата. Генерация шаблонов требует \(O(PD)\) операций над цифрами. Построение автомата стоит \(O(S)\), если не считать постоянный множитель алфавита из 10 символов.
Главную стоимость даёт таблица динамики:
$$O(D \cdot S \cdot 10)$$
по времени и
$$O(D \cdot S)$$
по памяти. Финальное восстановление добавляет лишь \(O(D \cdot 10)\) времени. По сравнению с перебором до \(10^{18}\)-го допустимого числа это ничтожно мало.
يُسمّى العدد الصحيح الموجب 11-free إذا كانت كتابته العشرية لا تحتوي، كسلسلة متجاورة، على الكتابة العشرية لأي قوة \(11^k\) حيث \(k \ge 1\). لذلك تبدأ الأنماط الممنوعة بالشكل
$$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$$
أما الرقم المفرد \(1\) فهو مسموح، لأن التعريف يستثني \(11^0\). وإذا رمزنا بـ \(E(n)\) إلى العدد الموجب رقم \(n\) ضمن الأعداد 11-free مرتبة تصاعديًا، فإن قيم التحقق \(E(3)=3\) و\(E(200)=213\) و\(E(500000)=531563\) تؤكد المقصود. المطلوب هو حساب \(E(10^{18})\)، ولذلك فالفحص المباشر للأعداد واحدًا واحدًا غير ممكن.
إذا كان طول الجواب النهائي لا يتجاوز \(D\) أرقام، فلا يمكن أن تظهر كجزء من كتابته إلا قوى العدد 11 التي لا يتجاوز طولها العشري \(D\). لذلك نعرّف
$$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$$
التنفيذ يولّد هذه السلاسل مباشرة في النظام العشري بواسطة ضرب متكرر في 11 على مستوى سلاسل الأرقام، من دون الاعتماد على مكتبة أعداد كبيرة. وتستخدم تطبيقات C++ وPython وJava كلها الحد الآمن \(D=64\)، وهو أكبر بكثير من طول الجواب الحقيقي، لذلك لا يضيع أي نمط ممنوع ذي صلة.
عند بناء العدد رقمًا رقمًا لا نحتاج إلى تذكّر البادئة كاملة. يكفي أن نعرف أطول لاحقة من البادئة الحالية تكون أيضًا بادئةً لأحد الأنماط الممنوعة. هذه هي بالضبط المعلومة التي تحتفظ بها آلة Aho-Corasick.
ليكن \(s_0\) حالة الجذر، ولتكن \(T(s,d)\) الحالة الناتجة عن إضافة الرقم \(d \in \{0,\dots,9\}\). وتُسمّى الحالة نهائية إذا كان أحد عناصر \(\mathcal{P}_D\) قد ظهر بالفعل كسلسلة فرعية. وبمجرد الوصول إلى حالة نهائية يصبح العدد غير صالح نهائيًا، ولا يمكن لأي أرقام لاحقة أن تصلحه.
لكل حالة آمنة \(s\) ولكل طول متبقٍّ \(r\)، نعرّف \(A(r,s)\) على أنه عدد السلاسل العشرية ذات الطول \(r\) التي يمكن إلحاقها من دون الوصول إلى أي حالة نهائية. أما الامتداد الفارغ فيعطي الشرط الابتدائي
$$A(0,s)=1.$$
ولكل \(r \ge 1\) نحصل على العلاقة
$$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ safe}}.$$
هذا هو الشكل القياسي لـ digit DP فوق حالات آلة منتهية. ويُعالَج منع الصفر في البداية بشكل منفصل، لذلك يُسمح بالصفر داخل الذيل نفسه. كذلك تُشبَع جميع العدادات عند القيمة \(n+1\)، لأن أي قيمة أكبر من الرتبة المطلوبة لا تحتاج إلى دقة إضافية من أجل قرارات المقارنة اللاحقة.
ليكن \(C_L\) عدد الأعداد الموجبة الصالحة ذات الطول \(L\). وبما أن الرقم الأول لا يمكن أن يكون صفرًا، فإن
$$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ safe}}.$$
بعد ذلك نفحص الأطوال \(L=1,2,3,\dots\) بالتتابع. فإذا كانت الرتبة الحالية \(n\) أكبر من \(C_L\)، فهذا يعني أن جميع الأعداد الصالحة ذات الطول \(L\) تقع قبل الجواب، فنطرح \(C_L\) وننتقل إلى الطول التالي. وأول طول لا تتجاوز فيه الرتبة المتبقية القيمة \(C_L\) هو طول \(E(n)\).
بعد معرفة الطول \(L\)، يُبنى العدد من اليسار إلى اليمين. إذا كنا في الموضع \(i\)، وفي الحالة \(s\)، ومعنا رتبة متبقية \(r\)، فإن عدد الإكمالات الصالحة للرقم المرشح \(d\) هو
$$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ safe}}.$$
إذا كان \(r > B_d\)، فهذا يعني أن كل عدد صالح يبدأ بهذا الرقم يأتي قبل الهدف، لذا نستبدل \(r\) بـ \(r-B_d\) ونجرّب الرقم التالي. أما إذا لم يحدث ذلك فنثبت هذا الرقم وننتقل إلى الموضع التالي. في الموضع الأول نختبر \(1,\dots,9\)، وبعده نختبر \(0,\dots,9\).
تنجح هذه الطريقة لأن كل الأطوال الأقصر قد أُزيلت أولًا، ولأن الترتيب المعجمي يطابق الترتيب العددي بين السلاسل العشرية ذات الطول نفسه من دون أصفار بادئة.
القيمة \(E(200)=213\) توضح القاعدة مباشرة. فالعدد \(211\) يُستبعَد لأنه يحتوي على السلسلة الممنوعة \(11\)، بينما يبقى \(212\) و\(213\) صالحين. والإطار نفسه المعتمد على الآلة والبرمجة الديناميكية يفسّر قيم التحقق المنشورة كلها من دون أي معالجة خاصة.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تبدأ بتوليد كل قوى 11 العشرية ذات الصلة حتى الحد الثابت لعدد الأرقام، ثم تبني آلة Aho-Corasick مع وصلات الإخفاق وانتشار العلامات النهائية بحيث يمكن فحص كل امتداد برقم جديد في زمن ثابت. بعد ذلك تُحسب مسبقًا الجداول \(A(r,s)\) لكل طول متبقٍّ ولكل حالة آمنة. وأخيرًا تُستخدَم هذه الجداول مرتين: مرة لتحديد طول الجواب، ومرة أخرى لإعادة بنائه رقمًا رقمًا بترتيب تصاعدي.
وهناك تفصيل تنفيذي مهم: تُخزَّن العدادات بعد تشبيعها عند \(n+1\). هذا يكفي للحفاظ على كل قرارات التفرع في عملية unranking، وفي الوقت نفسه يمنع تجاوز السعة في اللغات ذات الأعداد ثابتة العرض.
ليكن \(D\) حد عدد الأرقام المختار، و\(P=|\mathcal{P}_D|\) عدد القوى الممنوعة المولدة، و\(S\) عدد حالات الآلة. توليد الأنماط يكلف \(O(PD)\) من عمليات الأرقام. أما بناء الآلة فتكلفته \(O(S)\) مع إهمال عامل ثابت ناتج عن أبجدية عشرية من 10 رموز.
المرحلة المسيطرة هي جدول البرمجة الديناميكية:
$$O(D \cdot S \cdot 10)$$
زمنًا، و
$$O(D \cdot S)$$
ذاكرةً. أما إعادة البناء النهائية فتضيف فقط \(O(D \cdot 10)\) زمنًا. وهذا ضئيل جدًا مقارنة بمحاولة الوصول بالقوة الغاشمة إلى العدد الصالح رقم \(10^{18}\).