The implementations show that Problem 648 can be reformulated as a coefficient-extraction problem for truncated formal power series. With \(D=1000\) and modulus \(M=10^9\), the objective is to compute the coefficient of \(x^D\) in a cumulative series built from stage polynomials. Because only terms up to degree \(D\) can affect the final answer, every polynomial is truncated after \(x^{1000}\).
Write \([x^k]F(x)\) for the coefficient of \(x^k\) in a series \(F(x)\). The computation is organized around one polynomial per stage and a running product of those stage factors.
At stage \(n\), the implementation accumulates the coefficients of the finite sum
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
Using the binomial theorem, each summand contributes
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}.$$
Therefore the coefficient of \(x^k\) in \(\mathcal{A}_n(x)\) is
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}.$$
This is why the code first builds a truncated Pascal triangle up to row \(2D\): every stage only needs binomial coefficients coming from even exponents \(0,2,4,\dots,2D-2\), and only degrees \(k\le D\) matter.
The next polynomial is obtained by multiplying \(\mathcal{A}_n(x)\) by \(x(1-x)\):
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
Coefficient-wise this means
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x),$$
where missing coefficients are interpreted as \(0\). This shift-and-subtract rule is exactly what the implementations apply.
Because \(\mathcal{A}_n(x)\) is a geometric sum, there is also a closed form:
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
Hence
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}.$$
This rational-looking form is only an algebraic identity. The actual computation never divides modulo \(10^9\); it works entirely with finite coefficient arrays, additions, subtractions, and convolutions.
Define the running products by
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1).$$
The cumulative series whose degree-\(D\) coefficient is required is
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x).$$
So the answer is
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9.}$$
Equivalently,
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
Each stage factor is divisible by \(x\), so \(\mathcal{R}_n(x)\) is divisible by \(x^n\). Therefore no term with \(n>D\) can contribute to \([x^D]\), which explains why the loop stops exactly at \(D=1000\).
If
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j,$$
then the next product satisfies
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D).$$
This is the Cauchy product for series, truncated after degree \(D\). It is the dominant operation in the program: for each stage, every relevant coefficient of the current product is combined with every relevant coefficient of the new factor, and the result is reduced modulo \(10^9\).
At \(n=1\),
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
So
$$\mathcal{R}_1(x)=x-x^2.$$
At \(n=2\),
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
and therefore
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
Multiplying the first two stage factors gives
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6.$$
So after two stages the cumulative series begins
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots.$$
If we were only interested in degree \(4\), every later computation would keep only the truncation \(1+x+x^2-6x^3+7x^4\). The full problem performs this same process up to degree \(1000\).
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they precompute the needed binomial coefficients modulo \(10^9\) using Pascal's identity, keeping only columns \(0\) through \(D\). Next, stage \(n\) adds the coefficients of \((1-x)^{2(n-1)}\) into the running even-power sum, then applies the coefficient shift corresponding to multiplication by \(x(1-x)\) to obtain the new stage factor.
After that, the implementation multiplies the current product by the new stage factor using a truncated convolution, stores only degrees \(0\) through \(D\), and adds the new product into the running answer series. The C++ version uses a wider temporary accumulator before taking the modulus; the mathematical recurrence itself is the same across all three languages.
Let \(D=1000\). Building the truncated binomial table up to row \(2D\) and column \(D\) costs \(O(D^2)\) time and \(O(D^2)\) memory. Updating the stage factor itself is only \(O(D)\) per stage, but the truncated convolution for the running product is \(O(D^2)\) per stage. Repeating that over \(D\) stages gives total time \(O(D^3)\). The memory usage is dominated by the binomial table, so the overall space complexity is \(O(D^2)\).
Die Implementierungen zeigen, dass sich Problem 648 als Koeffizientenextraktion aus abgeschnittenen formalen Potenzreihen formulieren lasst. Mit \(D=1000\) und Modul \(M=10^9\) soll der Koeffizient von \(x^D\) in einer kumulierten Reihe von Stufenpolynomen berechnet werden. Da nur Terme bis Grad \(D\) das Endergebnis beeinflussen konnen, wird jedes Polynom nach \(x^{1000}\) abgeschnitten.
Schreibe \([x^k]F(x)\) fur den Koeffizienten von \(x^k\) in einer Reihe \(F(x)\). Die gesamte Rechnung ist um ein Polynom pro Stufe und um das laufende Produkt dieser Stufenfaktoren organisiert.
In Stufe \(n\) akkumuliert die Implementierung die Koeffizienten der endlichen Summe
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
Mit dem binomischen Lehrsatz liefert jeder Summand
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}.$$
Damit ist der Koeffizient von \(x^k\) in \(\mathcal{A}_n(x)\)
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}.$$
Genau deshalb baut der Code zuerst ein abgeschnittenes Pascalsches Dreieck bis Zeile \(2D\) auf: Jede Stufe braucht nur Binomialkoeffizienten aus den geraden Exponenten \(0,2,4,\dots,2D-2\), und nur Grade \(k\le D\) sind relevant.
Das nachste Polynom entsteht durch Multiplikation von \(\mathcal{A}_n(x)\) mit \(x(1-x)\):
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
Auf Koeffizientenebene bedeutet das
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x),$$
wobei fehlende Koeffizienten als \(0\) gelesen werden. Genau diese Verschiebe-und-Subtrahiere-Regel wird in den Implementierungen verwendet.
Weil \(\mathcal{A}_n(x)\) eine geometrische Summe ist, gibt es auch eine geschlossene Form:
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
Also
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}.$$
Diese rational wirkende Form ist nur eine algebraische Identitat. Tatsachlich wird niemals modulo \(10^9\) dividiert; die Rechnung verwendet ausschliesslich endliche Koeffizientenfelder, Additionen, Subtraktionen und Faltungen.
Definiere die laufenden Produkte durch
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1).$$
Die kumulierte Reihe, deren Koeffizient vom Grad \(D\) gesucht ist, lautet
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x).$$
Damit ist die gesuchte Grosse
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9.}$$
Aquivalent dazu gilt
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
Jeder Stufenfaktor ist durch \(x\) teilbar, also ist \(\mathcal{R}_n(x)\) durch \(x^n\) teilbar. Deshalb kann kein Term mit \(n>D\) zu \([x^D]\) beitragen; genau deswegen endet die Schleife bei \(D=1000\).
Falls
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j,$$
dann erfullt das nachste Produkt
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D).$$
Das ist das Cauchy-Produkt von Reihen, abgeschnitten nach Grad \(D\). Diese Operation dominiert die Laufzeit des Programms: In jeder Stufe wird jeder relevante Koeffizient des aktuellen Produkts mit jedem relevanten Koeffizienten des neuen Faktors kombiniert und danach modulo \(10^9\) reduziert.
Fur \(n=1\) gilt
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
Also
$$\mathcal{R}_1(x)=x-x^2.$$
Fur \(n=2\) ist
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
und damit
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
Das Produkt der ersten beiden Stufenfaktoren ist
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6.$$
Nach zwei Stufen beginnt die kumulierte Reihe also mit
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots.$$
Wenn nur Grad \(4\) interessiert, wurden alle spateren Rechnungen auf die Abschneidung \(1+x+x^2-6x^3+7x^4\) begrenzt. Das eigentliche Problem fuhrt denselben Prozess bis Grad \(1000\) aus.
Die Implementierungen in C++, Python und Java folgen derselben mathematischen Pipeline. Zuerst werden die benotigten Binomialkoeffizienten modulo \(10^9\) mit Pascals Identitat vorab berechnet, wobei nur die Spalten \(0\) bis \(D\) gespeichert werden. Danach addiert Stufe \(n\) die Koeffizienten von \((1-x)^{2(n-1)}\) zur laufenden Summe der geraden Potenzen und erzeugt anschliessend durch die zur Multiplikation mit \(x(1-x)\) gehorige Koeffizientenverschiebung den neuen Stufenfaktor.
Im Anschluss multipliziert die Implementierung das aktuelle Produkt per abgeschnittener Faltung mit dem neuen Stufenfaktor, speichert nur die Grade \(0\) bis \(D\) und addiert das neue Produkt in die laufende Antwortreihe. Die C++-Version verwendet vor der Modulo-Reduktion einen breiteren temporaren Akkumulator; die mathematische Rekurrenz ist jedoch in allen drei Sprachen dieselbe.
Sei \(D=1000\). Das Erzeugen der abgeschnittenen Binomialtabelle bis Zeile \(2D\) und Spalte \(D\) kostet \(O(D^2)\) Zeit und \(O(D^2)\) Speicher. Das Aktualisieren des Stufenfaktors selbst braucht nur \(O(D)\) pro Stufe, aber die abgeschnittene Faltung fur das laufende Produkt kostet \(O(D^2)\) pro Stufe. Uber \(D\) Stufen ergibt das insgesamt \(O(D^3)\) Laufzeit. Der Speicher wird von der Binomialtabelle dominiert, also insgesamt \(O(D^2)\).
Implementasyonlar, Problem 648'in kesilmis formel kuvvet serilerinde katsayi cekme problemine donusturulebildigini gosteriyor. \(D=1000\) ve mod \(M=10^9\) icin amac, asamali polinomlardan olusan kume serisinin \(x^D\) katsayisini hesaplamaktir. Sonucu yalnizca derece \(D\)'ye kadar olan terimler etkiledigi icin her polinom \(x^{1000}\) sonrasinda kesilir.
\([x^k]F(x)\) gosterimi, \(F(x)\) serisindeki \(x^k\) katsayisini ifade etsin. Hesaplama, her asama icin bir polinom ve bu asama carpanlarinin kosan carpimi etrafinda duzenlenir.
\(n\). asamada implementasyon su sonlu toplamin katsayilarini biriktirir:
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
Binom acilimina gore her terim
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}$$
katkisini verir. Dolayisiyla \(\mathcal{A}_n(x)\) icindeki \(x^k\) katsayisi
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}$$
olur. Kodun once \(2D\) satira kadar kesilmis bir Pascal ucgeni kurmasinin nedeni budur: her asama yalnizca \(0,2,4,\dots,2D-2\) cift uslerinden gelen binom katsayilarina ihtiyaç duyar ve sadece \(k\le D\) dereceleri anlamlidir.
Siradaki polinom, \(\mathcal{A}_n(x)\)'in \(x(1-x)\) ile carpilmasiyla elde edilir:
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
Katsayi seviyesinde bu
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x)$$
demektir; eksik indeksler \(0\) kabul edilir. Implementasyonlarin uyguladigi kaydir-ve-cikar kuralinin matematiksel anlami tam olarak budur.
\(\mathcal{A}_n(x)\) geometrik toplama esit oldugu icin kapali bicimi de vardir:
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
Bundan
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}$$
gelir. Bu kesirli gorunum sadece cebirsel bir ozettir. Gercek hesaplama mod \(10^9\) altinda hic bolme yapmaz; sadece sonlu katsayi dizileri, toplama, cikarma ve konvolusyon kullanir.
Kosan carpimlari
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1)$$
seklinde tanimlayalim. Derece \(D\) katsayisi aranan kume seri ise
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x)$$
olur. Dolayisiyla aranan nicelik
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9}$$
ifadesidir. Esdeger bicimde
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
Her asama carpani \(x\) ile bolunebildigi icin \(\mathcal{R}_n(x)\), \(x^n\) ile bolunur. Bu nedenle \(n>D\) olan hicbir terim \([x^D]\) katsayisina katkida bulunamaz; dongunun tam olarak \(D=1000\)'de bitmesinin sebebi budur.
Eger
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j$$
ise sonraki carpim
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D)$$
kosulunu saglar. Bu, seri carpimi icin Cauchy kuralidir ve derece \(D\)'den sonra kesilir. Programdaki baskin maliyet de budur: her asamada mevcut carpimin ilgili her katsayisi yeni carpanin ilgili her katsayisi ile eslestirilir ve sonuc mod \(10^9\) altinda indirgenir.
\(n=1\) icin
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
Dolayisiyla
$$\mathcal{R}_1(x)=x-x^2.$$
\(n=2\) icin
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
ve dolayisiyla
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
Ilk iki asama carpaninin carpimi
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6$$
olur. O halde iki asamadan sonra kume seri
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots$$
seklinde baslar. Yalnizca derece \(4\) ilgilendiriyorsa daha sonraki tum hesaplar \(1+x+x^2-6x^3+7x^4\) kesimiyle devam eder. Asil problem ayni sureci derece \(1000\)'e kadar uygular.
C++, Python ve Java implementasyonlari ayni matematiksel hattı izler. Once Pascal ozdesligi kullanilarak gerekli binom katsayilari mod \(10^9\) altinda onceden hesaplanir ve yalnizca \(0\) ile \(D\) arasindaki sutunlar tutulur. Sonra \(n\). asama, \((1-x)^{2(n-1)}\) katsayilarini kosan cift-kuvvet toplamına ekler ve \(x(1-x)\) ile carpma islemine denk gelen katsayi kaydirmasini uygulayarak yeni asama carpanini uretir.
Bunun ardindan implementasyon mevcut carpimi yeni asama carpanı ile kesilmis konvolusyonla carpar, sadece \(0\) ile \(D\) arasindaki dereceleri saklar ve yeni carpimi kosan cevap serisine ekler. C++ surumu mod alma oncesinde daha genis gecici bir toplayici kullanir; fakat matematiksel tekrar iliskisi uc dilde de aynidir.
\(D=1000\) olsun. \(2D\) satira ve \(D\) sutuna kadar kesilmis binom tablosunu kurmak \(O(D^2)\) zaman ve \(O(D^2)\) bellek gerektirir. Asama carpaninin guncellenmesi asama basina yalnizca \(O(D)\) iken, kosan carpim icin gereken kesilmis konvolusyon asama basina \(O(D^2)\) maliyetlidir. Bu islem \(D\) asama boyunca tekrarlandigi icin toplam zaman \(O(D^3)\) olur. Bellek kullanimini binom tablosu domine ettiginden toplam alan karmasikligi \(O(D^2)\)'dir.
Las implementaciones muestran que el Problema 648 puede reformularse como una extraccion de coeficientes en series formales truncadas. Con \(D=1000\) y modulo \(M=10^9\), el objetivo es calcular el coeficiente de \(x^D\) en una serie acumulada construida a partir de polinomios por etapas. Como solo los terminos hasta grado \(D\) pueden afectar la respuesta final, cada polinomio se recorta despues de \(x^{1000}\).
Escribamos \([x^k]F(x)\) para el coeficiente de \(x^k\) en una serie \(F(x)\). Todo el calculo se organiza alrededor de un polinomio por etapa y del producto acumulado de esos factores.
En la etapa \(n\), la implementacion acumula los coeficientes de la suma finita
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
Por el teorema binomial, cada sumando aporta
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}.$$
Por tanto, el coeficiente de \(x^k\) en \(\mathcal{A}_n(x)\) es
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}.$$
Esa es la razon por la que el codigo prepara primero un triangulo de Pascal truncado hasta la fila \(2D\): cada etapa solo necesita coeficientes binomiales procedentes de exponentes pares \(0,2,4,\dots,2D-2\), y solo importan los grados \(k\le D\).
El siguiente polinomio se obtiene multiplicando \(\mathcal{A}_n(x)\) por \(x(1-x)\):
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
A nivel de coeficientes, esto significa
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x),$$
donde los coeficientes inexistentes se interpretan como \(0\). Esa regla de desplazar y restar es exactamente la que aplican las implementaciones.
Como \(\mathcal{A}_n(x)\) es una suma geometrica, tambien existe una forma cerrada:
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
De ahi se obtiene
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}.$$
Esta expresion con denominador es solo una identidad algebraica. El calculo real nunca divide modulo \(10^9\); trabaja unicamente con arreglos finitos de coeficientes, sumas, restas y convoluciones.
Definimos los productos acumulados por
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1).$$
La serie acumulada cuyo coeficiente de grado \(D\) se necesita es
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x).$$
Asi, la respuesta es
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9.}$$
De forma equivalente,
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
Cada factor de etapa es divisible por \(x\), por lo que \(\mathcal{R}_n(x)\) es divisible por \(x^n\). En consecuencia, ningun termino con \(n>D\) puede contribuir a \([x^D]\), lo que explica por que el bucle termina exactamente en \(D=1000\).
Si
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j,$$
entonces el producto siguiente satisface
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D).$$
Este es el producto de Cauchy para series, truncado despues del grado \(D\). Es la operacion dominante del programa: en cada etapa, cada coeficiente relevante del producto actual se combina con cada coeficiente relevante del nuevo factor y el resultado se reduce modulo \(10^9\).
Para \(n=1\),
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
Por tanto,
$$\mathcal{R}_1(x)=x-x^2.$$
Para \(n=2\),
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
y entonces
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
Multiplicando los dos primeros factores se obtiene
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6.$$
Asi, despues de dos etapas, la serie acumulada comienza como
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots.$$
Si solo nos interesara el grado \(4\), todo lo posterior se recortaria a \(1+x+x^2-6x^3+7x^4\). El problema completo repite exactamente este proceso hasta el grado \(1000\).
Las implementaciones en C++, Python y Java siguen la misma tuberia matematica. Primero precalculan los coeficientes binomiales necesarios modulo \(10^9\) mediante la identidad de Pascal, guardando solo las columnas \(0\) a \(D\). Luego la etapa \(n\) agrega los coeficientes de \((1-x)^{2(n-1)}\) a la suma acumulada de potencias pares y aplica el desplazamiento de coeficientes correspondiente a multiplicar por \(x(1-x)\) para producir el nuevo factor de etapa.
Despues, la implementacion multiplica el producto actual por ese nuevo factor mediante una convolucion truncada, conserva solo los grados \(0\) a \(D\) y suma el nuevo producto a la serie respuesta acumulada. La version en C++ usa un acumulador temporal de mayor anchura antes de reducir modulo; la recurrencia matematica es la misma en los tres lenguajes.
Sea \(D=1000\). Construir la tabla binomial truncada hasta la fila \(2D\) y la columna \(D\) cuesta \(O(D^2)\) tiempo y \(O(D^2)\) memoria. Actualizar el factor de etapa solo requiere \(O(D)\) por etapa, pero la convolucion truncada del producto acumulado cuesta \(O(D^2)\) por etapa. Repetido durante \(D\) etapas, el tiempo total es \(O(D^3)\). La memoria esta dominada por la tabla binomial, por lo que el espacio total es \(O(D^2)\).
实现代码表明，Problem 648 可以改写成一个截断形式幂级数的系数提取问题。取 \(D=1000\)、模数 \(M=10^9\)，目标是求某个按阶段构造出来的累计级数中 \(x^D\) 的系数。由于最终答案只会受到次数不超过 \(D\) 的项影响，所以所有多项式都只保留到 \(x^{1000}\) 为止。
记 \([x^k]F(x)\) 为级数 \(F(x)\) 中 \(x^k\) 的系数。整个计算围绕着“每一阶段一个多项式因子”以及“这些因子的连乘结果”来展开。
在第 \(n\) 个阶段，程序先累加下面这个有限和的系数：
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
根据二项式定理，每一项都有
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}.$$
因此，\(\mathcal{A}_n(x)\) 中 \(x^k\) 的系数就是
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}.$$
这也解释了为什么实现要先构造一个截断的 Pascal 三角形，一直做到第 \(2D\) 行：每个阶段只会用到来自偶数指数 \(0,2,4,\dots,2D-2\) 的二项式系数，而且最终真正有意义的只有 \(k\le D\) 这些次数。
接下来要构造的多项式，是把 \(\mathcal{A}_n(x)\) 乘上 \(x(1-x)\)：
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
如果只看系数，这意味着
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x),$$
其中不存在的系数按 \(0\) 处理。也就是说，代码中的核心操作其实就是“整体右移一位，再减去整体右移两位”的差分规则。
由于 \(\mathcal{A}_n(x)\) 本身是等比和，它还有一个闭式：
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
所以
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}.$$
这里出现分母只是代数上的简写，并不是程序真的去做模 \(10^9\) 下的除法。实际实现始终只操作有限长度的系数数组，使用的只是加法、减法和卷积。
定义连乘多项式
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1).$$
那么我们真正关心的累计级数就是
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x).$$
最终答案因此可以写成
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9.}$$
把每个阶段的定义直接代进去，也可以写成
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
每个阶段因子都含有一个 \(x\)，所以 \(\mathcal{R}_n(x)\) 一定被 \(x^n\) 整除。这一点非常重要，因为它立刻说明：当 \(n>D\) 时，\(\mathcal{R}_n(x)\) 不可能对 \([x^D]\) 有贡献。因此程序只需要做到 \(n=D=1000\)，不用继续向后展开。
如果把
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j,$$
那么下一个乘积的系数满足
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D).$$
这就是幂级数乘法的 Cauchy 乘积公式，只不过程序在每一步都把次数截断到 \(D\)。从算法角度看，这一步是最耗时的部分：每个阶段都要把当前乘积中所有可能有用的系数，与新阶段因子中所有可能有用的系数配对相乘，然后再对 \(10^9\) 取模。
先看 \(n=1\)。这时
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
因此
$$\mathcal{R}_1(x)=x-x^2.$$
再看 \(n=2\)。有
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
于是
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
把前两个阶段因子相乘，就得到
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6.$$
因此，做到第二阶段为止，累计级数的开头部分是
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots.$$
如果我们只关心 \(x^4\) 的系数，那么后面的所有运算都只需要保留截断结果 \(1+x+x^2-6x^3+7x^4\)。真实题目做的事情完全一样，只是把这个过程持续到次数 \(1000\)。
C++、Python 和 Java 实现遵循同一条数学流水线。第一步是利用 Pascal 恒等式预计算所需的二项式系数，并且始终在模 \(10^9\) 下保存到第 \(D\) 列为止。第二步是在第 \(n\) 个阶段把 \((1-x)^{2(n-1)}\) 的系数加到“偶次幂累计和”里，再通过与乘以 \(x(1-x)\) 对应的系数平移，生成当前阶段因子。
随后，实现把当前连乘结果与新阶段因子做一次截断卷积，只保留次数 \(0\) 到 \(D\) 的部分，并把新的连乘结果加到累计答案级数中。C++ 版本在取模之前使用了更宽的临时累加器；但三种语言遵循的数学递推完全相同。
设 \(D=1000\)。构造到第 \(2D\) 行、第 \(D\) 列的截断二项式表，需要 \(O(D^2)\) 时间和 \(O(D^2)\) 空间。阶段因子的更新本身每次只要 \(O(D)\)，但累计乘积的截断卷积每一阶段都需要 \(O(D^2)\)。这样的阶段一共做 \(D\) 次，因此总时间复杂度是 \(O(D^3)\)。空间复杂度则由二项式表主导，所以总计为 \(O(D^2)\)。
Реализации показывают, что Problem 648 можно переписать как задачу извлечения коэффициента из усеченных формальных степенных рядов. При \(D=1000\) и модуле \(M=10^9\) нужно найти коэффициент при \(x^D\) в накопленном ряде, составленном из поэтапных многочленов. Поскольку на окончательный ответ влияют только члены степени не выше \(D\), каждый многочлен обрезается после \(x^{1000}\).
Обозначим через \([x^k]F(x)\) коэффициент при \(x^k\) в ряде \(F(x)\). Все вычисление организовано вокруг одного многочлена на каждом шаге и накопленного произведения этих шаговых множителей.
На шаге \(n\) программа накапливает коэффициенты конечной суммы
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
По биному Ньютона каждый слагаемый дает вклад
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}.$$
Следовательно, коэффициент при \(x^k\) в \(\mathcal{A}_n(x)\) равен
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}.$$
Именно поэтому код сначала строит усеченный треугольник Паскаля до строки \(2D\): на каждом шаге нужны только биномиальные коэффициенты, приходящие из четных показателей \(0,2,4,\dots,2D-2\), и только степени \(k\le D\) вообще способны повлиять на ответ.
Следующий многочлен получается умножением \(\mathcal{A}_n(x)\) на \(x(1-x)\):
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
На уровне коэффициентов это означает
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x),$$
где отсутствующие коэффициенты считаются равными нулю. Именно такое смещение и вычитание реализуют программы.
Поскольку \(\mathcal{A}_n(x)\) является геометрической суммой, у нее есть и замкнутая форма:
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
Отсюда
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}.$$
Вид с дробью нужен только как алгебраическое сокращение записи. На практике вычисление никогда не делит по модулю \(10^9\); используются только конечные массивы коэффициентов, сложение, вычитание и свертка.
Определим накопленные произведения:
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1).$$
Тогда интересующий нас накопленный ряд имеет вид
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x).$$
Следовательно, ответ равен
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9.}$$
Эквивалентно можно записать
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
Каждый шаговый множитель делится на \(x\), значит \(\mathcal{R}_n(x)\) делится на \(x^n\). Поэтому ни один член с \(n>D\) не может внести вклад в \([x^D]\). Именно этим объясняется, почему внешний цикл заканчивается ровно на \(D=1000\).
Если
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j,$$
то следующий произведенный многочлен удовлетворяет формуле
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D).$$
Это и есть произведение Коши для степенных рядов, обрезанное после степени \(D\). Именно эта операция определяет основную стоимость алгоритма: на каждом шаге каждый полезный коэффициент текущего произведения комбинируется с каждым полезным коэффициентом нового множителя, после чего результат берется по модулю \(10^9\).
При \(n=1\)
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
Поэтому
$$\mathcal{R}_1(x)=x-x^2.$$
При \(n=2\)
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
и тогда
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
Перемножая первые два множителя, получаем
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6.$$
Значит, после двух шагов накопленный ряд начинается так:
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots.$$
Если бы нас интересовала только степень \(4\), все последующие вычисления можно было бы вести с усечением \(1+x+x^2-6x^3+7x^4\). Полная задача делает то же самое, только до степени \(1000\).
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они предварительно вычисляют нужные биномиальные коэффициенты по модулю \(10^9\) с помощью тождества Паскаля, сохраняя только столбцы от \(0\) до \(D\). Затем на шаге \(n\) коэффициенты \((1-x)^{2(n-1)}\) добавляются к накопленной сумме четных степеней, а потом применяется сдвиг коэффициентов, соответствующий умножению на \(x(1-x)\), и получается новый шаговый множитель.
После этого реализация умножает текущее произведение на новый множитель с помощью усеченной свертки, оставляет только степени от \(0\) до \(D\) и добавляет новое произведение к накопленному ответному ряду. В версии на C++ перед взятием модуля используется более широкий временный аккумулятор, но сама математическая рекурсия во всех трех языках одинакова.
Пусть \(D=1000\). Построение усеченной биномиальной таблицы до строки \(2D\) и столбца \(D\) требует \(O(D^2)\) времени и \(O(D^2)\) памяти. Обновление шагового множителя занимает лишь \(O(D)\) на шаг, но усеченная свертка для накопленного произведения стоит \(O(D^2)\) на каждый шаг. Поскольку таких шагов \(D\), суммарное время равно \(O(D^3)\). Память определяется биномиальной таблицей, поэтому общая пространственная сложность составляет \(O(D^2)\).
توضح التنفيذات ان Problem 648 يمكن اعادة صياغته بوصفه مسالة استخراج معامل من سلاسل قوى شكلية مقتطعة. عند \(D=1000\) وباقي القسمة \(M=10^9\)، يكون الهدف هو حساب معامل \(x^D\) في سلسلة تراكمية مبنية من كثيرات حدود مرحلية. وبما ان النتيجة النهائية لا تتاثر الا بالحدود ذات الدرجة التي لا تتجاوز \(D\)، فان كل كثير حدود يقتطع بعد \(x^{1000}\).
لنرمز بـ \([x^k]F(x)\) الى معامل \(x^k\) في السلسلة \(F(x)\). ينظم الحساب كله حول كثير حدود واحد في كل مرحلة، وحول حاصل الضرب التراكمي لهذه العوامل المرحلية.
في المرحلة \(n\)، تجمع التنفيذات معاملات المجموع المنتهي
$$\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(1-x)^{2j}.$$
وبحسب نظرية ذات الحدين، يساهم كل حد بالقيمة
$$[x^k](1-x)^{2j}=(-1)^k\binom{2j}{k}.$$
ومن ثم يكون معامل \(x^k\) في \(\mathcal{A}_n(x)\) هو
$$[x^k]\mathcal{A}_n(x)=\sum_{j=0}^{n-1}(-1)^k\binom{2j}{k}.$$
ولهذا السبب يبني البرنامج اولا مثلث Pascal مقتطعا حتى الصف \(2D\): فكل مرحلة تحتاج فقط الى معاملات ثنائية مشتقة من الاسس الزوجية \(0,2,4,\dots,2D-2\)، كما ان الدرجات الوحيدة المهمة حقا هي \(k\le D\).
كثير الحدود التالي ينتج من ضرب \(\mathcal{A}_n(x)\) في \(x(1-x)\):
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x).$$
وعلى مستوى المعاملات يعني ذلك
$$[x^k]\mathcal{B}_n(x)=[x^{k-1}]\mathcal{A}_n(x)-[x^{k-2}]\mathcal{A}_n(x),$$
مع اعتبار المعاملات غير الموجودة مساوية للصفر. هذه بالضبط هي قاعدة الازاحة ثم الطرح التي تطبقها التنفيذات.
وبما ان \(\mathcal{A}_n(x)\) مجموع هندسي، فله ايضا صيغة مغلقة:
$$\mathcal{A}_n(x)=\frac{1-(1-x)^{2n}}{1-(1-x)^2}=\frac{1-(1-x)^{2n}}{2x-x^2}.$$
ومن ثم
$$\mathcal{B}_n(x)=x(1-x)\mathcal{A}_n(x)=\frac{(1-x)\bigl(1-(1-x)^{2n}\bigr)}{2-x}.$$
هذا الشكل الكسري مجرد هوية جبرية مضغوطة، وليس شيئا تنفذه الشيفرة حرفيا. فالحساب الفعلي لا يجري اي قسمة بترديد \(10^9\)، بل يعمل بالكامل على مصفوفات معاملات منتهية مع الجمع والطرح والالتفاف.
نعرف حاصل الضرب التراكمي بالصيغة
$$\mathcal{R}_0(x)=1,\qquad \mathcal{R}_n(x)=\mathcal{R}_{n-1}(x)\mathcal{B}_n(x)\quad (n\ge 1).$$
وعندئذ تكون السلسلة التراكمية المطلوبة هي
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\mathcal{R}_n(x).$$
لذلك يمكن كتابة الجواب على الصورة
$$\boxed{[x^D]\mathcal{T}_D(x)\bmod 10^9.}$$
وبشكل مكافئ،
$$\mathcal{T}_D(x)=1+\sum_{n=1}^{D}\prod_{i=1}^{n}\left(x(1-x)\sum_{j=0}^{i-1}(1-x)^{2j}\right).$$
كل عامل مرحلي قابل للقسمة على \(x\)، ولذلك تكون \(\mathcal{R}_n(x)\) قابلة للقسمة على \(x^n\). وهذا يبين مباشرة ان اي حد له \(n>D\) لا يمكنه المساهمة في \([x^D]\)، ولهذا تتوقف الحلقة عند \(D=1000\) بالضبط.
اذا كتبنا
$$\mathcal{R}_{n-1}(x)=\sum_{i=0}^{D} r_i x^i,\qquad \mathcal{B}_n(x)=\sum_{j=0}^{D} b_j x^j,$$
فان حاصل الضرب التالي يحقق
$$[x^k]\mathcal{R}_n(x)=\sum_{i=0}^{k} r_i\,b_{k-i}\qquad (0\le k\le D).$$
هذه هي قاعدة حاصل Cauchy لسلاسل القوى، بعد اقتطاع كل ما يتجاوز الدرجة \(D\). وهي ايضا العملية المهيمنة زمنيا داخل البرنامج: ففي كل مرحلة يقرن كل معامل مفيد من حاصل الضرب الحالي مع كل معامل مفيد من العامل الجديد، ثم يختزل الناتج بترديد \(10^9\).
عند \(n=1\) نحصل على
$$\mathcal{A}_1(x)=1,\qquad \mathcal{B}_1(x)=x(1-x)=x-x^2.$$
ومن ثم
$$\mathcal{R}_1(x)=x-x^2.$$
وعند \(n=2\) يكون
$$\mathcal{A}_2(x)=1+(1-x)^2=2-2x+x^2,$$
وبالتالي
$$\mathcal{B}_2(x)=x(1-x)(2-2x+x^2)=2x-4x^2+3x^3-x^4.$$
وبضرب عاملي المرحلتين الاوليين نحصل على
$$\mathcal{R}_2(x)=(x-x^2)(2x-4x^2+3x^3-x^4)=2x^2-6x^3+7x^4-4x^5+x^6.$$
اذن تبدأ السلسلة التراكمية بعد مرحلتين على النحو
$$1+\mathcal{R}_1(x)+\mathcal{R}_2(x)=1+x+x^2-6x^3+7x^4-4x^5+x^6+\cdots.$$
ولو كان المطلوب فقط حتى الدرجة \(4\)، لاحتفظنا بعد ذلك بالتقتيع \(1+x+x^2-6x^3+7x^4\) لا غير. المسالة الكاملة تكرر الفكرة نفسها حتى الدرجة \(1000\).
تتبع تنفيذات C++ وPython وJava المسار الرياضي نفسه. اولا يجري حساب معاملات ذات الحدين المطلوبة مسبقا باستخدام هوية Pascal مع الاختزال بترديد \(10^9\)، مع الاحتفاظ فقط بالاعمدة من \(0\) الى \(D\). ثم تضيف المرحلة \(n\) معاملات \((1-x)^{2(n-1)}\) الى مجموع القوى الزوجية المتراكم، وبعد ذلك تطبق ازاحة المعاملات الموافقة للضرب في \(x(1-x)\) من اجل توليد عامل المرحلة الجديد.
بعد هذا تضرب الشيفرة حاصل الضرب الحالي في عامل المرحلة الجديد بواسطة التفاف مقتطع، وتحفظ فقط الدرجات من \(0\) الى \(D\)، ثم تضيف الناتج الجديد الى السلسلة الجوابية المتراكمة. تستخدم نسخة C++ مجمعا وسيطا اعرض قبل اخذ الباقي، لكن العلاقة الرياضية نفسها ثابتة في اللغات الثلاث.
لتكن \(D=1000\). ان بناء جدول معاملات ذات الحدين المقتطع حتى الصف \(2D\) والعمود \(D\) يكلف \(O(D^2)\) زمنا و\(O(D^2)\) ذاكرة. تحديث عامل المرحلة نفسه يحتاج فقط الى \(O(D)\) في كل مرحلة، لكن التفاف حاصل الضرب المتراكم يكلف \(O(D^2)\) لكل مرحلة. ومع تكرار ذلك عبر \(D\) مرحلة يكون الزمن الكلي \(O(D^3)\). اما الذاكرة فتسيطر عليها جدول المعاملات الثنائية، ولذلك يكون التعقيد المكاني الكلي \(O(D^2)\).