Place \(F_0,F_1,\ldots,F_n\) in order with a minus sign between adjacent terms. A valid expression is a full parenthesization: every one of the \(n\) pairs of parentheses encloses exactly one top-level minus sign, although either side may contain further parenthesized subexpressions. The task is to add the values of all syntactically different expressions.
There are \(C_n\) such expressions, where \(C_n\) is the \(n\)-th Catalan number. Direct construction is therefore impossible at \(n=10^7\). We need
$$A(10^7)\pmod{p},\qquad p=10^9+9,$$
with the published checks \(A(3)=-6\), \(A(10)=-177666\), and \(A(100)\equiv71792794\pmod p\).
A parenthesized subtraction expression with \(m=n+1\) operands is an ordered full binary tree with \(m\) leaves. Its root chooses a unique split after \(k\) leaves: the left subtree uses the first \(k\) operands and the right subtree uses the remaining \(m-k\). A block of \(j+1\) leaves has
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
possible trees. The root split is the key because the value of the whole tree is “left value minus right value,” and every valid tree occurs at exactly one split.
Temporarily replace the Fibonacci operands by \(1,t,t^2,\ldots,t^{m-1}\). Let \(P_m(t)\) be the sum of the values of all parenthesizations of these \(m\) formal operands. In particular, \(P_1(t)=1\).
For a split after \(k\) leaves, the left sum \(P_k(t)\) is repeated once for every right tree, while the right sum is repeated once for every left tree and is shifted by \(t^k\). Therefore
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
This recurrence does not merely count trees. It preserves the complete signed contribution of every leaf position. For example,
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$
For four leaves, adding the five tree polynomials gives
$$P_4(t)=5-5t+t^2-t^3.$$
In the Fibonacci ring, \(r^2=1+r\) and \(r^3=1+2r\). Hence the root coefficient is
$$[r]P_4(r)=-5+1-2=-6,$$
which is the sum \(-4-2+0+2-2=-6\) from the five displayed expressions in the problem. This example simultaneously checks the Catalan multiplicities, the right-subtree sign, the exponent shift, and the Fibonacci extraction rule.
Introduce
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$
Thus \(T(z)\) is simply the ordinary Catalan generating function (also often denoted \(C(z)\)), while \(P(z,t)\), equivalently \(P(z,x)\) when the marker is named \(x\), is the bivariate sign-polynomial series.
Summing the root-split recurrence over \(m\) turns the two convolutions into products:
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
Writing \(q(z)=\sqrt{1-4z}\) and \(s(z)=\sqrt{1-4tz}\), we obtain the compact algebraic function
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$
Thus the exponentially large family of trees has been compressed into coefficient extraction from one algebraic power series.
Work modulo \(p\) in the quotient ring
$$R=\mathbb{F}_p[r]/(r^2-r-1).$$
Every element has the form \(a+br\). The defining relation gives, for \(i\ge1\),
$$r^i=F_{i-1}+F_ir,$$
and \(r^0=1\) has \(r\)-coefficient \(0=F_0\). Consequently the coefficient of \(r\) in \(P_m(r)\) is exactly the sum obtained when leaf \(i\) receives \(F_i\):
$$A(n)=[r]\,P_{n+1}(r).$$
No square root of \(5\) and no extension-field inversion is needed. Addition, subtraction, and multiplication by \(r\), \(r+1\), \(r-1\), or \(2-r\) reduce to operations on the pair \((a,b)\):
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
Now set \(t=r\), \(q(z)=\sqrt{1-4z}\), and \(s(z)=\sqrt{1-4rz}\). Define
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
Using \(q(z)^2=1-4z\), \(s(z)^2=1-4rz\), and \(r^2=r+1\), rationalizing the denominator of \(P\) yields
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$
This identity is chosen because its denominator is only linear in \(z\). It lets the implementation advance one coefficient at a time instead of storing a power-series table.
Let the factorial-scaled coefficients be
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$
With \(a_0=b_0=c_0=1\), \(c_{-1}=0\), and \(u_0=0\), coefficient comparison gives
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$
The scaled coefficient of \(N(z)\) is
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$
and the rationalized identity becomes the one-step update
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
The loop runs through \(m=n+1\). Finally it undoes the factorial scaling and extracts the root component:
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
Because \(p\) is prime and \(n+1=10000001\lt p\), both \(4\) and \((n+1)!\) are nonzero modulo \(p\). Their inverses are computed with Fermat's little theorem, \(x^{-1}\equiv x^{p-2}\pmod p\).
The optimized recurrence is compact but algebraically dense. For \(0\le n\le10\), the implementations independently enumerate every root split, construct every parenthesized value, and compare its direct sum with the ring recurrence. They also check the three published values. This catches sign errors at a right subtree, incorrect index shifts, and mistakes in either ring component before the large instance is evaluated.
Lemma 1. The recurrence for \(P_m(t)\) sums every valid parenthesization exactly once. Every full binary tree has one root split \(k\); the Catalan factors count the choices for the opposite subtree, and the right block acquires exactly the shift \(t^k\) and the root minus sign.
Lemma 2. The generating function \(P(z,t)\) has coefficient \(P_m(t)\). Multiplying by \(zC(z)\) and \(tzC(tz)\) reproduces the two split convolutions of Lemma 1, so solving the resulting linear equation gives \(2z/(2+q-s)\).
Lemma 3. In \(R\), the \(r\)-coefficient of \(r^i\) is \(F_i\). Linearity therefore changes the formal leaf weights \(t^i\) in \(P_m(t)\) into the required Fibonacci weights when \(t=r\).
Lemma 4. The updates for \(a_m,b_m,c_m,d_m,u_m\) are coefficient identities of the square-root series and the rationalized equation. Factorial scaling is reversible because the relevant factorial is invertible modulo \(p\).
By Lemmas 1 and 2, \(P_{n+1}\) represents the sum over all valid expressions; by Lemma 3 its root component is \(A(n)\); and by Lemma 4 the loop computes precisely that component. Hence the printed residue is \(A(10^7)\bmod(10^9+9)\).
alternating_sum keeps only the current \(a_m\), \(b_m\), the last two \(c_m\) values, the previous \(u_m\), and the running factorial. A ring element is stored as its constant and root components. The four short multiplication identities above are expanded directly in Python and Java to avoid allocating millions of temporary objects; they are the same operations performed by the C++ RingElement helpers.
mod_pow performs binary exponentiation for the two modular inverses. brute_values is deliberately separate from the optimized derivation: it recursively realizes all root splits for small inputs. run_checkpoints compares both methods for \(n=0,\ldots,10\), then verifies the published residues.
The main recurrence performs a constant number of modular ring operations for each \(m=1,\ldots,n+1\), so it takes \(O(n+\log p)\) time. The exponentiation term is negligible beside \(n=10^7\). Only a fixed number of scalar residues is retained, giving \(O(1)\) auxiliary memory.
Direct enumeration would require \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) expressions and is exponentially impossible. Even storing all coefficients through degree \(n\) would use \(O(n)\) memory; the linear-denominator recurrence avoids that storage.
Die Zahlen \(F_0,F_1,\ldots,F_n\) werden in dieser Reihenfolge notiert und benachbarte Terme durch Minuszeichen getrennt. Ein gültiger Ausdruck ist eine vollständige Klammerung: Jedes der \(n\) Klammerpaare enthält genau ein Minuszeichen auf seiner obersten Ebene; in den beiden Teilausdrücken dürfen weitere Klammern liegen. Gesucht ist die Summe der Werte aller syntaktisch verschiedenen Ausdrücke.
Ihre Anzahl ist die Catalan-Zahl \(C_n\). Für \(n=10^7\) kann man die Ausdrücke daher keinesfalls erzeugen. Berechnet werden muss
$$A(10^7)\pmod{p},\qquad p=10^9+9,$$
wobei \(A(3)=-6\), \(A(10)=-177666\) und \(A(100)\equiv71792794\pmod p\) als veröffentlichte Kontrollwerte dienen.
Ein vollständig geklammerter Subtraktionsausdruck mit \(m=n+1\) Operanden entspricht einem geordneten vollen Binärbaum mit \(m\) Blättern. Seine Wurzel bestimmt eindeutig eine Trennstelle nach \(k\) Blättern: Links stehen die ersten \(k\) Operanden, rechts die übrigen \(m-k\). Für einen Block aus \(j+1\) Blättern gibt es
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
mögliche Bäume. Die Wurzelzerlegung ist entscheidend, denn der Gesamtwert ist „linker Wert minus rechter Wert“, und jeder gültige Baum gehört zu genau einer solchen Trennstelle.
Ersetze die Fibonacci-Operanden vorübergehend durch \(1,t,t^2,\ldots,t^{m-1}\). Sei \(P_m(t)\) die Summe der Werte aller Klammerungen dieser \(m\) formalen Operanden; insbesondere ist \(P_1(t)=1\).
Bei einer Trennung nach \(k\) Blättern wird die linke Summe \(P_k(t)\) für jeden rechten Baum wiederholt. Die rechte Summe wird für jeden linken Baum wiederholt, wegen der verschobenen Blattindizes mit \(t^k\) multipliziert und an der Wurzel subtrahiert. Somit gilt
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
Diese Rekursion zählt nicht nur die Bäume, sondern bewahrt den vollständigen vorzeichenbehafteten Beitrag jeder Blattposition. Die ersten Fälle sind
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$
Für vier Blätter ergibt die Summe der fünf Baumpolynome
$$P_4(t)=5-5t+t^2-t^3.$$
Im Fibonacci-Ring gelten \(r^2=1+r\) und \(r^3=1+2r\). Der Wurzelkoeffizient ist daher
$$[r]P_4(r)=-5+1-2=-6.$$
Das stimmt mit \(-4-2+0+2-2=-6\), der Summe der fünf Ausdrücke aus der Aufgabenstellung, überein. Das Beispiel kontrolliert zugleich Catalan-Vielfachheiten, das Vorzeichen des rechten Teilbaums, die Exponentenverschiebung und die Fibonacci-Extraktion.
Wir führen
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m$$
ein. \(T(z)\) ist die gewöhnliche Catalan-Erzeugende (oft auch \(C(z)\) genannt); \(P(z,t)\), bei Benennung des Markers mit \(x\) also \(P(z,x)\), ist die zweivariable Vorzeichenpolynom-Reihe. Summiert man die Wurzelrekursion über \(m\), werden die beiden Faltungen zu Produkten:
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
Mit \(q(z)=\sqrt{1-4z}\) und \(s(z)=\sqrt{1-4tz}\) folgt die kompakte algebraische Funktion
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$
Die exponentiell große Baumfamilie ist damit auf die Koeffizientenextraktion aus einer einzigen algebraischen Potenzreihe reduziert.
Wir rechnen modulo \(p\) im Quotientenring
$$R=\mathbb{F}_p[r]/(r^2-r-1).$$
Jedes Element besitzt die Form \(a+br\). Aus der definierenden Relation folgt für \(i\ge1\)
$$r^i=F_{i-1}+F_ir,$$
während der \(r\)-Koeffizient von \(r^0=1\) gleich \(0=F_0\) ist. Der \(r\)-Koeffizient von \(P_m(r)\) ist deshalb genau die verlangte Summe, wenn das Blatt \(i\) das Gewicht \(F_i\) trägt:
$$A(n)=[r]\,P_{n+1}(r).$$
Man benötigt weder eine Quadratwurzel aus \(5\) noch eine Division in einem Erweiterungskörper. Die im Code vorkommenden Ringmultiplikationen werden direkt auf dem Paar \((a,b)\) ausgeführt:
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
Nun setzen wir \(t=r\), \(q(z)=\sqrt{1-4z}\) und \(s(z)=\sqrt{1-4rz}\). Definiere
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
Mit \(q(z)^2=1-4z\), \(s(z)^2=1-4rz\) und \(r^2=r+1\) ergibt das Rationalisieren des Nenners von \(P\)
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$
Der neue Nenner ist nur linear in \(z\). Daher kann die Implementierung jeweils den nächsten Koeffizienten berechnen und muss keine Tabelle aller bisherigen Koeffizienten speichern.
Verwende die skalierten Koeffizienten
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$
Aus \(a_0=b_0=c_0=1\), \(c_{-1}=0\) und \(u_0=0\) erhält man durch Koeffizientenvergleich
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$
Der skalierte Koeffizient von \(N(z)\) lautet
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$
und die rationalisierte Identität wird zur Einschritt-Rekursion
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
Die Schleife endet bei \(m=n+1\). Danach wird die Fakultätsskalierung rückgängig gemacht und die Wurzelkomponente entnommen:
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
Da \(p\) prim ist und \(n+1=10000001\lt p\) gilt, sind \(4\) und \((n+1)!\) modulo \(p\) von null verschieden. Ihre Inversen folgen aus dem kleinen Satz von Fermat: \(x^{-1}\equiv x^{p-2}\pmod p\).
Die optimierte Rekursion ist kurz, aber algebraisch dicht. Für \(0\le n\le10\) erzeugen die Programme unabhängig davon alle Wurzelzerlegungen und damit alle geklammerten Werte. Die direkte Summe wird mit der Ringrekursion verglichen; zusätzlich werden die drei veröffentlichten Werte geprüft. So werden ein falsches Vorzeichen im rechten Teilbaum, ein fehlerhafter Indexversatz oder eine Verwechslung der beiden Ringkomponenten vor der großen Rechnung erkannt.
Lemma 1. Die Rekursion für \(P_m(t)\) erfasst jede gültige Klammerung genau einmal. Jeder volle Binärbaum besitzt eine eindeutige Wurzeltrennung \(k\); die Catalan-Faktoren zählen die Möglichkeiten des jeweils anderen Teilbaums, und der rechte Block erhält genau den Faktor \(t^k\) und das Minuszeichen der Wurzel.
Lemma 2. Der Koeffizient von \(z^m\) in \(P(z,t)\) ist \(P_m(t)\). Die Produkte mit \(zC(z)\) beziehungsweise \(tzC(tz)\) reproduzieren die beiden Faltungen aus Lemma 1; das Auflösen der linearen Gleichung liefert \(2z/(2+q-s)\).
Lemma 3. Im Ring \(R\) ist der \(r\)-Koeffizient von \(r^i\) gleich \(F_i\). Wegen der Linearität ersetzt \(t=r\) daher alle formalen Blattgewichte durch die verlangten Fibonacci-Zahlen.
Lemma 4. Die Aktualisierungen für \(a_m,b_m,c_m,d_m,u_m\) sind Koeffizientenidentitäten der Wurzelreihen und der rationalisierten Gleichung. Die Fakultätsskalierung ist umkehrbar, weil die relevante Fakultät modulo \(p\) invertierbar ist.
Nach Lemma 1 und 2 beschreibt \(P_{n+1}\) die Summe aller gültigen Ausdrücke. Lemma 3 identifiziert ihre Wurzelkomponente mit \(A(n)\), und Lemma 4 zeigt, dass die Schleife genau diese Komponente berechnet. Somit ist die ausgegebene Zahl \(A(10^7)\bmod(10^9+9)\).
alternating_sum hält nur das aktuelle \(a_m\), \(b_m\), die letzten beiden \(c_m\)-Werte, das vorherige \(u_m\) und die laufende Fakultät. Ein Ringelement wird durch Konstanten- und Wurzelkomponente dargestellt. Python und Java schreiben die vier Ringidentitäten direkt in skalare Operationen aus, damit in zehn Millionen Schritten keine temporären Objekte erzeugt werden; mathematisch sind dies dieselben Operationen wie die RingElement-Hilfsfunktionen in C++.
mod_pow berechnet die modularen Inversen durch binäres Potenzieren. brute_values ist absichtlich unabhängig von der optimierten Herleitung und erzeugt für kleine Eingaben rekursiv alle Wurzeltrennungen. run_checkpoints vergleicht beide Methoden für \(n=0,\ldots,10\) und prüft anschließend die veröffentlichten Werte.
Für jedes \(m=1,\ldots,n+1\) wird eine konstante Anzahl modularer Ringoperationen ausgeführt. Die Laufzeit beträgt daher \(O(n+\log p)\), wobei das Potenzieren gegenüber \(n=10^7\) kaum ins Gewicht fällt. Es werden nur konstant viele Restklassen gespeichert, also ist der zusätzliche Speicherbedarf \(O(1)\).
Eine direkte Aufzählung benötigte \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) Ausdrücke und wäre exponentiell unmöglich. Auch eine vollständige Koeffiziententabelle würde \(O(n)\) Speicher verbrauchen; die lineare Nennerrekursion vermeidet diese Tabelle.
\(F_0,F_1,\ldots,F_n\) sayıları sırayla yazılır ve komşu terimlerin arasına birer eksi işareti konur. Geçerli bir ifade tam parantezlemedir: \(n\) parantez çiftinin her biri, alt parantezlerin içindekiler sayılmadığında, tam bir üst düzey eksi işareti içerir. Amaç, sözdizimsel olarak farklı bütün bu ifadelerin değerlerini toplamaktır.
İfade sayısı \(n\)'inci Catalan sayısı \(C_n\)'dir; dolayısıyla \(n=10^7\) için doğrudan üretim olanaksızdır. Hesaplanması gereken değer
$$A(10^7)\pmod{p},\qquad p=10^9+9$$
olup yayımlanmış kontrol noktaları \(A(3)=-6\), \(A(10)=-177666\) ve \(A(100)\equiv71792794\pmod p\)'dir.
\(m=n+1\) işlenenli tam parantezlenmiş bir çıkarma ifadesi, \(m\) yapraklı sıralı bir tam ikili ağaca karşılık gelir. Kök, \(k\) yapraktan sonraki bölmeyi tekil olarak belirler: sol alt ağaç ilk \(k\) işleneni, sağ alt ağaç kalan \(m-k\) işleneni alır. \(j+1\) yapraklı bir blok için olası ağaç sayısı
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
olur. Kök bölmesi çözümün temelidir; çünkü bütün ağacın değeri “sol değer eksi sağ değer”dir ve her geçerli ağaç tam bir kök bölmesine aittir.
Fibonacci işlenenlerini geçici olarak \(1,t,t^2,\ldots,t^{m-1}\) ile değiştirelim. Bu \(m\) biçimsel işlenenin bütün parantezlemelerinin değerleri toplamına \(P_m(t)\) diyelim. Başlangıçta \(P_1(t)=1\)'dir.
Kök \(k\) yapraktan sonra bölündüğünde sol toplam \(P_k(t)\), her sağ ağaç için bir kez yinelenir. Sağ toplam ise her sol ağaç için yinelenir; yaprak indisleri \(k\) kadar kaydığı için \(t^k\) ile çarpılır ve kökte çıkarılır. Bu nedenle
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
Bu bağıntı yalnızca ağaçları saymaz; her yaprak konumunun işaretli toplam katkısını eksiksiz korur. İlk değerler
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t$$
şeklindedir.
Dört yaprak için beş ağacın polinomları toplandığında
$$P_4(t)=5-5t+t^2-t^3$$
elde edilir. Fibonacci halkasında \(r^2=1+r\) ve \(r^3=1+2r\) olduğundan kök katsayısı
$$[r]P_4(r)=-5+1-2=-6$$
olur. Bu, soruda gösterilen beş değerin \(-4-2+0+2-2=-6\) toplamıdır. Böylece Catalan çoklukları, sağ alt ağacın eksi işareti, üs kayması ve Fibonacci katsayısı çıkarımı tek bir küçük örnekte sınanır.
Şu serileri tanımlayalım:
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$
\(T(z)\) olağan Catalan üreteç fonksiyonudur ve sıkça \(C(z)\) diye de gösterilir. \(P(z,t)\) ise iki değişkenli işaret polinomu serisidir; işaretleyiciye \(x\) adı verilirse aynı seri \(P(z,x)\) olur. Kök-bölme bağıntısını bütün \(m\) değerleri üzerinden toplamak iki evrişimi çarpıma dönüştürür:
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
\(q(z)=\sqrt{1-4z}\) ve \(s(z)=\sqrt{1-4tz}\) yazıldığında doğrusal denklem çözülerek
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}$$
bulunur. Üstel büyüklükteki ağaç ailesi artık tek bir cebirsel kuvvet serisinden katsayı çıkarma problemine dönüşmüştür.
Hesabı \(p\) modunda şu bölüm halkasında yapalım:
$$R=\mathbb{F}_p[r]/(r^2-r-1).$$
Her eleman \(a+br\) biçimindedir. Tanımlayıcı ilişki \(i\ge1\) için
$$r^i=F_{i-1}+F_ir$$
eşitliğini verir; ayrıca \(r^0=1\)'in \(r\) katsayısı \(0=F_0\)'dır. Dolayısıyla \(P_m(r)\)'nin \(r\) katsayısı, yaprak \(i\)'ye \(F_i\) verildiğinde istenen toplamın aynısıdır:
$$A(n)=[r]\,P_{n+1}(r).$$
\(\sqrt5\)'i seçmeye veya bir genişleme alanında genel çarpım yapmaya gerek yoktur. Kodda gereken sabit çarpanlar \((a,b)\) bileşenleri üzerinde doğrudan hesaplanır:
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
Şimdi \(t=r\), \(q(z)=\sqrt{1-4z}\) ve \(s(z)=\sqrt{1-4rz}\) olsun. Şunu tanımlayalım:
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
\(q(z)^2=1-4z\), \(s(z)^2=1-4rz\) ve \(r^2=r+1\) kullanılarak \(P\)'nin paydası rasyonelleştirildiğinde
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z)$$
özdeşliği elde edilir. Yeni payda \(z\)'de yalnızca birinci derecedir. Bu özellik kodun bütün kuvvet serisini saklamak yerine bir önceki katsayıdan yenisini üretmesini sağlar.
Faktöriyel ile ölçeklenmiş katsayıları
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r)$$
olarak tanımlayalım. \(a_0=b_0=c_0=1\), \(c_{-1}=0\) ve \(u_0=0\) başlangıçlarıyla katsayı karşılaştırması
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2} \end{aligned}$$
bağıntılarını verir. \(N(z)\)'nin ölçeklenmiş katsayısı
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1}$$
olduğundan rasyonelleştirilmiş özdeşlik kodun kullandığı tek adımlı güncellemeye dönüşür:
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
Döngü \(m=n+1\)'e kadar ilerler. Son adımda faktöriyel ölçeği kaldırılır ve \(r\) bileşeni alınır:
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
\(p\) asal ve \(n+1=10000001\lt p\) olduğu için hem \(4\) hem de \((n+1)!\), \(p\) modunda sıfırdan farklıdır. Tersleri Fermat'nın küçük teoremiyle \(x^{-1}\equiv x^{p-2}\pmod p\) biçiminde hesaplanır.
Eniyilenmiş bağıntı kısa fakat cebirsel açıdan yoğundur. Uygulamalar \(0\le n\le10\) için bağımsız olarak her kök bölmesini açar, bütün parantezlenmiş değerleri üretir ve doğrudan toplamı halka bağıntısıyla karşılaştırır. Ardından yayımlanmış üç kontrol noktası da doğrulanır. Böylece sağ alt ağaçtaki işaret, indis kayması veya sabit/kök bileşeniyle ilgili bir hata büyük girdi çalıştırılmadan yakalanır.
Önerme 1. \(P_m(t)\) bağıntısı her geçerli parantezlemeyi tam bir kez toplar. Her tam ikili ağacın tek bir \(k\) kök bölmesi vardır; Catalan çarpanları karşı taraftaki alt ağaç seçeneklerini sayar, sağ blok ise tam olarak \(t^k\) kaymasını ve kökün eksi işaretini alır.
Önerme 2. \(P(z,t)\)'de \(z^m\)'nin katsayısı \(P_m(t)\)'dir. \(zT(z)\) ve \(tzT(tz)\) ile çarpımlar birinci önermedeki iki evrişimi aynen üretir; doğrusal denklemin çözümü \(2z/(2+q-s)\)'dir.
Önerme 3. \(R\) halkasında \(r^i\)'nin \(r\) katsayısı \(F_i\)'dir. Doğrusallık nedeniyle \(t=r\) koymak bütün biçimsel yaprak ağırlıklarını istenen Fibonacci ağırlıklarına çevirir.
Önerme 4. \(a_m,b_m,c_m,d_m,u_m\) güncellemeleri karekök serileriyle rasyonelleştirilmiş denklemin katsayı özdeşlikleridir. İlgili faktöriyel terslenebilir olduğundan ölçekleme kayıpsızdır.
İlk iki önerme \(P_{n+1}\)'in bütün geçerli ifadelerin toplamını temsil ettiğini, üçüncü önerme kök bileşeninin \(A(n)\) olduğunu, dördüncü önerme de döngünün tam bu bileşeni hesapladığını gösterir. Bu yüzden yazdırılan kalan \(A(10^7)\bmod(10^9+9)\)'dur.
alternating_sum yalnızca geçerli \(a_m\), \(b_m\), son iki \(c_m\), önceki \(u_m\) ve ilerleyen faktöriyeli tutar. Bir halka elemanı sabit ve kök bileşenleriyle saklanır. Python ve Java sürümleri, on milyon adımda geçici nesne oluşturmamak için yukarıdaki dört çarpma özdeşliğini iki skaler üzerinde açar; bunlar C++ sürümündeki RingElement yardımcılarının matematiksel olarak aynısıdır.
mod_pow iki modüler tersi ikili üs alma ile bulur. brute_values eniyilenmiş türetimden bağımsızdır ve küçük girdilerde bütün kök bölmelerini özyinelemeli üretir. run_checkpoints, \(n=0,\ldots,10\) için iki yöntemi karşılaştırdıktan sonra yayımlanmış değerleri denetler.
Ana bağıntı \(m=1,\ldots,n+1\) adımlarının her birinde sabit sayıda modüler halka işlemi yapar; süre karmaşıklığı \(O(n+\log p)\)'dir. \(n=10^7\) yanında modüler üs almanın maliyeti önemsizdir. Yalnızca sabit sayıda skaler kalan tutulduğu için ek bellek \(O(1)\)'dir.
Doğrudan üretim \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) ifade gerektirir ve üstel olarak olanaksızdır. Derece \(n\)'ye kadarki bütün katsayıları saklamak bile \(O(n)\) bellek isterdi; doğrusal payda bağıntısı bu tabloyu ortadan kaldırır.
Se escriben \(F_0,F_1,\ldots,F_n\) en orden, con un signo menos entre términos adyacentes. Una expresión válida es una parentización completa: cada uno de los \(n\) pares de paréntesis contiene exactamente un signo menos de nivel superior, sin contar los que están dentro de sus subexpresiones. Debemos sumar los valores de todas las expresiones sintácticamente distintas.
Hay \(C_n\) expresiones, donde \(C_n\) es el número de Catalan de índice \(n\). Por eso es imposible construirlas para \(n=10^7\). Se pide
$$A(10^7)\pmod{p},\qquad p=10^9+9,$$
con los controles publicados \(A(3)=-6\), \(A(10)=-177666\) y \(A(100)\equiv71792794\pmod p\).
Una resta completamente parentizada con \(m=n+1\) operandos corresponde a un árbol binario completo ordenado con \(m\) hojas. La raíz determina un único corte tras \(k\) hojas: el subárbol izquierdo usa los primeros \(k\) operandos y el derecho los \(m-k\) restantes. Un bloque de \(j+1\) hojas tiene
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
árboles posibles. El corte de la raíz es la estructura esencial: el valor total es «valor izquierdo menos valor derecho» y cada árbol válido pertenece a un solo corte.
Sustituimos temporalmente los Fibonacci por \(1,t,t^2,\ldots,t^{m-1}\). Sea \(P_m(t)\) la suma de los valores de todas las parentizaciones de esos \(m\) operandos formales; en particular, \(P_1(t)=1\).
Si la raíz corta después de \(k\) hojas, la suma izquierda \(P_k(t)\) se repite por cada árbol derecho. La suma derecha se repite por cada árbol izquierdo, se desplaza mediante \(t^k\) y se resta en la raíz. Por tanto,
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
La recurrencia no solo cuenta árboles: conserva toda la contribución con signo de cada posición. Los primeros casos son
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$
Para cuatro hojas, la suma de los cinco polinomios de árbol es
$$P_4(t)=5-5t+t^2-t^3.$$
En el anillo de Fibonacci, \(r^2=1+r\) y \(r^3=1+2r\). Por ello, el coeficiente raíz vale
$$[r]P_4(r)=-5+1-2=-6.$$
Coincide con \(-4-2+0+2-2=-6\), la suma de las cinco expresiones del enunciado. El ejemplo comprueba simultáneamente las multiplicidades de Catalan, el signo del subárbol derecho, el desplazamiento de exponentes y la extracción de Fibonacci.
Definimos
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$
\(T(z)\) es la función generadora ordinaria de Catalan, también escrita a menudo \(C(z)\). \(P(z,t)\) es la serie bivariada de polinomios de signos; si el marcador se llama \(x\), es la misma \(P(z,x)\). Al sumar la recurrencia de cortes sobre \(m\), las dos convoluciones se convierten en productos:
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
Con \(q(z)=\sqrt{1-4z}\) y \(s(z)=\sqrt{1-4tz}\), al resolver la ecuación lineal resulta
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$
Así, una familia exponencial de árboles queda comprimida en la extracción de coeficientes de una sola serie algebraica.
Trabajamos módulo \(p\) en el anillo cociente
$$R=\mathbb{F}_p[r]/(r^2-r-1).$$
Cada elemento tiene forma \(a+br\). La relación definitoria implica, para \(i\ge1\),
$$r^i=F_{i-1}+F_ir,$$
y \(r^0=1\) tiene coeficiente de \(r\) igual a \(0=F_0\). Por consiguiente, el coeficiente de \(r\) en \(P_m(r)\) es exactamente la suma buscada cuando la hoja \(i\) recibe \(F_i\):
$$A(n)=[r]\,P_{n+1}(r).$$
No hace falta elegir una raíz de \(5\) ni efectuar divisiones generales en un cuerpo de extensión. Las multiplicaciones necesarias se reducen a estas operaciones sobre \((a,b)\):
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
Tomamos \(t=r\), \(q(z)=\sqrt{1-4z}\) y \(s(z)=\sqrt{1-4rz}\), y definimos
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
Al usar \(q(z)^2=1-4z\), \(s(z)^2=1-4rz\) y \(r^2=r+1\) para racionalizar el denominador de \(P\), se obtiene
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$
El nuevo denominador solo es lineal en \(z\). Por eso el programa puede avanzar un coeficiente cada vez, sin guardar una tabla de toda la serie.
Definimos los coeficientes escalados
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$
Con \(a_0=b_0=c_0=1\), \(c_{-1}=0\) y \(u_0=0\), la comparación de coeficientes da
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$
El coeficiente escalado de \(N(z)\) es
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$
y la identidad racionalizada se transforma en la actualización de un paso
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
El bucle llega hasta \(m=n+1\). Al final se deshace la escala factorial y se toma la componente raíz:
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
Como \(p\) es primo y \(n+1=10000001\lt p\), tanto \(4\) como \((n+1)!\) son no nulos módulo \(p\). Sus inversos se calculan con el pequeño teorema de Fermat, \(x^{-1}\equiv x^{p-2}\pmod p\).
La recurrencia optimizada es breve pero algebraicamente densa. Para \(0\le n\le10\), las implementaciones enumeran de forma independiente todos los cortes de raíz, generan todos los valores parentizados y comparan su suma directa con la recurrencia del anillo. También verifican los tres valores publicados. Así se detectan errores de signo en el subárbol derecho, desplazamientos incorrectos o una confusión entre las dos componentes antes del caso grande.
Lema 1. La recurrencia de \(P_m(t)\) suma cada parentización válida una sola vez. Todo árbol completo tiene un corte de raíz único; los factores de Catalan cuentan las opciones del subárbol opuesto y el bloque derecho recibe exactamente el desplazamiento \(t^k\) y el signo menos de la raíz.
Lema 2. El coeficiente de \(z^m\) en \(P(z,t)\) es \(P_m(t)\). Los productos por \(zT(z)\) y \(tzT(tz)\) reproducen las dos convoluciones del lema 1; resolver la ecuación lineal produce \(2z/(2+q-s)\).
Lema 3. En \(R\), el coeficiente de \(r\) en \(r^i\) es \(F_i\). Por linealidad, sustituir \(t=r\) convierte todos los pesos formales de las hojas en los Fibonacci requeridos.
Lema 4. Las actualizaciones de \(a_m,b_m,c_m,d_m,u_m\) son identidades de coeficientes de las series con raíz cuadrada y de la ecuación racionalizada. El escalado factorial es reversible porque el factorial relevante es invertible módulo \(p\).
Los lemas 1 y 2 muestran que \(P_{n+1}\) representa la suma de todas las expresiones. El lema 3 identifica su componente raíz con \(A(n)\), y el lema 4 prueba que el bucle calcula esa componente. Por tanto, el residuo impreso es \(A(10^7)\bmod(10^9+9)\).
alternating_sum conserva solo el \(a_m\) actual, \(b_m\), los dos últimos \(c_m\), el \(u_m\) anterior y el factorial acumulado. Cada elemento del anillo se guarda como componentes constante y raíz. Python y Java expanden las cuatro identidades anteriores sobre dos escalares para no crear millones de objetos temporales; son las mismas operaciones que realizan los auxiliares RingElement de C++.
mod_pow obtiene los dos inversos por exponenciación binaria. brute_values es independiente de la derivación optimizada y construye recursivamente todos los cortes para entradas pequeñas. run_checkpoints compara ambos métodos para \(n=0,\ldots,10\) y luego comprueba los valores publicados.
La recurrencia ejecuta un número constante de operaciones modulares para cada \(m=1,\ldots,n+1\), de modo que tarda \(O(n+\log p)\). La exponenciación es insignificante frente a \(n=10^7\). Solo se conservan unos pocos residuos escalares, por lo que la memoria auxiliar es \(O(1)\).
La enumeración directa exigiría \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) expresiones y sería exponencialmente imposible. Incluso guardar todos los coeficientes hasta grado \(n\) costaría \(O(n)\) memoria; la recurrencia de denominador lineal evita ese almacenamiento.
依次写下 \(F_0,F_1,\ldots,F_n\)，并在相邻两项间放一个减号。合法表达式是完全加括号的表达式：\(n\) 对括号中的每一对，在不计其子括号内部减号时，恰好包住一个顶层减号。目标是把所有语法结构不同的表达式的值相加。
这种表达式共有第 \(n\) 个 Catalan 数 \(C_n\) 个，所以在 \(n=10^7\) 时逐一构造完全不可行。我们要求
$$A(10^7)\pmod{p},\qquad p=10^9+9,$$
并以题目给出的 \(A(3)=-6\)、\(A(10)=-177666\) 和 \(A(100)\equiv71792794\pmod p\) 作为检查点。
含 \(m=n+1\) 个操作数的完全括号化减法式，对应一棵有 \(m\) 个叶子的有序满二叉树。根节点唯一地选择一个切分位置 \(k\)：左子树使用前 \(k\) 个操作数，右子树使用余下 \(m-k\) 个。含 \(j+1\) 个叶子的块共有
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
种树形。根切分是核心结构，因为整棵树的值就是“左值减右值”，而每棵合法树恰好属于一个根切分。
暂时把 Fibonacci 操作数替换为 \(1,t,t^2,\ldots,t^{m-1}\)。记 \(P_m(t)\) 为这 \(m\) 个形式操作数的所有括号化结果之和，特别地 \(P_1(t)=1\)。
若根在第 \(k\) 个叶子之后切分，左侧和 \(P_k(t)\) 会对每棵右树重复一次。右侧和会对每棵左树重复一次，由于叶子下标平移而乘以 \(t^k\)，并在根处被减去。因此
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
该递推不只是计数；它完整保留了每个叶子位置带符号的总贡献。最初几项为
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$
四个叶子的五棵树对应多项式相加后得到
$$P_4(t)=5-5t+t^2-t^3.$$
在 Fibonacci 环中 \(r^2=1+r\)、\(r^3=1+2r\)，所以根元系数是
$$[r]P_4(r)=-5+1-2=-6.$$
这正是题面五个值的和 \(-4-2+0+2-2=-6\)。这个小例子同时检查了 Catalan 重数、右子树的负号、指数平移和 Fibonacci 系数提取。
定义
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$
\(T(z)\) 是普通 Catalan 生成函数，也常写成 \(C(z)\)；\(P(z,t)\) 是二元符号多项式级数，若把标记变量记为 \(x\)，它就是 \(P(z,x)\)。对所有 \(m\) 汇总根切分递推后，两个卷积变成乘积：
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
令 \(q(z)=\sqrt{1-4z}\)、\(s(z)=\sqrt{1-4tz}\)，解这个线性方程得
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$
于是指数规模的树族被压缩为从一个代数幂级数中提取系数的问题。
在模 \(p\) 的商环
$$R=\mathbb{F}_p[r]/(r^2-r-1)$$
中计算。每个元素都写成 \(a+br\)。定义关系对 \(i\ge1\) 给出
$$r^i=F_{i-1}+F_ir,$$
而 \(r^0=1\) 的 \(r\) 系数为 \(0=F_0\)。因此 \(P_m(r)\) 的 \(r\) 系数，恰好就是第 \(i\) 个叶子赋值 \(F_i\) 后的目标和：
$$A(n)=[r]\,P_{n+1}(r).$$
不需要选择 \(\sqrt5\)，也不需要在扩域中做一般除法。程序所需的乘法可直接化为对分量 \((a,b)\) 的运算：
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
现在取 \(t=r\)、\(q(z)=\sqrt{1-4z}\)、\(s(z)=\sqrt{1-4rz}\)，并定义
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
利用 \(q(z)^2=1-4z\)、\(s(z)^2=1-4rz\) 和 \(r^2=r+1\) 对 \(P\) 的分母有理化，得到
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$
新分母关于 \(z\) 只有一次。因此程序可以从前一个系数推进到下一个系数，无须保存整个幂级数表。
定义阶乘缩放后的系数
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$
初值为 \(a_0=b_0=c_0=1\)、\(c_{-1}=0\)、\(u_0=0\)。比较系数得到
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$
\(N(z)\) 的缩放系数为
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$
而有理化恒等式化为代码中的单步更新：
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
循环运行到 \(m=n+1\)。最后撤销阶乘缩放并提取根元分量：
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
因为 \(p\) 是素数且 \(n+1=10000001\lt p\)，\(4\) 与 \((n+1)!\) 在模 \(p\) 下都非零。它们的逆由 Fermat 小定理 \(x^{-1}\equiv x^{p-2}\pmod p\) 求出。
优化递推虽然短，却包含密集的代数变换。三个实现对 \(0\le n\le10\) 独立枚举所有根切分，构造每个括号化值，再把直接总和与商环递推比较；随后还检查三个题目给出的数值。这样可在运行大实例前发现右子树符号、下标平移或两个环分量中的错误。
引理 1。\(P_m(t)\) 递推恰好一次计入每个合法括号化。每棵满二叉树有唯一根切分 \(k\)；Catalan 因子计数另一侧子树，右块恰好得到 \(t^k\) 平移和根节点的负号。
引理 2。\(P(z,t)\) 中 \(z^m\) 的系数是 \(P_m(t)\)。乘以 \(zT(z)\) 与 \(tzT(tz)\) 正好重现引理 1 的两个卷积，解线性方程即得 \(2z/(2+q-s)\)。
引理 3。在 \(R\) 中，\(r^i\) 的 \(r\) 系数等于 \(F_i\)。由线性性，代入 \(t=r\) 会把所有形式叶子权重变为所需 Fibonacci 权重。
引理 4。\(a_m,b_m,c_m,d_m,u_m\) 的更新都是平方根级数和有理化方程的系数恒等式。相关阶乘在模 \(p\) 下可逆，所以缩放可无损撤销。
引理 1 与 2 说明 \(P_{n+1}\) 表示所有合法表达式之和；引理 3 把其根元分量识别为 \(A(n)\)；引理 4 证明循环精确计算该分量。因此输出就是 \(A(10^7)\bmod(10^9+9)\)。
alternating_sum 只保存当前 \(a_m\)、\(b_m\)、最近两个 \(c_m\)、前一个 \(u_m\) 和累计阶乘。环元素用常数分量与根元分量表示。Python 与 Java 把上面的四个乘法恒等式直接展开成两个标量运算，以免在一千万步中创建临时对象；这与 C++ 的 RingElement 辅助函数完全等价。
mod_pow 用二进制快速幂计算两个模逆。brute_values 独立于优化推导，对小输入递归生成所有根切分。run_checkpoints 对 \(n=0,\ldots,10\) 比较两种方法，再检查题目公布的值。
主递推对每个 \(m=1,\ldots,n+1\) 执行常数次模环运算，所以时间为 \(O(n+\log p)\)；相对 \(n=10^7\)，快速幂开销可忽略。只保留固定数量的标量余数，辅助空间为 \(O(1)\)。
直接枚举需要 \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) 个表达式，呈指数级而不可行。即使保存到次数 \(n\) 的全部系数也需 \(O(n)\) 空间；线性分母递推避免了这张表。
Числа \(F_0,F_1,\ldots,F_n\) записываются по порядку, а между соседними членами ставятся знаки минус. Допустимое выражение является полной расстановкой скобок: каждая из \(n\) пар скобок содержит ровно один минус верхнего уровня, если не учитывать минусы внутри вложенных подвыражений. Требуется сложить значения всех синтаксически различных выражений.
Таких выражений \(C_n\), где \(C_n\) — \(n\)-е число Каталана. Поэтому для \(n=10^7\) непосредственное построение невозможно. Нужно найти
$$A(10^7)\pmod{p},\qquad p=10^9+9,$$
а опубликованные значения \(A(3)=-6\), \(A(10)=-177666\) и \(A(100)\equiv71792794\pmod p\) служат контрольными точками.
Полностью заключённое в скобки выражение с \(m=n+1\) операндами соответствует упорядоченному полному бинарному дереву с \(m\) листьями. Корень однозначно задаёт разбиение после \(k\) листьев: левое поддерево получает первые \(k\) операндов, правое — оставшиеся \(m-k\). Блок из \(j+1\) листьев допускает
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
деревьев. Корневое разбиение важно потому, что значение всего дерева равно «левое значение минус правое значение», и каждое допустимое дерево имеет ровно одно такое разбиение.
Временно заменим числа Фибоначчи формальными операндами \(1,t,t^2,\ldots,t^{m-1}\). Обозначим через \(P_m(t)\) сумму значений всех расстановок скобок для этих \(m\) операндов; в частности, \(P_1(t)=1\).
При разбиении после \(k\) листьев левая сумма \(P_k(t)\) повторяется для каждого правого дерева. Правая сумма повторяется для каждого левого дерева, умножается на \(t^k\) из-за сдвига индексов и вычитается в корне. Следовательно,
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
Эта рекурсия не просто считает деревья: она сохраняет полный знаковый вклад каждой позиции листа. Первые случаи имеют вид
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$
Для четырёх листьев сумма полиномов пяти деревьев равна
$$P_4(t)=5-5t+t^2-t^3.$$
В кольце Фибоначчи \(r^2=1+r\) и \(r^3=1+2r\), поэтому коэффициент при корне равен
$$[r]P_4(r)=-5+1-2=-6.$$
Это совпадает с \(-4-2+0+2-2=-6\), суммой пяти выражений из условия. Пример одновременно проверяет кратности Каталана, знак правого поддерева, сдвиг степеней и извлечение коэффициента Фибоначчи.
Введём
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$
\(T(z)\) — обычная производящая функция чисел Каталана, которую часто обозначают \(C(z)\). \(P(z,t)\) — двумерный ряд знаковых полиномов; если маркер назвать \(x\), это та же функция \(P(z,x)\). Суммирование корневой рекурсии по \(m\) превращает обе свёртки в произведения:
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
Положив \(q(z)=\sqrt{1-4z}\) и \(s(z)=\sqrt{1-4tz}\), решаем линейное уравнение и получаем
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$
Экспоненциальное семейство деревьев тем самым сжато до извлечения коэффициента одной алгебраической степенной серии.
Будем считать по модулю \(p\) в факторкольце
$$R=\mathbb{F}_p[r]/(r^2-r-1).$$
Каждый элемент имеет вид \(a+br\). Определяющее соотношение даёт для \(i\ge1\)
$$r^i=F_{i-1}+F_ir,$$
а коэффициент при \(r\) в \(r^0=1\) равен \(0=F_0\). Значит, коэффициент при \(r\) в \(P_m(r)\) в точности равен требуемой сумме, когда лист \(i\) получает вес \(F_i\):
$$A(n)=[r]\,P_{n+1}(r).$$
Не требуется выбирать квадратный корень из \(5\) или выполнять общее деление в расширении поля. Нужные умножения сводятся к операциям над парой \((a,b)\):
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
Теперь положим \(t=r\), \(q(z)=\sqrt{1-4z}\), \(s(z)=\sqrt{1-4rz}\) и определим
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
Рационализируя знаменатель \(P\) с помощью \(q(z)^2=1-4z\), \(s(z)^2=1-4rz\) и \(r^2=r+1\), получаем
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$
Новый знаменатель линеен по \(z\). Поэтому программа переходит от одного коэффициента к следующему и не хранит таблицу всей степенной серии.
Определим масштабированные коэффициенты
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$
При начальных значениях \(a_0=b_0=c_0=1\), \(c_{-1}=0\), \(u_0=0\) сравнение коэффициентов даёт
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$
Масштабированный коэффициент \(N(z)\) равен
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$
а рационализированное тождество превращается в одношаговое обновление
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
Цикл доходит до \(m=n+1\). Затем масштабирование снимается и берётся корневая компонента:
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
Поскольку \(p\) простое и \(n+1=10000001\lt p\), числа \(4\) и \((n+1)!\) ненулевые по модулю \(p\). Обратные вычисляются по малой теореме Ферма: \(x^{-1}\equiv x^{p-2}\pmod p\).
Оптимизированная рекурсия коротка, но алгебраически насыщенна. Для \(0\le n\le10\) реализации независимо перебирают все корневые разбиения, строят все значения со скобками и сравнивают прямую сумму с кольцевой рекурсией. Затем проверяются три опубликованных значения. Это выявляет ошибочный знак правого поддерева, неверный сдвиг индекса или путаницу двух компонент кольца до запуска большого случая.
Лемма 1. Рекурсия \(P_m(t)\) учитывает каждую допустимую расстановку скобок ровно один раз. У полного бинарного дерева есть единственное корневое разбиение \(k\); множители Каталана считают варианты противоположного поддерева, а правый блок получает ровно сдвиг \(t^k\) и минус корня.
Лемма 2. Коэффициент при \(z^m\) в \(P(z,t)\) равен \(P_m(t)\). Умножения на \(zT(z)\) и \(tzT(tz)\) воспроизводят две свёртки леммы 1, а решение линейного уравнения даёт \(2z/(2+q-s)\).
Лемма 3. В \(R\) коэффициент при \(r\) в \(r^i\) равен \(F_i\). Поэтому по линейности подстановка \(t=r\) заменяет формальные веса листьев требуемыми числами Фибоначчи.
Лемма 4. Обновления \(a_m,b_m,c_m,d_m,u_m\) являются тождествами для коэффициентов квадратнокорневых рядов и рационализированного уравнения. Факториальное масштабирование обратимо, поскольку нужный факториал обратим по модулю \(p\).
Леммы 1 и 2 показывают, что \(P_{n+1}\) представляет сумму всех допустимых выражений; лемма 3 отождествляет корневую компоненту с \(A(n)\); лемма 4 доказывает, что цикл вычисляет именно её. Следовательно, напечатанный остаток равен \(A(10^7)\bmod(10^9+9)\).
alternating_sum хранит только текущие \(a_m\), \(b_m\), два последних \(c_m\), предыдущее \(u_m\) и текущий факториал. Элемент кольца представлен постоянной и корневой компонентами. Python и Java раскрывают четыре приведённых тождества в операции над двумя скалярами, чтобы не создавать временные объекты на десяти миллионах шагов; это те же операции, что выполняют вспомогательные функции RingElement в C++.
mod_pow находит два обратных числа бинарным возведением в степень. brute_values независима от оптимизированного вывода и рекурсивно строит все разбиения для малых входов. run_checkpoints сравнивает оба метода для \(n=0,\ldots,10\), затем проверяет опубликованные значения.
На каждом \(m=1,\ldots,n+1\) выполняется постоянное число модульных операций в кольце, поэтому время равно \(O(n+\log p)\). На фоне \(n=10^7\) возведение в степень пренебрежимо мало. Хранится лишь фиксированное число скалярных остатков, так что дополнительная память равна \(O(1)\).
Прямой перебор потребовал бы \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) выражений и экспоненциально невозможен. Даже хранение всех коэффициентов до степени \(n\) заняло бы \(O(n)\) памяти; рекурсия с линейным знаменателем устраняет эту таблицу.
نكتب \(F_0,F_1,\ldots,F_n\) بالترتيب، ونضع إشارة طرح بين كل حدين متجاورين. التعبير المقبول هو وضع كامل للأقواس: كل زوج من أزواج الأقواس وعددها \(n\) يحتوي إشارة طرح واحدة بالضبط على مستواه الأعلى، من دون عد الإشارات الموجودة داخل تعبيراته الفرعية. والمطلوب جمع قيم جميع التعبيرات المختلفة من حيث البنية النحوية.
عدد هذه التعبيرات هو عدد كاتالان \(C_n\)، ولذلك يستحيل توليدها مباشرة عند \(n=10^7\). نريد حساب
$$A(10^7)\pmod{p},\qquad p=10^9+9,$$
مع استخدام القيم المنشورة \(A(3)=-6\)، و\(A(10)=-177666\)، و\(A(100)\equiv71792794\pmod p\) كنقاط تحقق.
كل تعبير طرح كامل الأقواس يضم \(m=n+1\) معاملات يماثل شجرة ثنائية كاملة مرتبة ذات \(m\) أوراق. يحدد الجذر موضع فصل وحيد بعد \(k\) أوراق: تستعمل الشجرة اليسرى أول \(k\) معاملات، وتستعمل اليمنى المعاملات \(m-k\) الباقية. والكتلة ذات \(j+1\) ورقة لها
$$C_j=\frac{1}{j+1}\binom{2j}{j}$$
أشجار ممكنة. فصل الجذر هو البنية الأساسية، لأن قيمة الشجرة كلها تساوي «القيمة اليسرى ناقص القيمة اليمنى»، ولأن كل شجرة مقبولة تنتمي إلى فصل جذر واحد فقط.
نستبدل معاملات فيبوناتشي مؤقتًا بـ \(1,t,t^2,\ldots,t^{m-1}\). ولتكن \(P_m(t)\) مجموع قيم جميع طرق وضع الأقواس حول هذه المعاملات الشكلية وعددها \(m\)، وبخاصة \(P_1(t)=1\).
عند الفصل بعد \(k\) أوراق يتكرر المجموع الأيسر \(P_k(t)\) مرة لكل شجرة يمنى. ويتكرر المجموع الأيمن مرة لكل شجرة يسرى، ويُضرب في \(t^k\) بسبب إزاحة فهارس الأوراق، ثم يُطرح عند الجذر. لذلك
$$P_m(t)=\sum_{k=1}^{m-1} \left(C_{m-k-1}P_k(t)-C_{k-1}t^kP_{m-k}(t)\right).$$
هذه العلاقة لا تعد الأشجار فحسب، بل تحفظ الإسهام الكامل ذي الإشارة لكل موضع ورقة. والحالات الأولى هي
$$P_1(t)=1,\qquad P_2(t)=1-t,\qquad P_3(t)=2-2t.$$
عند وجود أربع أوراق، يعطي جمع كثيرات حدود الأشجار الخمس
$$P_4(t)=5-5t+t^2-t^3.$$
وفي حلقة فيبوناتشي لدينا \(r^2=1+r\) و\(r^3=1+2r\)، ومن ثم يكون معامل الجذر
$$[r]P_4(r)=-5+1-2=-6.$$
وهذا يطابق \(-4-2+0+2-2=-6\)، أي مجموع التعبيرات الخمسة المعروضة في نص المسألة. يفحص هذا المثال في آن واحد تعددات كاتالان، وإشارة الشجرة اليمنى، وإزاحة الأس، وقاعدة استخراج فيبوناتشي.
نعرّف
$$T(z)=\sum_{j\ge0}C_jz^j=\frac{1-\sqrt{1-4z}}{2z}, \qquad P(z,t)=\sum_{m\ge1}P_m(t)z^m.$$
\(T(z)\) هي الدالة المولدة العادية لأعداد كاتالان، وتكتب كثيرًا \(C(z)\). أما \(P(z,t)\) فهي متسلسلة كثيرة حدود الإشارات ذات المتغيرين؛ وإذا سمينا المعلّم \(x\) فهي نفسها \(P(z,x)\). جمع علاقة فصل الجذر على قيم \(m\) يحول الالتفافين إلى حاصلَي ضرب:
$$P(z,t)=z+zT(z)P(z,t)-tzT(tz)P(z,t).$$
بوضع \(q(z)=\sqrt{1-4z}\) و\(s(z)=\sqrt{1-4tz}\)، يعطينا حل المعادلة الخطية
$$\boxed{P(z,t)=\frac{2z}{2+q(z)-s(z)}}.$$
وبهذا تنضغط عائلة الأشجار ذات الحجم الأسي إلى استخراج معامل من متسلسلة قوى جبرية واحدة.
نجري الحساب بترديد \(p\) داخل حلقة القسمة
$$R=\mathbb{F}_p[r]/(r^2-r-1).$$
لكل عنصر الصورة \(a+br\). وتعطي العلاقة المعرّفة، عندما \(i\ge1\)،
$$r^i=F_{i-1}+F_ir,$$
بينما معامل \(r\) في \(r^0=1\) هو \(0=F_0\). لذلك فإن معامل \(r\) في \(P_m(r)\) هو بالضبط المجموع المطلوب عندما تحمل الورقة \(i\) الوزن \(F_i\):
$$A(n)=[r]\,P_{n+1}(r).$$
لا نحتاج إلى اختيار جذر تربيعي للعدد \(5\)، ولا إلى قسمة عامة في حقل موسّع. عمليات الضرب المطلوبة تختزل إلى العمليات التالية على الزوج \((a,b)\):
$$\begin{aligned} r(a+br)&=b+(a+b)r,\\ (r+1)(a+br)&=(a+b)+(a+2b)r,\\ (r-1)(a+br)&=(b-a)+ar,\\ (2-r)(a+br)&=(2a-b)+(b-a)r. \end{aligned}$$
نضع الآن \(t=r\)، و\(q(z)=\sqrt{1-4z}\)، و\(s(z)=\sqrt{1-4rz}\)، ونعرّف
$$N(z)=1-q(z)+s(z)-q(z)s(z) +(r-1)z\bigl(q(z)+s(z)\bigr)+2(r+1)z.$$
باستعمال \(q(z)^2=1-4z\)، و\(s(z)^2=1-4rz\)، و\(r^2=r+1\) لترشيد مقام \(P\)، نحصل على
$$\bigl(4+2(2-r)^2z\bigr)P(z,r)=(2-r)N(z).$$
المقام الجديد خطي فقط في \(z\). لذلك يستطيع البرنامج الانتقال من معامل إلى المعامل التالي من دون حفظ جدول متسلسلة القوى كاملة.
نعرّف المعاملات المحجّمة بالمضروب:
$$a_m=m![z^m]q(z),\quad b_m=m![z^m]s(z),\quad c_m=m![z^m]q(z)s(z),\quad u_m=m![z^m]P(z,r).$$
مع القيم الابتدائية \(a_0=b_0=c_0=1\)، و\(c_{-1}=0\)، و\(u_0=0\)، تعطينا مقارنة المعاملات
$$\begin{aligned} a_m&=(4m-6)a_{m-1},\\ b_m&=(4m-6)r\,b_{m-1},\\ c_m&=2(2m-3)(r+1)c_{m-1} -16(m-3)(m-1)r\,c_{m-2}. \end{aligned}$$
أما المعامل المحجّم لـ \(N(z)\) فهو
$$d_m=-a_m+b_m-c_m +m(r-1)\bigl(a_{m-1}+b_{m-1}\bigr) +2(r+1)\delta_{m,1},$$
وتتحول هوية الترشيد إلى تحديث الخطوة الواحدة المستعمل في الكود:
$$\boxed{u_m=\frac{2-r}{4} \left(d_m-2m(2-r)u_{m-1}\right)}.$$
تستمر الحلقة حتى \(m=n+1\). وفي النهاية نلغي تحجيم المضروب ونأخذ مركبة الجذر:
$$A(n)=[r]\left(u_{n+1}\,((n+1)!)^{-1}\right)\pmod p.$$
بما أن \(p\) أولي و\(n+1=10000001\lt p\)، فإن \(4\) و\((n+1)!\) كلاهما غير صفري بترديد \(p\). تُحسب المعكوسات بمبرهنة فيرما الصغرى: \(x^{-1}\equiv x^{p-2}\pmod p\).
العلاقة المحسنة قصيرة لكنها كثيفة جبريًا. عند \(0\le n\le10\)، تعدّد التطبيقات كل فواصل الجذر بصورة مستقلة، وتبني كل القيم ذات الأقواس، ثم تقارن مجموعها المباشر بعلاقة الحلقة. كما تتحقق من القيم المنشورة الثلاث. وبذلك يُكتشف خطأ إشارة الشجرة اليمنى، أو إزاحة فهرس خاطئة، أو خلط بين مركبتي الحلقة قبل تشغيل الحالة الكبيرة.
اللمّة 1. تجمع علاقة \(P_m(t)\) كل وضع أقواس مقبول مرة واحدة بالضبط. لكل شجرة ثنائية كاملة فصل جذر وحيد \(k\)؛ تعد عوامل كاتالان خيارات الشجرة المقابلة، وتحصل الكتلة اليمنى على إزاحة \(t^k\) وإشارة الطرح عند الجذر بالضبط.
اللمّة 2. معامل \(z^m\) في \(P(z,t)\) هو \(P_m(t)\). يعيد الضرب في \(zT(z)\) و\(tzT(tz)\) الالتفافين في اللمّة 1، وحل المعادلة الخطية يعطي \(2z/(2+q-s)\).
اللمّة 3. في \(R\)، معامل \(r\) في \(r^i\) هو \(F_i\). وبفضل الخطية، يحول التعويض \(t=r\) كل أوزان الأوراق الشكلية إلى أوزان فيبوناتشي المطلوبة.
اللمّة 4. تحديثات \(a_m,b_m,c_m,d_m,u_m\) هي هويات معاملات لمتسلسلات الجذور التربيعية ولمعادلة الترشيد. تحجيم المضروب قابل للعكس لأن المضروب المعني له معكوس بترديد \(p\).
تبيّن اللمّتان 1 و2 أن \(P_{n+1}\) تمثل مجموع كل التعبيرات المقبولة؛ وتحدد اللمّة 3 مركبة الجذر بأنها \(A(n)\)؛ وتثبت اللمّة 4 أن الحلقة تحسب هذه المركبة نفسها. لذلك فإن الباقي المطبوع هو \(A(10^7)\bmod(10^9+9)\).
تحتفظ الدالة alternating_sum فقط بالقيم الحالية \(a_m\) و\(b_m\)، وآخر قيمتين لـ \(c_m\)، والقيمة السابقة \(u_m\)، والمضروب الجاري. يمثل عنصر الحلقة بمركبته الثابتة ومركبة الجذر. توسع نسختا Python وJava هويات الضرب الأربع إلى عمليات على قيمتين عدديتين كي لا تنشئا ملايين الكائنات المؤقتة؛ وهي العمليات الرياضية نفسها في مساعدات RingElement بنسخة C++.
تحسب mod_pow المعكوسين بالأس الثنائي. أما brute_values فهي مستقلة عن الاشتقاق المحسن وتبني كل فواصل الجذر تكراريًا للمدخلات الصغيرة. وتقارن run_checkpoints الطريقتين عند \(n=0,\ldots,10\)، ثم تفحص القيم المنشورة.
تنفذ العلاقة الرئيسية عددًا ثابتًا من عمليات الحلقة المعيارية لكل \(m=1,\ldots,n+1\)، لذلك زمنها \(O(n+\log p)\). وكلفة رفع القوة ضئيلة بجانب \(n=10^7\). لا يُحفظ إلا عدد ثابت من البواقي العددية، لذا فالذاكرة الإضافية \(O(1)\).
يحتاج التعداد المباشر إلى \(C_n\sim4^n/(n^{3/2}\sqrt{\pi})\) تعبيرًا، وهو مستحيل أسيًا. وحتى حفظ جميع المعاملات حتى الدرجة \(n\) يحتاج ذاكرة \(O(n)\)؛ أما علاقة المقام الخطي فتزيل هذا الجدول.