The task is to evaluate \(G(100)\) modulo
$$M=987654319.$$
For exposition, write \(T_n=G(n)\). The implementations use the base value \(T_0=1\) and, for every \(n\ge 1\), the recurrence
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}.$$
This is a weighted Catalan-type convolution. Every new term is built from all ordered splits of \(n-1\) into a left part of size \(i\) and a right part of size \(n-1-i\). A direct recursive evaluation would repeat the same smaller terms many times, so the practical method is a bottom-up dynamic program performed modulo \(M\).
The key observation is that the entire problem is encoded by one quadratic recurrence. Once that recurrence is rewritten clearly, the rest is coefficient extraction, dynamic programming, and modular arithmetic.
The formula used by the implementations contains a factor \(n(2n-1)\) followed by division by \(n\). Algebraically, the \(n\) cancels immediately, so the mathematical recurrence is simply
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1),$$
with \(T_0=1\).
The factor \(2n-1\) depends only on the current level \(n\). Everything structurally interesting happens inside the convolution
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0.$$
Define the generating function
$$F(x)=\sum_{n\ge 0} T_n x^n.$$
Then the square \(F(x)^2\) has coefficients
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}.$$
Therefore the inner sum in the recurrence is exactly the coefficient of \(x^{n-1}\) in \(F(x)^2\):
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
This explains why the recurrence is a textbook Cauchy-product convolution and why only previously computed terms are needed.
Substitute the coefficient formula back into the series for \(F(x)\):
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m.$$
If we write
$$F(x)^2=\sum_{m\ge 0} c_m x^m,$$
then
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'.$$
Hence
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
This differential identity is not required to compute the answer, but it confirms that the sequence is governed entirely by the weighted square of its own generating function.
Because \(T_n\) depends only on \(T_0,T_1,\dots,T_{n-1}\), the values can be computed in increasing order of \(n\). For a fixed \(n\), the convolution contains exactly \(n\) products. Once \(T_n\) has been stored, it can be reused by every later term. This turns an exponentially branching recursive definition into a quadratic-time table fill.
The first few terms show the pattern clearly:
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
The value \(T_4=994\) is the natural checkpoint for the recurrence and matches the verification built into the implementations.
Mathematically, one may multiply by \(2n-1\) directly. The implementations, however, keep the factorized form \(n(2n-1)\) and then divide by \(n\) modulo \(M\). That division is carried out as multiplication by the modular inverse of \(n\):
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
For the required range \(1\le n\le 100\), those inverses exist modulo \(M\), so the modular computation is exactly equivalent to the simplified recurrence.
The C++, Python, and Java implementations all follow the same numerical plan. They allocate a one-dimensional table of length \(101\), place the base value \(1\) in the first slot, and then iterate upward from \(n=1\) to \(n=100\).
At each step, the implementation runs one inner loop over all split positions \(i\). This produces the convolution sum
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}.$$
After that, it applies the weight \(n(2n-1)\) and multiplies by the modular inverse of \(n\), which is mathematically the same as multiplying by \(2n-1\).
The three language versions differ only in low-level arithmetic details. The C++ and Java implementations compute modular inverses with the extended Euclidean algorithm, while the Python implementation uses modular exponentiation. All three methods produce the same residue class modulo \(M\).
Let \(N\) be the target index. The recurrence for \(T_n\) uses exactly \(n\) products, so the total work is
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2).$$
The modular inverse step costs only \(O(\log M)\) per level, so across all levels it contributes \(O(N\log M)\), which is lower order than the quadratic convolution. The memory usage is \(O(N)\), because only the already computed sequence values need to be stored.
Gesucht ist \(G(100)\) modulo
$$M=987654319.$$
Zur Darstellung bezeichnen wir die Folge mit \(T_n=G(n)\). Die Implementierungen verwenden den Startwert \(T_0=1\) und für jedes \(n\ge 1\) die Rekurrenz
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}.$$
Das ist eine gewichtete katalanartige Faltung. Jeder neue Wert entsteht aus allen geordneten Zerlegungen von \(n-1\) in einen linken Teil der Größe \(i\) und einen rechten Teil der Größe \(n-1-i\). Eine direkte Rekursion würde dieselben kleineren Werte ständig neu berechnen, daher ist ein Bottom-up-DP modulo \(M\) die richtige Methode.
Der Kern des Problems ist vollständig in einer quadratischen Rekurrenz enthalten. Sobald diese sauber umgeschrieben ist, bleiben nur noch Koeffizientenextraktion, dynamische Programmierung und modulare Arithmetik.
Die von den Implementierungen verwendete Formel enthält den Faktor \(n(2n-1)\) und anschließend eine Division durch \(n\). Algebraisch kürzt sich \(n\) sofort weg, also lautet die eigentliche Rekurrenz
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1),$$
mit \(T_0=1\).
Der Faktor \(2n-1\) hängt nur von der aktuellen Stufe \(n\) ab. Die gesamte Struktur steckt in der Faltung
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0.$$
Definiere die erzeugende Funktion
$$F(x)=\sum_{n\ge 0} T_n x^n.$$
Dann hat das Quadrat \(F(x)^2\) die Koeffizienten
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}.$$
Die innere Summe der Rekurrenz ist also genau der Koeffizient von \(x^{n-1}\) in \(F(x)^2\):
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
Damit ist sofort klar, warum hier eine klassische Cauchy-Faltung vorliegt und warum nur bereits bekannte Werte benötigt werden.
Setzt man die Koeffizientenformel in die Reihenentwicklung von \(F(x)\) ein, erhält man
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m.$$
Mit
$$F(x)^2=\sum_{m\ge 0} c_m x^m$$
folgt
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'.$$
Also gilt
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
Diese Differentialidentität wird zum Rechnen nicht benötigt, zeigt aber sehr klar, dass die Folge vollständig durch das gewichtete Quadrat ihrer eigenen erzeugenden Funktion bestimmt ist.
Da \(T_n\) nur von \(T_0,T_1,\dots,T_{n-1}\) abhängt, kann man die Werte in aufsteigender Reihenfolge von \(n\) berechnen. Für festes \(n\) enthält die Faltung genau \(n\) Produkte. Sobald \(T_n\) gespeichert wurde, steht es für alle späteren Stufen wieder zur Verfügung. So wird aus einer exponentiell verzweigten Rekursion ein Verfahren mit quadratischer Laufzeit.
Die ersten Werte zeigen das Muster unmittelbar:
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
Der Kontrollwert \(T_4=994\) stimmt mit der Verifikation in den Implementierungen überein.
Mathematisch könnte man direkt mit \(2n-1\) multiplizieren. Die Implementierungen behalten jedoch die faktorisierte Form \(n(2n-1)\) bei und dividieren anschließend modulo \(M\) durch \(n\). Das geschieht als Multiplikation mit dem modularen Inversen von \(n\):
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
Für den benötigten Bereich \(1\le n\le 100\) existieren diese Inversen modulo \(M\), also ist die modulare Rechnung exakt äquivalent zur vereinfachten Rekurrenz.
Die Implementierungen in C++, Python und Java folgen demselben numerischen Plan. Sie legen eine eindimensionale Tabelle der Länge \(101\) an, setzen im ersten Feld den Startwert \(1\) und laufen dann von \(n=1\) bis \(n=100\) aufwärts.
In jedem Schritt wird in einer inneren Schleife über alle Split-Positionen \(i\) die Faltungssumme
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}$$
gebildet. Danach wird das Gewicht \(n(2n-1)\) angewandt und mit dem modularen Inversen von \(n\) multipliziert, was mathematisch genau einer Multiplikation mit \(2n-1\) entspricht.
Die drei Sprachversionen unterscheiden sich nur in Details der Arithmetik. C++ und Java bestimmen Inverse mit dem erweiterten Euklid-Algorithmus, Python mit modularer Potenzierung. Alle drei Wege liefern dieselbe Restklasse modulo \(M\).
Sei \(N\) der Zielindex. Für \(T_n\) werden genau \(n\) Produkte benötigt, also beträgt der Gesamtaufwand
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2).$$
Die Berechnung modularer Inversen kostet pro Stufe nur \(O(\log M)\) und trägt insgesamt \(O(N\log M)\) bei; das ist asymptotisch kleiner als die quadratische Faltung. Der Speicherbedarf ist \(O(N)\), weil nur die bereits berechneten Folgenwerte gespeichert werden müssen.
Hedef, \(G(100)\) değerini
$$M=987654319$$
modunda hesaplamaktır. Anlatımda \(T_n=G(n)\) notasyonunu kullanalım. Uygulamalar \(T_0=1\) başlangıç değeriyle başlıyor ve her \(n\ge 1\) için
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}$$
bağıntısını kullanıyor. Bu, ağırlıklı bir Catalan-tipi evrişimdir. Her yeni terim, \(n-1\)'in solda \(i\), sağda \(n-1-i\) olacak şekilde tüm sıralı ayrışımlarından üretilir. Doğrudan özyinelemeli hesap, aynı alt değerleri tekrar tekrar çağıracağı için pratik çözüm modüler bottom-up dinamik programlamadır.
Problemin tamamı tek bir ikinci dereceden bağıntının içinde saklıdır. Bu bağıntı temiz biçimde yazıldıktan sonra geriye katsayı çıkarımı, dinamik programlama ve modüler aritmetik kalır.
Uygulamaların kullandığı formülde önce \(n(2n-1)\) çarpanı, sonra da \(n\)'e bölme vardır. Cebirsel olarak bu \(n\) hemen sadeleşir; dolayısıyla asıl matematiksel bağıntı
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1)$$
ve \(T_0=1\) şeklindedir.
\(2n-1\) katsayısı yalnızca mevcut seviyeye bağlıdır. Yapının tamamı
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0$$
evrişim toplamının içindedir.
Üreteç fonksiyonunu
$$F(x)=\sum_{n\ge 0} T_n x^n$$
olarak tanımlayalım. O zaman \(F(x)^2\)'nin katsayıları
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}$$
olur. Yani bağıntıdaki iç toplam, doğrudan \(F(x)^2\)'nin \(x^{n-1}\) katsayısıdır:
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
Böylece neden klasik bir Cauchy çarpımıyla karşı karşıya olduğumuz ve neden sadece daha önce hesaplanan terimlerin gerektiği açık hale gelir.
Katsayı formülünü \(F(x)\)'in seri açılımına geri koyarsak
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m$$
elde edilir. Eğer
$$F(x)^2=\sum_{m\ge 0} c_m x^m$$
yazarsak,
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'$$
olur. Dolayısıyla
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
Bu diferansiyel özdeşlik programı yazmak için şart değildir; ancak dizinin kendi üreteç fonksiyonunun ağırlıklı karesiyle tamamen belirlendiğini gösterir.
\(T_n\) sadece \(T_0,T_1,\dots,T_{n-1}\) değerlerine bağlı olduğu için terimler artan \(n\) sırasıyla hesaplanabilir. Sabit bir \(n\) için evrişim toplamında tam \(n\) çarpım vardır. \(T_n\) bir kez saklandığında tüm daha büyük indisler için yeniden kullanılabilir. Böylece üstel dallanan özyineleme, karesel zamanlı bir tablo doldurmaya dönüşür.
İlk birkaç terim deseni açıkça gösterir:
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
\(T_4=994\) değeri bağıntı için doğal bir kontrol noktasıdır ve uygulamalardaki doğrulamayla aynıdır.
Matematiksel olarak doğrudan \(2n-1\) ile çarpılabilir. Fakat uygulamalar \(n(2n-1)\) biçimini koruyup sonra \(n\)'e modüler olarak bölüyor. Bu işlem, \(n\)'in modüler tersiyle çarpmak demektir:
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
Gerekli aralıkta \(1\le n\le 100\) için bu tersler modulo \(M\) vardır; dolayısıyla modüler hesap, sadeleştirilmiş bağıntıyla tamamen aynıdır.
C++, Python ve Java uygulamalarının tamamı aynı sayısal planı izler. Uzunluğu \(101\) olan tek boyutlu bir tablo ayrılır, ilk hücreye başlangıç değeri \(1\) konur ve sonra \(n=1\)'den \(n=100\)'e kadar ilerlenir.
Her adımda, tüm ayrışım noktaları \(i\) üzerinden bir iç döngü çalıştırılarak
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}$$
toplamı hesaplanır. Ardından \(n(2n-1)\) ağırlığı uygulanır ve \(n\)'in modüler tersiyle çarpılır; bu da matematiksel olarak \(2n-1\) ile çarpmaya eşdeğerdir.
Diller arasındaki fark yalnızca düşük seviyeli aritmetiktedir. C++ ve Java sürümleri tersleri genişletilmiş Öklid algoritmasıyla, Python sürümü ise modüler üs alma ile bulur. Matematiksel sonuç üçünde de aynıdır.
\(N\) hedef indis olsun. \(T_n\) için tam \(n\) çarpım gerektiğinden toplam iş yükü
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2)$$
olur. Modüler ters hesabı seviye başına yalnızca \(O(\log M)\) maliyet getirir; toplamda \(O(N\log M)\) eder ve karesel evrişimden daha küçüktür. Bellek kullanımı \(O(N)\)'dir; çünkü yalnızca daha önce bulunan dizi değerleri saklanır.
La tarea es evaluar \(G(100)\) módulo
$$M=987654319.$$
Para la exposición, escribamos \(T_n=G(n)\). Las implementaciones usan el valor inicial \(T_0=1\) y, para cada \(n\ge 1\), la recurrencia
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}.$$
Se trata de una convolución ponderada de tipo Catalan. Cada término nuevo se forma a partir de todas las particiones ordenadas de \(n-1\) en una parte izquierda de tamaño \(i\) y una parte derecha de tamaño \(n-1-i\). Una recursión ingenua repetiría los mismos subproblemas, así que el enfoque práctico es un programa dinámico ascendente trabajado módulo \(M\).
Todo el problema queda resumido en una sola recurrencia cuadrática. Una vez escrita con claridad, el resto consiste en extracción de coeficientes, programación dinámica y aritmética modular.
La fórmula usada por las implementaciones contiene el factor \(n(2n-1)\) seguido de una división por \(n\). Algebraicamente, ese \(n\) se cancela de inmediato, así que la recurrencia matemática real es
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1),$$
con \(T_0=1\).
El factor \(2n-1\) depende solo del nivel actual \(n\). Toda la estructura combinatoria está dentro de la convolución
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0.$$
Definamos la función generadora
$$F(x)=\sum_{n\ge 0} T_n x^n.$$
Entonces los coeficientes de \(F(x)^2\) son
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}.$$
Por lo tanto, la suma interior de la recurrencia es exactamente el coeficiente de \(x^{n-1}\) en \(F(x)^2\):
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
Esto deja claro por qué aparece una convolución de Cauchy y por qué bastan los términos previamente calculados.
Al sustituir la fórmula de coeficientes en la serie de \(F(x)\), obtenemos
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m.$$
Si escribimos
$$F(x)^2=\sum_{m\ge 0} c_m x^m,$$
entonces
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'.$$
Así se obtiene
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
Esta identidad diferencial no es necesaria para programar la solución, pero sí confirma que toda la secuencia queda determinada por el cuadrado ponderado de su propia función generadora.
Como \(T_n\) depende solo de \(T_0,T_1,\dots,T_{n-1}\), los valores pueden calcularse en orden creciente de \(n\). Para un \(n\) fijo, la convolución contiene exactamente \(n\) productos. Una vez almacenado \(T_n\), se reutiliza en todos los niveles posteriores. Eso transforma una definición recursiva con ramificación exponencial en un llenado de tabla de tiempo cuadrático.
Los primeros valores muestran el patrón con claridad:
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
El valor \(T_4=994\) funciona como comprobación inmediata de la recurrencia y coincide con la verificación usada por las implementaciones.
Desde el punto de vista matemático, se podría multiplicar directamente por \(2n-1\). Sin embargo, las implementaciones conservan la forma factorizada \(n(2n-1)\) y luego dividen por \(n\) en aritmética modular. Esa división se hace multiplicando por el inverso modular de \(n\):
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
Para el intervalo requerido \(1\le n\le 100\), esos inversos existen módulo \(M\), de modo que el cálculo modular es exactamente equivalente a la recurrencia simplificada.
Las implementaciones en C++, Python y Java siguen el mismo plan numérico. Reservan una tabla unidimensional de longitud \(101\), colocan el valor base \(1\) en la primera posición y luego avanzan desde \(n=1\) hasta \(n=100\).
En cada paso, la implementación ejecuta un bucle interno sobre todas las posiciones de partición \(i\) y acumula la suma de convolución
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}.$$
Después aplica el peso \(n(2n-1)\) y multiplica por el inverso modular de \(n\), lo cual es matemáticamente igual a multiplicar por \(2n-1\).
Las tres versiones difieren solo en detalles aritméticos de bajo nivel. C++ y Java obtienen inversos con el algoritmo extendido de Euclides; Python usa exponenciación modular. Los tres métodos producen la misma clase residual módulo \(M\).
Sea \(N\) el índice objetivo. La recurrencia de \(T_n\) usa exactamente \(n\) productos, así que el trabajo total es
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2).$$
El cálculo de inversos modulares cuesta solo \(O(\log M)\) por nivel, de modo que en conjunto aporta \(O(N\log M)\), un término menor frente a la convolución cuadrática. El uso de memoria es \(O(N)\), porque basta con guardar los valores ya calculados de la secuencia.
题目的目标是计算 \(G(100)\) 在模
$$M=987654319$$
下的值。为了叙述方便，记 \(T_n=G(n)\)。三种实现都采用相同的初值 \(T_0=1\)，并且对每个 \(n\ge 1\) 使用递推式
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}.$$
这是一类带权的 Catalan 型卷积。每个新项都来自 \(n-1\) 的所有有序拆分：左边大小为 \(i\)，右边大小为 \(n-1-i\)。如果直接用朴素递归去算，就会反复重算同样的较小项，因此真正可行的方法是按 \(n\) 从小到大做动态规划，并在每一步都对 \(M\) 取模。
这个问题的全部计算内容都浓缩在一个二次递推里。只要把这个递推拆解清楚，就可以自然地得到卷积视角、生成函数视角以及实际程序所需的模运算形式。
实现里写成了先乘 \(n(2n-1)\)，再除以 \(n\) 的形式，但从纯代数角度看，这个 \(n\) 可以先约掉，因此真正的数学递推就是
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1),$$
同时保留初值 \(T_0=1\)。
这里的 \(2n-1\) 只是当前层 \(n\) 的权重，真正反映结构的是中间那段卷积和
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0.$$
它把所有左右拆分都恰好统计一次。
定义生成函数
$$F(x)=\sum_{n\ge 0} T_n x^n.$$
那么平方 \(F(x)^2\) 的 \(x^m\) 项系数就是
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}.$$
因此递推中的卷积和正好等于 \(F(x)^2\) 的 \(x^{n-1}\) 项系数，于是可以写成
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
这一步非常重要，因为它说明程序并不是在做一堆看似偶然的双重循环，而是在逐项提取一个平方生成函数的系数。
把上面的系数公式代回 \(F(x)\) 本身：
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m.$$
如果把
$$F(x)^2=\sum_{m\ge 0} c_m x^m$$
记成一个新级数，那么就有
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'.$$
于是得到
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
这个微分恒等式不是程序运行所必需的，但它把“卷积递推”提升成了一个更紧凑的生成函数关系，也说明整条数列完全由自己的平方生成函数决定。
因为 \(T_n\) 只依赖 \(T_0,T_1,\dots,T_{n-1}\)，所以最自然的算法就是按顺序计算。固定某个 \(n\) 时，卷积和里恰好有 \(n\) 个乘积项。把 \(T_n\) 算出来并存起来之后，后面的更大下标都可以重复利用它。这样就把一棵会指数爆炸的递归调用树，压缩成了一个规模为 \(O(N^2)\) 的表格计算过程。
前四项足以把模式看得很清楚：
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
因此 \(T_4=994\)。这个值非常适合作为人工检查点，也正是实现中用来确认递推正确性的那个小规模结果。
从数学上说，既然前面的 \(n\) 已经可以约掉，直接乘 \(2n-1\) 就够了。不过实现保留了
$$n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)$$
这样的写法，再在模 \(M\) 下乘上 \(n\) 的逆元，也就是
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
对本题所需的范围 \(1\le n\le 100\) 来说，这些逆元都存在，因此这种写法与直接用简化后的递推完全等价，只是更贴合实际代码中的模运算流程。
C++、Python 和 Java 三个实现的整体思路完全一致。它们先分配一个长度为 \(101\) 的一维表，把第一个位置设为基值 \(1\)，然后按 \(n=1,2,\dots,100\) 的顺序逐步填表。
在每个 \(n\) 上，程序都执行一次内层循环，遍历所有拆分位置 \(i\)，累计卷积和
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}.$$
得到这个和之后，再乘上权重 \(n(2n-1)\)，并乘以 \(n\) 在模 \(M\) 下的逆元。数学上这和直接乘 \(2n-1\) 没有区别。
三个语言版本只是在底层求逆的方式上不同。C++ 与 Java 用扩展欧几里得算法求逆元，Python 用模幂来求逆元，但它们最终得到的是同一个模 \(M\) 的剩余类。
设目标下标为 \(N\)。求出 \(T_n\) 需要恰好 \(n\) 次乘法，因此总工作量为
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2).$$
每一层额外的逆元计算只需要 \(O(\log M)\)，因此全部加起来是 \(O(N\log M)\)，属于低阶项，不会改变主导复杂度。内存方面只需要保存已经得到的数列值，所以空间复杂度为 \(O(N)\)。
Нужно вычислить \(G(100)\) по модулю
$$M=987654319.$$
Для изложения обозначим \(T_n=G(n)\). Во всех реализациях используется начальное значение \(T_0=1\), а для каждого \(n\ge 1\) применяется рекуррентная формула
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}.$$
Это взвешенная свёртка каталановского типа. Каждый новый член строится из всех упорядоченных разбиений числа \(n-1\) на левую часть размера \(i\) и правую часть размера \(n-1-i\). Наивная рекурсия бесконечно переиспользовала бы одни и те же подзадачи, поэтому практически правильный путь — вычислять значения снизу вверх по модулю \(M\).
Содержательно задача полностью определяется одной квадратичной рекурсией. После аккуратного переписывания этой формулы остаются только извлечение коэффициентов, динамическое программирование и модульная арифметика.
В реализациях формула записана как произведение на \(n(2n-1)\) с последующим делением на \(n\). Алгебраически этот множитель \(n\) сокращается сразу, поэтому чистая математическая рекурсия имеет вид
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1),$$
при \(T_0=1\).
Коэффициент \(2n-1\) зависит только от текущего уровня \(n\). Вся содержательная структура находится внутри свёртки
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0.$$
Введём производящую функцию
$$F(x)=\sum_{n\ge 0} T_n x^n.$$
Тогда коэффициенты квадрата \(F(x)^2\) равны
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}.$$
Следовательно, внутренняя сумма в рекурсии — это просто коэффициент при \(x^{n-1}\) у \(F(x)^2\):
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
Так становится понятно, почему здесь возникает стандартная свёртка типа произведения Коши и почему для вычисления нужны только уже найденные члены.
Подставим коэффициентную формулу обратно в ряд для \(F(x)\):
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m.$$
Если записать
$$F(x)^2=\sum_{m\ge 0} c_m x^m,$$
то
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'.$$
Отсюда следует
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
Это дифференциальное тождество не обязательно для программирования, но оно наглядно показывает, что последовательность целиком задаётся взвешенным квадратом собственной производящей функции.
Так как \(T_n\) зависит только от \(T_0,T_1,\dots,T_{n-1}\), значения удобно считать по возрастанию \(n\). Для фиксированного \(n\) свёртка содержит ровно \(n\) произведений. После сохранения \(T_n\) это значение можно использовать во всех следующих шагах. Тем самым экспоненциально разветвляющееся рекурсивное определение превращается в квадратичное заполнение таблицы.
Первые члены хорошо демонстрируют структуру:
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
Значение \(T_4=994\) служит естественной контрольной точкой и совпадает с той проверкой, которая заложена в реализациях.
С математической точки зрения достаточно сразу умножать на \(2n-1\). Однако реализации сохраняют вид \(n(2n-1)\), а затем делят на \(n\) в кольце вычетов по модулю \(M\). Это делается умножением на обратный элемент к \(n\):
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
Для диапазона \(1\le n\le 100\), который нужен в задаче, такие обратные элементы существуют, поэтому модульное вычисление полностью эквивалентно сокращённой формуле.
Реализации на C++, Python и Java используют одну и ту же численную схему. Они создают одномерную таблицу длины \(101\), помещают в первый элемент базовое значение \(1\), а затем идут по \(n=1,2,\dots,100\).
На каждом шаге выполняется внутренний цикл по всем позициям разбиения \(i\), который накапливает свёрточную сумму
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}.$$
После этого применяется вес \(n(2n-1)\), а затем результат умножается на обратный по модулю элемент к \(n\); математически это то же самое, что умножение на \(2n-1\).
Различия между версиями только низкоуровневые. C++ и Java ищут обратные элементы расширенным алгоритмом Евклида, а Python использует модульное возведение в степень. С математической точки зрения все три версии делают одно и то же.
Пусть \(N\) — нужный индекс. Для вычисления \(T_n\) требуется ровно \(n\) произведений, значит общий объём работы равен
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2).$$
Нахождение обратных элементов стоит лишь \(O(\log M)\) на каждый уровень, так что суммарно это \(O(N\log M)\), что асимптотически меньше квадратичной свёртки. Память имеет порядок \(O(N)\), потому что достаточно хранить уже вычисленные члены последовательности.
المطلوب هو حساب \(G(100)\) بترديد
$$M=987654319.$$
ولأغراض الشرح سنكتب \(T_n=G(n)\). تستخدم جميع التطبيقات القيمة الابتدائية \(T_0=1\)، ولكل \(n\ge 1\) تعتمد العلاقة
$$T_n=\frac{n(2n-1)}{n}\sum_{i=0}^{n-1} T_i T_{n-1-i}=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}.$$
هذه علاقة التفاف موزونة من النمط الكاتالاني. كل حد جديد يُبنى من جميع طرق تقسيم \(n-1\) إلى جزء أيسر حجمه \(i\) وجزء أيمن حجمه \(n-1-i\). لو حُسبت العلاقة بالاستدعاء الذاتي المباشر فسيُعاد حساب الحدود الصغيرة مرات كثيرة، ولذلك فالطريقة العملية هي البرمجة الديناميكية التصاعدية مع الاختزال بترديد \(M\).
جوهر المسألة كله موجود داخل علاقة تراجعية تربيعية واحدة. وبعد إعادة صياغتها بوضوح، يصبح التحليل عبارة عن التفاف Cauchy ودوال مولدة وحساب معياري منضبط.
الصيغة المستخدمة في التطبيقات تحتوي على العامل \(n(2n-1)\) ثم قسمة على \(n\). جبريًا يختصر هذا العامل فورًا، ولذلك تصبح العلاقة الرياضية الأساسية
$$T_n=(2n-1)\sum_{i=0}^{n-1} T_i T_{n-1-i}\qquad (n\ge 1),$$
مع \(T_0=1\).
العامل \(2n-1\) يعتمد فقط على المستوى الحالي \(n\)، أما البنية الحقيقية فتوجد داخل مجموع الالتفاف
$$T_0T_{n-1}+T_1T_{n-2}+\cdots+T_{n-1}T_0.$$
لنعرّف الدالة المولدة
$$F(x)=\sum_{n\ge 0} T_n x^n.$$
عندئذ تكون معاملات \(F(x)^2\) هي
$$[x^m]F(x)^2=\sum_{i=0}^{m} T_i T_{m-i}.$$
أي أن المجموع الداخلي في العلاقة التراجعية هو بالضبط معامل \(x^{n-1}\) في \(F(x)^2\)، ومن ثم
$$T_n=(2n-1)[x^{n-1}]F(x)^2.$$
وهذا يوضح أن الحلقة الداخلية في التنفيذ ليست مجرد تجميع عددي، بل هي استخراج معاملات من مربع الدالة المولدة.
إذا عوضنا هذه الصيغة داخل متسلسلة \(F(x)\)، نحصل على
$$F(x)-1=\sum_{n\ge 1} T_n x^n=x\sum_{m\ge 0}(2m+1)[x^m]F(x)^2\,x^m.$$
ولو كتبنا
$$F(x)^2=\sum_{m\ge 0} c_m x^m,$$
فإن
$$\sum_{m\ge 0}(2m+1)c_m x^m=F(x)^2+2x\bigl(F(x)^2\bigr)'.$$
ومن هنا نستنتج
$$F(x)-1=xF(x)^2+2x^2\bigl(F(x)^2\bigr)'=xF(x)^2+4x^2F(x)F'(x).$$
هذه الهوية التفاضلية ليست ضرورية من أجل التنفيذ، لكنها تكشف بشكل مدمج أن المتتالية كلها محكومة بالمربع الموزون لدالتها المولدة.
بما أن \(T_n\) يعتمد فقط على \(T_0,T_1,\dots,T_{n-1}\)، فيمكن حساب القيم بترتيب تصاعدي. وعند قيمة ثابتة لـ \(n\) يحتوي مجموع الالتفاف على \(n\) جداءات بالضبط. وما إن نحسب \(T_n\) ونخزنه حتى يمكن إعادة استخدامه في جميع الحدود اللاحقة. وبهذا تتحول علاقة تراجعية ذات تفرع أسي إلى ملء جدول بزمن تربيعي.
أول الحدود تبيّن النمط مباشرة:
$$T_1=1\cdot(T_0T_0)=1.$$
$$T_2=3\cdot(T_0T_1+T_1T_0)=3(1+1)=6.$$
$$T_3=5\cdot(T_0T_2+T_1T_1+T_2T_0)=5(6+1+6)=65.$$
$$T_4=7\cdot(T_0T_3+T_1T_2+T_2T_1+T_3T_0)=7(65+6+6+65)=994.$$
إذن \(T_4=994\)، وهي نقطة فحص صغيرة ومفيدة، كما أنها تطابق التحقق المضمَّن في التنفيذ.
من الناحية الرياضية يكفي الضرب مباشرة في \(2n-1\). لكن التطبيقات تحتفظ بالشكل \(n(2n-1)\) ثم تقسم على \(n\) داخل الحساب المعياري. وهذه القسمة تُنفّذ عبر الضرب في المعكوس الضربي المعياري لـ \(n\):
$$T_n\equiv n(2n-1)\left(\sum_{i=0}^{n-1} T_i T_{n-1-i}\right)n^{-1}\pmod{M}.$$
ولأن المعكوسات المطلوبة موجودة لكل \(1\le n\le 100\)، فإن هذه الصياغة تعطي النتيجة نفسها تمامًا التي تعطيها العلاقة المبسطة.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. فهي تنشئ جدولًا أحادي البعد طوله \(101\)، وتضع القيمة الأساسية \(1\) في الخانة الأولى، ثم تتحرك من \(n=1\) حتى \(n=100\).
في كل خطوة تُنفَّذ حلقة داخلية على جميع مواضع التقسيم \(i\) لتجميع مجموع الالتفاف
$$\sum_{i=0}^{n-1} T_i T_{n-1-i}\pmod{M}.$$
بعد ذلك يُطبَّق الوزن \(n(2n-1)\)، ثم يُضرب الناتج في المعكوس المعياري لـ \(n\)، وهو ما يعادل رياضيًا الضرب في \(2n-1\).
الاختلاف بين اللغات الثلاث يقتصر على التفاصيل العددية المنخفضة المستوى. نسختا C++ وJava تستخدمان خوارزمية إقليدس الموسعة لاستخراج المعكوسات، بينما تستخدم نسخة Python الأس المعياري. لكن النتيجة الرياضية في جميع الحالات واحدة.
إذا كان \(N\) هو الفهرس المطلوب، فإن حساب \(T_n\) يحتاج إلى \(n\) جداءات بالضبط، ومن ثم يكون مجموع العمل
$$\sum_{n=1}^{N} n=\frac{N(N+1)}{2}=O(N^2).$$
أما حساب المعكوس المعياري فيكلف \(O(\log M)\) فقط في كل مستوى، أي \(O(N\log M)\) إجمالًا، وهو حد أدنى رتبة من التفاف الزمن التربيعي. واستهلاك الذاكرة هو \(O(N)\) لأننا لا نحتاج إلا إلى تخزين القيم التي حُسبت بالفعل.