An odd-run composition of \(n\) is a composition \(n=p_1+p_2+\cdots+p_m\) in which every maximal block of equal adjacent parts has odd length. For example, \(2+1+1+1\) is valid because the run of 1's has length 3, while \(2+2+1\) is invalid because the run of 2's has length 2.
The problem asks for the number \(u_{100000}\) of such compositions of \(100000\), reduced modulo \(1{,}111{,}124{,}111\). The solution does not enumerate compositions. Instead it builds a generating function for allowed runs, converts that to a divisor-sum coefficient sequence, and then extracts the required coefficient by inverting a formal power series.
Let \(u_n\) be the number of odd-run compositions of \(n\), and let
$$U(x)=\sum_{n\ge 0}u_nx^n,$$
with \(u_0=1\) for the empty composition. The derivation becomes clean once compositions are viewed as sequences of runs instead of sequences of individual parts.
Fix a part size \(j\ge 1\). A maximal run consisting of \(j\)'s may have length \(1,3,5,\dots\), so its contribution to the ordinary generating function is
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$
An odd-run composition is therefore a sequence of such runs where two consecutive runs are not allowed to have the same part size, because otherwise they would merge into a longer run.
A composition can be regarded as a word over the infinite alphabet \(\{1,2,3,\dots\}\), where the letter \(j\) carries weight \(x^j\). After compressing each maximal run into one symbol, we get a word with no equal adjacent letters. For such words, the standard Smirnov-word generating function with letter weights \(y_j\) is
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$
One way to see this is to start from unrestricted words, whose generating function is \(1/(1-\sum z_j)\), and replace a letter \(j\) by a positive run of \(j\)'s. Then \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\), so \(z_j=y_j/(1+y_j)\).
For odd-run compositions we substitute \(y_j=R_j(x)\), which gives
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$
So the whole problem is reduced to understanding the series
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}.$$
The Fibonacci generating function is
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$
Substituting \(t=-x^j\) yields
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$
Now collect equal powers of \(x\). Writing
$$A(x)=\sum_{n\ge 1}a_nx^n,$$
the coefficient of \(x^n\) receives one contribution from each factorization \(n=jm\). Equivalently,
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$
This divisor sum is exactly the sequence constructed by the implementations before any fast polynomial work begins.
Since \(U(x)=1/(1-A(x))\), we have
$$\bigl(1-A(x)\bigr)U(x)=1.$$
Comparing coefficients gives the fundamental recurrence
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
This already solves the problem conceptually: once the divisor-sum coefficients \(a_k\) are known, the answer sequence is determined uniquely.
The first divisor-sum coefficients are
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
Using the recurrence,
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$
and then
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$
This matches direct inspection. Valid examples include \(5\), \(1+3+1\), \(2+1+2\), \(2+1+1+1\), and \(1+1+1+1+1\). Invalid examples such as \(2+2+1\) or \(1+1+3\) fail because they contain an even-length run.
The C++, Python, and Java implementations first generate Fibonacci numbers modulo \(1{,}111{,}124{,}111\). Then, for each \(d\), they add the signed Fibonacci value \((-1)^{d-1}F_d\) to every multiple of \(d\). After this divisor sweep, the array holds \(a_1,a_2,\dots,a_n\), the coefficients of \(A(x)\).
A direct use of the coefficient recurrence is quadratic, so it is only suitable for small verification cases. For the real target \(n=100000\), the implementations form the series \(B(x)=1-A(x)\) and compute its inverse modulo \(x^{n+1}\) by Newton iteration. If \(G(x)\) is correct up to degree \(m-1\), the next approximation is
$$G_{\text{new}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$
Because the constant term of \(B(x)\) is 1, this inverse exists as a formal power series. Each Newton step roughly doubles the number of correct coefficients, and the coefficient of \(x^n\) in the final inverse is exactly \(u_n\).
The expensive part of Newton iteration is polynomial multiplication. The C++ and Java implementations evaluate these convolutions with a number-theoretic transform under three auxiliary NTT-friendly prime moduli, then recombine the results with the Chinese remainder theorem to recover coefficients modulo \(1{,}111{,}124{,}111\). The Python implementation is a thin wrapper around the same C++ computation, so all three language entries follow the same mathematical pipeline.
Constructing the divisor-sum coefficients costs
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$
The fast phase is the formal power-series inversion. With FFT-style multiplication cost \(M(n)=O(n\log n)\), Newton iteration runs in \(O(M(n)\log n)\), which here is \(O(n\log^2 n)\). Memory usage is \(O(n)\) for the coefficient arrays and transform buffers.
The slower recurrence \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) is \(O(n^2)\) and appears only as a correctness check on small inputs. The actual computation for \(n=100000\) relies on the quasi-linear series inversion.
Eine Odd-Run-Komposition von \(n\) ist eine Komposition \(n=p_1+p_2+\cdots+p_m\), bei der jeder maximale Block gleicher benachbarter Teile ungerade Länge hat. Zum Beispiel ist \(2+1+1+1\) erlaubt, weil der 1er-Block Länge 3 hat, während \(2+2+1\) verboten ist, weil der 2er-Block Länge 2 hat.
Gesucht ist die Anzahl \(u_{100000}\) solcher Kompositionen von \(100000\) modulo \(1{,}111{,}124{,}111\). Die Lösung zählt diese Objekte nicht direkt. Stattdessen formuliert sie eine erzeugende Funktion für zulässige Blöcke, überführt diese in eine Teiler-Summen-Folge und gewinnt den gesuchten Koeffizienten durch Inversion einer formalen Potenzreihe.
Sei \(u_n\) die Anzahl der Odd-Run-Kompositionen von \(n\), und sei
$$U(x)=\sum_{n\ge 0}u_nx^n,$$
wobei \(u_0=1\) die leere Komposition beschreibt. Die Herleitung wird übersichtlich, wenn man nicht einzelne Teile, sondern ganze Läufe betrachtet.
Fixiere eine Teilgröße \(j\ge 1\). Ein maximaler Lauf aus \(j\)'s darf Länge \(1,3,5,\dots\) haben. Sein Beitrag zur gewöhnlichen erzeugenden Funktion ist also
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$
Eine Odd-Run-Komposition ist damit eine Folge solcher Läufe, wobei zwei aufeinanderfolgende Läufe nicht dieselbe Teilgröße haben dürfen; andernfalls würden sie zu einem längeren Lauf verschmelzen.
Eine Komposition kann als Wort über dem unendlichen Alphabet \(\{1,2,3,\dots\}\) aufgefasst werden, wobei der Buchstabe \(j\) Gewicht \(x^j\) trägt. Wenn man jeden maximalen Lauf zu einem Symbol komprimiert, erhält man ein Wort ohne gleiche benachbarte Buchstaben. Für solche Wörter lautet die Standardformel für Smirnov-Wörter mit Buchstabengewichten \(y_j\)
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$
Man kann dies aus der Formel für uneingeschränkte Wörter \(1/(1-\sum z_j)\) gewinnen: Ersetzt man einen Buchstaben \(j\) durch einen positiven Lauf aus \(j\)'s, dann ist \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\), also \(z_j=y_j/(1+y_j)\).
Für Odd-Run-Kompositionen setzen wir \(y_j=R_j(x)\) ein und erhalten
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$
Damit ist alles auf die Reihe
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}$$
zurückgeführt.
Die erzeugende Funktion der Fibonacci-Zahlen ist
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$
Setzt man \(t=-x^j\), so folgt
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$
Nun werden gleiche Potenzen von \(x\) zusammengefasst. Mit
$$A(x)=\sum_{n\ge 1}a_nx^n$$
erhält jeder Koeffizient von \(x^n\) genau einen Beitrag für jede Faktorisierung \(n=jm\). Äquivalent dazu gilt
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$
Genau diese Teiler-Summe wird in den Implementierungen zuerst aufgebaut.
Aus \(U(x)=1/(1-A(x))\) folgt
$$\bigl(1-A(x)\bigr)U(x)=1.$$
Koeffizientenvergleich liefert die zentrale Rekurrenz
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
Damit ist das Problem bereits konzeptionell gelöst: Sind die Werte \(a_k\) bekannt, ist die Folge \(u_n\) eindeutig bestimmt.
Die ersten Teiler-Summen-Koeffizienten sind
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
Mit der Rekurrenz erhält man
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$
und dann
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$
Das stimmt mit direkter Aufzählung überein. Gültige Beispiele sind \(5\), \(1+3+1\), \(2+1+2\), \(2+1+1+1\) und \(1+1+1+1+1\). Ungültige Beispiele wie \(2+2+1\) oder \(1+1+3\) scheitern an einem Lauf gerader Länge.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst Fibonacci-Zahlen modulo \(1{,}111{,}124{,}111\). Danach addieren sie für jedes \(d\) den vorzeichenbehafteten Fibonacci-Wert \((-1)^{d-1}F_d\) zu jedem Vielfachen von \(d\). Nach diesem Teilerdurchlauf enthält das Array genau \(a_1,a_2,\dots,a_n\), also die Koeffizienten von \(A(x)\).
Die direkte Rekurrenz ist quadratisch und daher nur für kleine Kontrollfälle brauchbar. Für das eigentliche Ziel \(n=100000\) bilden die Implementierungen die Reihe \(B(x)=1-A(x)\) und berechnen ihre Inverse modulo \(x^{n+1}\) per Newton-Iteration. Ist \(G(x)\) bis Grad \(m-1\) korrekt, dann lautet die nächste Näherung
$$G_{\text{neu}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$
Da der konstante Term von \(B(x)\) gleich 1 ist, existiert diese Inverse als formale Potenzreihe. Jeder Newton-Schritt verdoppelt ungefähr die Zahl korrekter Koeffizienten, und der Koeffizient von \(x^n\) in der Endreihe ist genau \(u_n\).
Der teure Teil der Newton-Iteration ist die Polynom-Multiplikation. Die C++- und Java-Implementierungen verwenden dafür eine zahlentheoretische Transformation unter drei NTT-freundlichen Primmoduli und setzen die Resultate anschließend mit dem chinesischen Restsatz zu Koeffizienten modulo \(1{,}111{,}124{,}111\) zusammen. Der Python-Eintrag ist ein schlanker Wrapper um dieselbe C++-Berechnung; mathematisch folgen also alle drei Sprachversionen demselben Verfahren.
Der Aufbau der Teiler-Summen-Koeffizienten kostet
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$
Die schnelle Phase ist die Inversion der formalen Potenzreihe. Bei FFT-artigen Multiplikationskosten \(M(n)=O(n\log n)\) läuft die Newton-Iteration in \(O(M(n)\log n)\), also hier in \(O(n\log^2 n)\). Der Speicherbedarf ist \(O(n)\) für Koeffizientenfelder und Transformationspuffer.
Die langsamere Rekurrenz \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) hat Aufwand \(O(n^2)\) und dient nur zur Verifikation auf kleinen Eingaben. Für \(n=100000\) wird die quaselineare Reiheninversion verwendet.
Bir odd-run composition, yani tek uzunluklu koşu kompozisyonu, \(n=p_1+p_2+\cdots+p_m\) biçimindeki bir kompozisyondur ve eşit ardışık parçaların oluşturduğu her maksimal blok tek uzunluktadır. Örneğin \(2+1+1+1\) geçerlidir; çünkü 1'lerin koşu uzunluğu 3'tür. Buna karşılık \(2+2+1\) geçersizdir; çünkü 2'lerin koşu uzunluğu 2'dir.
Sorulan şey, \(100000\) sayısının bu tür kompozisyonlarının sayısı olan \(u_{100000}\) değerini \(1{,}111{,}124{,}111\) modunda bulmaktır. Çözüm bunu doğrudan saymaz. Bunun yerine izin verilen koşular için bir üreteç fonksiyonu kurar, bunu bölen toplamı biçimindeki katsayılara dönüştürür ve sonunda gereken katsayıyı bir formal kuvvet serisini tersleyerek çıkarır.
\(u_n\), \(n\)'in odd-run kompozisyonlarının sayısı olsun ve
$$U(x)=\sum_{n\ge 0}u_nx^n$$
olarak tanımlansın; burada boş kompozisyon için \(u_0=1\) alınır. Türetim, parçaları tek tek değil koşular halinde düşündüğümüzde doğal biçimde ortaya çıkar.
\(j\ge 1\) sabit bir parça boyutu olsun. Sadece \(j\)'lerden oluşan maksimal bir koşunun uzunluğu \(1,3,5,\dots\) olabilir. Dolayısıyla bu koşunun sıradan üreteç fonksiyonuna katkısı
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}$$
olur. Böylece odd-run kompozisyonlar, ardışık iki koşunun aynı parça boyutuna sahip olamadığı koşu dizileri haline gelir; aksi halde bu iki koşu birleşip daha uzun tek bir koşu oluşturur.
Bir kompozisyon, her \(j\) harfinin ağırlığı \(x^j\) olan sonsuz alfabe \(\{1,2,3,\dots\}\) üzerinde bir sözcük olarak görülebilir. Her maksimal koşuyu tek bir simgeye sıkıştırınca, yan yana eşit harf içermeyen bir sözcük elde ederiz. Böyle sözcükler için, harf ağırlıkları \(y_j\) ise standart Smirnov-sözcüğü üreteç fonksiyonu
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}$$
şeklindedir. Bunu, serbest sözcüklerin üreteç fonksiyonu \(1/(1-\sum z_j)\) üzerinden görebiliriz: bir \(j\) harfini pozitif uzunluklu bir \(j\) koşusuyla değiştirdiğimizde \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\) olur; dolayısıyla \(z_j=y_j/(1+y_j)\).
Odd-run kompozisyonlar için \(y_j=R_j(x)\) yazınca
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}$$
elde edilir. Böylece ana nesne
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}$$
serisidir.
Fibonacci sayılarına ait üreteç fonksiyonu
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1$$
şeklindedir. Burada \(t=-x^j\) koyarsak
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}$$
elde edilir. Şimdi eşit kuvvetleri gruplayalım. Eğer
$$A(x)=\sum_{n\ge 1}a_nx^n$$
ise, \(x^n\) katsayısı \(n=jm\) çarpanlaşmalarının her birinden bir katkı alır. Eşdeğer biçimde
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d$$
olur. Uygulamalar, hızlı polinom hesabına geçmeden önce tam olarak bu bölen-toplamı dizisini üretir.
\(U(x)=1/(1-A(x))\) olduğundan
$$\bigl(1-A(x)\bigr)U(x)=1$$
yazabiliriz. Katsayı karşılaştırmasından temel bağıntı gelir:
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
Yani kavramsal olarak problem çözülmüştür: \(a_k\) katsayıları bilindiğinde \(u_n\) dizisi tek biçimde belirlenir.
İlk bölen-toplamı katsayıları şöyledir:
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
Bağıntıdan
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4$$
ve ardından
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10$$
bulunur. Bu sonuç doğrudan sayımla da uyuşur. Geçerli örnekler arasında \(5\), \(1+3+1\), \(2+1+2\), \(2+1+1+1\) ve \(1+1+1+1+1\) vardır. \(2+2+1\) ve \(1+1+3\) gibi örnekler ise çift uzunluklu bir koşu içerdiği için dışarıda kalır.
C++, Python ve Java uygulamaları önce Fibonacci sayılarını \(1{,}111{,}124{,}111\) modunda üretir. Sonra her \(d\) için işaretli Fibonacci değeri \((-1)^{d-1}F_d\), \(d\)'nin bütün katlarına eklenir. Bu bölen taraması tamamlandığında dizide \(A(x)\)'in katsayıları olan \(a_1,a_2,\dots,a_n\) bulunur.
Doğrudan katsayı bağıntısını kullanmak \(O(n^2)\) maliyetlidir; bu yüzden ancak küçük doğrulama örnekleri için uygundur. Gerçek hedef olan \(n=100000\) için uygulamalar \(B(x)=1-A(x)\) serisini kurar ve bu serinin \(x^{n+1}\) modundaki tersini Newton iterasyonu ile hesaplar. Eğer \(G(x)\) serisi \(m-1\) dereceye kadar doğruysa yeni yaklaşım
$$G_{\text{yeni}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}$$
şeklindedir. \(B(x)\)'in sabit terimi 1 olduğu için bu ters formal kuvvet serisi olarak vardır. Her Newton adımı yaklaşık olarak doğru katsayı sayısını ikiye katlar; son serideki \(x^n\) katsayısı tam olarak \(u_n\)'dir.
Newton iterasyonunun pahalı kısmı polinom çarpımıdır. C++ ve Java uygulamaları bu konvolüsyonları üç farklı NTT-dostu asal mod altında sayı kuramsal dönüşüm ile hesaplar ve ardından sonuçları Çin kalan teoremiyle birleştirerek katsayıları \(1{,}111{,}124{,}111\) modunda geri kazanır. Python uygulaması ise aynı C++ hesabını çağıran ince bir sarmalayıcıdır; dolayısıyla üç dil girdisinin matematiksel omurgası aynıdır.
Bölen-toplamı katsayılarının kurulma maliyeti
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n)$$
kadardır. Hızlı aşama formal kuvvet serisinin terslenmesidir. FFT-benzeri çarpım maliyeti \(M(n)=O(n\log n)\) olduğunda Newton iterasyonu \(O(M(n)\log n)\), yani burada \(O(n\log^2 n)\) zamanda çalışır. Bellek kullanımı katsayı dizileri ve dönüşüm tamponları için \(O(n)\)'dir.
Daha yavaş olan \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) bağıntısı \(O(n^2)\) zaman alır ve yalnızca küçük girdilerde doğruluk kontrolü için kullanılır. \(n=100000\) için esas yöntem kuazi-lineer seriler terslemesidir.
Una composición de tipo odd-run de \(n\) es una composición \(n=p_1+p_2+\cdots+p_m\) en la que cada bloque maximal de partes iguales consecutivas tiene longitud impar. Por ejemplo, \(2+1+1+1\) es válida porque la racha de 1's tiene longitud 3, mientras que \(2+2+1\) no lo es porque la racha de 2's tiene longitud 2.
El objetivo es calcular \(u_{100000}\), el número de esas composiciones de \(100000\), módulo \(1{,}111{,}124{,}111\). La solución no enumera composiciones. En su lugar construye una función generadora para las rachas permitidas, la transforma en una sucesión de coeficientes dada por sumas sobre divisores y finalmente extrae el coeficiente buscado invirtiendo una serie formal de potencias.
Sea \(u_n\) el número de composiciones odd-run de \(n\), y sea
$$U(x)=\sum_{n\ge 0}u_nx^n,$$
con \(u_0=1\) para la composición vacía. La derivación se vuelve natural cuando se describen las composiciones por rachas máximas en vez de por partes individuales.
Fijemos un tamaño de parte \(j\ge 1\). Una racha maximal formada por \(j\)'s puede tener longitud \(1,3,5,\dots\), así que su contribución a la función generadora ordinaria es
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$
Por tanto, una composición odd-run es una secuencia de estas rachas en la que dos rachas consecutivas no pueden tener el mismo tamaño de parte; si lo tuvieran, se fusionarían en una sola racha más larga.
Una composición puede verse como una palabra sobre el alfabeto infinito \(\{1,2,3,\dots\}\), donde la letra \(j\) pesa \(x^j\). Al comprimir cada racha maximal en un solo símbolo se obtiene una palabra sin letras iguales adyacentes. Para esas palabras, la función generadora estándar de Smirnov con pesos \(y_j\) es
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$
Puede deducirse a partir de las palabras sin restricción, cuya función generadora es \(1/(1-\sum z_j)\): si una letra \(j\) se reemplaza por una racha positiva de \(j\)'s, entonces \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\), de modo que \(z_j=y_j/(1+y_j)\).
Al sustituir \(y_j=R_j(x)\) obtenemos
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$
Así, todo queda reducido a estudiar la serie
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}.$$
La función generadora de Fibonacci es
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$
Si sustituimos \(t=-x^j\), resulta
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$
Ahora agrupamos potencias iguales de \(x\). Si escribimos
$$A(x)=\sum_{n\ge 1}a_nx^n,$$
el coeficiente de \(x^n\) recibe una contribución por cada factorización \(n=jm\). De forma equivalente,
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$
Esa suma sobre divisores es exactamente la sucesión que construyen las implementaciones antes de pasar a la parte rápida de polinomios.
Como \(U(x)=1/(1-A(x))\), se cumple
$$\bigl(1-A(x)\bigr)U(x)=1.$$
Al comparar coeficientes aparece la recurrencia fundamental
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
Conceptualmente, esto ya resuelve el problema: en cuanto conocemos los coeficientes \(a_k\), la sucesión \(u_n\) queda determinada.
Los primeros coeficientes de la suma sobre divisores son
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
Usando la recurrencia se obtiene
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$
y luego
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$
Esto coincide con la enumeración directa. Entre los ejemplos válidos están \(5\), \(1+3+1\), \(2+1+2\), \(2+1+1+1\) y \(1+1+1+1+1\). Ejemplos como \(2+2+1\) o \(1+1+3\) se excluyen porque contienen una racha de longitud par.
Las implementaciones en C++, Python y Java generan primero los números de Fibonacci módulo \(1{,}111{,}124{,}111\). Después, para cada \(d\), añaden el valor firmado \((-1)^{d-1}F_d\) a todos los múltiplos de \(d\). Tras este barrido por divisores, el arreglo contiene \(a_1,a_2,\dots,a_n\), los coeficientes de \(A(x)\).
Usar la recurrencia directamente cuesta tiempo cuadrático, así que solo sirve para comprobaciones pequeñas. Para el objetivo real \(n=100000\), las implementaciones forman la serie \(B(x)=1-A(x)\) y calculan su inversa módulo \(x^{n+1}\) mediante iteración de Newton. Si \(G(x)\) es correcta hasta grado \(m-1\), la siguiente aproximación es
$$G_{\text{nuevo}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$
Como el término constante de \(B(x)\) es 1, esta inversa existe como serie formal de potencias. Cada paso de Newton duplica aproximadamente el número de coeficientes correctos, y el coeficiente de \(x^n\) en la inversa final es exactamente \(u_n\).
La parte costosa de la iteración de Newton es la multiplicación de polinomios. Las implementaciones en C++ y Java realizan esas convoluciones con una transformada numérico-teórica bajo tres módulos primos auxiliares compatibles con NTT y luego recombinan los resultados con el teorema chino del resto para recuperar los coeficientes módulo \(1{,}111{,}124{,}111\). La implementación en Python es un envoltorio fino alrededor del mismo cálculo en C++, por lo que las tres entradas siguen la misma idea matemática.
La construcción de los coeficientes por suma sobre divisores cuesta
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$
La fase rápida es la inversión de la serie formal. Con un coste de multiplicación tipo FFT \(M(n)=O(n\log n)\), la iteración de Newton tarda \(O(M(n)\log n)\), es decir, aquí \(O(n\log^2 n)\). El uso de memoria es \(O(n)\) para arreglos de coeficientes y buffers de transformada.
La recurrencia lenta \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) es \(O(n^2)\) y se usa solo como verificación en entradas pequeñas. El cálculo real para \(n=100000\) depende de la inversión cuasilineal de series.
一个 odd-run 组合是指形如 \(n=p_1+p_2+\cdots+p_m\) 的整数拆分，其中每个由相同相邻部分组成的极大连续段都必须是奇数长度。例如，\(2+1+1+1\) 是合法的，因为 1 的连续段长度是 3；而 \(2+2+1\) 不合法，因为 2 的连续段长度是 2。
题目要求计算 \(100000\) 的这类组合个数 \(u_{100000}\)，并对 \(1{,}111{,}124{,}111\) 取模。实现并不是暴力枚举所有组合，而是先为允许的连续段建立生成函数，再把它化成一个带除数求和的系数序列，最后通过形式幂级数求逆取出所需系数。
记 \(u_n\) 为 \(n\) 的 odd-run 组合个数，并设
$$U(x)=\sum_{n\ge 0}u_nx^n,$$
其中空组合对应 \(u_0=1\)。一旦把问题从“单个部分”改写成“连续段的序列”，整个推导就会变得非常直接。
固定一个部分大小 \(j\ge 1\)。只由 \(j\) 组成的极大连续段，其长度只能是 \(1,3,5,\dots\)，因此它对普通生成函数的贡献为
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$
于是，一个 odd-run 组合可以看成这样的连续段序列，并且相邻两段的部分大小不能相同；否则它们会并成更长的一段。
组合可以看成定义在无限字母表 \(\{1,2,3,\dots\}\) 上的一个词，其中字母 \(j\) 的权重是 \(x^j\)。把每个极大连续段压缩成一个符号以后，就得到一个“相邻字母不能相同”的词。对于这类词，如果字母权重是 \(y_j\)，标准的 Smirnov 词生成函数是
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$
它可以从无约束词的生成函数 \(1/(1-\sum z_j)\) 推出：若把字母 \(j\) 替换成一个正长度的 \(j\)-连续段，则有 \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\)，因此 \(z_j=y_j/(1+y_j)\)。
对 odd-run 组合代入 \(y_j=R_j(x)\)，便得到
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$
所以核心对象就是级数
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}.$$
Fibonacci 数的生成函数是
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$
把 \(t\) 替换成 \(-x^j\)，便有
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$
接下来按相同幂次收集项。若写成
$$A(x)=\sum_{n\ge 1}a_nx^n,$$
那么 \(x^n\) 的系数会从每一个分解 \(n=jm\) 处收到一份贡献。等价地，
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$
这正是实现中在所有快速多项式运算之前先构造出来的那条除数求和序列。
因为 \(U(x)=1/(1-A(x))\)，所以
$$\bigl(1-A(x)\bigr)U(x)=1.$$
比较系数可得基本递推式
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
从组合意义上说，这一步已经完全解决了问题：只要知道所有 \(a_k\)，整个答案序列 \(u_n\) 就唯一确定。
前几个除数求和系数为
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
由递推式得到
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$
再进一步有
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$
这与直接枚举完全一致。合法例子包括 \(5\)、\(1+3+1\)、\(2+1+2\)、\(2+1+1+1\) 和 \(1+1+1+1+1\)；而 \(2+2+1\)、\(1+1+3\) 等则因为含有偶数长度连续段而被排除。
C++、Python 和 Java 实现都会先在模 \(1{,}111{,}124{,}111\) 下生成 Fibonacci 数。然后对每个 \(d\)，把带符号的 Fibonacci 值 \((-1)^{d-1}F_d\) 加到所有 \(d\) 的倍数位置上。这个除数扫描结束后，数组中保存的就是 \(A(x)\) 的系数 \(a_1,a_2,\dots,a_n\)。
直接使用递推式需要二次时间，因此只适合小规模校验。对于真正的目标 \(n=100000\)，实现先构造 \(B(x)=1-A(x)\)，再用 Newton 迭代求它在模 \(x^{n+1}\) 意义下的逆。若 \(G(x)\) 已经在 \(m-1\) 次项以内正确，则下一步近似是
$$G_{\text{new}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$
由于 \(B(x)\) 的常数项等于 1，这个逆在形式幂级数意义下必然存在。每一步 Newton 迭代都大致把正确系数的个数翻倍，而最终逆级数中 \(x^n\) 的系数正好就是 \(u_n\)。
Newton 迭代最耗时的部分是多项式乘法。C++ 和 Java 实现使用三个适合 NTT 的辅助素数模数，在这些模数下进行数论变换卷积，然后借助中国剩余定理把结果合成为模 \(1{,}111{,}124{,}111\) 的系数。Python 实现本身不重写这一套多项式算法，而是作为一个薄封装调用同样的 C++ 计算，因此三种语言入口在数学上完全一致。
构造除数求和系数的代价为
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$
快速阶段是形式幂级数求逆。若 FFT 风格的乘法代价记为 \(M(n)=O(n\log n)\)，那么 Newton 迭代的总复杂度是 \(O(M(n)\log n)\)，在这里即 \(O(n\log^2 n)\)。内存开销为 \(O(n)\)，主要用于系数数组和变换缓冲区。
较慢的递推 \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) 复杂度为 \(O(n^2)\)，只用来做小规模正确性验证。真正用于 \(n=100000\) 的是准线性的级数求逆方法。
Odd-run-композиция числа \(n\) — это композиция \(n=p_1+p_2+\cdots+p_m\), в которой каждый максимальный блок одинаковых соседних слагаемых имеет нечётную длину. Например, \(2+1+1+1\) допустима, потому что блок единиц имеет длину 3, а \(2+2+1\) недопустима, потому что блок двоек имеет длину 2.
Нужно вычислить \(u_{100000}\), то есть число таких композиций числа \(100000\), по модулю \(1{,}111{,}124{,}111\). Решение не перебирает композиции напрямую. Вместо этого оно строит производящую функцию для допустимых блоков, превращает её в последовательность коэффициентов вида суммы по делителям и затем извлекает нужный коэффициент через обращение формального степенного ряда.
Пусть \(u_n\) обозначает число odd-run-композиций числа \(n\), а
$$U(x)=\sum_{n\ge 0}u_nx^n,$$
причём \(u_0=1\) соответствует пустой композиции. Вывод становится прозрачным, если рассматривать не отдельные части, а максимальные серии одинаковых частей.
Зафиксируем размер части \(j\ge 1\). Максимальная серия, состоящая только из \(j\), может иметь длину \(1,3,5,\dots\). Поэтому её вклад в обычную производящую функцию равен
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$
Значит, odd-run-композиция — это последовательность таких серий, в которой две соседние серии не могут иметь один и тот же размер части; иначе они слились бы в одну более длинную серию.
Композицию можно понимать как слово над бесконечным алфавитом \(\{1,2,3,\dots\}\), где буква \(j\) имеет вес \(x^j\). Если сжать каждую максимальную серию в один символ, получится слово без одинаковых соседних букв. Для таких слов стандартная формула для слов Смирнова с весами \(y_j\) имеет вид
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$
Её удобно вывести из формулы для неограниченных слов \(1/(1-\sum z_j)\): если букву \(j\) заменить положительной серией из \(j\), то \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\), а значит \(z_j=y_j/(1+y_j)\).
Подставляя \(y_j=R_j(x)\), получаем
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$
Следовательно, всё сводится к ряду
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}.$$
Производящая функция чисел Фибоначчи имеет вид
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$
Если положить \(t=-x^j\), то получится
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$
Теперь группируем одинаковые степени \(x\). Если написать
$$A(x)=\sum_{n\ge 1}a_nx^n,$$
то коэффициент при \(x^n\) получает вклад от каждого разложения \(n=jm\). Эквивалентно,
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$
Именно эту последовательность сумм по делителям реализации строят до начала быстрой работы с полиномами.
Так как \(U(x)=1/(1-A(x))\), имеем
$$\bigl(1-A(x)\bigr)U(x)=1.$$
Сравнение коэффициентов даёт основную рекурсию
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
С концептуальной точки зрения задача уже решена: как только известны коэффициенты \(a_k\), последовательность \(u_n\) определяется однозначно.
Первые коэффициенты сумм по делителям таковы:
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
Из рекурсии получаем
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$
а затем
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$
Это совпадает с прямым перебором. Допустимы, например, \(5\), \(1+3+1\), \(2+1+2\), \(2+1+1+1\) и \(1+1+1+1+1\). Примеры \(2+2+1\) и \(1+1+3\) запрещены, потому что содержат серию чётной длины.
Реализации на C++, Python и Java сначала вычисляют числа Фибоначчи по модулю \(1{,}111{,}124{,}111\). Затем для каждого \(d\) они добавляют подписанное значение \((-1)^{d-1}F_d\) ко всем кратным \(d\). После этого прохода по делителям массив уже содержит \(a_1,a_2,\dots,a_n\), то есть коэффициенты ряда \(A(x)\).
Прямое использование рекурсии имеет квадратичную сложность, поэтому годится только для небольших проверок. Для реальной цели \(n=100000\) реализации строят ряд \(B(x)=1-A(x)\) и вычисляют его обратный по модулю \(x^{n+1}\) методом Ньютона. Если \(G(x)\) уже верен до степени \(m-1\), то следующее приближение равно
$$G_{\text{new}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$
Поскольку свободный коэффициент \(B(x)\) равен 1, обратный ряд существует в кольце формальных степенных рядов. Каждый шаг Ньютона примерно удваивает число правильных коэффициентов, а коэффициент при \(x^n\) в конечном обратном ряде и есть искомое \(u_n\).
Самая дорогая часть метода Ньютона — умножение полиномов. Реализации на C++ и Java выполняют свёртки с помощью NTT под тремя вспомогательными простыми модулями, удобными для преобразования, а затем объединяют результаты по китайской теореме об остатках, чтобы восстановить коэффициенты по модулю \(1{,}111{,}124{,}111\). Реализация на Python — это тонкая оболочка над тем же вычислением на C++, так что математическая схема во всех трёх языках одинакова.
Построение коэффициентов через суммы по делителям стоит
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$
Быстрая фаза — это обращение формального степенного ряда. Если стоимость FFT-подобного умножения равна \(M(n)=O(n\log n)\), то метод Ньютона работает за \(O(M(n)\log n)\), то есть здесь за \(O(n\log^2 n)\). Память составляет \(O(n)\) для массивов коэффициентов и буферов преобразования.
Медленная рекурсия \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) имеет сложность \(O(n^2)\) и используется только для проверки на малых входах. Вычисление для \(n=100000\) опирается на квазилинейное обращение ряда.
التركيب من نوع odd-run للعدد \(n\) هو تركيب على الصورة \(n=p_1+p_2+\cdots+p_m\) بحيث يكون طول كل كتلة عظمى من الأجزاء المتساوية المتجاورة عددًا فرديًا. فمثلًا \(2+1+1+1\) تركيب صالح لأن طول كتلة الواحدات يساوي 3، بينما \(2+2+1\) غير صالح لأن طول كتلة الاثنينات يساوي 2.
المطلوب هو حساب \(u_{100000}\)، أي عدد هذه التراكيب للعدد \(100000\)، بترديد \(1{,}111{,}124{,}111\). لا تعتمد الحلول على تعداد جميع التراكيب مباشرة، بل تبني دالة مولدة للكتل المسموح بها، ثم تحولها إلى متتالية معاملات معطاة بمجاميع على القواسم، وأخيرًا تستخرج المعامل المطلوب عبر قلب سلسلة قوى شكلية.
لنرمز بعدد تراكيب odd-run للعدد \(n\) بالرمز \(u_n\)، ولنكتب
$$U(x)=\sum_{n\ge 0}u_nx^n,$$
مع أخذ \(u_0=1\) للتركيب الفارغ. يصبح الاشتقاق منظمًا جدًا إذا وصفنا التراكيب على مستوى الكتل المتتالية بدلًا من الأجزاء المفردة.
ثبّت حجم جزء \(j\ge 1\). الكتلة العظمى المكوّنة فقط من \(j\) يمكن أن يكون طولها \(1,3,5,\dots\)، ومن ثم يكون إسهامها في الدالة المولدة العادية
$$R_j(x)=x^j+x^{3j}+x^{5j}+\cdots=\frac{x^j}{1-x^{2j}}.$$
إذن فإن تركيب odd-run هو متتالية من هذه الكتل، مع شرط أن الكتلتين المتتاليتين لا يمكن أن تحملَا حجم الجزء نفسه، وإلا لاندـمجتا في كتلة أطول واحدة.
يمكن النظر إلى التركيب على أنه كلمة على الأبجدية اللانهائية \(\{1,2,3,\dots\}\)، حيث يحمل الحرف \(j\) الوزن \(x^j\). وعند ضغط كل كتلة عظمى إلى رمز واحد نحصل على كلمة لا تحتوي حرفين متساويين متجاورين. لهذه الكلمات تكون دالة سميرنوف المولدة القياسية مع أوزان الحروف \(y_j\) هي
$$S(\{y_j\})=\frac{1}{1-\sum_{j\ge 1}\frac{y_j}{1+y_j}}.$$
يمكن تبرير ذلك انطلاقًا من دالة الكلمات غير المقيدة \(1/(1-\sum z_j)\): إذا استُبدل الحرف \(j\) بكتلة موجبة الطول من \(j\)'s، فإن \(y_j=z_j+z_j^2+z_j^3+\cdots=z_j/(1-z_j)\)، ومن ثم \(z_j=y_j/(1+y_j)\).
وبالتعويض \(y_j=R_j(x)\) لتراكيب odd-run نحصل على
$$U(x)=\frac{1}{1-\sum_{j\ge 1}\frac{R_j(x)}{1+R_j(x)}}=\frac{1}{1-\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}}.$$
وهكذا يتركز كل التحليل في السلسلة
$$A(x)=\sum_{j\ge 1}\frac{x^j}{1+x^j-x^{2j}}.$$
الدالة المولدة لأعداد فيبوناتشي هي
$$\sum_{m\ge 1}F_m t^m=\frac{t}{1-t-t^2},\qquad F_1=F_2=1.$$
وبوضع \(t=-x^j\) نحصل على
$$\frac{x^j}{1+x^j-x^{2j}}=\sum_{m\ge 1}(-1)^{m-1}F_m x^{jm}.$$
الآن نجمع الحدود ذات الأس نفسه. إذا كتبنا
$$A(x)=\sum_{n\ge 1}a_nx^n,$$
فإن معامل \(x^n\) يستقبل مساهمة من كل تحليل \(n=jm\). وبصورة مكافئة،
$$a_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$
وهذه بالضبط هي متتالية مجاميع القواسم التي تبنيها الحلول قبل أي خطوة سريعة على كثيرات الحدود.
بما أن \(U(x)=1/(1-A(x))\)، فإن
$$\bigl(1-A(x)\bigr)U(x)=1.$$
وبمقارنة المعاملات نحصل على العلاقة الأساسية
$$u_0=1,\qquad u_n=\sum_{k=1}^{n}a_k\,u_{n-k}\quad(n\ge 1).$$
ومن الناحية المفاهيمية فهذا يحل المسألة تمامًا: ما إن تُعرف معاملات \(a_k\) حتى تتحدد متتالية \(u_n\) بصورة وحيدة.
أول معاملات مجموع القواسم هي
$$a_1=1,\quad a_2=0,\quad a_3=3,\quad a_4=-3,\quad a_5=6.$$
ومن العلاقة العودية نحصل على
$$u_1=1,\qquad u_2=1,\qquad u_3=4,\qquad u_4=4,$$
ثم
$$u_5=a_1u_4+a_2u_3+a_3u_2+a_4u_1+a_5u_0=4+0+3-3+6=10.$$
وهذا يطابق العد المباشر. من الأمثلة الصحيحة \(5\) و\(1+3+1\) و\(2+1+2\) و\(2+1+1+1\) و\(1+1+1+1+1\). أما \(2+2+1\) و\(1+1+3\) فمستبعدتان لأن كلًا منهما يحتوي على كتلة ذات طول زوجي.
تبدأ تطبيقات C++ وPython وJava بحساب أعداد فيبوناتشي بترديد \(1{,}111{,}124{,}111\). بعد ذلك، ولكل \(d\)، تضيف القيمة الموقعة \((-1)^{d-1}F_d\) إلى جميع مضاعفات \(d\). وبعد هذا المسح على القواسم، يحتوي المصفوف على \(a_1,a_2,\dots,a_n\)، أي معاملات السلسلة \(A(x)\).
الاعتماد المباشر على العلاقة العودية يكلّف زمنًا تربيعيًا، لذلك لا يصلح إلا لفحوصات صغيرة. أما للهدف الحقيقي \(n=100000\)، فتبني الحلول السلسلة \(B(x)=1-A(x)\) ثم تحسب معكوسها بترديد \(x^{n+1}\) باستخدام تكرار نيوتن. إذا كانت \(G(x)\) صحيحة حتى الدرجة \(m-1\)، فإن التقريب التالي هو
$$G_{\text{new}}(x)=G(x)\bigl(2-B(x)G(x)\bigr)\pmod{x^m}.$$
ولأن الحد الثابت في \(B(x)\) يساوي 1، فإن هذا المعكوس موجود في حلقة سلاسل القوى الشكلية. وكل خطوة من نيوتن تضاعف تقريبًا عدد المعاملات الصحيحة، ومعامل \(x^n\) في السلسلة النهائية المعكوسة هو بالضبط \(u_n\).
الجزء المكلف في طريقة نيوتن هو ضرب كثيرات الحدود. تنفذ تطبيقتا C++ وJava عمليات الالتفاف باستخدام تحويل عددي نظري تحت ثلاثة مقادير أولية مساعدة مناسبة لـ NTT، ثم تعيد تركيب النتائج بواسطة مبرهنة البواقي الصينية للحصول على المعاملات بترديد \(1{,}111{,}124{,}111\). أما تطبيق Python فهو غلاف خفيف يستدعي الحساب نفسه في C++، ولذلك فإن البنية الرياضية واحدة في اللغات الثلاث.
تكلفة بناء معاملات مجموع القواسم هي
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=O(n\log n).$$
أما المرحلة السريعة فهي قلب سلسلة قوى شكلية. إذا كانت كلفة الضرب على نمط FFT هي \(M(n)=O(n\log n)\)، فإن تكرار نيوتن يعمل في \(O(M(n)\log n)\)، أي هنا \(O(n\log^2 n)\). واستهلاك الذاكرة هو \(O(n)\) لمصفوفات المعاملات ومخازن التحويل.
العلاقة العودية الأبطأ \(u_n=\sum_{k=1}^{n}a_ku_{n-k}\) لها تعقيد \(O(n^2)\) وتُستخدم فقط للتحقق من الصحة على القيم الصغيرة. أما الحساب الفعلي عندما \(n=100000\) فيعتمد على قلب السلاسل شبه الخطي.