Problem 910 asks for the value of a deeply nested L-expression modulo \(10^9\). The solution is built around the quotient ring
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
Rather than expanding enormous symbolic expressions, the computation keeps every intermediate object as a single polynomial class in \(A\). For the official tuple \((12,345678,9012345,678,90)\), the target quantity is obtained by constructing the final polynomial layer, evaluating it at \(x=678\), adding \(90\), and reducing modulo \(10^9\).
The hard part is therefore not the final substitution. It is finding a representation in which repeated multiplication, repeated composition, and repeated nesting stay finite and algorithmically manageable.
The implementations succeed because the whole L-expression recursion can be rewritten as arithmetic on polynomials of degree at most \(39\). That degree bound is not a heuristic; it is a strict invariant forced by the ring \(A\).
The modulus polynomial \(P(x)\) is monic and has degree \(40\). Therefore every class in \(A\) has a unique remainder of the form
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}.$$
So every gigantic symbolic L-expression is compressed to a coefficient vector in the fixed basis
$$1,x,x^2,\dots,x^{39}.$$
This remains true even though the coefficient ring is \(\mathbb{Z}/10^9\mathbb{Z}\), which is not a field. No division or interpolation is needed; the whole method uses only ring operations that are valid modulo a composite number.
The recursive structure used by the implementations is
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
Here \(xU\) is ordinary multiplication in \(A\), while \(U^{\circ m}\) means \(m\)-fold self-composition. The final answer is then
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M.$$
The mathematical task is to carry out all three layers without ever leaving the degree-\(39\) basis.
Write
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
Because \(P(x)\equiv 0\) in the quotient ring, we have the reduction rule
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}.$$
If
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39},$$
then multiplication by \(x\) becomes
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
This identity is the central reduction step. Once it is available, every overflow term is folded back immediately, so no polynomial of degree \(40\) or more ever has to be stored explicitly.
The previous formula gives multiplication by \(x\). General ring multiplication follows from linearity:
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
So one can build a product from repeated shift-and-reduce steps. Ordinary powers such as \(x^\ell\) are then computed by binary exponentiation inside the ring \(A\).
Composition is handled in the same basis by
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
where all products \(q(x)^i\) are again reduced in \(A\). The same repeated-squaring idea also works for iterated composition, because iterates of one polynomial satisfy
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}.$$
That is exactly what makes the huge parameter \(m=345678\) tractable.
A small example from the built-in validation set is \((n,m,\ell,t,s)=(0,1,1,1,0)\). First,
$$D_1(1)=x+x^2.$$
Since \(m=1\), the middle layer is just one composition:
$$D_2(1,U)=U\circ(xU).$$
Substituting \(U=D_1(1)\) gives
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
with every multiplication reduced modulo \(P(x)\) and modulo \(10^9\). If we call this intermediate polynomial \(V\), then
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2.$$
Evaluating at \(t=1\) yields
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42.$$
This example is small enough to inspect by hand, but it already shows the full mechanism: repeated ring reduction prevents the symbolic nesting from exploding.
The C++, Python, and Java implementations store one polynomial as exactly \(40\) coefficients. Before the main recurrence starts, they expand \(P(x)\), keep its lower-degree coefficients, negate them modulo \(10^9\), and reuse that data whenever an \(x^{40}\) term appears. As a result, multiplying by \(x\) is only a coefficient shift plus one overflow fold-back.
Using that primitive, the implementation builds full polynomial multiplication from shifted copies, computes ordinary powers by binary exponentiation, and computes composition by accumulating \(1,q,q^2,\dots,q^{39}\) in the quotient ring. Iterated self-composition is then obtained by the same binary idea, but with composition replacing multiplication.
The implementation first constructs \(x^\ell\) and then forms the base layer \(x^\ell+x^{\ell+1}\). Next it applies the middle operator \(U\mapsto U^{\circ m}(xU)\) to obtain the first nontrivial nested polynomial. After that, it repeats the same operator \(n\) more times to build the outer layer.
When the final degree-\(39\) representative is ready, the implementation evaluates it at the integer point \(t\) by accumulating the powers \(1,t,t^2,\dots,t^{39}\) modulo \(10^9\). The last operation is simply to add \(s\) and reduce once more.
Let \(D=40\). One ring multiplication costs \(O(D^2)\), because it combines \(D\) shifted-and-reduced copies of a degree-\(39\) polynomial. One composition costs \(O(D^3)\), because it builds the powers \(1,q,q^2,\dots,q^{D-1}\) and combines them with the outer coefficients.
Computing \(x^\ell\) costs \(O(D^2\log \ell)\). Computing \(U^{\circ m}\) costs \(O(D^3\log m)\). Since the outer layer applies the same middle operator \(n+1\) times, the full running time is
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr).$$
With \(D=40\) fixed, this is effectively logarithmic in \(\ell\) and \(m\), and linear in the number of outer nestings. The polynomial storage is \(O(D)\), with only a small constant number of temporaries, plus the shallow recursion depth used for the outer layer.
Problem 910 verlangt den Wert eines tief verschachtelten L-Ausdrucks modulo \(10^9\). Die ganze Rechnung spielt sich im Quotientenring
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
ab. Anstatt riesige symbolische Ausdrücke explizit auszumultiplizieren, speichert die Lösung jedes Zwischenobjekt nur als eine einzige Polynomklasse in \(A\). Für das offizielle Tupel \((12,345678,9012345,678,90)\) wird die letzte Polynomschicht konstruiert, bei \(x=678\) ausgewertet, anschließend \(90\) addiert und alles modulo \(10^9\) reduziert.
Der eigentliche Schwierigkeitsgrad liegt also nicht in der letzten Einsetzung, sondern darin, wiederholte Multiplikation, wiederholte Komposition und wiederholte Verschachtelung in einer endlichen Darstellung zu halten.
Die Implementierungen funktionieren, weil sich die gesamte L-Ausdrucks-Rekursion als Arithmetik mit Polynomen vom Grad höchstens \(39\) formulieren lässt. Diese Schranke ist keine Näherung, sondern eine exakte Invariante des Rings \(A\).
Das Moduluspolynom \(P(x)\) ist normiert und hat Grad \(40\). Daher besitzt jede Klasse in \(A\) genau einen Rest der Form
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}.$$
Jeder noch so große symbolische L-Ausdruck wird also auf einen Koeffizientenvektor in der festen Basis
$$1,x,x^2,\dots,x^{39}$$
komprimiert. Das bleibt sogar dann gültig, wenn der Koeffizientenring \(\mathbb{Z}/10^9\mathbb{Z}\) kein Körper ist. Die Methode benötigt weder Divisionen noch Inversionen, sondern nur Ringoperationen, die modulo einer zusammengesetzten Zahl sinnvoll sind.
Die von den Implementierungen verwendete Rekursion lautet
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
Dabei ist \(xU\) das gewöhnliche Produkt in \(A\), während \(U^{\circ m}\) die \(m\)-fache Selbstkomposition bezeichnet. Die gesuchte Endgröße ist
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M.$$
Mathematisch geht es also darum, alle drei Ebenen vollständig innerhalb der Grad-\(39\)-Darstellung auszuwerten.
Schreibe
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
Da \(P(x)\equiv 0\) im Quotientenring gilt, folgt die zentrale Reduktionsregel
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}.$$
Für
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39}$$
wird Multiplikation mit \(x\) dadurch zu
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
Genau das ist der Kern der gesamten Reduktion. Sobald diese Formel feststeht, wird jeder Überlaufterm sofort zurückgefaltet; Polynome vom Grad \(40\) oder höher müssen nie explizit gespeichert werden.
Die vorherige Formel liefert Multiplikation mit \(x\). Allgemeine Ringmultiplikation folgt dann aus der Linearität:
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
Ein Produkt kann also aus wiederholten Verschiebungs- und Reduktionsschritten aufgebaut werden. Gewöhnliche Potenzen wie \(x^\ell\) lassen sich damit per binärem Exponentieren innerhalb von \(A\) berechnen.
Für die Komposition verwendet man dieselbe Basisdarstellung:
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
wobei auch hier jede Potenz \(q(x)^i\) laufend in \(A\) reduziert wird. Dasselbe Repeated-Squaring-Prinzip funktioniert auch für iterierte Komposition, denn für Iterierte desselben Polynoms gilt
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}.$$
Genau dadurch wird der große Parameter \(m=345678\) algorithmisch handhabbar.
Ein kleines Beispiel aus der eingebauten Validierung ist \((n,m,\ell,t,s)=(0,1,1,1,0)\). Zuerst gilt
$$D_1(1)=x+x^2.$$
Weil \(m=1\) ist, besteht die mittlere Ebene aus genau einer Komposition:
$$D_2(1,U)=U\circ(xU).$$
Mit \(U=D_1(1)\) ergibt sich
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
wobei jede Multiplikation modulo \(P(x)\) und modulo \(10^9\) reduziert wird. Nennt man dieses Zwischenpolynom \(V\), so ist
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2.$$
Die Auswertung bei \(t=1\) liefert
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42.$$
Das Beispiel ist klein genug, um die Struktur sichtbar zu machen, und zeigt bereits den ganzen Mechanismus: Die Quotientenring-Reduktion verhindert das symbolische Explosionstempo.
Die C++-, Python- und Java-Implementierungen speichern ein Polynom immer als genau \(40\) Koeffizienten. Vor der eigentlichen Rekursion wird \(P(x)\) expandiert, die Koeffizienten des unteren Teils werden extrahiert, modulo \(10^9\) negiert und bei jedem entstehenden \(x^{40}\)-Term wiederverwendet. Dadurch ist Multiplikation mit \(x\) nur eine Verschiebung der Koeffizienten plus ein einziges Zurückfalten des Überlaufs.
Auf diesem Baustein beruhen die restlichen Operationen: vollständige Multiplikation über verschobene Kopien, gewöhnliche Potenzen per binärer Exponentiation und Komposition über die Summe \(1,q,q^2,\dots,q^{39}\) im Quotientenring. Iterierte Selbstkomposition entsteht dann durch dasselbe binäre Prinzip, nur mit Komposition statt Multiplikation.
Die Implementierung konstruiert zuerst \(x^\ell\) und daraus die Basisschicht \(x^\ell+x^{\ell+1}\). Danach wird der mittlere Operator \(U\mapsto U^{\circ m}(xU)\) angewendet, um das erste nichttriviale verschachtelte Polynom zu erhalten. Anschließend wird derselbe Operator noch \(n\) weitere Male auf das Ergebnis angewandt.
Wenn der endgültige Grad-\(39\)-Repräsentant vorliegt, wird er am ganzzahligen Punkt \(t\) ausgewertet, indem die Potenzen \(1,t,t^2,\dots,t^{39}\) modulo \(10^9\) sukzessive aufgebaut werden. Zum Schluss kommt noch \(s\) hinzu, gefolgt von einer letzten Reduktion.
Sei \(D=40\). Eine Ringmultiplikation kostet \(O(D^2)\), weil \(D\) verschobene und reduzierte Kopien eines Polynoms kombiniert werden. Eine Komposition kostet \(O(D^3)\), weil die Potenzen \(1,q,q^2,\dots,q^{D-1}\) gebildet und mit den äußeren Koeffizienten gewichtet werden.
Die Berechnung von \(x^\ell\) benötigt \(O(D^2\log \ell)\). Die Berechnung von \(U^{\circ m}\) benötigt \(O(D^3\log m)\). Da die äußere Schicht denselben mittleren Operator \(n+1\)-mal anwendet, ergibt sich insgesamt
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr).$$
Für das feste \(D=40\) ist das effektiv logarithmisch in \(\ell\) und \(m\) und linear in der Anzahl äußerer Verschachtelungen. Der Speicherbedarf liegt bei \(O(D)\) für die Polynomdaten, zuzüglich der kleinen Rekursionstiefe der äußeren Ebene.
Problem 910, derin biçimde iç içe geçen bir L-ifadesinin \(10^9\) modundaki değerini istiyor. Hesabın tamamı şu bölüm halkasında yapılıyor:
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
Devasa sembolik ifadeleri açıkça büyütmek yerine çözüm, her ara nesneyi yalnızca \(A\) içindeki tek bir polinom sınıfı olarak tutuyor. Resmî beşli \((12,345678,9012345,678,90)\) için son polinom katmanı kuruluyor, \(x=678\)'de değerleniyor, ardından \(90\) eklenip sonuç \(10^9\) modunda indirgeniyor.
Dolayısıyla asıl zorluk son yerine koyma adımı değil; tekrar eden çarpım, tekrar eden bileşim ve dış içe yerleştirme işlemlerini sonlu bir temsil içinde tutabilmek.
Çözümün çalışmasının nedeni, bütün L-ifadesi yinelemesinin derece en fazla \(39\) olan polinomlarla ifade edilebilmesidir. Bu sınır sezgisel değil, \(A\) halkasının zorladığı tam bir invariattır.
Modül polinomu \(P(x)\) monik ve derece \(40\) olduğundan, \(A\) içindeki her sınıfın
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}$$
biçiminde tek bir kalanı vardır. Böylece ne kadar büyük olursa olsun her L-ifadesi, sabit
$$1,x,x^2,\dots,x^{39}$$
tabanında bir katsayı vektörüne sıkıştırılır. Katsayı halkası \(\mathbb{Z}/10^9\mathbb{Z}\) bir cisim olmadığı halde bu yaklaşım yine geçerlidir; çünkü yöntem hiç bölme ya da ters alma kullanmaz, sadece bileşik mod altında anlamlı olan halka işlemlerini kullanır.
Uygulamaların kullandığı özyinelemeli yapı şöyledir:
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
Burada \(xU\), \(A\) içindeki sıradan çarpımdır; \(U^{\circ m}\) ise \(U\)'nun \(m\) kez kendisiyle bileşimidir. Sonuçta istenen değer
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M$$
olur. Matematiksel görev, bu üç katmanın tamamını derece-\(39\) temsili terk etmeden hesaplamaktır.
Şöyle yazalım:
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
Bölüm halkasında \(P(x)\equiv 0\) olduğundan temel indirgeme kuralı
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}$$
şeklindedir. Eğer
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39}$$
ise, \(x\) ile çarpma şu hale gelir:
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
Bütün hesaplamanın çekirdeği budur. Bu bağıntı sayesinde taşan her terim anında geri katlanır; derece \(40\) veya daha büyük bir polinomu açıkça saklamaya hiç gerek kalmaz.
Önceki formül bize \(x\) ile çarpmayı verir. Genel halka çarpımı ise doğrusallıktan gelir:
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
Yani bir çarpım, tekrar eden kaydırma ve indirgeme adımlarından kurulabilir. \(x^\ell\) gibi sıradan kuvvetler de böylece \(A\) içinde ikili üs alma ile hesaplanır.
Bileşim de aynı tabanda yapılır:
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
ve burada ortaya çıkan her \(q(x)^i\) yine \(A\) içinde indirgenir. Aynı repeated-squaring fikri yinelemeli bileşim için de çalışır; çünkü aynı polinomun itereleri için
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}$$
geçerlidir. Büyük \(m=345678\) değerinin yönetilebilir olmasının nedeni tam olarak budur.
Yerleşik küçük kontrollerden biri \((n,m,\ell,t,s)=(0,1,1,1,0)\) örneğidir. Önce
$$D_1(1)=x+x^2$$
olur. \(m=1\) olduğu için orta katman tek bir bileşime iner:
$$D_2(1,U)=U\circ(xU).$$
\(U=D_1(1)\) koyunca
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
ve buradaki her çarpım hem \(P(x)\)'e göre hem de \(10^9\)'a göre indirgenir. Bu ara polinoma \(V\) dersek
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2$$
elde edilir. \(t=1\)'de değerleme
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42$$
sonucunu verir. Küçük görünse de bu örnek tam çözüm mekanizmasını gösterir: bölüm halkası indirgemesi sembolik büyümeyi kontrol altında tutar.
C++, Python ve Java uygulamaları bir polinomu her zaman tam \(40\) katsayıyla temsil eder. Ana özyineleme başlamadan önce \(P(x)\) açılır, alt derece katsayıları alınır, bunlar \(10^9\) modunda negatiflenir ve her \(x^{40}\) taşması oluştuğunda yeniden kullanılır. Böylece \(x\) ile çarpma yalnızca katsayı kaydırması ve tek bir taşma geri katlama adımı olur.
Bu ilkel işlemden hareketle tam polinom çarpımı kaydırılmış kopyalarla kurulur, sıradan kuvvetler ikili üs alma ile bulunur, bileşim ise \(1,q,q^2,\dots,q^{39}\) kuvvetlerini bölüm halkasında biriktirerek yapılır. Yinelemeli öz-bileşim de aynı ikili fikirle, bu kez çarpım yerine bileşim kullanılarak hesaplanır.
Uygulama önce \(x^\ell\)'yi oluşturur ve bundan taban katmanı \(x^\ell+x^{\ell+1}\) üretir. Sonra orta operatör \(U\mapsto U^{\circ m}(xU)\) uygulanarak ilk gerçek iç içe polinom elde edilir. Ardından aynı operatör sonuç üzerine \(n\) kez daha uygulanır.
Son derece-\(39\) temsilcisi hazır olduğunda, tamsayı noktası \(t\) için \(1,t,t^2,\dots,t^{39}\) kuvvetleri sırayla kurulup değerleme yapılır. En son yalnızca \(s\) eklenir ve bir kez daha mod alınır.
\(D=40\) olsun. Bir halka çarpımı \(O(D^2)\) zaman alır; çünkü bir polinomun \(D\) kaydırılmış ve indirgenmiş kopyası birleştirilir. Bir bileşim işlemi \(O(D^3)\) maliyetlidir; çünkü \(1,q,q^2,\dots,q^{D-1}\) kuvvetleri kurulup dış polinom katsayılarıyla ağırlıklandırılır.
\(x^\ell\) hesabı \(O(D^2\log \ell)\), \(U^{\circ m}\) hesabı \(O(D^3\log m)\) sürer. Dış katman aynı orta operatörü \(n+1\) kez uyguladığı için toplam süre
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr)$$
olur. \(D=40\) sabit olduğundan pratikte bu, \(\ell\) ve \(m\) için logaritmik, dış katman sayısı için doğrusal davranır. Polinom depolama maliyeti \(O(D)\)'dir; buna dış katmanın sığ özyineleme derinliği eklenir.
El problema 910 pide el valor, módulo \(10^9\), de una L-expresión profundamente anidada. Toda la cuenta vive en el anillo cociente
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
En lugar de expandir expresiones simbólicas gigantes, la solución guarda cada objeto intermedio como una sola clase polinómica en \(A\). Para la quíntupla oficial \((12,345678,9012345,678,90)\), se construye la capa polinómica final, se evalúa en \(x=678\), se suma \(90\) y se reduce todo módulo \(10^9\).
Por tanto, la dificultad real no está en la última sustitución numérica, sino en mantener finitos y controlables la multiplicación repetida, la composición repetida y el anidamiento repetido.
La clave es que toda la recursión de las L-expresiones puede reescribirse como aritmética con polinomios de grado a lo sumo \(39\). Ese límite no es una aproximación: es una invariante exacta impuesta por el anillo \(A\).
El polinomio módulo \(P(x)\) es mónico y tiene grado \(40\). Por eso, cada clase de \(A\) posee un resto único de la forma
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}.$$
Así, cualquier L-expresión, por enorme que sea, se comprime en un vector de coeficientes respecto de la base fija
$$1,x,x^2,\dots,x^{39}.$$
Esto sigue siendo válido aunque el anillo de coeficientes \(\mathbb{Z}/10^9\mathbb{Z}\) no sea un cuerpo. El método nunca usa divisiones ni inversos; solo operaciones de anillo que siguen siendo legítimas módulo un número compuesto.
La estructura recursiva utilizada por las implementaciones es
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
Aquí \(xU\) es el producto ordinario en \(A\), mientras que \(U^{\circ m}\) significa \(m\) autocomposiciones sucesivas. El valor final buscado es
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M.$$
Todo el reto matemático consiste en evaluar estas tres capas sin abandonar nunca la representación de grado menor que \(40\).
Escribamos
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
Como \(P(x)\equiv 0\) dentro del anillo cociente, se obtiene la regla fundamental
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}.$$
Si
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39},$$
entonces multiplicar por \(x\) se convierte en
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
Esta identidad es el motor de toda la reducción. Gracias a ella, cada término desbordado se pliega de inmediato hacia grados menores, y nunca hace falta almacenar explícitamente un polinomio de grado \(40\) o mayor.
La fórmula anterior da la multiplicación por \(x\). La multiplicación general en el anillo sigue por linealidad:
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
Así, un producto completo puede construirse mediante pasos repetidos de desplazamiento y reducción. Las potencias ordinarias, como \(x^\ell\), se obtienen entonces por exponenciación binaria dentro de \(A\).
La composición se maneja con la misma base:
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
y cada potencia \(q(x)^i\) vuelve a reducirse en \(A\). La misma idea de repeated squaring sirve para la autocomposición iterada, porque las iteradas del mismo polinomio cumplen
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}.$$
Esa es exactamente la razón por la que el parámetro enorme \(m=345678\) sigue siendo computable.
Un ejemplo pequeño de la validación interna es \((n,m,\ell,t,s)=(0,1,1,1,0)\). Primero,
$$D_1(1)=x+x^2.$$
Como \(m=1\), la capa intermedia se reduce a una sola composición:
$$D_2(1,U)=U\circ(xU).$$
Sustituyendo \(U=D_1(1)\), se obtiene
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
donde cada multiplicación se reduce tanto módulo \(P(x)\) como módulo \(10^9\). Si llamamos \(V\) a ese polinomio intermedio, entonces
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2.$$
La evaluación en \(t=1\) da
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42.$$
Aunque es un caso pequeño, muestra el mecanismo completo: la reducción en el anillo cociente impide que el anidamiento simbólico se dispare.
Las implementaciones en C++, Python y Java representan cada polinomio con exactamente \(40\) coeficientes. Antes de iniciar la recursión principal, expanden \(P(x)\), conservan sus coeficientes de grado menor, los niegan módulo \(10^9\) y reutilizan esa información cada vez que aparece un término \(x^{40}\). Por eso, multiplicar por \(x\) se reduce a un desplazamiento de coeficientes y un único repliegue del desbordamiento.
Con ese bloque básico, la implementación arma la multiplicación completa a partir de copias desplazadas, calcula potencias ordinarias mediante exponenciación binaria y realiza la composición acumulando \(1,q,q^2,\dots,q^{39}\) dentro del anillo cociente. La autocomposición iterada usa la misma idea binaria, pero sustituyendo multiplicación por composición.
Primero se construye \(x^\ell\) y, a partir de él, la capa base \(x^\ell+x^{\ell+1}\). Luego se aplica el operador intermedio \(U\mapsto U^{\circ m}(xU)\) para obtener el primer polinomio anidado no trivial. Después, ese mismo operador se reaplica otras \(n\) veces.
Cuando el representante final de grado menor que \(40\) está listo, la implementación lo evalúa en el entero \(t\) acumulando las potencias \(1,t,t^2,\dots,t^{39}\) módulo \(10^9\). El último paso es sumar \(s\) y volver a reducir.
Sea \(D=40\). Una multiplicación en el anillo cuesta \(O(D^2)\), porque combina \(D\) copias desplazadas y reducidas de un polinomio. Una composición cuesta \(O(D^3)\), porque construye \(1,q,q^2,\dots,q^{D-1}\) y las combina con los coeficientes del polinomio exterior.
Calcular \(x^\ell\) cuesta \(O(D^2\log \ell)\). Calcular \(U^{\circ m}\) cuesta \(O(D^3\log m)\). Como la capa exterior aplica el mismo operador intermedio \(n+1\) veces, el costo total es
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr).$$
Con \(D=40\) fijo, esto es en la práctica logarítmico en \(\ell\) y \(m\), y lineal en el número de anidamientos exteriores. El almacenamiento polinómico es \(O(D)\), más la profundidad pequeña de la recursión exterior.
第 910 题要求计算一个高度嵌套的 L-expression 在模 \(10^9\) 下的值。整个计算都在下面这个商环中进行：
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
实现并不会把巨大的符号表达式真正展开，而是把每一个中间对象都视为 \(A\) 中的一个多项式类。对官方参数 \((12,345678,9012345,678,90)\)，做法是先构造最外层得到的最终多项式，再在 \(x=678\) 处取值，随后加上 \(90\)，最后对 \(10^9\) 取模。
因此，真正困难的地方不是最后一次代值，而是如何把反复出现的乘法、复合和外层嵌套始终压缩在一个有限、稳定的表示之中。
实现之所以可行，是因为整套 L-expression 递归都可以改写成“次数不超过 \(39\) 的多项式运算”。这个次数上界不是经验性的，而是由商环 \(A\) 强制给出的严格不变量。
模多项式 \(P(x)\) 是一个次数为 \(40\) 的首一多项式，所以 \(A\) 中每一个等价类都有唯一的低次代表元
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}.$$
这意味着无论某个 L-expression 在符号层面膨胀到多么夸张，程序真正保存的都只是相对于固定基底
$$1,x,x^2,\dots,x^{39}$$
的一个长度为 \(40\) 的系数向量。即使系数环 \(\mathbb{Z}/10^9\mathbb{Z}\) 不是域，这一点仍然成立，因为整个方法从头到尾都不依赖除法或逆元，只使用模合数下同样成立的环运算。
实现所遵循的递归结构是
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
这里的 \(xU\) 是 \(A\) 中的普通乘法，\(U^{\circ m}\) 表示把 \(U\) 与自己复合 \(m\) 次。题目最终要求的量可以写成
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M.$$
所以数学任务就是在始终保持“次数小于 \(40\)”的前提下，把这三层结构完整算出来。
把模多项式写成
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
由于在商环中 \(P(x)\equiv 0\)，我们立刻得到核心约化公式
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}.$$
若
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39},$$
那么乘以 \(x\) 就变成
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
这条公式就是整个算法的发动机。只要出现溢出的 \(x^{40}\) 项，就立刻按这条关系折回到低次部分，因此程序根本不需要显式存储任何次数达到 \(40\) 或以上的多项式。
前一节给出了“乘以 \(x\)”的方法。一般乘法则来自线性性：
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
因此，一个完整的环内乘法可以拆成反复的移位加约化。像 \(x^\ell\) 这样的普通幂，自然就能在 \(A\) 中用二分快速幂完成。
复合也完全在同一基底中进行：
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
其中出现的每一个 \(q(x)^i\) 仍然都在 \(A\) 中约化。对自复合 \(U^{\circ m}\) 也可以使用同样的 repeated squaring 思想，因为同一个多项式的迭代满足
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}.$$
这正是为什么像 \(m=345678\) 这样的巨大参数仍然能够高效处理。
内置验证中的一个小例子是 \((n,m,\ell,t,s)=(0,1,1,1,0)\)。先有
$$D_1(1)=x+x^2.$$
由于 \(m=1\)，中间层只是一轮复合：
$$D_2(1,U)=U\circ(xU).$$
把 \(U=D_1(1)\) 代入，可得
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
这里每一步乘法都要同时对 \(P(x)\) 和 \(10^9\) 做约化。把这个中间多项式记为 \(V\)，则
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2.$$
再在 \(t=1\) 处取值，就得到
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42.$$
虽然这个例子很小，但它已经完整展示了核心机制：商环约化让原本会爆炸增长的符号嵌套始终保持在固定的 40 维表示中。
C++、Python 和 Java 实现都把每个多项式存成长度恰好为 \(40\) 的系数数组。主递归开始前，程序先展开 \(P(x)\)，保留它的低次系数，把这些系数在模 \(10^9\) 下取负；以后每当出现 \(x^{40}\) 的溢出项时，就直接复用这组数据完成回折。因此，“乘以 \(x\)”并不是昂贵的长除法，而只是一次数组移位加一次固定形式的溢出回填。
在这个基础上，完整乘法通过若干移位副本相加来实现，普通幂通过二分快速幂实现，而多项式复合则通过累积 \(1,q,q^2,\dots,q^{39}\) 来实现。自复合 \(U^{\circ m}\) 使用同样的二进制拆分思想，只不过把“乘法”换成了“复合”。
实现首先构造 \(x^\ell\)，再得到基础层 \(x^\ell+x^{\ell+1}\)。随后应用中间算子 \(U\mapsto U^{\circ m}(xU)\)，得到第一个真正嵌套出来的多项式。然后在此基础上再重复应用同一个算子 \(n\) 次，形成最外层结果。
当最终的次数小于 \(40\) 的代表元准备好之后，程序通过依次累乘 \(1,t,t^2,\dots,t^{39}\) 来计算它在整数点 \(t\) 处的值，全程都取模 \(10^9\)。最后再加上 \(s\)，再做一次模约化，就得到答案。
记 \(D=40\)。一次环内乘法的代价是 \(O(D^2)\)，因为它要组合 \(D\) 个移位并约化后的多项式副本。一次复合的代价是 \(O(D^3)\)，因为它需要构造 \(1,q,q^2,\dots,q^{D-1}\)，再与外层多项式的系数线性组合。
计算 \(x^\ell\) 需要 \(O(D^2\log \ell)\)，计算 \(U^{\circ m}\) 需要 \(O(D^3\log m)\)。由于最外层总共会把同一个中间算子应用 \(n+1\) 次，因此总时间复杂度为
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr).$$
在本题里 \(D=40\) 是固定常数，所以实际表现可以看作对 \(\ell\) 和 \(m\) 呈对数增长、对外层嵌套次数呈线性增长。多项式数据本身占用 \(O(D)\) 空间，外加最外层递归带来的很浅的调用栈。
В задаче 910 требуется вычислить значение глубоко вложенного L-выражения по модулю \(10^9\). Вся арифметика выполняется в факторкольце
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
Вместо прямого раскрытия огромных символьных выражений решение хранит каждый промежуточный объект как один класс многочленов в \(A\). Для официальной пятёрки параметров \((12,345678,9012345,678,90)\) сначала строится финальный многочлен внешнего слоя, затем он вычисляется в точке \(x=678\), после чего прибавляется \(90\), и результат снова берётся по модулю \(10^9\).
Значит, основная сложность вовсе не в последней подстановке, а в том, чтобы повторные умножения, композиции и вложения всегда оставались в конечном и управляемом представлении.
Решение работает потому, что всю рекурсию L-выражений можно переписать как арифметику с многочленами степени не выше \(39\). Это ограничение не является приближением; оно является точным инвариантом, навязанным кольцом \(A\).
Модульный многочлен \(P(x)\) приведён и имеет степень \(40\). Поэтому каждый класс в \(A\) имеет единственный остаток вида
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}.$$
То есть любой, сколь угодно большой, L-объект сжимается до вектора коэффициентов в фиксированном базисе
$$1,x,x^2,\dots,x^{39}.$$
Это остаётся верным и при том, что кольцо коэффициентов \(\mathbb{Z}/10^9\mathbb{Z}\) не является полем. Метод не требует деления и не использует обратимые элементы; в нём нужны только кольцевые операции, корректные и по составному модулю.
Рекурсивная структура, используемая реализациями, имеет вид
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
Здесь \(xU\) означает обычное умножение в \(A\), а \(U^{\circ m}\) обозначает \(m\)-кратную композицию \(U\) с самим собой. Окончательный ответ выражается как
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M.$$
По существу надо вычислить все три слоя, ни разу не покидая представление степени меньше \(40\).
Запишем
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
Так как в факторкольце \(P(x)\equiv 0\), получаем основное правило редукции
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}.$$
Если
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39},$$
то умножение на \(x\) превращается в
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
Именно это равенство лежит в центре алгоритма. Каждый переполняющий член немедленно сворачивается обратно в степени меньше \(40\), поэтому многочлены высокой степени никогда не нужно хранить явно.
Предыдущее равенство даёт умножение на \(x\). Общая кольцевая мультипликация следует из линейности:
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
Значит, полное произведение можно собрать из повторяющихся сдвигов и редукций. Обычные степени, такие как \(x^\ell\), после этого вычисляются бинарным возведением в степень прямо внутри \(A\).
Композиция обрабатывается в том же базисе:
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
и каждая степень \(q(x)^i\) также немедленно редуцируется в \(A\). Та же идея repeated squaring подходит и для итеративной композиции, потому что для итератов одного и того же многочлена выполняется
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}.$$
Именно это делает вычислимым большой параметр \(m=345678\).
Небольшой пример из встроенной проверки: \((n,m,\ell,t,s)=(0,1,1,1,0)\). Сначала
$$D_1(1)=x+x^2.$$
Поскольку \(m=1\), средний слой сводится к одной композиции:
$$D_2(1,U)=U\circ(xU).$$
Подставляя \(U=D_1(1)\), получаем
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
причём каждое умножение здесь редуцируется и по \(P(x)\), и по модулю \(10^9\). Если обозначить этот промежуточный многочлен через \(V\), то
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2.$$
Подстановка \(t=1\) даёт
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42.$$
Хотя пример маленький, он полностью демонстрирует механизм решения: редукция в факторкольце не даёт символьной вложенности выйти из-под контроля.
Реализации на C++, Python и Java представляют каждый многочлен ровно \(40\) коэффициентами. До запуска основной рекурсии они раскрывают \(P(x)\), сохраняют его коэффициенты низших степеней, берут их отрицание по модулю \(10^9\) и повторно используют их каждый раз, когда возникает член \(x^{40}\). Поэтому умножение на \(x\) сводится всего лишь к сдвигу коэффициентов и одному свёртыванию переполнения.
Из этого примитива строятся остальные операции: полное умножение через сдвинутые копии, обычные степени через бинарное возведение в степень и композиция через накопление \(1,q,q^2,\dots,q^{39}\) внутри факторкольца. Итеративная самокомпозиция использует ту же бинарную схему, только вместо умножения берётся композиция.
Сначала реализация получает \(x^\ell\), а затем формирует базовый слой \(x^\ell+x^{\ell+1}\). После этого применяется средний оператор \(U\mapsto U^{\circ m}(xU)\), и получается первый нетривиальный вложенный многочлен. Затем этот же оператор применяется к результату ещё \(n\) раз.
Когда окончательный представитель степени меньше \(40\) готов, код вычисляет его в целой точке \(t\), последовательно накапливая степени \(1,t,t^2,\dots,t^{39}\) по модулю \(10^9\). В конце прибавляется \(s\), и выполняется последняя редукция.
Пусть \(D=40\). Одно умножение в кольце стоит \(O(D^2)\), потому что комбинируются \(D\) сдвинутых и редуцированных копий многочлена. Одна композиция стоит \(O(D^3)\), так как строятся степени \(1,q,q^2,\dots,q^{D-1}\) и затем взвешиваются коэффициентами внешнего многочлена.
Вычисление \(x^\ell\) требует \(O(D^2\log \ell)\), а вычисление \(U^{\circ m}\) требует \(O(D^3\log m)\). Поскольку внешний слой применяет тот же средний оператор \(n+1\) раз, полное время работы равно
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr).$$
При фиксированном \(D=40\) это фактически означает логарифмическую зависимость от \(\ell\) и \(m\) и линейную зависимость от числа внешних вложений. Память для полиномиальных данных равна \(O(D)\), плюс очень малая глубина рекурсии внешнего слоя.
تطلب المسألة 910 حساب قيمة L-expression متداخلة جدًا بترديد \(10^9\). وتُجرى الحسابات كلها داخل حلقة القسمة
$$M=10^9,\qquad P(x)=\prod_{k=1}^{40}(x+k),\qquad A=(\mathbb{Z}/M\mathbb{Z})[x]/(P(x)).$$
بدلًا من توسيع التعابير الرمزية الهائلة مباشرة، يحتفظ الحل بكل كائن وسيط على أنه فئة كثيرة حدود واحدة داخل \(A\). وللقيم الرسمية \((12,345678,9012345,678,90)\)، تُبنى الطبقة النهائية من كثيرات الحدود، ثم تُقيَّم عند \(x=678\)، ثم يُضاف \(90\)، ثم تُؤخذ النتيجة بترديد \(10^9\).
إذًا فالصعوبة الحقيقية ليست في التعويض العددي الأخير، بل في إبقاء الضرب المتكرر، والتركيب المتكرر، والتداخل الخارجي المتكرر داخل تمثيل محدود يمكن التحكم فيه.
ينجح الحل لأن كامل العودية الخاصة بـ L-expression يمكن إعادة صياغتها على أنها حسابات على كثيرات حدود درجتها لا تتجاوز \(39\). وهذا القيد ليس تقريبًا، بل ثابت دقيق تفرضه الحلقة \(A\).
بما أن كثير الحدود \(P(x)\) أحادي المعامل الرئيس ودرجته \(40\)، فإن كل فئة في \(A\) لها باق وحيد من الصورة
$$r(x)=r_0+r_1x+\cdots+r_{39}x^{39}.$$
وهكذا تنضغط أي L-expression مهما كانت ضخمة إلى متجه معاملات بالنسبة إلى الأساس الثابت
$$1,x,x^2,\dots,x^{39}.$$
ويبقى هذا صحيحًا رغم أن حلقة المعاملات \(\mathbb{Z}/10^9\mathbb{Z}\) ليست حقلًا. فالطريقة لا تعتمد على القسمة أو على المعكوسات، بل تستخدم فقط عمليات حلقية تبقى صحيحة حتى مع مودولو مركب.
البنية العودية التي تستخدمها التطبيقات هي
$$D_1(\ell)=x^\ell+x^{\ell+1},$$
$$D_2(m,U)=U^{\circ m}\circ(xU),$$
$$D_3(0,m,\ell)=D_1(\ell)\circ D_2(m,D_1(\ell)),$$
$$D_3(n,m,\ell)=D_2(m,D_3(n-1,m,\ell)).$$
هنا يعبّر \(xU\) عن الضرب العادي داخل \(A\)، بينما يعبّر \(U^{\circ m}\) عن تركيب \(U\) مع نفسه \(m\) مرة. وبعد ذلك تصبح القيمة المطلوبة
$$\operatorname{Ans}(n,m,\ell,t,s)=\bigl(D_3(n,m,\ell)(t)+s\bigr)\bmod M.$$
إذن فالمهمة الرياضية هي تقييم هذه الطبقات الثلاث كلها من دون مغادرة تمثيل الدرجة الأصغر من \(40\).
لنكتب
$$P(x)=x^{40}+p_{39}x^{39}+\cdots+p_1x+p_0.$$
وبما أن \(P(x)\equiv 0\) داخل حلقة القسمة، نحصل على قاعدة الاختزال الأساسية
$$x^{40}\equiv-\bigl(p_{39}x^{39}+\cdots+p_1x+p_0\bigr)\pmod{P(x)}.$$
إذا كان
$$q(x)=q_0+q_1x+\cdots+q_{39}x^{39},$$
فإن الضرب في \(x\) يتحول إلى
$$xq(x)\equiv \sum_{i=0}^{38} q_i x^{i+1}-q_{39}\bigl(p_0+p_1x+\cdots+p_{39}x^{39}\bigr).$$
هذه العلاقة هي قلب الخوارزمية. فكل حد فائض من نوع \(x^{40}\) يُطوى فورًا إلى حدود أقل درجة، ولذلك لا نحتاج أبدًا إلى تخزين كثير حدود من الدرجة \(40\) أو أعلى بشكل صريح.
تعطينا الصيغة السابقة الضرب في \(x\). أما الضرب العام في الحلقة فيأتي من الخطية:
$$\left(\sum_{i=0}^{39} a_i x^i\right)q(x)=\sum_{i=0}^{39} a_i\bigl(x^i q(x)\bigr).$$
ولهذا يمكن بناء حاصل الضرب الكامل من خطوات متكررة من الإزاحة والاختزال. وبعد ذلك تُحسب الأسس العادية مثل \(x^\ell\) بواسطة الرفع الثنائي للأس داخل الحلقة \(A\).
أما التركيب فيُعالج داخل الأساس نفسه:
$$p\circ q=p(q(x))=\sum_{i=0}^{39} a_i q(x)^i,$$
حيث تُختزل كل قوة \(q(x)^i\) من جديد داخل \(A\). والفكرة نفسها الخاصة بـ repeated squaring تعمل أيضًا مع التركيب التكراري، لأن مكررات كثير الحدود نفسه تحقق
$$U^{\circ a}\circ U^{\circ b}=U^{\circ(a+b)}.$$
وهذا بالضبط ما يجعل القيمة الكبيرة \(m=345678\) قابلة للحساب عمليًا.
أحد أمثلة التحقق الصغيرة هو \((n,m,\ell,t,s)=(0,1,1,1,0)\). أولًا
$$D_1(1)=x+x^2.$$
وبما أن \(m=1\)، فإن الطبقة الوسطى تصبح تركيبًا واحدًا فقط:
$$D_2(1,U)=U\circ(xU).$$
بالتعويض عن \(U=D_1(1)\) نحصل على
$$xU=x(x+x^2)=x^2+x^3,$$
$$D_2(1,D_1(1))=(x+x^2)\circ(x^2+x^3)=(x^2+x^3)+(x^2+x^3)^2,$$
مع اختزال كل عملية ضرب بالنسبة إلى \(P(x)\) وإلى \(10^9\). وإذا سمينا هذا كثير الحدود الوسيط \(V\)، فإن
$$D_3(0,1,1)=D_1(1)\circ V=V+V^2.$$
وعند التقييم في \(t=1\) نحصل على
$$\bigl(D_3(0,1,1)(1)+0\bigr)\bmod 10^9=42.$$
ورغم أن المثال صغير، فإنه يكشف الآلية كاملة: الاختزال داخل حلقة القسمة يمنع التوسع الرمزي من الانفجار.
تمثل تطبيقات C++ وPython وJava كل كثير حدود بواسطة \(40\) معاملًا فقط. قبل بدء العودية الرئيسية، توسّع \(P(x)\)، وتحتفظ بمعاملاته ذات الدرجات المنخفضة، ثم تأخذ سالبها بترديد \(10^9\)، وتعيد استخدام هذه البيانات كلما ظهر الحد \(x^{40}\). لذلك فإن الضرب في \(x\) لا يحتاج إلى قسمة كثيرة حدود كاملة، بل يقتصر على إزاحة معاملات مع خطوة واحدة لطي الفائض.
انطلاقًا من هذا البناء الأساسي، يُنشأ الضرب الكامل من نسخ مزاحة، وتُحسب الأسس العادية بالرفع الثنائي، بينما يُنفَّذ التركيب عبر تجميع \(1,q,q^2,\dots,q^{39}\) داخل حلقة القسمة. أما التركيب الذاتي المتكرر فيستعمل الفكرة الثنائية نفسها، لكن مع استبدال الضرب بالتركيب.
يبدأ التنفيذ ببناء \(x^\ell\)، ثم تشكيل الطبقة الأساسية \(x^\ell+x^{\ell+1}\). بعد ذلك يُطبَّق المؤثر الأوسط \(U\mapsto U^{\circ m}(xU)\) للحصول على أول كثير حدود متداخل غير بسيط. ثم يُعاد تطبيق المؤثر نفسه \(n\) مرات إضافية لبناء الطبقة الخارجية.
وعندما يصبح الممثل النهائي من الدرجة الأقل من \(40\) جاهزًا، يقيّمه التنفيذ عند العدد الصحيح \(t\) عبر تكوين القوى \(1,t,t^2,\dots,t^{39}\) تباعًا بترديد \(10^9\). وفي النهاية يُضاف \(s\) ثم تُؤخذ البقية مرة أخيرة.
لنرمز إلى \(D=40\). تكلفة عملية ضرب واحدة داخل الحلقة هي \(O(D^2)\)، لأنها تجمع \(D\) نسخًا مزاحة ومختزلة من كثير حدود. أما عملية تركيب واحدة فتكلف \(O(D^3)\)، لأنها تبني القوى \(1,q,q^2,\dots,q^{D-1}\) ثم تجمعها مع معاملات كثير الحدود الخارجي.
حساب \(x^\ell\) يحتاج إلى \(O(D^2\log \ell)\)، بينما حساب \(U^{\circ m}\) يحتاج إلى \(O(D^3\log m)\). وبما أن الطبقة الخارجية تطبق المؤثر الأوسط نفسه \(n+1\) مرة، فإن الزمن الكلي يساوي
$$O\bigl(D^2\log \ell+(n+1)D^3\log m\bigr).$$
ومع ثبات \(D=40\)، يصبح السلوك العملي لوغاريتميًا في \(\ell\) و\(m\)، وخطيًا في عدد التداخلات الخارجية. أما تخزين كثيرات الحدود فيكلف \(O(D)\)، مع عمق عودية صغير جدًا للطبقة الخارجية.