For each pair \((w,h)\), we must count castles of width \(w\) and exact height \(h\) that satisfy the parity condition built into the problem statement, with every result taken modulo \(10^9+7\). The final answer is the sum of three such evaluations. Direct enumeration is hopeless, so the implementation turns the construction into coefficient extraction from rational generating functions.
The implementation works with cumulative counts up to a height bound and only at the end converts them into the exact-height quantity required by the problem.
Let \(x\) mark the width. The castle decomposition used by the implementation can be summarized by a two-state transfer, and there are two versions of that transfer:
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
The first matrix counts every admissible object positively. The second matrix attaches a sign so that averaging the two channels later will keep only the even-parity contribution required by the problem.
Starting from the base vector
$$v_0=\binom{0}{1},$$
the effect of allowing height at most \(h\) is obtained from
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}.$$
The corresponding cumulative generating functions are
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}.$$
If we write
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x),$$
then \(S_h(w)\) and \(D_h(w)\) are the two cumulative counts for width \(w\) and height at most \(h\).
The signed channel is designed so that odd-parity objects cancel and even-parity objects survive. Therefore the cumulative even count is
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}.$$
But the problem asks for exact height \(h\), not height at most \(h\). So we subtract the previous cumulative level:
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
This is the quantity reported by the implementation for each query.
Suppose we need one coefficient of a rational function \(P(x)/Q(x)\), namely \([x^k]P(x)/Q(x)\). For very large \(w\), the implementation avoids expanding the whole series. It defines
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x).$$
The polynomial \(V(x)\) is even, so only even powers remain in the denominator. If \(k=2m\), we keep the even coefficients of \(U\); if \(k=2m+1\), we keep the odd coefficients. After that selection, the target coefficient becomes a coefficient of index \(m\) in a new rational function. Repeating this halves the index again and again until only a constant term remains. This is the Bostan-Mori step used when width is enormous and height is relatively small.
When \(w\) is moderate, only coefficients up to degree \(w\) matter. In that regime every polynomial multiplication is truncated modulo \(x^{w+1}\), so the matrix power never grows beyond degree \(w\). Once \(P(x)\) and \(Q(x)\) are known up to that degree, the implementation computes the inverse series of \(Q(x)\):
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
Because the constant term of \(Q(x)\) is nonzero, the coefficients of \(I(x)\) are determined recursively by
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}.$$
Then
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr),$$
so the desired count is obtained without ever expanding beyond the needed degree.
The implementation validates itself on the checkpoint \(F(4,2)=10\). For height \(2\), the positive channel gives
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots.$$
The signed channel gives
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots.$$
Therefore
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10.$$
For height \(1\), the two channels are
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x},$$
so their average contributes \(0\) at every width. Hence
$$F(4,2)=E_2(4)-E_1(4)=10-0=10,$$
exactly as required.
After defining \(F(w,h)\) as above, the requested answer is
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}.$$
The entire job is therefore reduced to evaluating the same exact-height routine three times.
The C++, Python, and Java implementations all follow the same mathematical pipeline. For a given pair \((w,h)\), they compute the cumulative count for height at most \(h\) in the positive channel and in the signed channel, repeat the same computation for height at most \(h-1\), average the two channel results with the modular inverse of \(2\), and subtract the previous level to isolate exact height.
Inside one channel, the implementation first raises the relevant \(2\times 2\) polynomial matrix to the required height by binary exponentiation. It then extracts the coefficient of \(x^w\) from the resulting rational function. When width is huge, it uses repeated Bostan-Mori halving; when width is smaller, it truncates every polynomial to degree \(w\), computes a formal inverse for the denominator, and reads the target coefficient directly from the truncated product.
The Python implementation is only a thin launcher around the same arithmetic, while the C++ and Java implementations carry out the polynomial and matrix operations directly. The mathematical result is identical in all three languages.
Let \(M(n)\) denote the cost of multiplying degree-\(n\) polynomials. In these implementations the underlying polynomial multiplication is quadratic, so \(M(n)=O(n^2)\).
In the Bostan-Mori branch, the matrix power for height \(h\) produces polynomials of degree \(O(h)\). The cost of building the rational function is therefore \(O(h^2\log h)\), and the repeated coefficient-halving stage adds \(O(h^2\log w)\). Memory usage is \(O(h)\).
In the truncated branch, all polynomial degrees are clipped at \(w\). Binary exponentiation of the matrix then costs \(O(w^2\log h)\), the inverse-series recursion costs \(O(w^2)\), and memory usage is \(O(w)\). The implementation switches between the two branches because the three required queries live in very different parameter regimes.
Für jedes Paar \((w,h)\) müssen wir Burgen der Breite \(w\) und exakten Höhe \(h\) zählen, die die in der Aufgabenstellung vorgegebene Paritätsbedingung erfüllen; gerechnet wird modulo \(10^9+7\). Die endgültige Antwort ist die Summe von drei solchen Auswertungen. Direkte Enumeration ist unmöglich, daher übersetzt die Implementierung die Konstruktion in Koeffizientenextraktion aus rationalen erzeugenden Funktionen.
Die Implementierung arbeitet zunächst mit kumulativen Zählungen bis zu einer Höhenobergrenze und gewinnt erst am Ende die Anzahl für exakt die Höhe \(h\).
Die Breite wird durch \(x\) markiert. Die in der Implementierung verwendete Zerlegung der Burgen lässt sich durch einen Transfer mit zwei Zuständen beschreiben, und davon gibt es zwei Versionen:
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
Die erste Matrix zählt jedes zulässige Objekt positiv. Die zweite versieht Objekte mit einem Vorzeichen, sodass beim späteren Mitteln genau der gerade Paritätsanteil übrig bleibt, den die Aufgabe verlangt.
Ausgehend vom Startvektor
$$v_0=\binom{0}{1}$$
erhält man die Wirkung einer Höhenbeschränkung \(h\) aus
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}.$$
Die zugehörigen kumulativen erzeugenden Funktionen sind
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}.$$
Mit
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x)$$
sind \(S_h(w)\) und \(D_h(w)\) genau die beiden kumulativen Zählungen für Breite \(w\) und Höhe höchstens \(h\).
Der signierte Kanal ist so konstruiert, dass Objekte ungerader Parität sich aufheben und Objekte gerader Parität erhalten bleiben. Deshalb gilt für die kumulative gerade Zählung
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}.$$
Gesucht ist jedoch nicht Höhe höchstens \(h\), sondern genau Höhe \(h\). Daher ziehen wir die vorherige kumulative Stufe ab:
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
Genau diese Größe liefert die Implementierung für jede Anfrage.
Angenommen, wir benötigen aus einer rationalen Funktion \(P(x)/Q(x)\) nur den Koeffizienten \([x^k]P(x)/Q(x)\). Für sehr großes \(w\) expandiert die Implementierung die Reihe nicht vollständig, sondern definiert
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x).$$
Das Polynom \(V(x)\) ist gerade, also bleiben im Nenner nur gerade Potenzen übrig. Ist \(k=2m\), behält man aus \(U\) die geraden Koeffizienten; ist \(k=2m+1\), behält man die ungeraden. Danach wird der Zielkoeffizient zu einem Koeffizienten mit Index \(m\) in einer neuen rationalen Funktion. Wiederholt man das, halbiert sich der Index immer weiter, bis nur noch ein konstanter Term übrig ist. Genau dies ist der Bostan-Mori-Schritt für den Fall riesiger Breite und vergleichsweise kleiner Höhe.
Ist \(w\) moderat, interessieren nur Koeffizienten bis Grad \(w\). Dann wird jede Polynom-Multiplikation modulo \(x^{w+1}\) abgeschnitten, sodass die Matrixpotenz nie über Grad \(w\) hinauswächst. Sobald \(P(x)\) und \(Q(x)\) bis zu diesem Grad bekannt sind, berechnet die Implementierung die inverse Reihe von \(Q(x)\):
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
Weil der konstante Term von \(Q(x)\) ungleich \(0\) ist, werden die Koeffizienten von \(I(x)\) rekursiv durch
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}$$
bestimmt. Danach ist
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr),$$
und der gesuchte Wert wird erhalten, ohne jemals höhere Grade ausrechnen zu müssen.
Die Implementierung validiert sich selbst mit dem Kontrollwert \(F(4,2)=10\). Für Höhe \(2\) liefert der positive Kanal
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots.$$
Der signierte Kanal liefert
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots.$$
Damit gilt
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10.$$
Für Höhe \(1\) erhält man
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x},$$
deren Mittelwert bei jeder Breite \(0\) ist. Also
$$F(4,2)=E_2(4)-E_1(4)=10-0=10,$$
genau wie gefordert.
Nach Definition von \(F(w,h)\) ist die gesuchte Endantwort
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}.$$
Die gesamte Aufgabe reduziert sich also darauf, dieselbe Exakt-Höhen-Routine dreimal auszuwerten.
Die C++-, Python- und Java-Implementierungen folgen alle demselben mathematischen Ablauf. Für ein Paar \((w,h)\) berechnen sie die kumulative Zählung bis Höhe \(h\) im positiven und im signierten Kanal, wiederholen dasselbe für Höhe \(h-1\), mitteln die beiden Kanalwerte mit dem modularen Inversen von \(2\) und subtrahieren die vorherige Stufe, um exakt Höhe \(h\) zu isolieren.
Innerhalb eines Kanals wird zunächst die zugehörige \(2\times 2\)-Polynom-Matrix durch binäre Exponentiation auf die gewünschte Höhe gebracht. Anschließend wird der Koeffizient von \(x^w\) aus der entstehenden rationalen Funktion extrahiert. Bei riesiger Breite geschieht das per wiederholter Bostan-Mori-Halbierung; bei kleinerer Breite werden alle Polynome auf Grad \(w\) abgeschnitten, der Nenner als formale Reihe invertiert und der Zielkoeffizient direkt aus dem abgeschnittenen Produkt gelesen.
Die Python-Implementierung ist nur ein schmaler Starter für dieselbe Arithmetik, während C++ und Java die Polynom- und Matrixrechnungen direkt ausführen. Das mathematische Ergebnis ist in allen drei Sprachen identisch.
Sei \(M(n)\) der Aufwand für die Multiplikation von Polynomen vom Grad \(n\). In diesen Implementierungen ist die zugrunde liegende Polynom-Multiplikation quadratisch, also \(M(n)=O(n^2)\).
Im Bostan-Mori-Zweig erzeugt die Matrixpotenz für Höhe \(h\) Polynome vom Grad \(O(h)\). Das Aufbauen der rationalen Funktion kostet daher \(O(h^2\log h)\), und die wiederholte Koeffizientenhalbierung fügt \(O(h^2\log w)\) hinzu. Der Speicherbedarf beträgt \(O(h)\).
Im abgeschnittenen Zweig werden alle Grade bei \(w\) gekappt. Die binäre Exponentiation der Matrix kostet dann \(O(w^2\log h)\), die Inversenrekursion \(O(w^2)\), und der Speicherbedarf ist \(O(w)\). Zwischen diesen beiden Zweigen wird gewechselt, weil die drei geforderten Anfragen in sehr unterschiedlichen Parameterbereichen liegen.
Her \((w,h)\) çifti için, genişliği \(w\) ve tam yüksekliği \(h\) olan, ayrıca sorudaki parite koşulunu sağlayan kale yapılarını modulo \(10^9+7\) altında saymamız gerekir. Nihai cevap bu tür üç ayrı değerin toplamıdır. Doğrudan üretim mümkün olmadığı için uygulama, yapıyı rasyonel üreteç fonksiyonlardan katsayı çıkarma problemine dönüştürür.
Uygulama önce yüksekliği en fazla \(h\) olan kümülatif sayımları hesaplar; tam yükseklik şartı en son adımda elde edilir.
Genişlik değişkeni olarak \(x\) kullanılır. Uygulamadaki kale ayrışımı iki durumlu bir geçişle özetlenebilir ve bunun iki versiyonu vardır:
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
İlk matris her uygun yapıyı pozitif işaretle sayar. İkinci matris ise işaret ekleyerek daha sonra alınacak ortalamada sorunun istediği çift parite katkısını ayıklar.
Başlangıç vektörü
$$v_0=\binom{0}{1}$$
olduğunda, yüksekliğin en fazla \(h\) olmasına karşılık gelen etki
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}$$
şeklindedir. Buradan gelen kümülatif üreteç fonksiyonlar
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}$$
olur. Eğer
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x)$$
dersek, \(S_h(w)\) ve \(D_h(w)\) genişlik \(w\) için, yüksekliği en fazla \(h\) olan iki kümülatif sayımı verir.
İşaretli kanal, tek pariteli nesneler birbirini götürecek ve çift pariteliler kalacak şekilde kurulmuştur. Bu nedenle çift pariteli kümülatif sayı
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}$$
olur. Fakat soru yüksekliği en fazla \(h\) değil, tam olarak \(h\) ister. O yüzden bir önceki kümülatif katmanı çıkarırız:
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
Uygulamanın her sorgu için döndürdüğü değer budur.
Elimizde \(P(x)/Q(x)\) rasyonel fonksiyonu olsun ve sadece \([x^k]P(x)/Q(x)\) katsayısını isteyelim. \(w\) çok büyükse uygulama tüm seriyi açmaz; onun yerine
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x)$$
tanımlar. \(V(x)\) çift polinomdur; dolayısıyla paydada yalnızca çift kuvvetler kalır. Eğer \(k=2m\) ise \(U\)'nun çift katsayıları, \(k=2m+1\) ise tek katsayıları tutulur. Böylece aranan katsayı, yeni bir rasyonel fonksiyonda indis \(m\) olan katsayıya dönüşür. Bu işlem tekrarlandıkça indis sürekli yarıya iner ve sonunda sabit terime kadar düşer. İşte uygulamanın çok büyük genişlik ve görece küçük yükseklik durumunda kullandığı Bostan-Mori adımı budur.
\(w\) orta büyüklükteyse yalnızca derece \(w\)'ye kadar katsayılar önemlidir. Bu durumda her polinom çarpımı \(x^{w+1}\) modunda kesilir; böylece matris kuvveti hiçbir zaman derece \(w\)'yi aşmaz. \(P(x)\) ve \(Q(x)\) bu dereceye kadar elde edilince uygulama \(Q(x)\)'in ters formal serisini hesaplar:
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
\(Q(x)\)'in sabit terimi sıfır olmadığı için \(I(x)\)'in katsayıları
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}$$
bağıntısıyla bulunur. Sonra
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr)$$
olduğu için gerekli değer, hiç daha yüksek dereceye çıkmadan okunur.
Uygulama kendini \(F(4,2)=10\) kontrol değeriyle doğrular. Yükseklik \(2\) için pozitif kanal
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots$$
verir. İşaretli kanal ise
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots$$
verir. Böylece
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10$$
olur. Yükseklik \(1\) için
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x}$$
elde edilir ve bunların ortalaması her genişlikte \(0\) verir. Dolayısıyla
$$F(4,2)=E_2(4)-E_1(4)=10-0=10$$
çıkar; bu da beklenen kontroldür.
\(F(w,h)\) bu şekilde tanımlandıktan sonra sorunun istediği nihai cevap
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}$$
olur. Yani tüm iş, aynı tam-yükseklik yordamını üç kez çalıştırmaya indirgenir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Verilen \((w,h)\) çifti için, önce yüksekliği en fazla \(h\) olan pozitif kanal ve işaretli kanal sayıları hesaplanır; sonra aynı işlem \(h-1\) için tekrarlanır; iki kanal sonucu \(2\)'nin modüler tersi ile ortalanır ve bir önceki seviye çıkarılarak tam yükseklik \(h\) izole edilir.
Tek bir kanal içinde uygulama önce ilgili \(2\times 2\) polinom matrisini ikili üs alma ile istenen yüksekliğe yükseltir. Sonra ortaya çıkan rasyonel fonksiyondan \(x^w\) katsayısını çıkarır. Genişlik çok büyükse yinelemeli Bostan-Mori yarılama kullanılır; genişlik daha küçükse tüm polinomlar derece \(w\)'de kesilir, paydanın formal tersi hesaplanır ve hedef katsayı kesilmiş çarpımdan doğrudan okunur.
Python uygulaması aynı aritmetiği başlatan ince bir katmandır; C++ ve Java ise polinom ve matris işlemlerini doğrudan yapar. Matematiksel sonuç üç dilde de aynıdır.
\(M(n)\), derece \(n\) polinomların çarpım maliyeti olsun. Bu uygulamalarda kullanılan temel polinom çarpımı kareseldir; dolayısıyla \(M(n)=O(n^2)\).
Bostan-Mori kolunda, yükseklik \(h\) için matris üs alma sonunda derece \(O(h)\) polinomlar oluşur. Bu rasyonel fonksiyonu kurmanın maliyeti \(O(h^2\log h)\), tekrarlı katsayı yarılama adımı ise ek olarak \(O(h^2\log w)\) olur. Bellek kullanımı \(O(h)\)'dir.
Kesilmiş-seri kolunda tüm dereceler \(w\) ile sınırlandırılır. Bu durumda matrisin ikili üs alması \(O(w^2\log h)\), ters-seri özyinelemesi \(O(w^2)\), bellek kullanımı ise \(O(w)\) olur. Uygulama iki kol arasında geçiş yapar çünkü sorudaki üç sorgu çok farklı parametre bölgelerinde yer alır.
Para cada par \((w,h)\), debemos contar castillos de anchura \(w\) y altura exacta \(h\) que satisfacen la condición de paridad incorporada en el enunciado, todo ello módulo \(10^9+7\). La respuesta final es la suma de tres evaluaciones de ese tipo. Una enumeración directa es inviable, así que la implementación convierte la construcción en una extracción de coeficientes de funciones generadoras racionales.
La implementación trabaja primero con conteos acumulados hasta una cota de altura y solo al final los transforma en la cantidad de altura exacta pedida por el problema.
La anchura se marca con la variable \(x\). La descomposición de castillos usada por la implementación se resume en una transferencia de dos estados, y hay dos versiones de esa transferencia:
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
La primera matriz cuenta cada objeto válido con signo positivo. La segunda introduce signos de modo que, al promediar ambos canales más adelante, sobreviva exactamente la contribución de paridad par exigida por el problema.
Partiendo del vector inicial
$$v_0=\binom{0}{1},$$
el efecto de permitir altura a lo sumo \(h\) viene dado por
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}.$$
Las funciones generadoras acumuladas asociadas son
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}.$$
Si definimos
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x),$$
entonces \(S_h(w)\) y \(D_h(w)\) son los dos conteos acumulados para anchura \(w\) y altura no mayor que \(h\).
El canal con signo está construido para que los objetos de paridad impar se cancelen y permanezcan los de paridad par. Por tanto, el conteo acumulado par es
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}.$$
Pero el problema pide altura exacta \(h\), no altura a lo sumo \(h\). Por eso restamos el nivel acumulado anterior:
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
Esa es la cantidad que devuelve la implementación para cada consulta.
Supongamos que solo queremos el coeficiente \([x^k]P(x)/Q(x)\) de una función racional \(P(x)/Q(x)\). Cuando \(w\) es muy grande, la implementación evita expandir toda la serie y define
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x).$$
El polinomio \(V(x)\) es par, así que en el denominador solo quedan potencias pares. Si \(k=2m\), se conservan los coeficientes pares de \(U\); si \(k=2m+1\), se conservan los impares. Tras esa selección, el coeficiente buscado se convierte en un coeficiente de índice \(m\) en una nueva función racional. Repetir el proceso vuelve a dividir el índice entre dos hasta llegar a un término constante. Ese es el paso de Bostan-Mori utilizado cuando la anchura es enorme y la altura es comparativamente pequeña.
Cuando \(w\) es moderado, solo interesan los coeficientes hasta grado \(w\). En ese caso cada multiplicación de polinomios se trunca módulo \(x^{w+1}\), de modo que la potencia matricial nunca supera el grado \(w\). Una vez conocidos \(P(x)\) y \(Q(x)\) hasta ese grado, la implementación calcula la serie inversa de \(Q(x)\):
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
Como el término constante de \(Q(x)\) no es cero, los coeficientes de \(I(x)\) quedan fijados recursivamente por
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}.$$
Entonces
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr),$$
y el valor buscado se obtiene sin calcular grados superiores.
La implementación se valida con el punto de control \(F(4,2)=10\). Para altura \(2\), el canal positivo da
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots.$$
El canal con signo da
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots.$$
Por consiguiente,
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10.$$
Para altura \(1\), los dos canales son
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x},$$
y su promedio vale \(0\) en cualquier anchura. Por tanto,
$$F(4,2)=E_2(4)-E_1(4)=10-0=10,$$
exactamente como exige la comprobación.
Una vez definido \(F(w,h)\), la respuesta pedida es
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}.$$
Así, toda la tarea se reduce a evaluar la misma rutina de altura exacta tres veces.
Las implementaciones en C++, Python y Java siguen exactamente la misma cadena matemática. Para un par \((w,h)\), calculan el conteo acumulado hasta altura \(h\) en el canal positivo y en el canal con signo, repiten la misma operación para altura \(h-1\), promedian ambos resultados con el inverso modular de \(2\) y restan el nivel anterior para aislar la altura exacta.
Dentro de un canal, la implementación eleva primero la matriz polinómica \(2\times 2\) correspondiente mediante exponenciación binaria. Después extrae el coeficiente de \(x^w\) de la función racional resultante. Si la anchura es enorme, usa la reducción iterativa de Bostan-Mori; si la anchura es menor, trunca todos los polinomios al grado \(w\), invierte formalmente el denominador y lee el coeficiente objetivo del producto truncado.
La implementación en Python es solo un lanzador ligero alrededor de la misma aritmética, mientras que C++ y Java realizan directamente las operaciones con polinomios y matrices. El resultado matemático es el mismo en los tres lenguajes.
Sea \(M(n)\) el coste de multiplicar polinomios de grado \(n\). En estas implementaciones la multiplicación subyacente es cuadrática, así que \(M(n)=O(n^2)\).
En la rama Bostan-Mori, la potencia matricial para altura \(h\) produce polinomios de grado \(O(h)\). Construir la función racional cuesta \(O(h^2\log h)\), y la fase de halving repetido de coeficientes añade \(O(h^2\log w)\). El uso de memoria es \(O(h)\).
En la rama truncada, todos los grados se recortan en \(w\). La exponenciación binaria de la matriz cuesta entonces \(O(w^2\log h)\), la recursión de la serie inversa cuesta \(O(w^2)\), y la memoria es \(O(w)\). La implementación alterna entre ambas ramas porque las tres consultas del problema pertenecen a regímenes de parámetros muy distintos.
对于每个 \((w,h)\)，我们要计算宽度为 \(w\)、精确高度为 \(h\) 且满足题目中奇偶性条件的城堡数量，结果对 \(10^9+7\) 取模。整道题的最终答案是三个这样的值之和。直接枚举显然不可行，所以实现把组合计数转化为有理生成函数的系数提取问题。
实现并不是直接计算“高度恰好为 \(h\)”的数量，而是先计算“高度至多为 \(h\)”的累计数量，最后再做一次差分得到精确高度。
令 \(x\) 记录总宽度。实现所使用的城堡分解可以压缩成一个两状态转移，而且这个转移有两个版本：
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
第一个矩阵把每个合法对象都按正号计数。第二个矩阵给对象附加符号，使得后面把两个通道取平均时，奇数奇偶类相互抵消，只留下题目要求的偶数奇偶类贡献。
从初始向量
$$v_0=\binom{0}{1}$$
出发，允许高度不超过 \(h\) 的效果由
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}$$
给出。于是对应的累计生成函数为
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}.$$
再定义
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x),$$
那么 \(S_h(w)\) 和 \(D_h(w)\) 就分别表示宽度为 \(w\)、高度至多为 \(h\) 时的两个累计计数通道。
带符号的通道专门用来做奇偶性筛选。奇数奇偶类在求和时会互相抵消，而偶数奇偶类会被保留下来，因此偶数部分的累计计数为
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}.$$
但题目要求的是“高度恰好等于 \(h\)”，不是“高度不超过 \(h\)”。所以还要减去上一层累计值：
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
这就是实现对单个查询真正返回的量。
设我们有一个有理函数 \(P(x)/Q(x)\)，只需要其中一个系数 \([x^k]P(x)/Q(x)\)。当 \(w\) 极大时，展开整个幂级数完全没有意义。实现改用如下变换：
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x).$$
因为 \(V(x)\) 是偶多项式，所以新的分母只含偶次幂。如果 \(k=2m\)，就在 \(U(x)\) 中保留偶次项；如果 \(k=2m+1\)，就在 \(U(x)\) 中保留奇次项。这样一来，原来索引为 \(k\) 的目标系数，就转化成一个新有理函数中索引为 \(m\) 的系数。重复这个过程，索引会不断减半，最后降到常数项。实现正是利用这一点在“宽度极大、而高度相对较小”的情形下高效提取所需系数。
如果 \(w\) 不大，那么我们只关心到 \(x^w\) 为止的系数。在这种情况下，每一次多项式乘法都直接按 \(x^{w+1}\) 取模截断，因此矩阵幂运算中的多项式次数始终不会超过 \(w\)。得到 \(P(x)\) 和 \(Q(x)\) 的截断形式后，实现再求 \(Q(x)\) 的逆幂级数：
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
由于 \(Q(x)\) 的常数项非零，\(I(x)\) 的系数可由递推唯一确定：
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}.$$
于是
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr),$$
所需答案可以直接从截断乘积中读出，而不需要处理更高次数。
实现里有一个重要校验点：\(F(4,2)=10\)。当高度为 \(2\) 时，正号通道给出
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots.$$
带符号通道给出
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots.$$
因此
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10.$$
而在高度 \(1\) 时，两个通道分别是
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x},$$
两者平均后在任意宽度上的系数都为 \(0\)。所以
$$F(4,2)=E_2(4)-E_1(4)=10-0=10,$$
与校验值完全一致。
按上述定义，题目最终要求的是
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}.$$
也就是说，只要把同一个“精确高度计数”过程应用到三个不同参数对上，再把结果相加即可。
C++、Python 和 Java 实现遵循同一条数学流水线。对于给定的 \((w,h)\)，它们先分别计算正号通道与带符号通道在“高度至多 \(h\)”时的累计计数，再对 \(h-1\) 重复同样的过程，然后用 \(2\) 的模逆把两个通道平均，最后做差得到“高度恰好为 \(h\)”的答案。
在单个通道内部，实现先通过二进制快速幂把相应的 \(2\times 2\) 多项式矩阵提升到指定高度，然后从得到的有理函数中提取 \(x^w\) 的系数。当宽度特别大时，使用反复减半索引的 Bostan-Mori 方案；当宽度较小时，把所有多项式截断到 \(w\) 次，求分母的形式逆，再从截断乘积中直接读取目标系数。
Python 实现本身只是对同一套核心算术的轻量封装，而 C++ 与 Java 版本直接完成多项式和矩阵运算。三种语言的数学内容完全一致。
记 \(M(n)\) 为次数为 \(n\) 的多项式相乘的代价。在这些实现里，基础多项式乘法是二次的，因此 \(M(n)=O(n^2)\)。
在 Bostan-Mori 分支中，把矩阵提升到高度 \(h\) 后得到的多项式次数是 \(O(h)\)。构造对应有理函数需要 \(O(h^2\log h)\) 时间，后续反复减半索引的系数提取再增加 \(O(h^2\log w)\) 时间，空间复杂度为 \(O(h)\)。
在截断分支中，所有多项式都被裁到 \(w\) 次，因此矩阵二进制快速幂需要 \(O(w^2\log h)\) 时间，逆幂级数递推需要 \(O(w^2)\) 时间，空间复杂度为 \(O(w)\)。实现之所以在两条分支间切换，是因为题目中的三个查询落在完全不同的参数区间里。
Для каждой пары \((w,h)\) нужно посчитать число замков ширины \(w\) и точной высоты \(h\), удовлетворяющих условию чётности из формулировки задачи, по модулю \(10^9+7\). Итоговый ответ равен сумме трёх таких значений. Прямой перебор нереален, поэтому реализация сводит задачу к извлечению коэффициента из рациональных производящих функций.
Сначала реализация считает накопленные количества для высоты не больше \(h\), а затем переводит их в число объектов ровно высоты \(h\).
Ширина отмечается переменной \(x\). Используемое в реализации разложение замков сводится к переходу с двумя состояниями, причём у него есть две версии:
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
Первая матрица считает каждый допустимый объект с положительным знаком. Вторая прикрепляет знак так, чтобы при последующем усреднении двух каналов сохранился только вклад нужной чётности.
Начиная с базового вектора
$$v_0=\binom{0}{1},$$
получаем эффект ограничения высоты \(h\) из равенства
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}.$$
Соответствующие накопленные производящие функции равны
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}.$$
Если положить
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x),$$
то \(S_h(w)\) и \(D_h(w)\) дают два накопленных счёта для ширины \(w\) и высоты не больше \(h\).
Знаковый канал устроен так, что объекты неправильной чётности взаимно уничтожаются, а объекты правильной чётности сохраняются. Поэтому накопленный чётный счёт равен
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}.$$
Но в задаче нужна не высота не больше \(h\), а ровно \(h\). Значит, надо вычесть предыдущий накопленный уровень:
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
Именно это значение реализация и вычисляет для каждого запроса.
Пусть дана рациональная функция \(P(x)/Q(x)\), и нужен только коэффициент \([x^k]P(x)/Q(x)\). Когда \(w\) очень велико, разворачивать весь ряд бессмысленно. Реализация задаёт
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x).$$
Полином \(V(x)\) является чётным, поэтому в знаменателе остаются только чётные степени. Если \(k=2m\), сохраняются чётные коэффициенты \(U\); если \(k=2m+1\), сохраняются нечётные. После этого целевой коэффициент превращается в коэффициент с индексом \(m\) у новой рациональной функции. Повторяя шаг, мы снова и снова делим индекс пополам, пока не дойдём до свободного члена. Это и есть используемый в реализации приём Бостана-Мори для случая огромной ширины и сравнительно малой высоты.
Если \(w\) невелико, важны только коэффициенты до степени \(w\). Тогда каждое умножение полиномов сразу усечается по модулю \(x^{w+1}\), и степени в матричной степени никогда не превышают \(w\). Когда \(P(x)\) и \(Q(x)\) известны до этого порядка, реализация вычисляет обратный формальный ряд к \(Q(x)\):
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
Поскольку свободный член \(Q(x)\) не равен нулю, коэффициенты \(I(x)\) определяются рекурсией
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}.$$
Тогда
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr),$$
и нужное значение можно считать прямо из усечённого произведения.
В реализации есть контрольная точка \(F(4,2)=10\). Для высоты \(2\) положительный канал даёт
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots.$$
Знаковый канал даёт
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots.$$
Следовательно,
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10.$$
Для высоты \(1\) имеем
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x},$$
а их среднее даёт \(0\) при любой ширине. Поэтому
$$F(4,2)=E_2(4)-E_1(4)=10-0=10,$$
ровно как и требуется.
После определения \(F(w,h)\) итоговый ответ имеет вид
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}.$$
То есть вся задача сводится к трём вызовам одной и той же процедуры подсчёта для точной высоты.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Для пары \((w,h)\) они сначала вычисляют накопленный счёт до высоты \(h\) в положительном и знаковом каналах, затем повторяют то же самое для высоты \(h-1\), усредняют два канала с помощью обратного по модулю числа \(2\) и вычитают предыдущий уровень, чтобы оставить только точную высоту \(h\).
Внутри одного канала реализация сначала возводит соответствующую \(2\times 2\) матрицу полиномов в нужную степень бинарным возведением. Затем из полученной рациональной функции извлекается коэффициент при \(x^w\). Если ширина огромна, используется итеративное деление индекса пополам по схеме Бостана-Мори; если ширина меньше, все полиномы усекаются до степени \(w\), знаменатель обращается как формальный ряд, и нужный коэффициент считывается из усечённого произведения.
Python-реализация является лишь тонким запуском той же арифметики, тогда как C++ и Java выполняют полиномиальные и матричные операции напрямую. Математический результат во всех трёх языках одинаков.
Пусть \(M(n)\) обозначает стоимость умножения полиномов степени \(n\). В данных реализациях базовое умножение полиномов квадратичное, то есть \(M(n)=O(n^2)\).
В ветви Бостана-Мори матричная степень для высоты \(h\) порождает полиномы степени \(O(h)\). Построение рациональной функции стоит \(O(h^2\log h)\), а стадия многократного деления индекса пополам добавляет \(O(h^2\log w)\). Память имеет порядок \(O(h)\).
В усечённой ветви все степени ограничены числом \(w\). Тогда бинарное возведение матрицы в степень требует \(O(w^2\log h)\), рекурсия для обратного ряда требует \(O(w^2)\), а память равна \(O(w)\). Реализация переключается между ветвями, потому что три запросa задачи лежат в разных параметрических режимах.
لكل زوج \((w,h)\) نريد عدّ القلاع ذات العرض \(w\) والارتفاع الدقيق \(h\) التي تحقق شرط الزوجية الوارد في نص المسألة، مع أخذ النتيجة بترديد \(10^9+7\). الجواب النهائي هو مجموع ثلاث قيم من هذا النوع. التعداد المباشر غير عملي تماماً، لذلك تحوّل الخوارزمية المسألة إلى استخراج معامل من دوال مولدة كسرية.
بدلاً من عدّ القلاع ذات الارتفاع الدقيق مباشرة، تبدأ الخوارزمية بحساب الأعداد التراكمية للقلاع ذات الارتفاع الذي لا يتجاوز \(h\)، ثم تحوّل هذه القيم في النهاية إلى عدد القلاع ذات الارتفاع الدقيق المطلوب.
نستخدم \(x\) لتتبع العرض. التفكيك التركيبي الذي تعتمد عليه الخوارزمية يمكن تلخيصه في انتقال ذي حالتين، وله نسختان:
$$M_{+}(x)=\begin{pmatrix}1+x & x\\ -x & 1-x\end{pmatrix},\qquad M_{-}(x)=\begin{pmatrix}-(1+x) & -x\\ -x & 1-x\end{pmatrix}.$$
المصفوفة الأولى تعدّ كل بنية صالحة بإشارة موجبة. أما الثانية فتضيف إشارة تجعل المتوسط بين القناتين يعزل في النهاية المساهمة ذات الزوجية المطلوبة في المسألة.
انطلاقاً من المتجه الابتدائي
$$v_0=\binom{0}{1}$$
فإن أثر السماح بارتفاع لا يتجاوز \(h\) يُعطى بالعلاقة
$$M_{\pm}(x)^h v_0=\binom{P_h^{(\pm)}(x)}{Q_h^{(\pm)}(x)}.$$
ومن هنا نحصل على الدالتين المولّدتين التراكميتين
$$R_h^{(+)}(x)=\frac{P_h^{(+)}(x)}{Q_h^{(+)}(x)},\qquad R_h^{(-)}(x)=\frac{P_h^{(-)}(x)}{Q_h^{(-)}(x)}.$$
وإذا عرّفنا
$$S_h(w)=[x^w]R_h^{(+)}(x),\qquad D_h(w)=[x^w]R_h^{(-)}(x),$$
فإن \(S_h(w)\) و\(D_h(w)\) يمثلان العدّين التراكميين للعرض \(w\) مع ارتفاع لا يزيد على \(h\).
القناة الموقعة مصممة بحيث تلغي الأجسام ذات الزوجية غير المطلوبة وتُبقي الأجسام ذات الزوجية المطلوبة. لذلك يكون العدد التراكمي الموافق هو
$$E_h(w)=\frac{S_h(w)+D_h(w)}{2}\pmod{10^9+7}.$$
لكن المطلوب في المسألة هو الارتفاع الدقيق \(h\)، لا الارتفاع الذي لا يتجاوزه. ولهذا نطرح المستوى التراكمي السابق:
$$F(w,h)=E_h(w)-E_{h-1}(w)\pmod{10^9+7}.$$
هذه هي الكمية التي تعيدها الخوارزمية لكل استعلام.
لنفرض أن لدينا الدالة الكسرية \(P(x)/Q(x)\) ونريد فقط المعامل \([x^k]P(x)/Q(x)\). عندما يكون \(w\) ضخماً لا جدوى من توسيع السلسلة كاملة، ولذلك تعرّف الخوارزمية
$$\widetilde{Q}(x)=Q(-x),\qquad U(x)=P(x)\widetilde{Q}(x),\qquad V(x)=Q(x)\widetilde{Q}(x).$$
بما أن \(V(x)\) كثير حدود زوجي، فإن المقام الجديد لا يحوي إلا الأسس الزوجية. فإذا كان \(k=2m\) نحتفظ بالمعاملات الزوجية من \(U\)، وإذا كان \(k=2m+1\) نحتفظ بالمعاملات الفردية. بعد هذه الخطوة يتحول المعامل المطلوب إلى معامل ذي فهرس \(m\) في دالة كسرية جديدة. ومع تكرار العملية ينخفض الفهرس إلى النصف مرة بعد مرة حتى نصل إلى حد ثابت. هذه هي حيلة Bostan-Mori التي تستخدمها الخوارزمية عندما يكون العرض هائلاً والارتفاع أصغر بكثير.
إذا كان \(w\) متوسطاً أو صغيراً، فنحن لا نهتم إلا بالمعاملات حتى الدرجة \(w\). لذلك تُقطع كل عملية ضرب لكثيرات الحدود بترديد \(x^{w+1}\)، وبذلك لا تتجاوز درجات كثيرات الحدود داخل رفع المصفوفة الدرجة \(w\) أبداً. وبعد الحصول على \(P(x)\) و\(Q(x)\) حتى هذه الدرجة، تحسب الخوارزمية معكوس \(Q(x)\) كسلسلة قوى شكلية:
$$Q(x)^{-1}\equiv I(x)\pmod{x^{w+1}},\qquad I(x)=\sum_{n=0}^{w} i_n x^n.$$
وبما أن الحد الثابت في \(Q(x)\) غير صفري، فإن معاملات \(I(x)\) تُحدَّد بالعلاقة العودية
$$i_0=q_0^{-1},\qquad i_n=-q_0^{-1}\sum_{j=1}^{n} q_j\,i_{n-j}\pmod{10^9+7}.$$
وعندها نحصل على
$$[x^w]\frac{P(x)}{Q(x)}=[x^w]\bigl(P(x)I(x)\bigr),$$
فتُقرأ القيمة المطلوبة مباشرة من الجداء المقطوع من دون الحاجة إلى درجات أعلى.
تتحقق الخوارزمية من نفسها عند النقطة \(F(4,2)=10\). عند الارتفاع \(2\)، تعطي القناة الموجبة
$$M_{+}(x)^2 v_0=\binom{2x}{1-2x},\qquad R_2^{(+)}(x)=\frac{2x}{1-2x}=2x+4x^2+8x^3+16x^4+\cdots.$$
أما القناة الموقعة فتعطي
$$M_{-}(x)^2 v_0=\binom{2x^2}{1-2x+2x^2},\qquad R_2^{(-)}(x)=\frac{2x^2}{1-2x+2x^2}=2x^2+4x^3+4x^4+\cdots.$$
ومن ثم
$$S_2(4)=16,\qquad D_2(4)=4,\qquad E_2(4)=\frac{16+4}{2}=10.$$
وعند الارتفاع \(1\) نحصل على
$$R_1^{(+)}(x)=\frac{x}{1-x},\qquad R_1^{(-)}(x)=-\frac{x}{1-x},$$
ومتوسطهما يساوي \(0\) عند كل عرض. لذلك
$$F(4,2)=E_2(4)-E_1(4)=10-0=10,$$
وهو تماماً مقدار التحقق المستخدم في التنفيذ.
بعد تعريف \(F(w,h)\) بهذه الطريقة، يكون المطلوب النهائي هو
$$F(10^{12},100)+F(10^4,10^4)+F(100,10^{12})\pmod{10^9+7}.$$
وبذلك تختزل المسألة كلها إلى تشغيل الإجراء نفسه الخاص بالارتفاع الدقيق ثلاث مرات.
تتبع تطبيقات C++ وPython وJava السلسلة الرياضية نفسها. فلكل زوج \((w,h)\)، تحسب أولاً العدّ التراكمي حتى الارتفاع \(h\) في القناة الموجبة والقناة الموقعة، ثم تعيد العملية نفسها للارتفاع \(h-1\)، وبعد ذلك تأخذ متوسط القناتين باستعمال المعكوس المعياري للعدد \(2\)، ثم تطرح المستوى السابق لعزل العدد الموافق للارتفاع الدقيق \(h\).
داخل كل قناة، ترفع الخوارزمية أولاً مصفوفة كثيرات الحدود \(2\times 2\) المناسبة إلى الارتفاع المطلوب باستعمال الرفع الثنائي. ثم تستخرج معامل \(x^w\) من الدالة الكسرية الناتجة. إذا كان العرض ضخماً جداً تُستخدم حيلة Bostan-Mori ذات التقسيم المتكرر للفهرس إلى النصف، وإذا كان العرض أصغر فتُقطع كثيرات الحدود عند الدرجة \(w\)، ثم يُحسب معكوس المقام كسلسلة شكلية، ثم يُقرأ المعامل المطلوب مباشرة من الجداء المقطوع.
تطبيق Python مجرد طبقة تشغيل خفيفة لنفس الحسابات، بينما ينفذ C++ وJava عمليات كثيرات الحدود والمصفوفات مباشرة. النتيجة الرياضية واحدة في اللغات الثلاث.
لنرمز بـ \(M(n)\) إلى كلفة ضرب كثيري حدود من الدرجة \(n\). في هذه التطبيقات، الضرب الأساسي تربيعي، أي \(M(n)=O(n^2)\).
في فرع Bostan-Mori، يؤدي رفع المصفوفة إلى الارتفاع \(h\) إلى كثيرات حدود من الدرجة \(O(h)\). بناء الدالة الكسرية يكلف \(O(h^2\log h)\)، ثم تضيف مرحلة تقليص الفهرس المتكرر كلفة \(O(h^2\log w)\). أما الذاكرة فهي من الرتبة \(O(h)\).
في الفرع المقطوع، تُقص جميع الدرجات عند \(w\). وعندئذ يكلف الرفع الثنائي للمصفوفة \(O(w^2\log h)\)، وتكلف عودية معكوس السلسلة \(O(w^2)\)، وتكون الذاكرة \(O(w)\). لهذا السبب تنتقل الخوارزمية بين الفرعين، لأن الاستعلامات الثلاثة المطلوبة تقع في أنظمة معاملات مختلفة تماماً.