The problem asks for the tricoloured coin-fountain count \(T(20000)\) modulo \(10^9\). Exhaustive generation is completely impractical at this size, so the solution works with truncated generating functions and formal power-series algebra instead of exploring fountain states directly.
The computation is organized around one auxiliary series \(F_2(x)\). After that series is known to the required degree, a second rational transformation produces the generating function whose coefficients are the desired values \(T(n)\).
The auxiliary series is
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
This continued fraction is the compact object behind the counting problem. Expanding it directly to degree \(20000\) would be awkward, so the implementations switch to an equivalent quotient of two explicit \(q\)-series.
Define the finite \(q\)-Pochhammer product
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k).$$
The key identity used by the implementations is
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}.$$
So the continued fraction is converted into a numerator series and a denominator series. For a truncation to degree \(N\), only finitely many indices \(m\) contribute: once both \(m(m+1)\) and \(m(m+2)\) exceed \(N\), that index can no longer affect any coefficient up to \(x^N\).
The reciprocal products are updated one step at a time through
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right).$$
This means that once the truncated coefficients of \(1/(x;x)_m\) are known, the next one is obtained by adding shifted copies spaced by \(m+1\). The code therefore carries a single evolving truncated series instead of rebuilding each reciprocal product from scratch.
Suppose
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
If
$$A(x)=\sum_{n\ge 0} a_n x^n,$$
then comparing coefficients in \(A(x)D(x)=N(x)\) gives
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1).$$
Because the constant term of the denominator is \(1\), every new coefficient depends only on earlier ones. The implementations use this recurrence first to recover \(F_2(x)\), and later to recover the final target series.
After \(F_2(x)\) has been computed to the required degree, the target series is
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}.$$
The desired counting sequence is then extracted through
$$T(n)=3\,[x^n]\,t(x),$$
where \([x^n]\) denotes the coefficient of \(x^n\). So the whole computation is: build the two \(q\)-series for \(F_2\), divide them, form the numerator and denominator of \(t(x)\), divide again, read the coefficient of \(x^n\), and multiply by \(3\).
To degree \(4\), the continued fraction contributes only enough to give
$$F_2(x)=1+x^2+x^4+O(x^5).$$
Hence
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5).$$
Writing \(t(x)=\sum_{n\ge 0} t_n x^n\), the division recurrence yields
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16.$$
Therefore
$$T(4)=3\,t_4=48,$$
which matches the low-degree checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same mathematical pipeline. The truncated numerator and denominator of \(F_2(x)\) are accumulated term by term, with alternating signs, while a rolling truncated series stores the current reciprocal product \(1/(x;x)_m\). After the first formal division, the code builds the numerator and denominator of \(t(x)\) from the coefficients of \(F_2(x)\) and applies the same division recurrence again.
The final answer is the coefficient of \(x^{20000}\) in \(t(x)\), multiplied by \(3\) and reduced modulo \(10^9\). The implementations also perform small internal checks: they compare the \(q\)-series coefficients of \(F_2\) with a direct low-degree continued-fraction expansion, and they verify checkpoint values such as \(T(4)=48\) and \(T(10)=17760\). The Java implementation delegates the heavy computation to the compiled implementation of the same formulas.
Let \(N\) be the truncation degree. Building the two \(q\)-series for \(F_2(x)\) takes \(O(N\sqrt{N})\) coefficient updates because only \(m\le O(\sqrt{N})\) contribute, and each contributing index touches \(O(N)\) coefficients. The dominant cost is the two formal series divisions, each of which is \(O(N^2)\). Therefore the overall running time is \(O(N^2)\), and the memory usage is \(O(N)\).
Gesucht ist die Anzahl \(T(20000)\) der trikolorierten Münzfontänen modulo \(10^9\). Eine direkte Erzeugung aller Konfigurationen ist in dieser Größenordnung aussichtslos, daher arbeitet die Lösung nicht mit Zustandsrekursion, sondern mit abgeschnittenen erzeugenden Funktionen und formalen Potenzreihen.
Die Rechnung wird durch eine Hilfsreihe \(F_2(x)\) organisiert. Sobald diese Reihe bis zum benötigten Grad bekannt ist, liefert eine zweite rationale Transformation die erzeugende Funktion, aus der die Werte \(T(n)\) als Koeffizienten abgelesen werden.
Die Hilfsreihe lautet
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
Dieser Kettenbruch ist das kompakte mathematische Objekt hinter der Zählung. Ihn direkt bis Grad \(20000\) auszumultiplizieren wäre unhandlich, deshalb wechseln die Implementierungen zu einer äquivalenten Darstellung als Quotient zweier expliziter \(q\)-Reihen.
Definiere das endliche \(q\)-Pochhammer-Produkt
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k).$$
Die entscheidende Identität ist
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}.$$
Damit wird der Kettenbruch in eine Zählerreihe und eine Nennerreihe überführt. Für eine Trunkierung bis Grad \(N\) sind nur endlich viele Indizes \(m\) relevant: Sobald sowohl \(m(m+1)\) als auch \(m(m+2)\) größer als \(N\) sind, kann dieser Summand keinen Koeffizienten bis \(x^N\) mehr beeinflussen.
Die Kehrwerte der Produkte werden über
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right)$$
iterativ aktualisiert. Kennt man also die abgeschnittenen Koeffizienten von \(1/(x;x)_m\), so erhält man die nächste Reihe durch das Addieren verschobener Kopien im Abstand \(m+1\). Genau deshalb hält der Code nur eine fortlaufend aktualisierte Hilfsreihe vor und konstruiert die Produkte nicht jedes Mal neu.
Sei
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
Für
$$A(x)=\sum_{n\ge 0} a_n x^n$$
liefert der Koeffizientenvergleich in \(A(x)D(x)=N(x)\)
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1).$$
Da der konstante Nennerterm gleich \(1\) ist, hängt jeder neue Koeffizient nur von bereits bekannten früheren Koeffizienten ab. Diese Rekursion wird zuerst für \(F_2(x)\) und danach noch einmal für die Zielreihe verwendet.
Nachdem \(F_2(x)\) bis zum gewünschten Grad berechnet wurde, setzt man
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}.$$
Die gesuchte Folge erhält man dann über
$$T(n)=3\,[x^n]\,t(x),$$
wobei \([x^n]\) den Koeffizienten von \(x^n\) bezeichnet. Praktisch heißt das: erst die beiden \(q\)-Reihen für \(F_2\) aufbauen, dividieren, daraus Zähler und Nenner von \(t(x)\) bilden, erneut dividieren, den Koeffizienten von \(x^n\) auslesen und am Ende mit \(3\) multiplizieren.
Bis Grad \(4\) liefert der Kettenbruch bereits
$$F_2(x)=1+x^2+x^4+O(x^5).$$
Daraus folgt
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5).$$
Schreibt man \(t(x)=\sum_{n\ge 0} t_n x^n\), so ergibt die Reihendivision
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16.$$
Damit ist
$$T(4)=3\,t_4=48,$$
genau der kleine Kontrollwert, den die Implementierungen prüfen.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Pipeline. Zähler und Nenner von \(F_2(x)\) werden gliedweise mit alternierenden Vorzeichen aufgebaut, während eine fortlaufend aktualisierte Hilfsreihe den aktuellen Kehrwert \(1/(x;x)_m\) speichert. Nach der ersten formalen Division werden aus den Koeffizienten von \(F_2(x)\) Zähler und Nenner von \(t(x)\) gebildet, und dieselbe Divisionsrekursion wird ein zweites Mal angewandt.
Die Endausgabe ist der Koeffizient von \(x^{20000}\) in \(t(x)\), mit \(3\) multipliziert und modulo \(10^9\) reduziert. Zusätzlich führen die Implementierungen kleine interne Prüfungen aus: Sie vergleichen die \(q\)-Reihen-Koeffizienten von \(F_2\) mit einer direkten Kettenbruchentwicklung niedrigen Grades und kontrollieren Werte wie \(T(4)=48\) und \(T(10)=17760\). Die Java-Implementierung delegiert die eigentliche Schwerarbeit an die kompilierte Implementierung derselben Formeln.
Sei \(N\) der abgeschnittene Grad. Der Aufbau der beiden \(q\)-Reihen für \(F_2(x)\) benötigt \(O(N\sqrt{N})\) Koeffizientenaktualisierungen, weil nur \(m\le O(\sqrt{N})\) beitragen und jeder beitragende Index \(O(N)\) Koeffizienten berührt. Dominant sind jedoch die beiden formalen Reihendivisionen mit jeweils \(O(N^2)\). Insgesamt ergibt sich also Laufzeit \(O(N^2)\) bei Speicherbedarf \(O(N)\).
İstenen şey, üç renkli madeni para çeşmeleri için \(T(20000)\) değerini \(10^9\) modunda bulmaktır. Bu büyüklükte tüm yapıları doğrudan üretmek pratik değildir; bu yüzden çözüm durum uzayını dolaşmak yerine kesilmiş üreteç fonksiyonları ve formal kuvvet serileri kullanır.
Hesaplama bir yardımcı seri olan \(F_2(x)\) etrafında kuruludur. Bu seri istenen dereceye kadar hesaplandıktan sonra, ikinci bir rasyonel dönüşüm \(T(n)\) değerlerini veren üreteç fonksiyonunu üretir.
Yardımcı seri şudur:
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
Bu sürekli kesir, sayım probleminin arkasındaki kompakt nesnedir. Bunu doğrudan \(20000\). dereceye kadar açmak zahmetli olacağı için uygulamalar eşdeğer iki açık \(q\)-serisinin bölümüne geçer.
Sonlu \(q\)-Pochhammer çarpımını
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k)$$
olarak tanımlayalım. Uygulamaların kullandığı temel özdeşlik
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}$$
şeklindedir. Böylece sürekli kesir, bir pay serisi ve bir payda serisine dönüşür. Derece \(N\)'de kesildiğinde yalnızca sonlu sayıda \(m\) değeri katkı verir; çünkü hem \(m(m+1)\) hem de \(m(m+2)\) ifadeleri \(N\)'yi geçtiği anda o terim \(x^N\)'e kadar hiçbir katsayıyı etkileyemez.
Ters çarpımlar şu bağıntıyla güncellenir:
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right).$$
Yani \(1/(x;x)_m\) serisinin kesilmiş katsayıları biliniyorsa, bir sonraki seri \(m+1\) aralıklı kaydırılmış kopyalar eklenerek elde edilir. Kod bu yüzden her adımda ürünü sıfırdan kurmaz; tek bir hareketli yardımcı seri taşır ve onu güncelleyerek hem payda hem pay için kullanır.
Şöyle olsun:
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
Eğer
$$A(x)=\sum_{n\ge 0} a_n x^n$$
ise, \(A(x)D(x)=N(x)\) denkleminde katsayı karşılaştırması
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1)$$
sonucunu verir. Paydanın sabit terimi \(1\) olduğu için her yeni katsayı sadece önceki katsayılara bağlıdır. Uygulamalar bu yinelemeyi önce \(F_2(x)\) için, sonra da hedef seri için tekrar kullanır.
\(F_2(x)\) istenen dereceye kadar hesaplandıktan sonra
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}$$
tanımlanır. Aranan dizi de
$$T(n)=3\,[x^n]\,t(x)$$
ile elde edilir; burada \([x^n]\), \(x^n\)'in katsayısını ifade eder. Yani algoritma sırasıyla \(F_2\) için iki \(q\)-serisini kurar, böler, \(t(x)\)'in pay ve paydasını oluşturur, yeniden böler, \(x^n\) katsayısını alır ve son olarak \(3\) ile çarpar.
Derece \(4\)'e kadar sürekli kesirden
$$F_2(x)=1+x^2+x^4+O(x^5)$$
elde edilir. Buradan
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5)$$
olur. \(t(x)=\sum_{n\ge 0} t_n x^n\) yazıp bölüm yinelemesini uygularsak
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16$$
bulunur. Dolayısıyla
$$T(4)=3\,t_4=48,$$
ki bu da uygulamaların kontrol ettiği küçük doğrulama değeridir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. \(F_2(x)\)'in kesilmiş pay ve paydası, işaretleri dönüşümlü terimler halinde toplanırken, ayrı bir hareketli seri o andaki \(1/(x;x)_m\) değerini tutar. İlk formal bölüm tamamlandıktan sonra \(F_2(x)\) katsayılarından \(t(x)\)'in payı ve paydası kurulur ve aynı bölüm yinelemesi ikinci kez uygulanır.
Sonuç, \(t(x)\) içinde \(x^{20000}\) katsayısının \(3\) ile çarpılıp \(10^9\) moduna indirgenmesidir. Uygulamalar ayrıca küçük iç kontroller yapar: \(F_2\)'nin \(q\)-serisi katsayılarını düşük dereceli doğrudan sürekli kesir açılımıyla karşılaştırırlar ve \(T(4)=48\), \(T(10)=17760\) gibi değerleri doğrularlar. Java uygulaması ağır hesabı aynı formülleri kullanan derlenmiş uygulamaya devreder.
\(N\) kesme derecesi olsun. \(F_2(x)\) için iki \(q\)-serisini kurmak \(O(N\sqrt{N})\) katsayı güncellemesi gerektirir; çünkü yalnızca \(m\le O(\sqrt{N})\) katkı verir ve her katkı veren indeks \(O(N)\) katsayıya dokunur. Baskın maliyet ise her biri \(O(N^2)\) olan iki formal seri bölmesidir. Bu nedenle toplam süre \(O(N^2)\), bellek kullanımı ise \(O(N)\) olur.
Se pide el valor \(T(20000)\) para las fuentes de monedas tricolores, módulo \(10^9\). Generar todas las configuraciones de forma directa es inviable a esta escala, así que la solución reemplaza la recursión combinatoria por funciones generadoras truncadas y álgebra de series formales.
El cálculo se organiza alrededor de una serie auxiliar \(F_2(x)\). Cuando esa serie se conoce hasta el grado necesario, una segunda transformación racional produce la función generadora cuyas coeficientes son precisamente los valores \(T(n)\).
La serie auxiliar es
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
Esa fracción continua es el objeto compacto que codifica el conteo. Expandirla directamente hasta grado \(20000\) sería incómodo, por eso las implementaciones pasan a un cociente equivalente de dos \(q\)-series explícitas.
Definimos el producto finito de \(q\)-Pochhammer
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k).$$
La identidad clave es
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}.$$
Así, la fracción continua se convierte en una serie numeradora y una serie denominadora. Si truncamos en grado \(N\), solo intervienen finitos índices \(m\): en cuanto tanto \(m(m+1)\) como \(m(m+2)\) superan \(N\), ese término ya no puede afectar ningún coeficiente hasta \(x^N\).
Los productos recíprocos se actualizan mediante
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right).$$
Eso significa que, si ya conocemos los coeficientes truncados de \(1/(x;x)_m\), la siguiente serie se obtiene añadiendo copias desplazadas con salto \(m+1\). El código mantiene entonces una sola serie auxiliar en evolución, en lugar de reconstruir cada producto desde cero.
Supongamos que
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
Si
$$A(x)=\sum_{n\ge 0} a_n x^n,$$
entonces al comparar coeficientes en \(A(x)D(x)=N(x)\) se obtiene
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1).$$
Como el término constante del denominador es \(1\), cada coeficiente nuevo depende solo de coeficientes anteriores ya conocidos. Las implementaciones usan esta recurrencia primero para obtener \(F_2(x)\) y luego una segunda vez para la serie final.
Después de calcular \(F_2(x)\) hasta el grado requerido, se define
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}.$$
La secuencia pedida se extrae mediante
$$T(n)=3\,[x^n]\,t(x),$$
donde \([x^n]\) significa “coeficiente de \(x^n\)”. En otras palabras: se construyen las dos \(q\)-series de \(F_2\), se dividen, se forman el numerador y el denominador de \(t(x)\), se vuelve a dividir, se lee el coeficiente de \(x^n\) y al final se multiplica por \(3\).
Hasta grado \(4\), la fracción continua produce
$$F_2(x)=1+x^2+x^4+O(x^5).$$
Por tanto,
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5).$$
Si escribimos \(t(x)=\sum_{n\ge 0} t_n x^n\), la recurrencia de división da
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16.$$
En consecuencia,
$$T(4)=3\,t_4=48,$$
que coincide con el valor de comprobación de bajo grado usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia matemática. El numerador y el denominador truncados de \(F_2(x)\) se van acumulando término a término con signos alternados, mientras una serie auxiliar móvil almacena el recíproco actual \(1/(x;x)_m\). Tras la primera división formal, el código construye el numerador y el denominador de \(t(x)\) a partir de los coeficientes de \(F_2(x)\) y aplica de nuevo la misma recurrencia de división.
La salida final es el coeficiente de \(x^{20000}\) en \(t(x)\), multiplicado por \(3\) y reducido módulo \(10^9\). Además, las implementaciones realizan comprobaciones internas pequeñas: comparan los coeficientes de \(F_2\) obtenidos por \(q\)-series con una expansión directa de la fracción continua a bajo grado, y verifican valores como \(T(4)=48\) y \(T(10)=17760\). La implementación en Java delega el cálculo pesado a la implementación compilada de las mismas fórmulas.
Sea \(N\) el grado de truncamiento. Construir las dos \(q\)-series de \(F_2(x)\) requiere \(O(N\sqrt{N})\) actualizaciones de coeficientes, porque solo contribuyen índices \(m\le O(\sqrt{N})\) y cada uno toca \(O(N)\) coeficientes. El coste dominante está en las dos divisiones formales de series, cada una de orden \(O(N^2)\). Por tanto, el tiempo total es \(O(N^2)\) y la memoria utilizada es \(O(N)\).
本题要求求出三色硬币喷泉计数 \(T(20000)\) 的最后九位，也就是模 \(10^9\) 的结果。若直接枚举所有喷泉结构，状态空间会大到无法处理，因此解法完全转向生成函数、截断幂级数以及形式级数运算。
整个计算围绕一个辅助级数 \(F_2(x)\) 展开。先把 \(F_2(x)\) 的系数算到所需次数，再通过一次额外的有理变换得到目标生成函数，最后提取相应系数得到 \(T(n)\)。
辅助级数定义为
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
这个连分式就是计数问题背后的核心对象。若直接把它展开到 \(20000\) 次，会非常笨重；因此实现并不沿着连分式硬展开，而是改用一个与之等价、但更适合截断计算的 \(q\)-级数商。
定义有限 \(q\)-Pochhammer 乘积
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k).$$
实现所使用的关键恒等式是
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}.$$
这样一来，原来的连分式就被转换为一个分子级数和一个分母级数。若只需要到 \(x^N\) 为止的系数，那么只有有限多个 \(m\) 真正有贡献；一旦 \(m(m+1)\) 与 \(m(m+2)\) 都已经大于 \(N\)，这个 \(m\) 对所有不超过 \(x^N\) 的项都不可能再产生影响。
倒数乘积满足
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right).$$
这意味着：如果已经知道 \(1/(x;x)_m\) 的截断系数，那么 \(1/(x;x)_{m+1}\) 可以通过加入若干个相隔 \(m+1\) 次幂的平移副本来得到。实现正是利用这一点，让一条不断更新的辅助级数一路向前推进，而不是为每个 \(m\) 重新计算整个倒数乘积。
设
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
若
$$A(x)=\sum_{n\ge 0} a_n x^n,$$
则由 \(A(x)D(x)=N(x)\) 的同次幂系数比较可得
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1).$$
因为分母常数项是 \(1\)，所以每个新系数都只依赖已经算出的更低阶系数。实现先用这条递推从分子和分母恢复 \(F_2(x)\)，然后在最终变换之后再做一次同样的级数除法。
当 \(F_2(x)\) 已经算到所需次数后，定义
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}.$$
目标序列由
$$T(n)=3\,[x^n]\,t(x)$$
给出，其中 \([x^n]\) 表示取 \(x^n\) 的系数。也就是说，算法流程是：先构造 \(F_2\) 的两个 \(q\)-级数，做第一次除法得到 \(F_2\)；再构造 \(t(x)\) 的分子与分母，做第二次除法；最后读出 \(x^n\) 的系数并乘上 \(3\)。
只保留到 \(4\) 次项时，连分式给出
$$F_2(x)=1+x^2+x^4+O(x^5).$$
因此
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5).$$
设 \(t(x)=\sum_{n\ge 0} t_n x^n\)，利用上面的除法递推可得
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16.$$
于是
$$T(4)=3\,t_4=48,$$
这正好与实现中使用的低阶校验值一致。
C++、Python 和 Java 三个实现遵循同一条数学流水线。首先，程序逐项累加 \(F_2(x)\) 的截断分子与分母；在这个过程中，一条滚动更新的辅助级数始终保存当前的 \(1/(x;x)_m\)。得到 \(F_2(x)\) 之后，再依据其系数构造 \(t(x)\) 的分子与分母，并用同一套形式级数除法递推恢复 \(t(x)\) 的系数。
最终答案就是 \(t(x)\) 中 \(x^{20000}\) 的系数乘以 \(3\)，再对 \(10^9\) 取模。实现还包含若干小型内部校验：一方面把 \(F_2\) 的 \(q\)-级数结果与低次数的直接连分式展开做比较；另一方面检查 \(T(4)=48\)、\(T(10)=17760\) 这样的已知小值。Java 实现并不重新手写全部级数代数，而是调用采用同一组公式的已编译实现完成主要计算。
记截断次数为 \(N\)。构造 \(F_2(x)\) 的两个 \(q\)-级数需要 \(O(N\sqrt{N})\) 次系数更新，因为真正有贡献的 \(m\) 只有 \(O(\sqrt{N})\) 个，而每个这样的 \(m\) 会触碰 \(O(N)\) 个系数。真正主导总时间的是两次形式级数除法，每次都是 \(O(N^2)\)。因此总时间复杂度为 \(O(N^2)\)，空间复杂度为 \(O(N)\)。
Нужно вычислить число \(T(20000)\) для трёхцветных фонтанов из монет по модулю \(10^9\). Прямое перечисление всех конфигураций здесь нереально, поэтому решение полностью опирается на производящие функции, усечённые степенные ряды и формальные операции с коэффициентами.
В центре вычисления находится вспомогательный ряд \(F_2(x)\). Когда его коэффициенты найдены до нужной степени, ещё одно рациональное преобразование даёт производящую функцию, коэффициенты которой и образуют искомую последовательность \(T(n)\).
Вспомогательный ряд задаётся формулой
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
Именно эта непрерывная дробь компактно кодирует задачу подсчёта. Разворачивать её напрямую до степени \(20000\) неудобно, поэтому реализации переходят к эквивалентному представлению в виде отношения двух явных \(q\)-рядов.
Введём конечное произведение \(q\)-Похгаммера
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k).$$
Ключевое тождество имеет вид
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}.$$
Тем самым непрерывная дробь превращается в числитель и знаменатель, которые можно строить коэффициентно. При усечении до степени \(N\) реально участвуют лишь конечные \(m\): как только одновременно \(m(m+1)>N\) и \(m(m+2)>N\), данный индекс уже не может повлиять ни на один коэффициент до \(x^N\).
Обратные произведения обновляются по формуле
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right).$$
Это означает, что, зная усечённые коэффициенты \(1/(x;x)_m\), следующую серию можно получить, добавляя сдвинутые копии с шагом \(m+1\). Поэтому код хранит одну движущуюся вспомогательную серию и обновляет её на каждом шаге, а не пересчитывает весь обратный множитель заново.
Пусть
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
Если
$$A(x)=\sum_{n\ge 0} a_n x^n,$$
то из равенства \(A(x)D(x)=N(x)\) следует рекурсия
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1).$$
Поскольку свободный член знаменателя равен \(1\), каждый новый коэффициент определяется только через уже найденные более низкие коэффициенты. Именно эта схема сначала восстанавливает \(F_2(x)\), а затем ещё раз применяется к конечному преобразованию.
После вычисления \(F_2(x)\) до требуемой степени вводится ряд
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}.$$
Тогда искомая последовательность извлекается по формуле
$$T(n)=3\,[x^n]\,t(x),$$
где \([x^n]\) означает коэффициент при \(x^n\). Следовательно, алгоритм таков: построить два \(q\)-ряда для \(F_2\), разделить их, затем построить числитель и знаменатель для \(t(x)\), снова выполнить формальное деление, считать коэффициент при \(x^n\) и умножить результат на \(3\).
До степени \(4\) непрерывная дробь даёт
$$F_2(x)=1+x^2+x^4+O(x^5).$$
Отсюда
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5).$$
Если записать \(t(x)=\sum_{n\ge 0} t_n x^n\), то рекурсия деления даёт
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16.$$
Следовательно,
$$T(4)=3\,t_4=48,$$
и это совпадает с малой контрольной величиной, используемой в реализациях.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Усечённые числитель и знаменатель для \(F_2(x)\) накапливаются почленно с чередующимися знаками, а отдельный обновляемый массив коэффициентов хранит текущее значение \(1/(x;x)_m\). После первого формального деления из коэффициентов \(F_2(x)\) строятся числитель и знаменатель для \(t(x)\), и затем та же рекурсия деления применяется ещё раз.
Окончательный ответ получается как коэффициент при \(x^{20000}\) в \(t(x)\), умноженный на \(3\) и взятый по модулю \(10^9\). Дополнительно реализации выполняют небольшие внутренние проверки: сравнивают коэффициенты \(F_2\), полученные через \(q\)-ряды, с прямым разложением непрерывной дроби при малых степенях и проверяют значения вроде \(T(4)=48\) и \(T(10)=17760\). Реализация на Java делегирует тяжёлую часть вычисления скомпилированной реализации тех же формул.
Пусть \(N\) обозначает степень усечения. Построение двух \(q\)-рядов для \(F_2(x)\) требует \(O(N\sqrt{N})\) обновлений коэффициентов, потому что вклад дают только индексы \(m\le O(\sqrt{N})\), а каждый такой индекс затрагивает \(O(N)\) коэффициентов. Основное время, однако, тратится на два формальных деления рядов, каждое из которых имеет сложность \(O(N^2)\). Итак, общая временная сложность равна \(O(N^2)\), а память составляет \(O(N)\).
المطلوب هو حساب القيمة \(T(20000)\) الخاصة بنوافير العملات ثلاثية الألوان مع أخذ النتيجة بترديد \(10^9\). التوليد المباشر لكل البنى الممكنة غير عملي تمامًا عند هذا الحجم، لذلك يعتمد الحل على الدوال المولِّدة والسلاسل القوية الشكلية المقطوعة بدلًا من تتبّع الحالات واحدةً بعد أخرى.
تدور الفكرة كلها حول سلسلة مساعدة اسمها \(F_2(x)\). بعد حساب هذه السلسلة حتى الدرجة المطلوبة، تُطبَّق عليها عملية تحويل كسرية ثانية فتنتج الدالة المولِّدة التي تحمل معاملاتُها القيمَ المطلوبة \(T(n)\).
السلسلة المساعدة هي
$$F_2(x)=\frac{1}{1-\frac{x^2}{1-\frac{x^3}{1-\frac{x^4}{\ddots}}}}.$$
هذا الكسر المستمر هو الصياغة المضغوطة للبنية التوافقية في المسألة. توسيعه مباشرة حتى الدرجة \(20000\) سيكون غير مريح، لذلك تنتقل التطبيقات إلى صيغة مكافئة على شكل خارج قسمة بين سلسلتين صريحتين من نوع \(q\)-series.
لنعرّف جداء \(q\)-Pochhammer المنتهي:
$$(x;x)_m=\prod_{k=1}^{m}(1-x^k).$$
الهوية الأساسية المستخدمة في التطبيقات هي
$$F_2(x)=\frac{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+2)}}{(x;x)_m}}{\sum_{m\ge 0}(-1)^m\dfrac{x^{m(m+1)}}{(x;x)_m}}.$$
وبذلك يتحول الكسر المستمر إلى سلسلة في البسط وسلسلة في المقام. وإذا كنا نهتم بالمعاملات حتى الدرجة \(N\) فقط، فعدد القيم الفعلية لـ \(m\) يكون محدودًا؛ لأن أي قيمة تحقق فيها \(m(m+1)>N\) و\(m(m+2)>N\) معًا لن تؤثر بعد ذلك في أي معامل حتى \(x^N\).
مقلوبات هذه الجداءات تُحدَّث بواسطة العلاقة
$$\frac{1}{(x;x)_{m+1}}=\frac{1}{(x;x)_m}\cdot\frac{1}{1-x^{m+1}}=\frac{1}{(x;x)_m}\left(1+x^{m+1}+x^{2(m+1)}+\cdots\right).$$
هذا يعني أنه إذا كانت معاملات \(1/(x;x)_m\) المقطوعة معلومة، فإن السلسلة التالية تُستخرج بإضافة نسخ مزاحة تفصل بينها مسافة \(m+1\). ولهذا السبب لا يعيد التنفيذ تكوين الجداء من الصفر في كل مرة، بل يحتفظ بسلسلة متحركة واحدة ويحدّثها تدريجيًا.
افترض أن
$$A(x)=\frac{N(x)}{D(x)},\qquad D(x)=1+\sum_{i\ge 1} d_i x^i,\qquad N(x)=\sum_{n\ge 0} n_n x^n.$$
وأن
$$A(x)=\sum_{n\ge 0} a_n x^n.$$
بمقارنة المعاملات في العلاقة \(A(x)D(x)=N(x)\) نحصل على
$$a_0=n_0,\qquad a_n=n_n-\sum_{i=1}^{n} d_i a_{n-i}\pmod{10^9}\quad(n\ge 1).$$
وبما أن الحد الثابت في المقام يساوي \(1\)، فإن كل معامل جديد يعتمد فقط على معاملات سابقة معروفة. تستخدم التطبيقات هذه العلاقة أولًا لاستخراج \(F_2(x)\)، ثم تستخدمها مرة ثانية بعد التحويل النهائي للوصول إلى السلسلة الهدف.
بعد حساب \(F_2(x)\) حتى الدرجة المطلوبة نعرّف
$$t(x)=\frac{x(2F_2(x)-1)}{1-2x(2F_2(x)-1)}.$$
وعندئذٍ تُستخرج المتتالية المطلوبة من
$$T(n)=3\,[x^n]\,t(x),$$
حيث ترمز \([x^n]\) إلى معامل \(x^n\). وبعبارة عملية: نبني سلسلتي \(q\) الخاصتين بـ \(F_2\)، نقسمهما، ثم نبني بسط \(t(x)\) ومقامه، ونقسم مرة أخرى، ونأخذ معامل \(x^n\)، ثم نضرب في \(3\).
حتى الدرجة \(4\) يعطي الكسر المستمر
$$F_2(x)=1+x^2+x^4+O(x^5).$$
ومن ثم
$$A(x)=2F_2(x)-1=1+2x^2+2x^4+O(x^5),$$
$$N(x)=xA(x)=x+2x^3+O(x^5),$$
$$D(x)=1-2xA(x)=1-2x-4x^3+O(x^5).$$
إذا كتبنا \(t(x)=\sum_{n\ge 0} t_n x^n\)، فإن علاقة القسمة تعطينا
$$t_0=0,\qquad t_1=1,\qquad t_2=2,\qquad t_3=6,\qquad t_4=16.$$
لذلك
$$T(4)=3\,t_4=48,$$
وهو تمامًا مقدار التحقق الصغير الذي تستخدمه التطبيقات.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. يُجمَع بسط \(F_2(x)\) ومقامه على نحوٍ تراكمي حدًا بعد حد مع إشارات متناوبة، بينما تخزن سلسلة مساعدة متحركة القيمة الحالية لـ \(1/(x;x)_m\). وبعد القسمة الشكلية الأولى تُبنى معاملات بسط \(t(x)\) ومقامه انطلاقًا من معاملات \(F_2(x)\)، ثم تُطبَّق قاعدة القسمة نفسها مرة ثانية.
الجواب النهائي هو معامل \(x^{20000}\) في \(t(x)\) بعد ضربه في \(3\) ثم أخذ الباقي modulo \(10^9\). كما تُجري التطبيقات اختبارات داخلية صغيرة: فهي تقارن معاملات \(F_2\) الناتجة من صيغة \(q\)-series مع توسع مباشر منخفض الدرجة للكسر المستمر، وتتحقق من قيم مثل \(T(4)=48\) و\(T(10)=17760\). أما تنفيذ Java فيفوّض الحساب الثقيل إلى التنفيذ المترجم الذي يطبق الصيغ نفسها.
إذا رمزنا لدرجة القطع بـ \(N\)، فإن بناء سلسلتي \(q\) الخاصتين بـ \(F_2(x)\) يحتاج إلى \(O(N\sqrt{N})\) من تحديثات المعاملات، لأن القيم المؤثرة من \(m\) لا تتجاوز \(O(\sqrt{N})\)، وكل واحدة منها تمس \(O(N)\) من المعاملات. لكن الكلفة المسيطرة فعليًا تأتي من قسمي السلاسل الشكليتين، وكل واحدة منهما ذات تعقيد \(O(N^2)\). لذلك يكون الزمن الكلي \(O(N^2)\)، واستهلاك الذاكرة \(O(N)\).