We must count directed lattice paths from \((0,0)\) to \((w,h)\). Every step is a nonzero vector \((a,b)\in \mathbb{Z}_{\ge 0}^2\) whose Euclidean length is a Fibonacci number, so each admissible move satisfies
$$a^2+b^2=F_k^2$$
for some Fibonacci number \(F_k\). The answer is required modulo \(10^9+7\).
The main difficulty is that the step set is neither purely local nor regular. Horizontal and vertical Fibonacci jumps are always possible when they fit inside the rectangle, while off-axis moves only appear when a Fibonacci number is also the hypotenuse of an integer right triangle, such as \((3,4)\) for length \(5\).
Let \(D(x,y)\) denote the number of admissible paths from the origin to \((x,y)\). The solution has two layers: first enumerate all legal step vectors, then evaluate an acyclic dynamic program over the grid.
Any usable step must satisfy \(0\le a\le w\) and \(0\le b\le h\). Therefore its length cannot exceed the diagonal of the target rectangle:
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
Only Fibonacci numbers \(F_k\le R\) can matter. This immediately makes the geometric preprocessing finite and small, because the Fibonacci sequence grows exponentially.
Define the step set
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ for some } F_k\le R\right\}.$$
For each relevant Fibonacci number \(F_k\), we search for all nonnegative integer lattice points on the circle \(a^2+b^2=F_k^2\) that also satisfy \(a\le w\) and \(b\le h\). Axis-aligned moves \((F_k,0)\) and \((0,F_k)\) appear automatically when they fit. Additional moves come from Pythagorean triples.
After sorting and deduplication, split \(S\) into
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$$
The set \(V\) contains the purely vertical moves, while \(O\) contains everything that advances in the \(x\)-direction, including horizontal moves.
The path count satisfies the direct recurrence
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
This is valid because every admissible path reaching \((x,y)\) has a well-defined final step, and removing that final step leaves a path to \((x-a,y-b)\). Since \(a\) and \(b\) are never both zero, every dependency points strictly left, strictly down, or both. The state graph is therefore acyclic.
The only awkward part is that vertical moves have \(a=0\), so they stay inside the same column. For a fixed column \(x\), define the contribution from all moves that come from earlier columns:
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
Once \(A_x(y)\) is known, the current column can be filled from bottom to top using
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
with one extra \(1\) added at \((x,y)=(0,0)\) for the empty path. This transforms the two-dimensional recurrence into a clean sweep: all non-vertical steps are accumulated first, then vertical steps are resolved in increasing \(y\) order within the same column.
Let
$$M=\max\{a:(a,b)\in O\},$$
with the convention \(M=0\) if no such step exists. A transition into column \(x\) can only read columns \(x-1,x-2,\dots,x-M\). Anything older is irrelevant. So instead of storing the whole \((w+1)\times(h+1)\) table, it is enough to store columns modulo \(M+1\). This is exactly why a ring buffer is correct.
Here the diagonal length is
$$R=\sqrt{3^2+4^2}=5,$$
so the relevant Fibonacci lengths are \(1,2,3,5\). The admissible steps are
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$$
Column \(x=0\) is determined only by vertical moves:
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
For \(x=1\), the only non-vertical source is \((1,0)\), so \(A_1(y)=D(0,y)\). After adding vertical continuations we get
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$$
For \(x=2\), the source term is \(A_2(y)=D(1,y)+D(0,y)\), which yields
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$$
For \(x=3\), we add contributions from \((1,0)\), \((2,0)\), \((3,0)\), and the diagonal step \((3,4)\) from the origin. The final value becomes
$$D(3,4)=278,$$
which matches the small checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same mathematical pipeline. They first generate Fibonacci numbers up to \(R\), then enumerate every admissible pair \((a,b)\) by scanning \(a\) and checking whether \(F_k^2-a^2\) is a perfect square. After sorting and deduplicating the pairs, they store vertical moves separately from moves with positive \(x\)-advance, and they record the largest horizontal component \(M\).
The dynamic program then processes columns from \(x=0\) to \(x=w\). For each column, a temporary array accumulates every contribution coming from earlier columns. After that, the column itself is filled from \(y=0\) upward, so same-column vertical dependencies are already available when needed. The C++ and Java implementations execute this recurrence directly, while the Python implementation reuses the same native computation and returns the parsed final value. In every case, all arithmetic is reduced modulo \(10^9+7\).
Let \(s_O=|O|\), \(s_V=|V|\), and \(M=\max\{a:(a,b)\in O\}\). Generating Fibonacci numbers costs \(O(\log R)\), and enumerating candidate steps costs
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$$
which is modest because the Fibonacci sequence grows exponentially. The dominant part is the grid DP: each column applies every non-vertical step across the valid \(y\)-range and then applies every vertical step while sweeping upward. Thus the running time is
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr),$$
and the memory usage is
$$O\bigl((M+1)(h+1)\bigr),$$
plus one extra temporary array of length \(h+1\).
Gesucht ist die Anzahl gerichteter Gitterwege von \((0,0)\) nach \((w,h)\). Jeder Schritt ist ein von Null verschiedener Vektor \((a,b)\in \mathbb{Z}_{\ge 0}^2\), dessen euklidische Länge eine Fibonacci-Zahl ist. Also muss jeder zulässige Schritt die Bedingung
$$a^2+b^2=F_k^2$$
für eine Fibonacci-Zahl \(F_k\) erfüllen. Das Ergebnis wird modulo \(10^9+7\) verlangt.
Die Schwierigkeit liegt darin, dass die Schrittmengen nicht lokal und nicht regelmäßig sind. Horizontale und vertikale Fibonacci-Sprünge sind stets möglich, wenn sie in das Rechteck passen. Schräge Schritte tauchen nur dann auf, wenn eine Fibonacci-Zahl zugleich die Hypotenuse eines ganzzahligen rechtwinkligen Dreiecks ist, etwa \((3,4)\) bei Länge \(5\).
Sei \(D(x,y)\) die Anzahl zulässiger Wege vom Ursprung nach \((x,y)\). Die Lösung besteht aus zwei Teilen: zuerst alle legalen Schrittvektoren bestimmen, danach ein azyklisches dynamisches Programm über dem Gitter auswerten.
Ein verwendbarer Schritt muss \(0\le a\le w\) und \(0\le b\le h\) erfüllen. Seine Länge kann also die Rechtecksdiagonale nicht überschreiten:
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
Damit kommen nur Fibonacci-Zahlen \(F_k\le R\) in Frage. Die geometrische Vorberechnung bleibt deshalb endlich und klein, weil Fibonacci-Zahlen exponentiell wachsen.
Definiere
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ für ein } F_k\le R\right\}.$$
Für jede relevante Fibonacci-Zahl \(F_k\) suchen wir alle nichtnegativen ganzzahligen Gitterpunkte auf dem Kreis \(a^2+b^2=F_k^2\), die zusätzlich \(a\le w\) und \(b\le h\) erfüllen. Achsenparallele Schritte \((F_k,0)\) und \((0,F_k)\) entstehen automatisch, sofern sie im Suchraum liegen. Weitere Schritte stammen aus pythagoreischen Tripeln.
Nach Sortierung und Deduplikation zerlegen wir \(S\) in
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$$
\(V\) enthält also die rein vertikalen Schritte, während \(O\) alle Schritte mit positivem \(x\)-Fortschritt enthält, einschließlich horizontaler Sprünge.
Die Weganzahl erfüllt
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
Jeder zulässige Weg nach \((x,y)\) besitzt einen eindeutig bestimmten letzten Schritt; entfernt man ihn, bleibt ein Weg nach \((x-a,y-b)\). Da \(a\) und \(b\) nie gleichzeitig Null sind, zeigen alle Abhängigkeiten strikt nach links, nach unten oder in beide Richtungen. Der Zustandsgraph ist also azyklisch.
Der einzige heikle Punkt ist \(a=0\): vertikale Schritte bleiben in derselben Spalte. Für eine feste Spalte \(x\) definieren wir deshalb zuerst den Beitrag aller Schritte aus früheren Spalten:
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
Ist \(A_x(y)\) bekannt, lässt sich die aktuelle Spalte von unten nach oben berechnen mit
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
wobei bei \((x,y)=(0,0)\) zusätzlich \(1\) für den leeren Weg addiert wird. So wird die zweidimensionale Rekurrenz in einen sauberen Spaltendurchlauf zerlegt: erst alle nichtvertikalen Beiträge, dann die vertikalen Abhängigkeiten in wachsender \(y\)-Reihenfolge.
Setze
$$M=\max\{a:(a,b)\in O\},$$
und konventionell \(M=0\), falls es keinen solchen Schritt gibt. Eine Transition in Spalte \(x\) liest höchstens die Spalten \(x-1,x-2,\dots,x-M\). Ältere Spalten werden nie mehr benötigt. Daher genügt es, Spalten modulo \(M+1\) zu speichern. Genau das rechtfertigt den Ringpuffer.
Hier ist die Diagonalenlänge
$$R=\sqrt{3^2+4^2}=5,$$
also sind die relevanten Fibonacci-Längen \(1,2,3,5\). Die zulässigen Schritte sind
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$$
Die Spalte \(x=0\) hängt nur von vertikalen Schritten ab:
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
Für \(x=1\) ist die einzige nichtvertikale Quelle \((1,0)\), also \(A_1(y)=D(0,y)\). Nach Einbeziehung der vertikalen Fortsetzungen erhält man
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$$
Für \(x=2\) gilt \(A_2(y)=D(1,y)+D(0,y)\), woraus folgt
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$$
In Spalte \(x=3\) kommen die Beiträge von \((1,0)\), \((2,0)\), \((3,0)\) und zusätzlich der Diagonalschritt \((3,4)\) vom Ursprung hinzu. Am Ende ergibt sich
$$D(3,4)=278,$$
genau der kleine Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Pipeline. Zuerst werden alle Fibonacci-Zahlen bis \(R\) erzeugt. Danach werden sämtliche zulässigen Paare \((a,b)\) aufgezählt, indem \(a\) durchlaufen und geprüft wird, ob \(F_k^2-a^2\) ein Quadrat ist. Nach Sortierung und Deduplikation werden vertikale Schritte getrennt von Schritten mit positivem \(x\)-Fortschritt gespeichert; zugleich wird die größte horizontale Komponente \(M\) bestimmt.
Das dynamische Programm verarbeitet dann die Spalten von \(x=0\) bis \(x=w\). Für jede Spalte sammelt ein temporäres Feld zunächst alle Beiträge aus früheren Spalten. Anschließend wird die Spalte selbst von \(y=0\) nach oben gefüllt, sodass vertikale Abhängigkeiten innerhalb derselben Spalte bereits verfügbar sind. Die C++- und Java-Implementierungen führen diese Rekurrenz direkt aus, während die Python-Implementierung dieselbe native Berechnung wiederverwendet und den numerischen Endwert ausgibt. Alle Rechnungen erfolgen modulo \(10^9+7\).
Seien \(s_O=|O|\), \(s_V=|V|\) und \(M=\max\{a:(a,b)\in O\}\). Das Erzeugen der Fibonacci-Zahlen kostet \(O(\log R)\), und die Aufzählung der Kandidatenschritte benötigt
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$$
was wegen des exponentiellen Wachstums der Fibonacci-Zahlen überschaubar bleibt. Dominant ist das Gitter-DP: In jeder Spalte werden alle nichtvertikalen Schritte über den gültigen \(y\)-Bereich angewandt, danach alle vertikalen Schritte im aufsteigenden Durchlauf. Insgesamt ergibt sich
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr)$$
Zeit und
$$O\bigl((M+1)(h+1)\bigr)$$
Speicher, zuzüglich eines temporären Feldes der Länge \(h+1\).
\((0,0)\)'dan \((w,h)\)'ye giden yönlü kafes yollarının sayısı istenir. Her adım, \((a,b)\in \mathbb{Z}_{\ge 0}^2\) içinde sıfırdan farklı bir vektördür ve Öklid uzunluğu bir Fibonacci sayısı olmak zorundadır. Yani izinli her adım
$$a^2+b^2=F_k^2$$
eşitliğini sağlayan bir \(F_k\) ile tanımlanır. Sonuç \(10^9+7\) modunda verilir.
Zorluk, adım kümesinin düzenli olmamasıdır. Yatay ve dikey Fibonacci sıçramaları, sınırlar içinde kaldıkları sürece her zaman mümkündür. Eğik adımlar ise ancak bir Fibonacci sayısı aynı zamanda tam sayı kenarlı bir dik üçgenin hipotenüsü olduğunda ortaya çıkar; uzunluğu \(5\) olan \((3,4)\) adımı bunun klasik örneğidir.
\(D(x,y)\), başlangıçtan \((x,y)\)'ye giden geçerli yol sayısı olsun. Çözüm iki aşamalıdır: önce bütün izinli adımlar listelenir, sonra bu adımlar üzerinde çevrimsiz bir dinamik program uygulanır.
Kullanılabilir bir adım için \(0\le a\le w\) ve \(0\le b\le h\) olmalıdır. Dolayısıyla adım uzunluğu hedef dikdörtgenin köşegenini aşamaz:
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
Böylece yalnızca \(F_k\le R\) olan Fibonacci sayıları önemlidir. Fibonacci dizisi üstel büyüdüğü için bu ön işleme küçük kalır.
Adım kümesini
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ olacak bir } F_k\le R \text{ vardır}\right\}$$
şeklinde tanımlayalım. Her uygun Fibonacci sayısı için, \(a^2+b^2=F_k^2\) denklemini sağlayan ve aynı zamanda \(a\le w,\ b\le h\) koşullarını karşılayan bütün negatif olmayan tam sayı çiftleri aranır. \((F_k,0)\) ve \((0,F_k)\) gibi eksen doğrultulu adımlar otomatik olarak oluşur. Eksen dışındaki adımlar ise Pisagor üçlülerinden gelir.
Sıralama ve tekilleştirmeden sonra \(S\) kümesini
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}$$
olarak ikiye ayırırız. \(V\) yalnızca dikey adımları, \(O\) ise \(x\) yönünde ilerleme yapan tüm adımları içerir; yatay adımlar da buna dahildir.
Yol sayısı doğrudan şu bağıntıyı sağlar:
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
Çünkü \((x,y)\)'ye ulaşan her geçerli yolun son adımı tektir; bu son adımı kaldırınca \((x-a,y-b)\)'ye giden bir yol kalır. Ayrıca \(a\) ve \(b\) aynı anda sıfır olmadığı için bağımlılıklar her zaman sola, aşağıya ya da her ikisine birden gider. Yani durum grafı çevrimsizdir.
Zor nokta, \(a=0\) olan dikey adımların aynı sütunda kalmasıdır. Bu yüzden sabit bir \(x\) sütunu için önce önceki sütunlardan gelen katkıyı tanımlarız:
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
\(A_x(y)\) bilindiğinde, mevcut sütun aşağıdan yukarıya şu şekilde doldurulur:
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
ve \((x,y)=(0,0)\) noktasında boş yol için ek bir \(1\) eklenir. Böylece iki boyutlu bağıntı düzenli bir sütun taramasına dönüşür: önce yatay ilerleme içeren tüm adımlar, sonra aynı sütun içindeki dikey bağımlılıklar.
$$M=\max\{a:(a,b)\in O\}$$
olsun; böyle bir adım yoksa \(M=0\) kabul edilir. \(x\) sütununa gelirken en fazla \(x-1,x-2,\dots,x-M\) sütunlarına bakılır. Daha eski sütunlara bir daha ihtiyaç duyulmaz. Bu nedenle tüm tabloyu tutmak yerine sütunları \(M+1\) ile mod alarak saklamak yeterlidir. Halka tampon fikri tam olarak buradan gelir.
Bu durumda köşegen uzunluğu
$$R=\sqrt{3^2+4^2}=5$$
olduğundan ilgili Fibonacci uzunlukları \(1,2,3,5\) olur. Geçerli adımlar
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}$$
şeklindedir. \(x=0\) sütunu yalnızca dikey adımlardan oluşur:
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
\(x=1\) için tek dış katkı \((1,0)\) adımıdır, yani \(A_1(y)=D(0,y)\). Dikey uzatmalar eklenince
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26$$
elde edilir. \(x=2\) için \(A_2(y)=D(1,y)+D(0,y)\) olur ve
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89$$
çıkar. \(x=3\) sütununda \((1,0)\), \((2,0)\), \((3,0)\) ve kökenden gelen \((3,4)\) çapraz adımı birlikte hesaba katılır. Sonuç
$$D(3,4)=278$$
olur; bu da uygulamanın küçük kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı matematiksel akışı izler. Önce \(R\)'ye kadar Fibonacci sayıları üretilir. Sonra her Fibonacci uzunluğu için \(a\) değerleri taranır ve \(F_k^2-a^2\) ifadesinin tam kare olup olmadığına bakılarak bütün izinli \((a,b)\) çiftleri bulunur. Sıralama ve tekilleştirmeden sonra dikey adımlar, \(x\) yönünde ilerleyen adımlardan ayrı tutulur; aynı anda en büyük yatay bileşen \(M\) de kaydedilir.
Dinamik program daha sonra \(x=0\)'dan \(x=w\)'ye kadar sütun sütun ilerler. Her sütunda geçici bir dizi, önceki sütunlardan gelen tüm katkıları toplar. Ardından sütunun kendisi \(y=0\)'dan yukarı doğru doldurulur; böylece aynı sütun içindeki dikey bağımlılıklar ihtiyaç anında hazır olur. C++ ve Java uygulamaları bu bağıntıyı doğrudan yürütür. Python uygulaması ise aynı yerel hesaplamayı yeniden kullanır ve son sayısal çıktıyı döndürür. Tüm işlemler \(10^9+7\) modunda yapılır.
\(s_O=|O|\), \(s_V=|V|\) ve \(M=\max\{a:(a,b)\in O\}\) olsun. Fibonacci listesi üretmek \(O(\log R)\) sürer. Aday adımları tarama maliyeti
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right)$$
kadardır ve Fibonacci sayılarının hızlı büyümesi nedeniyle sınırlı kalır. Asıl baskın kısım ızgara üzerindeki DP'dir: her sütunda bütün yatay ilerlemeli adımlar geçerli \(y\) aralığında uygulanır, ardından bütün dikey adımlar yukarı doğru taramada işlenir. Toplam süre
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr)$$
ve bellek kullanımı
$$O\bigl((M+1)(h+1)\bigr)$$
olur; buna ek olarak uzunluğu \(h+1\) olan bir geçici dizi vardır.
Debemos contar caminos dirigidos en la retícula desde \((0,0)\) hasta \((w,h)\). Cada paso es un vector no nulo \((a,b)\in \mathbb{Z}_{\ge 0}^2\) cuya longitud euclídea debe ser un número de Fibonacci. Por tanto, cada movimiento permitido satisface
$$a^2+b^2=F_k^2$$
para algún número de Fibonacci \(F_k\). La respuesta se pide módulo \(10^9+7\).
La dificultad es que el conjunto de pasos no es uniforme. Los saltos horizontales y verticales de longitud Fibonacci aparecen siempre que quepan en el rectángulo, mientras que los pasos oblicuos solo existen cuando un número de Fibonacci también es la hipotenusa de un triángulo rectángulo con lados enteros, como \((3,4)\) para longitud \(5\).
Sea \(D(x,y)\) el número de caminos válidos desde el origen hasta \((x,y)\). La solución tiene dos capas: primero enumerar todos los vectores de paso permitidos y luego evaluar una programación dinámica acíclica sobre la rejilla.
Cualquier paso utilizable debe cumplir \(0\le a\le w\) y \(0\le b\le h\). En consecuencia, su longitud no puede superar la diagonal del rectángulo objetivo:
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
Solo importan los números de Fibonacci \(F_k\le R\). Esto hace que el preprocesamiento geométrico sea pequeño, porque la sucesión de Fibonacci crece exponencialmente.
Definimos
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ para algún } F_k\le R\right\}.$$
Para cada Fibonacci relevante, buscamos todos los puntos enteros no negativos del círculo \(a^2+b^2=F_k^2\) que además satisfacen \(a\le w\) y \(b\le h\). Los pasos sobre los ejes, \((F_k,0)\) y \((0,F_k)\), aparecen de forma natural si están dentro de los límites. Los demás pasos provienen de ternas pitagóricas.
Después de ordenar y eliminar duplicados, separamos \(S\) en
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$$
El conjunto \(V\) contiene los pasos puramente verticales, y \(O\) contiene todos los que avanzan en la dirección \(x\), incluidos los horizontales.
El conteo de caminos cumple
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
La justificación es directa: cualquier camino válido que termina en \((x,y)\) tiene un último paso bien definido, y al quitarlo queda un camino hacia \((x-a,y-b)\). Como \(a\) y \(b\) no pueden ser ambos cero, cada dependencia apunta estrictamente a la izquierda, hacia abajo o a ambos lados. El grafo de estados es acíclico.
La única complicación es que los pasos verticales tienen \(a=0\), así que permanecen en la misma columna. Para una columna fija \(x\), definimos primero el aporte de todos los movimientos que llegan desde columnas anteriores:
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
Una vez conocido \(A_x(y)\), la columna actual se rellena de abajo hacia arriba mediante
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
añadiendo un \(1\) extra en \((0,0)\) por el camino vacío. Así, la recurrencia bidimensional se convierte en un barrido por columnas: primero se acumulan los pasos con avance horizontal y luego se resuelven las dependencias verticales dentro de la misma columna.
Sea
$$M=\max\{a:(a,b)\in O\},$$
y tomamos \(M=0\) si no existe tal paso. Una transición hacia la columna \(x\) solo puede mirar las columnas \(x-1,x-2,\dots,x-M\). Las columnas más antiguas dejan de ser útiles. Por eso basta con almacenar las columnas módulo \(M+1\). Esa es la razón matemática del buffer circular.
Aquí la diagonal vale
$$R=\sqrt{3^2+4^2}=5,$$
de modo que las longitudes Fibonacci relevantes son \(1,2,3,5\). Los pasos válidos son
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$$
La columna \(x=0\) depende solo de pasos verticales:
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
Para \(x=1\), la única fuente no vertical es \((1,0)\), así que \(A_1(y)=D(0,y)\). Tras añadir las continuaciones verticales obtenemos
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$$
Para \(x=2\), se tiene \(A_2(y)=D(1,y)+D(0,y)\), lo que produce
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$$
En la columna \(x=3\) se agregan las contribuciones de \((1,0)\), \((2,0)\), \((3,0)\) y del paso diagonal \((3,4)\) desde el origen. El resultado final es
$$D(3,4)=278,$$
que coincide con el pequeño punto de control usado por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma tubería matemática. Primero generan todos los números de Fibonacci hasta \(R\). Después enumeran cada par admisible \((a,b)\) recorriendo \(a\) y comprobando si \(F_k^2-a^2\) es un cuadrado perfecto. Tras ordenar y eliminar duplicados, separan los pasos verticales de los pasos con avance positivo en \(x\), y registran el mayor componente horizontal \(M\).
Luego la programación dinámica recorre las columnas desde \(x=0\) hasta \(x=w\). Para cada columna, un arreglo temporal acumula todas las contribuciones que llegan desde columnas anteriores. Después la propia columna se completa de \(y=0\) hacia arriba, de modo que las dependencias verticales dentro de esa columna ya están disponibles cuando se necesitan. Las versiones en C++ y Java ejecutan esta recurrencia de forma directa, mientras que la versión en Python reutiliza el mismo cálculo nativo y devuelve el valor final parseado. Toda la aritmética se reduce módulo \(10^9+7\).
Sean \(s_O=|O|\), \(s_V=|V|\) y \(M=\max\{a:(a,b)\in O\}\). Generar la lista de Fibonacci cuesta \(O(\log R)\), y enumerar los pasos candidatos cuesta
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$$
que es moderado porque la sucesión de Fibonacci crece con rapidez. La parte dominante es la DP sobre la rejilla: en cada columna se aplican todos los pasos no verticales sobre el rango válido de \(y\), y luego se procesan todos los pasos verticales durante el barrido ascendente. Por tanto, el tiempo total es
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr),$$
mientras que la memoria utilizada es
$$O\bigl((M+1)(h+1)\bigr),$$
más un arreglo temporal adicional de longitud \(h+1\).
题目要求统计从 \((0,0)\) 走到 \((w,h)\) 的有向格点路径数。每一步都是一个非零向量 \((a,b)\in \mathbb{Z}_{\ge 0}^2\)，并且它的欧几里得长度必须是某个斐波那契数。也就是说，允许的每一步都满足
$$a^2+b^2=F_k^2$$
其中 \(F_k\) 是斐波那契数。最终答案对 \(10^9+7\) 取模。
这个问题的难点在于允许步集合并不规则。只要不越界，水平方向和竖直方向的 Fibonacci 长跳都会出现；而斜向步只有在某个 Fibonacci 数同时还是整数直角三角形的斜边时才会出现，例如长度 \(5\) 对应的 \((3,4)\)。
记 \(D(x,y)\) 为从原点到 \((x,y)\) 的合法路径条数。整体思路分成两层：先把所有允许的步向量完整枚举出来，再在网格上做一个没有环的动态规划。
任何可用的步都必须满足 \(0\le a\le w\) 且 \(0\le b\le h\)。因此它的长度不可能超过目标矩形的对角线：
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
所以只有 \(F_k\le R\) 的斐波那契数才有机会出现。这一点非常重要，因为斐波那契数增长很快，预处理时需要检查的长度其实很少。
定义步集合
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ for some } F_k\le R\right\}.$$
对于每一个相关的斐波那契数 \(F_k\)，我们寻找圆 \(a^2+b^2=F_k^2\) 上所有非负整数格点，并额外要求 \(a\le w,\ b\le h\)。轴向步 \((F_k,0)\) 和 \((0,F_k)\) 只要在边界内就一定存在；而其他步则来自勾股数组合，也就是整数点落在该圆上的情形。
实现中会先排序并去重，然后把 \(S\) 拆成两部分：
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$$
这里 \(V\) 只保留纯竖直步的高度，\(O\) 则收集所有 \(x\) 坐标严格增加的步，因此水平步也包含在 \(O\) 中。
一旦步集合固定，路径计数满足最直接的递推：
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
理由很简单：任何一条到达 \((x,y)\) 的合法路径都有一个明确的最后一步；去掉最后一步后，剩下的就是一条到达 \((x-a,y-b)\) 的合法路径。由于 \((a,b)\neq(0,0)\)，所以依赖永远只会指向左边、下方，或者同时向左下。状态图天然无环，因此动态规划是成立的。
真正需要仔细处理的是竖直步，因为它们满足 \(a=0\)，会留在同一列里。对于固定的列 \(x\)，先定义所有来自旧列的贡献：
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
这部分只依赖更早的列，所以可以先全部算好。然后当前列按 \(y\) 从小到大填表：
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
并且在原点 \((0,0)\) 额外加上空路径贡献 \(1\)。这样一来，原本二维的递推就被拆成了一个清晰的列扫描过程：先汇总所有横向前进步带来的贡献，再在同一列内处理竖直延伸。
设
$$M=\max\{a:(a,b)\in O\},$$
如果不存在这样的步，就约定 \(M=0\)。那么在计算第 \(x\) 列时，最多只会访问第 \(x-1,x-2,\dots,x-M\) 列。更早的列永远不会再被读到，因此没有必要保存整个 \((w+1)\times(h+1)\) 的表。只要把列按 \(M+1\) 取模循环复用，就能保证正确性，这就是环形缓冲区的数学依据。
此时矩形对角线长度为
$$R=\sqrt{3^2+4^2}=5,$$
所以只需考虑长度 \(1,2,3,5\) 这几个斐波那契数。可用步集合为
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$$
第 \(0\) 列只受竖直步影响，因此有
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
到第 \(1\) 列时，唯一的非竖直来源是 \((1,0)\)，所以 \(A_1(y)=D(0,y)\)。再加上同列竖直延伸后得到
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$$
第 \(2\) 列满足 \(A_2(y)=D(1,y)+D(0,y)\)，于是
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$$
第 \(3\) 列除了 \((1,0)\)、\((2,0)\)、\((3,0)\) 这些来源外，还会额外收到从原点一步走到 \((3,4)\) 的贡献。最终得到
$$D(3,4)=278,$$
这与实现中使用的小规模校验值完全一致。
C++、Python 和 Java 三种实现遵循同一条数学主线。首先生成所有不超过 \(R\) 的斐波那契数。接着对每个这样的长度扫描 \(a\)，检查 \(F_k^2-a^2\) 是否是完全平方，从而找出所有合法的 \((a,b)\) 对。完成排序和去重后，程序把纯竖直步与 \(x\) 正向推进的步分开存储，并记录最大的水平位移 \(M\)。
动态规划部分按列推进，从 \(x=0\) 一直到 \(x=w\)。每一列先用一个临时数组累加所有来自更早列的贡献，然后再按 \(y=0,1,\dots,h\) 的顺序填当前列，这样当前列中的竖直依赖在使用前就已经计算好了。C++ 与 Java 版本直接执行这套递推；Python 版本则复用同一份本地计算流程，并返回解析后的最终数值。整个过程中所有加法都在 \(10^9+7\) 模下进行。
设 \(s_O=|O|\)、\(s_V=|V|\)，以及 \(M=\max\{a:(a,b)\in O\}\)。生成斐波那契表需要 \(O(\log R)\) 时间。候选步的枚举成本为
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$$
由于斐波那契数增长很快，这部分通常远小于主动态规划。主过程里，每一列都要对所有非竖直步扫描一次有效的 \(y\) 区间，再对所有竖直步做一次同列递推，因此总时间为
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr),$$
空间复杂度为
$$O\bigl((M+1)(h+1)\bigr),$$
另加一个长度为 \(h+1\) 的临时数组。
Нужно посчитать количество направленных путей по решетке из \((0,0)\) в \((w,h)\). Каждый шаг представляет собой ненулевой вектор \((a,b)\in \mathbb{Z}_{\ge 0}^2\), а его евклидова длина обязана быть числом Фибоначчи. Иными словами, допустимый шаг удовлетворяет условию
$$a^2+b^2=F_k^2$$
для некоторого числа Фибоначчи \(F_k\). Ответ требуется по модулю \(10^9+7\).
Сложность состоит в том, что множество шагов нерегулярно. Горизонтальные и вертикальные прыжки длины Фибоначчи появляются всегда, если помещаются в прямоугольник. Косые шаги возникают только тогда, когда число Фибоначчи одновременно является гипотенузой прямоугольного треугольника с целыми катетами, например \((3,4)\) для длины \(5\).
Обозначим через \(D(x,y)\) число допустимых путей из начала координат в точку \((x,y)\). Решение состоит из двух частей: сначала перечисляется весь набор допустимых шагов, затем по этой структуре вычисляется ациклическое динамическое программирование на решетке.
Любой используемый шаг должен удовлетворять неравенствам \(0\le a\le w\) и \(0\le b\le h\). Поэтому его длина не может превосходить диагональ целевого прямоугольника:
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
Значит, имеют смысл только числа Фибоначчи \(F_k\le R\). Это сразу делает геометрическую подготовку компактной, потому что последовательность Фибоначчи растет экспоненциально.
Введем множество
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ для некоторого } F_k\le R\right\}.$$
Для каждого подходящего числа Фибоначчи \(F_k\) мы ищем все неотрицательные целочисленные точки на окружности \(a^2+b^2=F_k^2\), которые также удовлетворяют ограничениям \(a\le w\) и \(b\le h\). Осевая пара \((F_k,0)\) и \((0,F_k)\) возникает автоматически, если не выходит за границы. Остальные шаги приходят из пифагоровых троек.
После сортировки и удаления повторов множество \(S\) разбивается на
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$$
Здесь \(V\) содержит чисто вертикальные шаги, а \(O\) содержит все шаги с положительным продвижением по оси \(x\), включая горизонтальные.
Количество путей удовлетворяет формуле
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
Это верно потому, что у любого допустимого пути в \((x,y)\) есть однозначно определенный последний шаг; если его удалить, останется допустимый путь в \((x-a,y-b)\). Так как \(a\) и \(b\) не могут одновременно быть нулем, любая зависимость ведет строго влево, вниз или влево-вниз. Следовательно, граф состояний не содержит циклов.
Единственная тонкость связана с вертикальными шагами: у них \(a=0\), поэтому они остаются в том же столбце. Для фиксированного \(x\) сначала определим вклад всех переходов из предыдущих столбцов:
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
Когда \(A_x(y)\) уже известно, текущий столбец можно вычислять снизу вверх по формуле
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
добавляя еще \(1\) в точке \((0,0)\) за пустой путь. Тем самым двумерная рекурсия превращается в аккуратный проход по столбцу: сначала собираются все переходы из более ранних столбцов, а затем внутри текущего столбца разрешаются вертикальные зависимости в порядке возрастания \(y\).
Пусть
$$M=\max\{a:(a,b)\in O\},$$
а если таких шагов нет, считаем \(M=0\). Тогда для вычисления столбца \(x\) нужны только столбцы \(x-1,x-2,\dots,x-M\). Более старые данные уже никогда не будут использованы. Поэтому весь массив столбцов хранить не нужно: достаточно сохранять их по модулю \(M+1\). Именно это и оправдывает кольцевой буфер.
Здесь длина диагонали равна
$$R=\sqrt{3^2+4^2}=5,$$
поэтому рассматриваются длины Фибоначчи \(1,2,3,5\). Допустимые шаги равны
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$$
Столбец \(x=0\) определяется только вертикальными переходами:
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
Для \(x=1\) единственным не вертикальным источником является \((1,0)\), то есть \(A_1(y)=D(0,y)\). После учета вертикальных продолжений получаем
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$$
Для \(x=2\) имеем \(A_2(y)=D(1,y)+D(0,y)\), откуда следует
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$$
В столбце \(x=3\) добавляются вклады от \((1,0)\), \((2,0)\), \((3,0)\) и диагонального шага \((3,4)\) из начала координат. В итоге
$$D(3,4)=278,$$
что совпадает с малым контрольным значением, используемым в реализации.
Реализации на C++, Python и Java используют одну и ту же математическую схему. Сначала они генерируют все числа Фибоначчи до \(R\). Затем для каждого такого числа перебирают \(a\) и проверяют, является ли \(F_k^2-a^2\) точным квадратом; так перечисляются все допустимые пары \((a,b)\). После сортировки и удаления повторов вертикальные шаги хранятся отдельно от шагов с положительным сдвигом по \(x\), а также запоминается максимальная горизонтальная компонента \(M\).
Далее динамическое программирование проходит по столбцам от \(x=0\) до \(x=w\). Для каждого столбца временный массив сначала собирает все вклады из предыдущих столбцов. Затем сам столбец заполняется снизу вверх, так что вертикальные зависимости внутри столбца уже вычислены к моменту обращения к ним. Версии на C++ и Java выполняют эту рекурсию напрямую, а версия на Python повторно использует то же нативное вычисление и возвращает разобранное итоговое число. Все операции выполняются по модулю \(10^9+7\).
Пусть \(s_O=|O|\), \(s_V=|V|\), \(M=\max\{a:(a,b)\in O\}\). Построение списка Фибоначчи требует \(O(\log R)\) времени. Перебор кандидатов для шагов стоит
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$$
что умеренно благодаря быстрому росту последовательности Фибоначчи. Основную стоимость дает DP по сетке: в каждом столбце для всех не вертикальных шагов просматривается допустимый диапазон \(y\), после чего в том же столбце обрабатываются все вертикальные шаги. Поэтому суммарное время равно
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr),$$
а память составляет
$$O\bigl((M+1)(h+1)\bigr),$$
плюс один временный массив длины \(h+1\).
نريد عدّ المسارات الشبكية الموجّهة من \((0,0)\) إلى \((w,h)\). كل خطوة هي متجه غير صفري \((a,b)\in \mathbb{Z}_{\ge 0}^2\)، ويجب أن يكون طولها الإقليدي عددًا من أعداد فيبوناتشي. أي إن كل خطوة مسموحة تحقق
$$a^2+b^2=F_k^2$$
لعدد فيبوناتشي ما \(F_k\). ويُطلب الناتج بترديد \(10^9+7\).
الصعوبة الأساسية أن مجموعة الخطوات ليست منتظمة. القفزات الأفقية والرأسية ذات الأطوال الفيبوناتشية تظهر كلما بقيت داخل المستطيل، أما الخطوات المائلة فلا تظهر إلا عندما يكون عدد فيبوناتشي نفسه وترًا لمثلث قائم بأضلاع صحيحة، مثل \((3,4)\) عندما يكون الطول \(5\).
لنرمز بـ \(D(x,y)\) إلى عدد المسارات المسموح بها من الأصل إلى النقطة \((x,y)\). يتكوّن الحل من مرحلتين: أولًا نحصر كل متجهات الخطوات الممكنة، ثم نحسب برمجة ديناميكية لا تحتوي على دورات فوق الشبكة.
أي خطوة قابلة للاستعمال يجب أن تحقق \(0\le a\le w\) و\(0\le b\le h\). لذلك لا يمكن أن يتجاوز طولها قطر المستطيل الهدف:
$$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$$
إذن لا نحتاج إلا إلى أعداد فيبوناتشي التي تحقق \(F_k\le R\). وهذه ملاحظة مهمة لأن متتالية فيبوناتشي تنمو بسرعة أسية، وبالتالي يبقى عدد الأطوال التي نفحصها صغيرًا.
نعرّف مجموعة الخطوات
$$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ for some } F_k\le R\right\}.$$
لكل عدد فيبوناتشي مناسب \(F_k\)، نبحث عن كل النقاط الصحيحة غير السالبة على الدائرة \(a^2+b^2=F_k^2\)، مع الشرطين الإضافيين \(a\le w\) و\(b\le h\). الخطوتان المحوريتان \((F_k,0)\) و\((0,F_k)\) تظهران تلقائيًا متى كانتا داخل الحدود، أما الخطوات الأخرى فتأتي من ثلاثيات فيثاغورس.
بعد الفرز وإزالة التكرار نقسم \(S\) إلى
$$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$$
المجموعة \(V\) تحتوي فقط على الخطوات الرأسية الخالصة، بينما \(O\) تحتوي كل خطوة تحقق تقدمًا موجبًا في اتجاه \(x\)، بما في ذلك الخطوات الأفقية.
عدد المسارات يحقق العلاقة
$$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$$
السبب مباشر: كل مسار صالح يصل إلى \((x,y)\) يملك خطوة أخيرة محددة، وإذا حذفناها تبقى لدينا مسار صالح إلى \((x-a,y-b)\). وبما أن \(a\) و\(b\) لا يمكن أن يكونا صفرين معًا، فإن كل اعتماد يتجه دائمًا إلى اليسار أو الأسفل أو كليهما. لذلك يكون مخطط الحالات غير دوري.
النقطة الدقيقة الوحيدة هي الخطوات الرأسية، لأنها تحقق \(a=0\) وتبقى داخل العمود نفسه. لذلك، ولأجل عمود ثابت \(x\)، نعرّف أولًا مجموع المساهمات القادمة من الأعمدة السابقة:
$$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$$
بعد معرفة \(A_x(y)\)، يمكن ملء العمود الحالي من الأسفل إلى الأعلى وفق
$$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$$
مع إضافة \(1\) إضافية عند \((0,0)\) لتمثيل المسار الفارغ. وهكذا تتحول علاقة العودية الثنائية الأبعاد إلى مسح عمودي منظم: أولًا نحسب كل ما يأتي من خطوات تتقدم أفقيًا، ثم نعالج الاستمرار الرأسي داخل العمود نفسه بترتيب \(y\) المتصاعد.
لتكن
$$M=\max\{a:(a,b)\in O\},$$
ومع عدم وجود مثل هذه الخطوات نأخذ \(M=0\). عند حساب العمود \(x\)، لا يمكن الرجوع إلا إلى الأعمدة \(x-1,x-2,\dots,x-M\). أما الأعمدة الأقدم من ذلك فلن تُستخدم مرة أخرى. لذا لا حاجة إلى تخزين الجدول كاملًا؛ يكفي إعادة استخدام الأعمدة بترديد \(M+1\). وهذه هي الفكرة الرياضية خلف المخزن الدائري.
في هذه الحالة يكون طول القطر
$$R=\sqrt{3^2+4^2}=5,$$
ولذلك نحتاج فقط إلى أطوال فيبوناتشي \(1,2,3,5\). مجموعة الخطوات المسموح بها هي
$$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$$
العمود \(x=0\) يعتمد فقط على الخطوات الرأسية، ومن ثم
$$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$$
عند \(x=1\)، المصدر غير الرأسي الوحيد هو \((1,0)\)، أي إن \(A_1(y)=D(0,y)\). وبعد إضافة الاستمرارات الرأسية نحصل على
$$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$$
أما عند \(x=2\)، فلدينا \(A_2(y)=D(1,y)+D(0,y)\)، وبالتالي
$$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$$
وفي العمود \(x=3\) تضاف مساهمات \((1,0)\) و\((2,0)\) و\((3,0)\) وكذلك الخطوة القطرية \((3,4)\) القادمة مباشرة من الأصل. في النهاية نحصل على
$$D(3,4)=278,$$
وهو نفس مقدار التحقق الصغير المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava البنية الرياضية نفسها. أولًا تُولّد جميع أعداد فيبوناتشي حتى \(R\). بعد ذلك يُفحص كل طول بحيث تُجرَّب قيم \(a\)، ويُتحقق مما إذا كان \(F_k^2-a^2\) مربعًا كاملًا، وبذلك تُستخرج جميع الأزواج المسموح بها \((a,b)\). وبعد الفرز وإزالة التكرار تُخزن الخطوات الرأسية منفصلة عن الخطوات ذات التقدم الموجب في \(x\)، مع تسجيل أكبر إزاحة أفقية \(M\).
ثم تسير البرمجة الديناميكية عمودًا بعد عمود من \(x=0\) حتى \(x=w\). في كل عمود، تُجمِّع مصفوفة مؤقتة كل المساهمات القادمة من الأعمدة السابقة. بعد ذلك يُملأ العمود نفسه بترتيب \(y=0,1,\dots,h\)، بحيث تكون الاعتمادات الرأسية داخل العمود قد حُسبت بالفعل عند الحاجة إليها. تنفذ نسختا C++ وJava هذه العودية مباشرة، بينما تعيد نسخة Python استخدام الحساب المحلي نفسه وتستخرج القيمة النهائية. جميع العمليات الحسابية تتم بترديد \(10^9+7\).
لنرمز إلى \(s_O=|O|\) و\(s_V=|V|\) و\(M=\max\{a:(a,b)\in O\}\). توليد قائمة فيبوناتشي يكلف \(O(\log R)\)، أما تعداد الخطوات المرشحة فيكلف
$$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$$
وهو مقدار محدود لأن أعداد فيبوناتشي تنمو بسرعة. الجزء المسيطر هو البرمجة الديناميكية على الشبكة: في كل عمود نطبّق جميع الخطوات غير الرأسية على مجال \(y\) الصالح، ثم نعالج جميع الخطوات الرأسية في المسح الصاعد. إذن الزمن الكلي هو
$$O\bigl((w+1)(h+1)(s_O+s_V)\bigr),$$
بينما استهلاك الذاكرة هو
$$O\bigl((M+1)(h+1)\bigr),$$
مع مصفوفة مؤقتة إضافية طولها \(h+1\).