Let \(A_1 = 1\), and obtain each later term by reading the previous term as consecutive runs of equal digits. Thus
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
If \(a_n\), \(b_n\), and \(c_n\) denote the numbers of digits \(1\), \(2\), and \(3\) in \(A_n\), the goal is to determine \((a_n,b_n,c_n)\) for an enormous index \(n\). Directly generating \(A_n\) is hopeless because the string length grows exponentially, so the solution must compress the evolution into a fixed-size linear system.
Conway's cosmological theorem states that, after finitely many initial terms, every look-and-say word generated from \(1\) can be decomposed into a concatenation of 92 irreducible building blocks, usually called Conway atoms or Conway elements. The crucial point is that each atom has a deterministic one-step decay into a short list of atoms.
Let \(v_n \in \mathbb{N}^{92}\) be the atom-count vector of \(A_n\), where \(v_n(i)\) is the number of copies of atom \(i\). Define the transition matrix \(M\) by
$$M_{ij} = \text{number of copies of atom } i \text{ produced from one copy of atom } j \text{ in one step}.$$
Then the nonlinear string process becomes the linear recurrence
$$v_{n+1} = M v_n.$$
This is the main mathematical reduction used by the implementation: the sequence is complicated at the string level, but it is linear on the 92-dimensional atom population vector.
The implementations do not start from \(A_1\) in atom form. Instead they move to a small term that already decomposes cleanly into Conway atoms. The first eight terms are
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
The eighth term already lies inside the Conway alphabet and splits as
$$A_8 = 11132 \, 13211.$$
These two substrings are Conway atoms, so \(v_8\) has exactly two nonzero entries, each equal to \(1\). Therefore, for every \(n \ge 8\),
$$v_n = M^{n-8} v_8.$$
For a huge target such as \(n = 10^{12}\), this formula is the reason the problem becomes tractable.
For each atom \(i\), precompute its digit histogram
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
where \(u_{i,r}\) is the number of times digit \(r\) appears in that atom. If we write
$$x_n = (a_n,b_n,c_n),$$
then the final answer is obtained by linear aggregation:
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
Equivalently, if \(D\) is the \(3 \times 92\) matrix of per-atom digit counts, then
$$x_n = D v_n.$$
So the full computation consists of two stages: evolve the atom population, then convert that population into the required digit totals.
Applying \(M\) step by step would still require about \(10^{12}\) updates, which is far too slow. Instead, the implementation computes \(M^{n-8}\) by exponentiation by squaring. That reduces the dependence on \(n\) from linear to logarithmic:
$$M^{n-8} = \prod_{\text{bits of } n-8} M^{2^k}.$$
Because the required output is taken modulo \(2^{30}\), every intermediate matrix entry, vector entry, and digit accumulation can also be reduced modulo \(2^{30}\) without changing the final result modulo \(2^{30}\).
The chosen anchor is also a convenient consistency check. Since
$$A_8 = 1113213211,$$
we immediately obtain
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2.$$
This agrees with the atom decomposition \(11132 \, 13211\): once the initial vector is correct, the matrix method and direct counting coincide at the anchor before any large exponentiation begins.
The C++, Python, and Java implementations all encode the same mathematical data: the 92 Conway atom strings, the one-step decay rule for each atom, and the corresponding sparse \(92 \times 92\) transition matrix. Each column has only a few nonzero entries because one atom decays into at most six atoms.
They also precompute, once, how many \(1\)s, \(2\)s, and \(3\)s occur inside each atom. Starting from the two-atom decomposition of the 8th term, the implementation applies binary exponentiation to evolve the atom-count vector to the requested term and then forms the final digit triple by a weighted sum of those precomputed histograms.
The C++ implementation additionally includes a tiny direct generator for small indices so that checkpoint terms can be verified against the matrix method. The fast path for the real target is the same linear-algebra approach in all three languages.
Let \(K = 92\). In a dense matrix model, one matrix squaring costs \(O(K^3)\), and exponentiation by squaring needs \(O(\log n)\) squarings, so the total running time is
$$O(K^3 \log n).$$
Applying a matrix to a vector costs \(O(K^2)\) and does not change the overall asymptotic bound. The memory usage is \(O(K^2)\) for the transition matrix and \(O(K)\) for vectors and per-atom digit histograms. In practice the runtime is noticeably better than the dense estimate because the transition matrix is sparse.
Es gilt \(A_1 = 1\), und jeder weitere Term entsteht, indem der vorherige Term als Folge gleichartiger Ziffern beschrieben wird. Damit beginnt die Folge als
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
Bezeichnen \(a_n\), \(b_n\) und \(c_n\) die Anzahlen der Ziffern \(1\), \(2\) und \(3\) in \(A_n\), so soll \((a_n,b_n,c_n)\) für ein extrem großes \(n\) bestimmt werden. Eine direkte Erzeugung von \(A_n\) scheidet aus, weil die Wortlänge exponentiell wächst. Deshalb wird die Entwicklung in ein lineares System fester Dimension übersetzt.
Nach dem kosmologischen Satz von Conway zerfällt jedes hinreichend späte Glied der Look-and-say-Folge, die bei \(1\) startet, in eine Verkettung von 92 irreduziblen Bausteinen, den Conway-Atomen. Entscheidend ist dabei: Jedes Atom besitzt eine feste Zerfallsregel und erzeugt nach einem Schritt stets dieselbe kurze Liste anderer Atome.
Sei \(v_n \in \mathbb{N}^{92}\) der Zählvektor der Atome in \(A_n\), also \(v_n(i)\) die Anzahl der Vorkommen von Atom \(i\). Die Übergangsmatrix \(M\) wird definiert durch
$$M_{ij} = \text{Anzahl der Kopien von Atom } i \text{, die aus einer Kopie von Atom } j \text{ in einem Schritt entstehen}.$$
Dann gilt die lineare Rekursion
$$v_{n+1} = M v_n.$$
Damit wird der nichtlineare String-Prozess auf eine lineare Dynamik in nur 92 Dimensionen reduziert.
Die Implementierungen beginnen nicht bei \(A_1\) in Atomdarstellung, sondern springen zu einem kleinen Term, der bereits sauber in Conway-Atome zerfällt. Die ersten acht Glieder lauten
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
Der achte Term gehört bereits zum Conway-Alphabet und zerfällt als
$$A_8 = 11132 \, 13211.$$
Diese beiden Teilwörter sind Conway-Atome. Also besitzt \(v_8\) genau zwei von Null verschiedene Einträge, beide gleich \(1\). Für alle \(n \ge 8\) folgt daher
$$v_n = M^{n-8} v_8.$$
Gerade diese Ankerwahl macht sehr große Zielindizes praktisch berechenbar.
Für jedes Atom \(i\) wird sein Ziffernvektor vorab bestimmt:
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
wobei \(u_{i,r}\) die Anzahl der Ziffer \(r\) in diesem Atom bezeichnet. Schreiben wir
$$x_n = (a_n,b_n,c_n),$$
so erhält man das Endergebnis durch lineare Summation:
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
Mit einer \(3 \times 92\)-Matrix \(D\) der Atom-Histogramme kann man auch schreiben
$$x_n = D v_n.$$
Damit besteht die gesamte Rechnung aus zwei klar getrennten Teilen: erst die Atompopulation entwickeln, dann diese Population in die Zahlen von \(1\), \(2\) und \(3\) umrechnen.
Eine schrittweise Anwendung von \(M\) würde immer noch ungefähr \(10^{12}\) Updates erfordern und ist daher unbrauchbar. Stattdessen wird \(M^{n-8}\) mit binärer Exponentiation berechnet. Dadurch sinkt die Abhängigkeit von \(n\) von linear auf logarithmisch.
Da die Ausgabe modulo \(2^{30}\) gefragt ist, dürfen auch alle Zwischensummen, Matrixeinträge und Vektoreinträge fortlaufend modulo \(2^{30}\) reduziert werden, ohne das Endergebnis modulo \(2^{30}\) zu verändern.
Für den gewählten Anker gilt
$$A_8 = 1113213211,$$
also sofort
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2.$$
Das ist ein nützlicher Kontrollpunkt: Die direkte Zählung stimmt bereits am Startpunkt exakt mit der Atomzerlegung \(11132 \, 13211\) überein.
Die C++-, Python- und Java-Implementierungen verwenden dasselbe mathematische Modell. Sie speichern die 92 Conway-Atomstrings, die jeweilige Ein-Schritt-Zerfallsregel und daraus abgeleitet eine dünn besetzte \(92 \times 92\)-Übergangsmatrix. Jede Spalte hat nur wenige Nichtnull-Einträge, weil ein Atom in höchstens sechs Atome zerfällt.
Zusätzlich wird für jedes Atom einmalig gezählt, wie viele \(1\)en, \(2\)en und \(3\)en es enthält. Ausgehend von der Zwei-Atom-Zerlegung des achten Terms entwickelt die Implementierung per binärer Exponentiation den Atom-Zählvektor bis zum gewünschten Index und bildet anschließend das gesuchte Zifferntripel als gewichtete Summe dieser vorberechneten Histogramme.
Die C++-Implementierung enthält darüber hinaus einen kleinen direkten Generator für sehr kleine Indizes, um Kontrollwerte gegen die Matrixmethode zu prüfen. Der eigentliche schnelle Lösungsweg ist jedoch in allen drei Sprachen identisch.
Mit \(K = 92\) kostet eine Matrixquadratur im dichten Modell \(O(K^3)\), und die binäre Exponentiation benötigt \(O(\log n)\) solcher Schritte. Insgesamt ergibt sich also
$$O(K^3 \log n)$$
Zeit. Eine Matrix-Vektor-Anwendung benötigt \(O(K^2)\) und ändert die asymptotische Schranke nicht. Der Speicherbedarf beträgt \(O(K^2)\) für die Übergangsmatrix sowie \(O(K)\) für Vektoren und Atom-Histogramme. Praktisch ist die Laufzeit deutlich besser als die dichte Abschätzung, weil die Matrix sehr spärlich ist.
\(A_1 = 1\) olsun ve her sonraki terim, bir önceki terimdeki eşit rakam blokları okunarak oluşturulsun. Başlangıç şu şekildedir:
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
\(A_n\) içindeki \(1\), \(2\) ve \(3\) rakamlarının sayıları sırasıyla \(a_n\), \(b_n\) ve \(c_n\) olsun. Amaç, çok büyük bir \(n\) için \((a_n,b_n,c_n)\) değerlerini bulmaktır. Diziyi doğrudan üretmek mümkün değildir, çünkü terim uzunluğu üstel olarak büyür. Bu yüzden çözüm, süreci sabit boyutlu doğrusal cebire indirger.
Conway'in kozmolojik bozunma teoremine göre, \(1\) ile başlayan look-and-say dizisinin yeterince geç terimleri 92 adet indirgenemez yapı taşının ardışık birleşimi olarak yazılabilir. Bu yapı taşlarına Conway atomları denir. Kritik nokta şudur: Her atom, bir adım sonra daima aynı kısa atom listesine dönüşür.
\(A_n\) terimindeki atom sayılarını veren vektör \(v_n \in \mathbb{N}^{92}\) olsun; burada \(v_n(i)\), \(i\). atomun kaç kez göründüğünü belirtir. Geçiş matrisi \(M\) şu şekilde tanımlanır:
$$M_{ij} = \text{bir } j \text{ atomunun bir adım sonra ürettiği } i \text{ atomu sayısı}.$$
Böylece doğrusal bağıntı elde edilir:
$$v_{n+1} = M v_n.$$
Yani metin düzeyinde karmaşık görünen dönüşüm, 92 boyutlu sabit bir vektör uzayında doğrusal hale gelir.
Uygulamalar atom gösterimine doğrudan \(A_1\)'den başlamaz. Bunun yerine, Conway atomlarına temiz biçimde ayrışan küçük bir terim seçilir. İlk sekiz terim şöyledir:
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
Sekizinci terim zaten Conway alfabesinin içindedir ve
$$A_8 = 11132 \, 13211$$
şeklinde ayrılır. Bu iki parça Conway atomudur. Dolayısıyla \(v_8\) vektöründe yalnızca iki tane sıfır olmayan bileşen vardır ve ikisi de \(1\)'dir. Böylece tüm \(n \ge 8\) için
$$v_n = M^{n-8} v_8$$
yazılır. Çok büyük indeksler için asıl hız kazancı buradan gelir.
Her atom \(i\) için rakam histogramı önceden hesaplanır:
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
burada \(u_{i,r}\), ilgili atom içinde \(r\) rakamının kaç kez geçtiğini gösterir. Şimdi
$$x_n = (a_n,b_n,c_n)$$
olsun. O zaman sonuç doğrusal toplama ile bulunur:
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
Eğer atom başına rakam sayılarını tutan \(3 \times 92\) boyutlu matrise \(D\) dersek, aynı ifade
$$x_n = D v_n$$
şeklinde de yazılabilir. Böylece tüm çözüm iki aşamaya ayrılır: önce atom popülasyonunu ilerletmek, sonra bu popülasyondan \(1\), \(2\), \(3\) toplamlarını çıkarmak.
\(M\) matrisini tek tek uygulamak hâlâ yaklaşık \(10^{12}\) adım gerektirir. Bu nedenle uygulama \(M^{n-8}\) ifadesini ikili üs alma ile hesaplar. Böylece \(n\)'ye bağlı maliyet doğrusal olmaktan çıkıp logaritmik olur.
Çıktı \(2^{30}\) modunda istendiği için, bütün ara toplamlarda ve çarpımlarda da sürekli olarak \(2^{30}\) moduna göre indirgeme yapılabilir. Uygulamalar tam olarak bunu yapar.
Seçilen başlangıç terimi için
$$A_8 = 1113213211$$
olduğundan doğrudan
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2$$
elde edilir. Bu, kullanışlı bir doğrulama noktasıdır: atom ayrışımı \(11132 \, 13211\) ile doğrudan rakam sayımı aynı sonucu verir.
C++, Python ve Java uygulamaları aynı matematiksel veriyi kullanır. 92 Conway atomu sabit olarak tanımlanır, her atomun bir sonraki adımda hangi atomlara bozunduğu saklanır ve buradan seyrek bir \(92 \times 92\) geçiş matrisi oluşturulur. Her sütunda çok az sıfır olmayan giriş vardır; çünkü bir atom en fazla altı atoma ayrılır.
Buna ek olarak, her atomun içinde kaç tane \(1\), \(2\) ve \(3\) bulunduğu bir kez önceden sayılır. Sekizinci terimin iki atomlu ayrışımından başlanır, atom sayım vektörü ikili üs alma ile hedef adıma taşınır ve son olarak rakam üçlüsü bu önceden hazırlanmış histogramların ağırlıklı toplamı olarak hesaplanır.
C++ uygulaması ayrıca küçük indeksler için doğrudan üretim yapan bir kontrol yolu içerir. Ancak gerçek hedef için hızlı yöntem, üç dilde de aynı matris yaklaşımıdır.
\(K = 92\) olsun. Yoğun matris modelinde bir kare alma işlemi \(O(K^3)\) zaman alır ve ikili üs alma \(O(\log n)\) adet kare alma gerektirir. Dolayısıyla toplam süre
$$O(K^3 \log n)$$
olur. Matris-vektör çarpımı \(O(K^2)\) maliyetlidir ve baskın terimi değiştirmez. Bellek kullanımı geçiş matrisi için \(O(K^2)\), vektörler ve atom başına rakam sayıları için \(O(K)\)'dir. Pratikte matris seyrek olduğu için çalışma süresi bu kaba üst sınırdan daha iyidir.
Sea \(A_1 = 1\), y obténgase cada término siguiente leyendo el anterior como bloques consecutivos de dígitos iguales. El comienzo de la sucesión es
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
Si \(a_n\), \(b_n\) y \(c_n\) representan cuántos dígitos \(1\), \(2\) y \(3\) aparecen en \(A_n\), debemos hallar \((a_n,b_n,c_n)\) para un índice enorme \(n\). Construir \(A_n\) explícitamente es inviable porque la longitud crece de manera exponencial, así que la solución reemplaza la evolución textual por un sistema lineal de tamaño fijo.
El teorema cosmológico de Conway afirma que, tras un número finito de pasos iniciales, toda palabra look-and-say generada desde \(1\) se descompone en una concatenación de 92 bloques irreducibles, llamados átomos o elementos de Conway. Lo importante es que cada átomo tiene una regla de decaimiento fija: después de un paso siempre produce la misma lista corta de átomos.
Sea \(v_n \in \mathbb{N}^{92}\) el vector de recuentos atómicos de \(A_n\), donde \(v_n(i)\) es el número de copias del átomo \(i\). Definimos la matriz de transición \(M\) por
$$M_{ij} = \text{número de copias del átomo } i \text{ producidas por una copia del átomo } j \text{ en un paso}.$$
Entonces se cumple la recurrencia lineal
$$v_{n+1} = M v_n.$$
Esta es la simplificación decisiva: el proceso no lineal sobre cadenas pasa a ser una evolución lineal en dimensión fija \(92\).
Las implementaciones no arrancan en forma atómica desde \(A_1\). En lugar de eso, avanzan hasta un término pequeño que ya se descompone limpiamente en átomos de Conway. Los ocho primeros términos son
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
El octavo término ya pertenece al alfabeto de Conway y se separa como
$$A_8 = 11132 \, 13211.$$
Estas dos subcadenas son átomos. Por tanto, \(v_8\) tiene exactamente dos entradas no nulas, ambas iguales a \(1\). Para todo \(n \ge 8\) obtenemos
$$v_n = M^{n-8} v_8.$$
Ese punto de partida concreto es lo que hace posible manejar índices gigantescos.
Para cada átomo \(i\) se precalcula su histograma de dígitos:
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
donde \(u_{i,r}\) es el número de veces que el dígito \(r\) aparece en ese átomo. Si escribimos
$$x_n = (a_n,b_n,c_n),$$
entonces el resultado final se obtiene por suma lineal:
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
Equivalentemente, si \(D\) es la matriz \(3 \times 92\) de conteos por átomo, entonces
$$x_n = D v_n.$$
Así, todo el problema se divide en dos partes limpias: evolucionar la población de átomos y luego convertirla en el triple pedido de dígitos.
Aplicar \(M\) una vez por paso seguiría requiriendo alrededor de \(10^{12}\) iteraciones, lo cual es demasiado. Por eso la implementación calcula \(M^{n-8}\) mediante exponenciación binaria. Con ello, la dependencia respecto de \(n\) pasa de lineal a logarítmica.
Como la salida final se toma módulo \(2^{30}\), todas las entradas intermedias de matrices, vectores y sumas también pueden reducirse módulo \(2^{30}\) sin alterar el resultado final módulo \(2^{30}\).
Para el ancla elegida tenemos
$$A_8 = 1113213211,$$
de donde se sigue inmediatamente
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2.$$
Este es un buen control interno: la descomposición atómica \(11132 \, 13211\) y el conteo directo de dígitos coinciden exactamente antes de cualquier potenciación grande.
Las implementaciones en C++, Python y Java usan el mismo modelo matemático. Guardan las 92 cadenas atómicas de Conway, guardan la regla de decaimiento de un paso para cada átomo y construyen a partir de ellas una matriz de transición dispersa de tamaño \(92 \times 92\). Cada columna tiene muy pocas entradas no nulas porque un átomo genera como máximo seis átomos.
Además, precalculan cuántos \(1\), \(2\) y \(3\) contiene cada átomo. Partiendo de la descomposición en dos átomos del octavo término, la implementación evoluciona el vector de recuentos mediante exponenciación binaria y, al final, obtiene \((a_n,b_n,c_n)\) como suma ponderada de esos histogramas por átomo.
La implementación en C++ también conserva un generador directo para índices pequeños, útil para verificar puntos de control. Sin embargo, la vía rápida para el caso real es la misma en los tres lenguajes.
Sea \(K = 92\). En un modelo denso, cada cuadrado de matrices cuesta \(O(K^3)\), y la exponenciación binaria requiere \(O(\log n)\) cuadrados. Por tanto, el tiempo total es
$$O(K^3 \log n).$$
Aplicar una matriz a un vector cuesta \(O(K^2)\) y no cambia la cota asintótica dominante. La memoria es \(O(K^2)\) para la matriz de transición y \(O(K)\) para vectores e histogramas por átomo. En la práctica el rendimiento es mejor que el análisis denso porque la matriz es muy dispersa.
设 \(A_1 = 1\)，之后每一项都通过“读出”前一项中连续相同数字的分组得到，因此序列开头为
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
若 \(a_n\)、\(b_n\)、\(c_n\) 分别表示 \(A_n\) 中数字 \(1\)、\(2\)、\(3\) 的出现次数，题目要求在极大的 \(n\) 下求出三元组 \((a_n,b_n,c_n)\)。直接构造 \(A_n\) 不可行，因为长度按指数级增长，所以必须把字符串演化压缩成一个固定维度的线性系统。
Conway 的 cosmological theorem 说明：从 \(1\) 出发的 look-and-say 序列，在经过有限个初始项之后，每一项都可以唯一地分解成 92 个不可再分的基本块，这些基本块通常称为 Conway 原子。关键之处在于，每个原子在执行一次 look-and-say 之后，都会按固定规则变成一小组新的原子。
令 \(v_n \in \mathbb{N}^{92}\) 表示 \(A_n\) 的原子计数向量，其中 \(v_n(i)\) 是第 \(i\) 个原子的出现次数。定义转移矩阵 \(M\) 为
$$M_{ij} = \text{一个原子 } j \text{ 在一步之后产生的原子 } i \text{ 的个数}.$$
于是原子数量满足线性递推
$$v_{n+1} = M v_n.$$
这一步就是核心简化：原本非线性的字符串改写，被转化成了固定 92 维空间中的线性演化。
实现并不是从 \(A_1\) 就直接写成原子向量，而是先走到一个已经可以干净分解的较小项。前八项为
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
第八项已经落在 Conway 原子字母表中，并且可分解为
$$A_8 = 11132 \, 13211.$$
这两个子串都是 Conway 原子，因此 \(v_8\) 恰好只有两个非零分量，而且它们都等于 \(1\)。于是对于所有 \(n \ge 8\)，有
$$v_n = M^{n-8} v_8.$$
对于 \(n = 10^{12}\) 这样的目标，下式正是整个算法能够成立的关键。
对每个原子 \(i\)，预处理它的数字直方图
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
其中 \(u_{i,r}\) 表示数字 \(r\) 在该原子中出现的次数。记
$$x_n = (a_n,b_n,c_n),$$
则最终答案可以线性求和得到：
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
如果把每个原子的数字计数写成一个 \(3 \times 92\) 矩阵 \(D\)，同样可以写成
$$x_n = D v_n.$$
因此整个过程可以分成两段：先求原子种群的演化，再把原子计数映射回所需的数字总数。
如果按步反复应用 \(M\)，仍然需要大约 \(10^{12}\) 次更新，速度无法接受。所以实现采用二进制快速幂来计算 \(M^{n-8}\)，把对 \(n\) 的依赖从线性降到对数级。
由于最终输出要求按 \(2^{30}\) 取模，矩阵、向量以及累计和都可以在计算过程中持续按 \(2^{30}\) 取模，而不会改变最终的模 \(2^{30}\) 结果。
由
$$A_8 = 1113213211$$
可直接读出
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2.$$
这正好提供了一个很好的检查点：原子分解 \(11132 \, 13211\) 与直接数字计数在起始锚点上完全一致。
C++、Python 和 Java 三个实现使用的是同一套数学模型。它们预置了 92 个 Conway 原子的字符串表示，预置了每个原子一步之后会衰变成哪些原子，并据此构造出一个稀疏的 \(92 \times 92\) 转移矩阵。由于一个原子最多只会产生六个原子，所以每一列的非零项都很少。
随后，程序会一次性统计每个原子内部包含多少个 \(1\)、\(2\)、\(3\)。从第八项对应的两个原子开始，用二进制快速幂把原子计数向量推进到目标项，再将该向量与预处理好的数字直方图做加权求和，得到最终三元组。
C++ 实现另外保留了一个针对很小 \(n\) 的直接生成器，用来做检查点验证；但面向真实目标的快速路径，在三种语言里本质上完全相同。
记 \(K = 92\)。在稠密矩阵分析下，一次矩阵平方的代价是 \(O(K^3)\)，而快速幂需要 \(O(\log n)\) 次这样的运算，因此总时间复杂度为
$$O(K^3 \log n).$$
矩阵乘向量的代价是 \(O(K^2)\)，不会改变主导项。空间复杂度为 \(O(K^2)\)，主要来自转移矩阵；向量和每个原子的数字统计只需要 \(O(K)\) 空间。由于实际矩阵非常稀疏，实际运行时间会明显优于稠密上界。
Пусть \(A_1 = 1\), а каждый следующий член получается из предыдущего чтением подряд идущих одинаковых цифр. Начало последовательности выглядит так:
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
Если \(a_n\), \(b_n\) и \(c_n\) обозначают количества цифр \(1\), \(2\) и \(3\) в \(A_n\), требуется найти тройку \((a_n,b_n,c_n)\) для очень большого \(n\). Прямое построение строки невозможно, потому что длина растет экспоненциально, поэтому решение переводит задачу в линейную алгебру фиксированной размерности.
Космологическая теорема Конвея утверждает, что после конечного числа начальных шагов любой член look-and-say-последовательности, порожденной из \(1\), раскладывается в конкатенацию 92 неделимых блоков, называемых атомами Конвея. Главное свойство этих атомов состоит в том, что каждый атом через один шаг распадается в фиксированный короткий список других атомов.
Обозначим через \(v_n \in \mathbb{N}^{92}\) вектор количеств атомов в \(A_n\), где \(v_n(i)\) равно числу копий атома \(i\). Переходная матрица \(M\) определяется так:
$$M_{ij} = \text{число копий атома } i \text{, возникающих из одной копии атома } j \text{ за один шаг}.$$
Тогда выполняется линейная рекурсия
$$v_{n+1} = M v_n.$$
Именно это и является основным упрощением: нелинейное преобразование строки заменяется линейной динамикой в 92-мерном пространстве.
Реализации не начинают атомное описание прямо с \(A_1\). Вместо этого они переходят к небольшому члену, который уже целиком раскладывается на атомы Конвея. Первые восемь членов таковы:
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
Восьмой член уже принадлежит атомному алфавиту и раскладывается как
$$A_8 = 11132 \, 13211.$$
Обе подстроки являются атомами Конвея. Следовательно, у \(v_8\) ровно две ненулевые компоненты, и обе равны \(1\). Поэтому для всех \(n \ge 8\) имеем
$$v_n = M^{n-8} v_8.$$
Именно этот выбор опорного шага делает возможной работу с индексами порядка \(10^{12}\).
Для каждого атома \(i\) заранее вычисляется его цифровой профиль
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
где \(u_{i,r}\) означает число вхождений цифры \(r\) в этом атоме. Обозначим
$$x_n = (a_n,b_n,c_n).$$
Тогда окончательный ответ получается линейным суммированием:
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
Если собрать эти профили в матрицу \(D\) размера \(3 \times 92\), то то же самое записывается как
$$x_n = D v_n.$$
Значит, весь алгоритм распадается на две ясные части: сначала эволюция популяции атомов, затем перевод этой популяции в искомые суммарные количества цифр.
Если применять \(M\) шаг за шагом, все равно потребуется около \(10^{12}\) обновлений, что слишком медленно. Поэтому реализация вычисляет \(M^{n-8}\) методом двоичного возведения в степень, уменьшая зависимость от \(n\) с линейной до логарифмической.
Так как ответ требуется по модулю \(2^{30}\), все промежуточные значения матриц, векторов и сумм тоже можно все время сокращать по модулю \(2^{30}\), не изменяя итоговый результат по тому же модулю.
Из равенства
$$A_8 = 1113213211$$
сразу следует
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2.$$
Это удобная контрольная точка: атомное разложение \(11132 \, 13211\) согласуется с прямым подсчетом цифр уже в стартовом опорном состоянии.
Реализации на C++, Python и Java используют одну и ту же математическую модель. В них жестко заданы 92 строки атомов Конвея, для каждого атома задан его распад за один шаг, и из этих данных строится разреженная переходная матрица \(92 \times 92\). В каждом столбце очень мало ненулевых элементов, потому что один атом порождает не более шести атомов.
Кроме того, один раз вычисляется, сколько цифр \(1\), \(2\) и \(3\) содержит каждый атом. Начиная с двухатомного разложения восьмого члена, реализация двигает вектор атомных количеств к целевому индексу с помощью двоичного возведения в степень, а затем получает итоговую тройку цифр как взвешенную сумму этих заранее вычисленных профилей.
В версии на C++ дополнительно есть маленький прямой генератор для совсем малых индексов, чтобы сверять контрольные значения. Однако быстрый путь для реальной задачи одинаков во всех трех языках.
Пусть \(K = 92\). В плотной модели одно возведение матрицы в квадрат стоит \(O(K^3)\), а двоичное возведение в степень требует \(O(\log n)\) таких операций. Следовательно, суммарная временная сложность равна
$$O(K^3 \log n).$$
Умножение матрицы на вектор стоит \(O(K^2)\) и не меняет основной асимптотики. Память составляет \(O(K^2)\) для переходной матрицы и \(O(K)\) для векторов и цифровых профилей атомов. На практике время работы лучше плотной оценки, потому что матрица сильно разрежена.
لتكن \(A_1 = 1\)، ويُنشأ كل حد تالٍ بقراءة الحد السابق على هيئة كتل متتالية من الأرقام المتساوية. وبذلك تبدأ المتتالية كما يلي:
$$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$
إذا كانت \(a_n\) و\(b_n\) و\(c_n\) تمثل أعداد الأرقام \(1\) و\(2\) و\(3\) داخل \(A_n\)، فالمطلوب هو إيجاد الثلاثي \((a_n,b_n,c_n)\) عندما يكون \(n\) ضخماً جداً. بناء \(A_n\) حرفياً غير عملي لأن طول السلسلة ينمو نمواً أسياً، لذلك يجب استبدال هذا التطور النصي بنظام خطي ذي بعد ثابت.
تنص نظرية كونواي الكونية على أنه بعد عدد محدود من الحدود الأولى، فإن كل حد من متتالية look-and-say الناتجة من \(1\) يمكن تفكيكه إلى تركيب من 92 لبنة غير قابلة للاختزال، وتسمى عادة بذرات كونواي. الخاصية الحاسمة هنا أن كل ذرة تملك قانون تحلل ثابتاً: بعد خطوة واحدة تتحول دائماً إلى قائمة قصيرة محددة من الذرات.
لنرمز بـ \(v_n \in \mathbb{N}^{92}\) إلى متجه أعداد الذرات في \(A_n\)، بحيث تكون \(v_n(i)\) هي عدد نسخ الذرة \(i\). وإذا رمزنا بـ \(M_{ij}\) إلى عدد نسخ الذرة \(i\) الناتجة من نسخة واحدة من الذرة \(j\) بعد خطوة واحدة، فإن مصفوفة الانتقال \(M\) تحقق
وعندئذٍ نحصل على العلاقة الخطية
$$v_{n+1} = M v_n.$$
وهذه هي الفكرة الجوهرية في الحل: التحويل غير الخطي على مستوى السلسلة يصبح تطوراً خطياً في فضاء بعده \(92\) فقط.
لا تبدأ التطبيقات من \(A_1\) مباشرة بصيغة الذرات، بل تنتقل أولاً إلى حد صغير صار تفكيكه إلى ذرات ممكناً بصورة نظيفة. الحدود الثمانية الأولى هي
$$1,\ 11,\ 21,\ 1211,\ 111221,\ 312211,\ 13112221,\ 1113213211.$$
والحد الثامن أصبح بالفعل داخل أبجدية كونواي، وينقسم إلى
$$A_8 = 11132 \, 13211.$$
وهذان الجزآن ذرتان من ذرات كونواي. لذلك فإن \(v_8\) يحتوي على مركبتين غير صفريتين فقط، وكل منهما يساوي \(1\). ومن ثم، لكل \(n \ge 8\)،
$$v_n = M^{n-8} v_8.$$
وهذه الصيغة هي التي تجعل التعامل مع قيم ضخمة جداً مثل \(10^{12}\) ممكناً عملياً.
لكل ذرة \(i\) نحسب مسبقاً متجه التكرار الرقمي الخاص بها:
$$d_i = (u_{i,1}, u_{i,2}, u_{i,3}),$$
حيث إن \(u_{i,r}\) هو عدد مرات ظهور الرقم \(r\) داخل تلك الذرة. وإذا كتبنا
$$x_n = (a_n,b_n,c_n),$$
فإن النتيجة النهائية تُستخرج بالتجميع الخطي:
$$x_n = \sum_{i=1}^{92} v_n(i)\, d_i.$$
وبصياغة مصفوفية، إذا كانت \(D\) هي مصفوفة الأبعاد \(3 \times 92\) التي تحمل إحصاءات الأرقام داخل الذرات، فإن
$$x_n = D v_n.$$
وبذلك تنقسم المسألة إلى مرحلتين واضحتين: تطوير تعداد الذرات، ثم تحويله إلى أعداد الأرقام المطلوبة.
لو طبقنا \(M\) خطوة بعد خطوة فسنظل بحاجة إلى نحو \(10^{12}\) تحديث، وهذا بطيء جداً. لذلك تحسب التطبيقات \(M^{n-8}\) باستعمال الأس الثنائي، فتنخفض الكلفة المعتمدة على \(n\) من خطية إلى لوغاريتمية.
ولأن الناتج النهائي مطلوب بترديد \(2^{30}\)، يمكن أيضاً اختزال جميع القيم الوسيطة في المصفوفات والمتجهات والمجاميع بترديد \(2^{30}\) دون أن يتغير الجواب النهائي تحت هذا الترديد.
بما أن
$$A_8 = 1113213211,$$
فنحصل مباشرة على
$$a_8 = 6,\qquad b_8 = 2,\qquad c_8 = 2.$$
وهذه نقطة تحقق جيدة: التفكيك الذري \(11132 \, 13211\) يطابق العد المباشر للأرقام قبل البدء بأي عملية رفع كبيرة للقوة.
تستعمل تطبيقات C++ وPython وJava النموذج الرياضي نفسه. فهي تخزن الذرات الـ 92، وتخزن لكل ذرة قائمة الذرات الناتجة عنها بعد خطوة واحدة، ثم تبني من ذلك مصفوفة انتقال sparse بحجم \(92 \times 92\). وكل عمود فيها يحوي عدداً قليلاً من القيم غير الصفرية، لأن الذرة الواحدة تتحلل إلى ست ذرات كحد أقصى.
كذلك تُحسب مرة واحدة أعداد \(1\) و\(2\) و\(3\) داخل كل ذرة. وانطلاقاً من التفكيك المكوَّن من ذرتين للحد الثامن، تقوم الشيفرة بتطوير متجه أعداد الذرات باستخدام الأس الثنائي، ثم تجمع المساهمات الرقمية لهذه الذرات للحصول على الثلاثي النهائي المطلوب.
وتحتوي نسخة C++ أيضاً على مولد مباشر صغير للمؤشرات الصغيرة بهدف التحقق من نقاط الفحص. أما المسار السريع للحالة الحقيقية فهو نفسه في اللغات الثلاث.
لنفرض أن \(K = 92\). في التحليل الكثيف، تكلفة تربيع مصفوفة واحدة هي \(O(K^3)\)، ويحتاج الأس الثنائي إلى \(O(\log n)\) من هذه العمليات. لذلك يكون الزمن الكلي
$$O(K^3 \log n).$$
أما ضرب مصفوفة في متجه فيكلف \(O(K^2)\) ولا يغير الرتبة الغالبة. واستهلاك الذاكرة هو \(O(K^2)\) للمصفوفة الانتقالية و\(O(K)\) للمتجهات وإحصاءات الأرقام لكل ذرة. وعملياً تكون السرعة أفضل من هذا الحد الأعلى لأن المصفوفة شديدة الندرة.