Problem 940 asks for values of a two-dimensional recurrence \(A(m,n)\) at Fibonacci-indexed coordinates \((F_i,F_j)\), summed over all \(2 \le i,j \le 50\), with the final result reduced modulo \(1123581313\).
The implementations show that this surface is generated by two fixed \(2\times 2\) matrices. That matrix viewpoint is enough to reconstruct the actual recurrence, the boundary data, and an efficient evaluation strategy for indices as large as \(F_{50}=12586269025\) without ever filling a gigantic grid.
Introduce the matrices and vectors
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}.$$
The scalar quantity being sampled is
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0.$$
Everything important in the problem comes from the relations between \(C\) and \(M\).
Start with the row \(m=0\). If we write
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0,$$
then \(u_n\) is just the first component of \(C^n v_0\). Let \(C^n v_0=(x_n,y_n)^{\mathsf T}\). Multiplying once more by \(C\) gives
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n,$$
so the first component satisfies
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1.$$
The first values are therefore
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
This single one-dimensional recurrence is the boundary from which the whole two-dimensional array can be generated.
The key identity is
$$M=I+C.$$
Using that directly inside the definition of \(A(m,n)\),
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1).$$
This is the genuinely two-dimensional recurrence. Moving one step in the \(m\)-direction means taking the current value and adding the value one column further in the \(n\)-direction. Once the boundary row \(A(0,n)\) is known, repeated use of this rule fills every higher row.
The matrix \(C\) satisfies its characteristic equation
$$C^2=C+3I.$$
Multiplying on the left by \(e_1^{\mathsf T}M^m\) and on the right by \(C^n v_0\) gives a vertical recurrence valid in every row:
$$A(m,n+2)=A(m,n+1)+3A(m,n).$$
Likewise \(M\) has characteristic polynomial \(x^2-3x-1\), so
$$M^2=3M+I,$$
and therefore
$$A(m+2,n)=3A(m+1,n)+A(m,n).$$
The surface is thus anisotropic but perfectly consistent: one recurrence governs vertical motion and another governs horizontal motion.
Because \(M=I+C\) is a polynomial in \(C\), the two matrices commute. Expanding \((I+C)^m\) shows
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}.$$
So every row is a binomial transform of the boundary sequence \(u_n\). The implementations do not explicitly expand this formula, but it explains why the matrix model and the recurrence model describe exactly the same object.
Using \(u_0=0\), \(u_1=1\), \(u_2=1\), \(u_3=4\), the first rows become
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
For instance, \(A(2,2)=16\) can be verified in two independent ways. From the horizontal rule,
$$A(2,2)=A(1,2)+A(1,3)=5+11=16.$$
From the vertical rule,
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
This is a compact check that both recurrences are describing the same table.
Let \(F_0=0\), \(F_1=1\), and \(F_{r+2}=F_{r+1}+F_r\). The target quantity is
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j),$$
with the final answer being \(S(50)\pmod{1123581313}\).
These indices grow very quickly, so it is not practical to build the grid cell by cell up to \(m,n=F_{50}\). Matrix exponentiation reaches \(M^{F_i}\) and \(C^{F_j}\) in logarithmic time in the exponent, which is exactly what makes the computation feasible.
The C++, Python, and Java implementations first generate the Fibonacci numbers up to the requested limit. They then apply binary exponentiation under the modulus \(1123581313\) to the two fixed \(2\times 2\) matrices \(M\) and \(C\).
For each Fibonacci index \(F_i\), the implementation stores two reusable objects: the full matrix \(M^{F_i}\) and the vector \(C^{F_i}v_0\). Once those have been prepared, a term of the double sum is only a first-row dot product:
$$A(F_i,F_j)=\bigl(\text{first row of }M^{F_i}\bigr)\cdot\bigl(C^{F_j}v_0\bigr).$$
This avoids repeating expensive exponentiations inside the final nested loop. The last pass therefore consists only of modular additions and multiplications on already cached 2-component data.
One implementation also checks small identities such as \(A(1,1)=2\), \(A(2,2)=16\), \(S(3)=30\), and \(S(5)=10396\), which match the recurrence table above.
Generating the Fibonacci list costs \(O(k)\). The code then computes \(k-1\) powers of \(M\) and \(k-1\) powers of \(C\). Each power is obtained by exponentiation by squaring, so each one costs \(O(\log F_k)\) multiplications of \(2\times 2\) matrices, and each such multiplication has constant cost.
The preprocessing phase is therefore \(O(k\log F_k)\). The final accumulation over all ordered pairs \((i,j)\) with \(2\le i,j\le k\) is \(O(k^2)\). Memory usage is \(O(k)\) for the Fibonacci values, the cached matrices, and the cached vectors. For the actual target \(k=50\), these costs are very small.
Problem 940 verlangt Werte einer zweidimensionalen Rekurrenz \(A(m,n)\) an Fibonacci-indizierten Stellen \((F_i,F_j)\). Diese Werte werden fur alle \(2 \le i,j \le 50\) aufsummiert, und das Endergebnis wird modulo \(1123581313\) genommen.
Die Implementierungen zeigen, dass die gesamte Flache durch zwei feste \(2\times 2\)-Matrizen erzeugt wird. Diese Darstellung reicht aus, um die eigentliche Rekurrenz, die Randwerte und eine effiziente Auswertungsmethode fur Indizes der Grose \(F_{50}=12586269025\) herzuleiten, ohne ein riesiges Gitter aufzubauen.
Wir fuhren die Matrizen und Vektoren
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}$$
ein und definieren
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0.$$
Alle wesentlichen Eigenschaften der Aufgabe folgen aus den Beziehungen zwischen \(C\) und \(M\).
Betrachte zuerst die Zeile \(m=0\). Mit
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0$$
ist \(u_n\) gerade die erste Komponente von \(C^n v_0\). Schreibe \(C^n v_0=(x_n,y_n)^{\mathsf T}\). Eine weitere Multiplikation mit \(C\) liefert
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n,$$
also erfullt die erste Komponente
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1.$$
Die ersten Werte sind damit
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
Diese eindimensionale Folge ist die Randinformation, aus der die gesamte zweidimensionale Tabelle entsteht.
Die Schlusselidentitat lautet
$$M=I+C.$$
Setzt man das direkt in die Definition ein, so ergibt sich
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1).$$
Das ist die eigentliche zweidimensionale Rekurrenz. Ein Schritt in \(m\)-Richtung ersetzt den aktuellen Wert durch die Summe aus diesem Wert und dem Wert eine Spalte weiter in \(n\)-Richtung. Kennt man die Randzeile \(A(0,n)\), dann kann man damit alle hoheren Zeilen erzeugen.
Die Matrix \(C\) erfullt ihre charakteristische Gleichung
$$C^2=C+3I.$$
Links mit \(e_1^{\mathsf T}M^m\) und rechts mit \(C^n v_0\) multipliziert ergibt das fur jede Zeile
$$A(m,n+2)=A(m,n+1)+3A(m,n).$$
Ebenso besitzt \(M\) das charakteristische Polynom \(x^2-3x-1\), also
$$M^2=3M+I,$$
und daher
$$A(m+2,n)=3A(m+1,n)+A(m,n).$$
Die Flache lasst sich also in beiden Richtungen fortsetzen, allerdings mit unterschiedlichen eindimensionalen Rekurrenzen.
Weil \(M=I+C\) ein Polynom in \(C\) ist, kommutieren beide Matrizen. Durch Ausmultiplizieren von \((I+C)^m\) erhalt man
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}.$$
Jede Zeile ist also eine Binomialtransformierte der Randfolge \(u_n\). Die Implementierungen benutzen diese Formel nicht explizit, aber sie erklart, warum Matrixdarstellung und Rekurrenzdarstellung exakt dasselbe Objekt beschreiben.
Aus \(u_0=0\), \(u_1=1\), \(u_2=1\), \(u_3=4\) folgen die ersten Zeilen
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
Zum Beispiel kann \(A(2,2)=16\) auf zwei Arten gepruft werden. Horizontal gilt
$$A(2,2)=A(1,2)+A(1,3)=5+11=16,$$
und vertikal gilt
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
Damit sieht man direkt, dass beide Rekurrenzen dieselbe Tabelle beschreiben.
Seien \(F_0=0\), \(F_1=1\) und \(F_{r+2}=F_{r+1}+F_r\). Gesucht ist
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j),$$
wobei am Ende \(S(50)\pmod{1123581313}\) berechnet wird.
Diese Indizes wachsen sehr schnell. Deshalb ist es unpraktisch, die Tabelle Zelle fur Zelle bis \(m,n=F_{50}\) aufzubauen. Matrixpotenzierung erreicht \(M^{F_i}\) und \(C^{F_j}\) in logarithmischer Zeit bezuglich des Exponenten und macht die Rechnung dadurch moglich.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst die Fibonacci-Zahlen bis zur gewunschten Grenze. Danach wenden sie binare Exponentiation modulo \(1123581313\) auf die beiden festen \(2\times 2\)-Matrizen \(M\) und \(C\) an.
Zu jedem Fibonacci-Index \(F_i\) werden zwei wiederverwendbare Objekte gespeichert: die gesamte Matrix \(M^{F_i}\) und der Vektor \(C^{F_i}v_0\). Ist beides vorbereitet, dann ist ein Summand nur noch ein Skalarprodukt aus erster Zeile und Spaltenvektor:
$$A(F_i,F_j)=\bigl(\text{erste Zeile von }M^{F_i}\bigr)\cdot\bigl(C^{F_j}v_0\bigr).$$
Dadurch werden teure Potenzierungen im abschliesenden Doppelloop vermieden. Im letzten Durchlauf bleiben nur modulare Additionen und Multiplikationen auf bereits vorbereiteten 2-Komponenten-Daten ubrig.
Eine Implementierung pruft zusatzlich kleine Identitaten wie \(A(1,1)=2\), \(A(2,2)=16\), \(S(3)=30\) und \(S(5)=10396\). Diese Werte stimmen exakt mit der oben hergeleiteten Tabelle uberein.
Die Erzeugung der Fibonacci-Liste kostet \(O(k)\). Danach berechnet der Code \(k-1\) Potenzen von \(M\) und \(k-1\) Potenzen von \(C\). Jede Potenz wird mit Exponentiation by Squaring berechnet und benotigt daher \(O(\log F_k)\) Multiplikationen von \(2\times 2\)-Matrizen; jede solche Multiplikation hat konstanten Aufwand.
Die Vorverarbeitung hat somit Aufwand \(O(k\log F_k)\). Die anschliesende Summe uber alle geordneten Paare \((i,j)\) mit \(2\le i,j\le k\) kostet \(O(k^2)\). Der Speicherbedarf ist \(O(k)\) fur Fibonacci-Werte, zwischengespeicherte Matrizen und zwischengespeicherte Vektoren. Fur den tatsachlichen Zielwert \(k=50\) ist das sehr klein.
Problem 940, Fibonacci indekslerinde \((F_i,F_j)\) noktalarinda tanimlanan iki degiskenli bir yinelemenin \(A(m,n)\) degerlerini toplatir. Toplam, tum \(2 \le i,j \le 50\) ciftleri uzerinden alinır ve sonuc \(1123581313\) modunda verilir.
Uygulamalar, bu yuzeyin iki sabit \(2\times 2\) matris tarafindan uretildigini gosteriyor. Bu bakis acisi, hem gercek yinelemeyi hem de sinir kosullarini geri cikarmaya yeter; boylece \(F_{50}=12586269025\) gibi cok buyuk indeksler icin devasa bir tablo kurmadan hesap yapilabilir.
Su matris ve vektorleri tanimlayalim:
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}.$$
Orneklenen skaler buyukluk
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0$$
olarak verilir. Problemin matematigi, esas olarak \(C\) ile \(M\) arasindaki iliskiden cikar.
Ilk olarak \(m=0\) satirina bakalim. Eger
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0$$
dersek, \(u_n\) sadece \(C^n v_0\) vektorunun ilk bilesenidir. \(C^n v_0=(x_n,y_n)^{\mathsf T}\) yazarsak bir kez daha \(C\) ile carpmak
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n$$
verir; dolayisiyla ilk bilesen
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1$$
yinelemesini saglar. Ilk terimler
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
olur. Tum iki boyutlu tablo, bu tek boyutlu sinir dizisinden uretilir.
Temel ozdeslik
$$M=I+C$$
seklindedir. Bunu dogrudan tanima yerlestirince
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1)$$
elde edilir. Bu, problemin gercek iki boyutlu yinelemesidir. Yani \(m\) yonunde bir adim atmak, mevcut hucreye \(n\) yonunde bir sonraki hucreyi eklemek demektir. Sinir satiri \(A(0,n)\) bilindiginde, bu kural tum daha yuksek satirlari doldurur.
\(C\) matrisi kendi karakteristik denklemini saglar:
$$C^2=C+3I.$$
Soldan \(e_1^{\mathsf T}M^m\), sagdan \(C^n v_0\) ile carpilinca her satir icin
$$A(m,n+2)=A(m,n+1)+3A(m,n)$$
bulunur. Benzer bicimde \(M\) matrisi de \(x^2-3x-1\) karakteristik polinomuna sahiptir; dolayisiyla
$$M^2=3M+I,$$
ve bundan
$$A(m+2,n)=3A(m+1,n)+A(m,n)$$
cikar. Yuzey her iki yonde de ilerletilebilir, fakat iki yonun tek boyutlu yinelemeleri ayni degildir.
\(M=I+C\), \(C\)'nin bir polinomu oldugu icin bu iki matris komuttur. \((I+C)^m\) acilimi
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}$$
formulunu verir. Yani her satir, sinir dizisi \(u_n\)'nin bir binom donusumudur. Uygulamalar bu acilimi acikca kullanmaz, fakat matris modelinin ve yineleme modelinin ayni nesneyi anlattigini guzelce aciklar.
\(u_0=0\), \(u_1=1\), \(u_2=1\), \(u_3=4\) kullanildiginda ilk satirlar
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
olur. Ornegin \(A(2,2)=16\) iki farkli yoldan kontrol edilebilir. Yatay kuraldan
$$A(2,2)=A(1,2)+A(1,3)=5+11=16,$$
dikey kuraldan ise
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
Boylece her iki yinelemenin de ayni tabloyu tanimladigi gorulur.
\(F_0=0\), \(F_1=1\) ve \(F_{r+2}=F_{r+1}+F_r\) olsun. Hesaplanacak buyukluk
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j)$$
olup nihai hedef \(S(50)\pmod{1123581313}\)'dir.
Bu indeksler cok hizli buyudugu icin \(m,n=F_{50}\)'ye kadar hucre hucre ilerlemek pratik degildir. Matris us alma, \(M^{F_i}\) ve \(C^{F_j}\) degerlerine us cinsinden logaritmik zamanda ulasir; hesabi mumkun kilan nokta budur.
C++, Python ve Java uygulamalari once gerekli Fibonacci sayilarini uretir. Ardindan sabit \(2\times 2\) matrisler \(M\) ve \(C\) icin, \(1123581313\) modu altinda ikili us alma uygular.
Her Fibonacci indeksi \(F_i\) icin iki yeniden kullanilabilir nesne saklanir: tum \(M^{F_i}\) matrisi ve \(C^{F_i}v_0\) vektoru. Bunlar hazirlandiktan sonra bir toplam terimi yalnizca ilk satirla vektor arasindaki nokta carpimidir:
$$A(F_i,F_j)=\bigl(\text{\(M^{F_i}\)'nin ilk satiri}\bigr)\cdot\bigl(C^{F_j}v_0\bigr).$$
Boylece son cift dongu icinde tekrar tekrar pahali us alma yapmak gerekmez. Son asama, onceden hesaplanmis iki bilesenli veriler uzerinde moduler toplama ve carpma islemine iner.
Surumlerden biri ayrica \(A(1,1)=2\), \(A(2,2)=16\), \(S(3)=30\) ve \(S(5)=10396\) gibi kucuk dogrulamalari kontrol eder. Bu degerler yukaridaki yineleme tablosuyla birebir uyumludur.
Fibonacci listesini uretmek \(O(k)\) zaman alir. Daha sonra kod, \(M\) icin \(k-1\) us ve \(C\) icin \(k-1\) us hesaplar. Her us, exponentiation by squaring ile elde edilir; bu nedenle her biri \(O(\log F_k)\) tane \(2\times 2\) matris carpimi gerektirir ve bu carpimlarin her birinin maliyeti sabittir.
Dolayisiyla onisleme asamasi \(O(k\log F_k)\), son toplama asamasi ise \(2\le i,j\le k\) tum sirali ciftler uzerinden gecildigi icin \(O(k^2)\) olur. Bellek kullanimi, Fibonacci degerleri, onbelleklenmis matrisler ve onbelleklenmis vektorler icin \(O(k)\)'dir. Gercek hedef olan \(k=50\) icin bu maliyetler cok kucuktur.
El problema 940 pide evaluar una recurrencia bidimensional \(A(m,n)\) en coordenadas indexadas por Fibonacci \((F_i,F_j)\), sumar todos esos valores para \(2 \le i,j \le 50\) y reducir el resultado modulo \(1123581313\).
Las implementaciones muestran que toda la superficie esta generada por dos matrices fijas de tamano \(2\times 2\). Ese punto de vista matricial permite reconstruir la recurrencia real, las condiciones iniciales y una forma eficiente de trabajar con indices tan grandes como \(F_{50}=12586269025\) sin rellenar una tabla inmensa.
Introducimos las matrices y vectores
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}.$$
La cantidad escalar que se evalua es
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0.$$
Todo lo importante en el problema nace de las relaciones algebraicas entre \(C\) y \(M\).
Empezamos con la fila \(m=0\). Si definimos
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0,$$
entonces \(u_n\) es simplemente la primera componente de \(C^n v_0\). Escribiendo \(C^n v_0=(x_n,y_n)^{\mathsf T}\), una multiplicacion adicional por \(C\) produce
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n,$$
de modo que la primera componente satisface
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1.$$
Los primeros valores son
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
Esta sucesion unidimensional de borde es la base desde la cual se genera toda la tabla bidimensional.
La identidad clave es
$$M=I+C.$$
Al sustituirla en la definicion de \(A(m,n)\), obtenemos
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1).$$
Esta es la recurrencia realmente bidimensional. Un paso en la direccion \(m\) toma el valor actual y le suma el valor situado una columna mas adelante en la direccion \(n\). Una vez conocida la fila de borde \(A(0,n)\), esta regla construye todas las filas superiores.
La matriz \(C\) satisface su ecuacion caracteristica
$$C^2=C+3I.$$
Multiplicando por la izquierda por \(e_1^{\mathsf T}M^m\) y por la derecha por \(C^n v_0\), se obtiene una recurrencia vertical valida en cualquier fila:
$$A(m,n+2)=A(m,n+1)+3A(m,n).$$
Ademas, \(M\) tiene polinomio caracteristico \(x^2-3x-1\), asi que
$$M^2=3M+I,$$
y por tanto
$$A(m+2,n)=3A(m+1,n)+A(m,n).$$
La superficie puede avanzar en ambas direcciones, aunque con recurrencias unidimensionales diferentes.
Como \(M=I+C\) es un polinomio en \(C\), ambas matrices conmutan. Al expandir \((I+C)^m\) aparece
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}.$$
Cada fila es, por tanto, una transformada binomial de la sucesion de borde \(u_n\). Las implementaciones no desarrollan esta formula de manera explicita, pero sirve para ver que la descripcion matricial y la descripcion por recurrencias son exactamente la misma estructura.
Usando \(u_0=0\), \(u_1=1\), \(u_2=1\), \(u_3=4\), las primeras filas son
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
Por ejemplo, \(A(2,2)=16\) puede verificarse de dos maneras independientes. Horizontalmente,
$$A(2,2)=A(1,2)+A(1,3)=5+11=16.$$
Verticalmente,
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
Es una comprobacion compacta de que ambas recurrencias generan la misma tabla.
Sea \(F_0=0\), \(F_1=1\) y \(F_{r+2}=F_{r+1}+F_r\). La cantidad buscada es
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j),$$
y el objetivo final es \(S(50)\pmod{1123581313}\).
Estos indices crecen muy deprisa. Por eso no es realista construir la tabla celda a celda hasta \(m,n=F_{50}\). La exponenciacion matricial alcanza \(M^{F_i}\) y \(C^{F_j}\) en tiempo logaritmico respecto del exponente, y esa es precisamente la idea que vuelve viable el calculo.
Las implementaciones en C++, Python y Java generan primero los numeros de Fibonacci hasta el limite pedido. Despues aplican exponenciacion binaria, siempre modulo \(1123581313\), a las dos matrices fijas \(M\) y \(C\).
Para cada indice de Fibonacci \(F_i\), la implementacion guarda dos objetos reutilizables: la matriz completa \(M^{F_i}\) y el vector \(C^{F_i}v_0\). Una vez hecho eso, cada termino de la suma doble se reduce a un producto escalar entre la primera fila y ese vector:
$$A(F_i,F_j)=\bigl(\text{primera fila de }M^{F_i}\bigr)\cdot\bigl(C^{F_j}v_0\bigr).$$
Asi se evita repetir exponenciaciones costosas dentro del bucle final. El recorrido final solo necesita sumas y multiplicaciones modulares sobre datos de 2 componentes ya preparados.
Una de las implementaciones tambien verifica pequenas identidades como \(A(1,1)=2\), \(A(2,2)=16\), \(S(3)=30\) y \(S(5)=10396\), exactamente las mismas cifras que aparecen en la tabla derivada arriba.
Generar la lista de Fibonacci cuesta \(O(k)\). Despues, el codigo calcula \(k-1\) potencias de \(M\) y \(k-1\) potencias de \(C\). Cada potencia se obtiene mediante exponenciacion por cuadrados, asi que cada una requiere \(O(\log F_k)\) multiplicaciones de matrices \(2\times 2\), y cada multiplicacion tiene coste constante.
Por tanto, la fase de precomputo es \(O(k\log F_k)\). La acumulacion final sobre todos los pares ordenados \((i,j)\) con \(2\le i,j\le k\) es \(O(k^2)\). El uso de memoria es \(O(k)\) para los Fibonacci, las matrices almacenadas y los vectores almacenados. Para el caso real \(k=50\), estos costes son muy pequenos.
第 940 题要求在 Fibonacci 下标位置 \((F_i,F_j)\) 上取二维递推 \(A(m,n)\) 的值，并对所有 \(2 \le i,j \le 50\) 的组合求和，最后对 \(1123581313\) 取模。
从实现可以看出，这个二维数表并不是靠逐格递推到巨大坐标，而是由两个固定的 \(2\times 2\) 矩阵生成。这个矩阵视角足以恢复题目真正的递推关系、边界条件以及高效算法，因此即使 \(F_{50}=12586269025\) 这么大，也不需要建立一个天文规模的表。
先引入下面的矩阵与向量：
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}.$$
题目实际取用的标量函数是
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0.$$
问题中的所有结构，都是从 \(C\) 与 \(M\) 的代数关系推出来的。
先看最底部一行 \(m=0\)。定义
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0,$$
那么 \(u_n\) 就是向量 \(C^n v_0\) 的第一分量。设
$$C^n v_0=(x_n,y_n)^{\mathsf T},$$
再乘一次 \(C\) 就得到
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n.$$
于是第一分量满足
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1.$$
前几项因此是
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
这条一维边界序列，就是整个二维表面的起点。
最关键的恒等式是
$$M=I+C.$$
把它直接代入 \(A(m,n)\) 的定义：
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1).$$
这就是题目的核心二维递推。也就是说，在 \(m\) 方向向前走一步，等于把当前格子的值与 \(n\) 方向下一格的值相加。只要知道边界行 \(A(0,n)\)，不断应用这条规则就能生成更高的各行。
矩阵 \(C\) 满足自己的特征方程
$$C^2=C+3I.$$
左乘 \(e_1^{\mathsf T}M^m\)、右乘 \(C^n v_0\) 后，可得每一行都满足的纵向递推：
$$A(m,n+2)=A(m,n+1)+3A(m,n).$$
另一方面，\(M\) 的特征多项式是 \(x^2-3x-1\)，因此
$$M^2=3M+I,$$
于是横向也有
$$A(m+2,n)=3A(m+1,n)+A(m,n).$$
所以这个二维表面虽然在两个方向上的一维递推系数不同，但整体完全一致。
因为 \(M=I+C\) 是 \(C\) 的多项式，所以 \(M\) 与 \(C\) 可交换。展开 \((I+C)^m\) 可得
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}.$$
换句话说，每一行都是边界序列 \(u_n\) 的一个二项变换。实现里并没有显式把公式写成这样，但这个观察清楚地说明了矩阵模型与递推模型其实是同一个对象的两种写法。
利用 \(u_0=0\)、\(u_1=1\)、\(u_2=1\)、\(u_3=4\)，可以得到前几行：
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
例如 \(A(2,2)=16\) 可以从两条递推同时验证。按横向规则，
$$A(2,2)=A(1,2)+A(1,3)=5+11=16.$$
按纵向规则，
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
这个小例子很好地说明了两种递推完全兼容。
设 \(F_0=0\)、\(F_1=1\)、\(F_{r+2}=F_{r+1}+F_r\)。题目要求计算
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j),$$
最终目标是 \(S(50)\pmod{1123581313}\)。
由于 Fibonacci 下标增长极快，逐格推到 \(m,n=F_{50}\) 显然不现实。矩阵快速幂可以在对数时间内直接得到 \(M^{F_i}\) 和 \(C^{F_j}\)，这正是算法可行的关键。
C++、Python 和 Java 实现都会先生成所需的 Fibonacci 数列，然后在模 \(1123581313\) 下对两个固定的 \(2\times 2\) 矩阵 \(M\) 与 \(C\) 使用二进制快速幂。
对于每个 Fibonacci 下标 \(F_i\)，实现都会缓存两个可复用对象：完整的矩阵 \(M^{F_i}\) 以及向量 \(C^{F_i}v_0\)。这样一来，双重求和中的单个项就只剩下一次“第一行与列向量”的点积：
$$A(F_i,F_j)=\bigl(\text{\(M^{F_i}\) 的第一行}\bigr)\cdot\bigl(C^{F_j}v_0\bigr).$$
这样就避免了在最终双重循环内部重复做昂贵的矩阵幂计算。最后一轮累加只涉及已经准备好的 2 维数据上的模加法与模乘法。
其中一个实现还会检查一些小规模恒等式，例如 \(A(1,1)=2\)、\(A(2,2)=16\)、\(S(3)=30\)、\(S(5)=10396\)。这些数值与上面的递推表完全一致。
生成 Fibonacci 列表需要 \(O(k)\) 时间。随后代码分别计算 \(k-1\) 个 \(M\) 的幂和 \(k-1\) 个 \(C\) 的幂。每个幂都通过快速幂完成，因此每次需要 \(O(\log F_k)\) 次 \(2\times 2\) 矩阵乘法，而每次矩阵乘法的代价是常数。
所以预处理阶段是 \(O(k\log F_k)\)，最终对所有满足 \(2\le i,j\le k\) 的有序对求和需要 \(O(k^2)\)。内存复杂度是 \(O(k)\)，用于存放 Fibonacci 数、缓存矩阵和缓存向量。对于实际目标 \(k=50\)，这些开销都非常小。
В задаче 940 нужно вычислить значения двумерной рекуррентной таблицы \(A(m,n)\) в точках \((F_i,F_j)\), где \(F_i\) и \(F_j\) являются числами Фибоначчи, просуммировать их по всем \(2 \le i,j \le 50\) и взять результат по модулю \(1123581313\).
Из реализаций видно, что вся поверхность задается двумя фиксированными матрицами размера \(2\times 2\). Такой взгляд сразу восстанавливает настоящую рекурсию, граничные данные и эффективный способ работать с индексами масштаба \(F_{50}=12586269025\), не строя гигантскую таблицу целиком.
Введем матрицы и векторы
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}.$$
Скалярная величина, которая реально используется в задаче, имеет вид
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0.$$
Все содержательные свойства задачи следуют из алгебраических связей между \(C\) и \(M\).
Начнем со строки \(m=0\). Обозначим
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0.$$
Тогда \(u_n\) - это просто первая компонента вектора \(C^n v_0\). Если записать
$$C^n v_0=(x_n,y_n)^{\mathsf T},$$
то еще одно умножение на \(C\) дает
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n,$$
а значит первая компонента удовлетворяет рекурсии
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1.$$
Первые значения таковы:
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
Именно эта одномерная последовательность играет роль границы, из которой вырастает вся двумерная таблица.
Ключевое тождество имеет вид
$$M=I+C.$$
Подставляя его непосредственно в определение \(A(m,n)\), получаем
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1).$$
Это и есть подлинная двумерная рекурсия задачи. Один шаг в направлении \(m\) означает, что к текущей ячейке прибавляется значение из следующей колонки по направлению \(n\). Как только известна граничная строка \(A(0,n)\), это правило строит все остальные строки.
Матрица \(C\) удовлетворяет своему характеристическому уравнению
$$C^2=C+3I.$$
Умножая слева на \(e_1^{\mathsf T}M^m\) и справа на \(C^n v_0\), получаем вертикальную рекурсию, справедливую в любой строке:
$$A(m,n+2)=A(m,n+1)+3A(m,n).$$
Матрица \(M\) имеет характеристический многочлен \(x^2-3x-1\), поэтому
$$M^2=3M+I,$$
и отсюда следует
$$A(m+2,n)=3A(m+1,n)+A(m,n).$$
Значит, поверхность можно продолжать в обоих направлениях, но одномерные правила по горизонтали и вертикали различаются.
Поскольку \(M=I+C\) является многочленом от \(C\), эти матрицы коммутируют. Раскрывая \((I+C)^m\), получаем
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}.$$
Итак, каждая строка является биномиальным преобразованием граничной последовательности \(u_n\). Реализации не раскрывают формулу именно так, но она хорошо объясняет, почему матричное описание и рекуррентное описание представляют один и тот же объект.
Из \(u_0=0\), \(u_1=1\), \(u_2=1\), \(u_3=4\) получаем первые строки
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
Например, \(A(2,2)=16\) легко проверить двумя способами. По горизонтальной рекурсии
$$A(2,2)=A(1,2)+A(1,3)=5+11=16,$$
а по вертикальной рекурсии
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
Это короткая, но наглядная проверка согласованности обеих рекурсий.
Пусть \(F_0=0\), \(F_1=1\), \(F_{r+2}=F_{r+1}+F_r\). Тогда искомая сумма равна
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j),$$
а конечная цель задачи - вычислить \(S(50)\pmod{1123581313}\).
Индексы Фибоначчи растут очень быстро, поэтому строить таблицу по клеткам до \(m,n=F_{50}\) неразумно. Матричное возведение в степень позволяет получить \(M^{F_i}\) и \(C^{F_j}\) за логарифмическое время по величине показателя, и именно это делает вычисление практичным.
Реализации на C++, Python и Java сначала генерируют нужные числа Фибоначчи. Затем они применяют бинарное возведение в степень по модулю \(1123581313\) к двум фиксированным матрицам \(M\) и \(C\) размера \(2\times 2\).
Для каждого индекса \(F_i\) сохраняются два переиспользуемых объекта: полная матрица \(M^{F_i}\) и вектор \(C^{F_i}v_0\). После этого любой член двойной суммы становится обычным скалярным произведением первой строки на вектор:
$$A(F_i,F_j)=\bigl(\text{первая строка }M^{F_i}\bigr)\cdot\bigl(C^{F_j}v_0\bigr).$$
Это избавляет от повторного возведения в степень внутри финального вложенного цикла. На последнем проходе остаются только модульные сложения и умножения над уже подготовленными двухкомпонентными данными.
В одной из реализаций дополнительно проверяются малые тождества \(A(1,1)=2\), \(A(2,2)=16\), \(S(3)=30\) и \(S(5)=10396\). Эти значения точно совпадают с таблицей, полученной выше.
Построение списка чисел Фибоначчи занимает \(O(k)\). Затем код вычисляет \(k-1\) степеней матрицы \(M\) и \(k-1\) степеней матрицы \(C\). Каждая степень получается методом быстрого возведения, поэтому требует \(O(\log F_k)\) умножений матриц \(2\times 2\), а стоимость каждого такого умножения постоянна.
Следовательно, этап предварительных вычислений имеет сложность \(O(k\log F_k)\). Финальная сумма по всем упорядоченным парам \((i,j)\) при \(2\le i,j\le k\) стоит \(O(k^2)\). Память составляет \(O(k)\): для чисел Фибоначчи, кэшированных матриц и кэшированных векторов. Для реального значения \(k=50\) это очень маленькие затраты.
تطلب المسألة 940 حساب قيم علاقة عودية ثنائية البعد \(A(m,n)\) عند الاحداثيات المفهرسة باعداد فيبوناتشي \((F_i,F_j)\)، ثم جمع هذه القيم لكل \(2 \le i,j \le 50\)، واخذ النتيجة النهائية بترديد \(1123581313\).
توضح التطبيقات ان هذا السطح العددي لا يُبنى خلية بعد خلية حتى يصل الى مؤشرات هائلة، بل يُولد بواسطة مصفوفتين ثابتتين من الحجم \(2\times 2\). هذا المنظور المصفوفي يكشف العلاقة العودية الحقيقية، والبيانات الحدية، والطريقة الفعالة للتعامل مع فهارس كبيرة جدا مثل \(F_{50}=12586269025\) من دون تكوين جدول ضخم.
نعرّف المصفوفتين والمتجهين التاليين:
$$C=\begin{pmatrix}0&1\\3&1\end{pmatrix},\qquad M=\begin{pmatrix}1&1\\3&2\end{pmatrix},\qquad v_0=\begin{pmatrix}0\\1\end{pmatrix},\qquad e_1=\begin{pmatrix}1\\0\end{pmatrix}.$$
والكمية العددية التي تُؤخذ منها القيم هي
$$A(m,n)=e_1^{\mathsf T} M^m C^n v_0.$$
كل البنية الرياضية في المسألة تخرج من العلاقات الجبرية بين \(C\) و\(M\).
لنبدأ بالصف \(m=0\). اذا كتبنا
$$u_n=A(0,n)=e_1^{\mathsf T} C^n v_0,$$
فان \(u_n\) هو ببساطة المركبة الاولى للمتجه \(C^n v_0\). لنكتب
$$C^n v_0=(x_n,y_n)^{\mathsf T}.$$
عند الضرب مرة اخرى في \(C\) نحصل على
$$x_{n+1}=y_n,\qquad y_{n+1}=3x_n+y_n,$$
ومن ثم تحقق المركبة الاولى العلاقة
$$u_{n+2}=u_{n+1}+3u_n,\qquad u_0=0,\qquad u_1=1.$$
وبالتالي تكون القيم الاولى
$$u_0=0,\ u_1=1,\ u_2=1,\ u_3=4,\ u_4=7,\ u_5=19,\dots$$
وهذه المتتالية الاحادية هي الحد الذي ينطلق منه السطح الثنائي كله.
الهوية المركزية هي
$$M=I+C.$$
وبالتعويض المباشر في تعريف \(A(m,n)\) نحصل على
$$A(m+1,n)=e_1^{\mathsf T} M^m (I+C) C^n v_0=A(m,n)+A(m,n+1).$$
هذه هي العلاقة العودية الثنائية الحقيقية. فكل خطوة واحدة في اتجاه \(m\) تعني اخذ القيمة الحالية ثم اضافة القيمة الموجودة في العمود التالي باتجاه \(n\). وما ان نعرف الصف الحدّي \(A(0,n)\)، يمكن توليد جميع الصفوف الاعلى بهذه القاعدة.
المصفوفة \(C\) تحقق معادلتها المميزة
$$C^2=C+3I.$$
وبالضرب من اليسار في \(e_1^{\mathsf T}M^m\) ومن اليمين في \(C^n v_0\) نحصل على علاقة راسية صالحة في كل صف:
$$A(m,n+2)=A(m,n+1)+3A(m,n).$$
كذلك فان \(M\) لها كثير الحدود المميز \(x^2-3x-1\)، ولذلك
$$M^2=3M+I,$$
ومن ثم
$$A(m+2,n)=3A(m+1,n)+A(m,n).$$
إذن يمكن تحريك السطح في كلا الاتجاهين، لكن العودية الاحادية في كل اتجاه ليست نفسها.
بما ان \(M=I+C\) كثير حدود في \(C\)، فان المصفوفتين تتبادلان في الضرب. وعند توسيع \((I+C)^m\) نحصل على
$$A(m,n)=e_1^{\mathsf T}(I+C)^m C^n v_0=\sum_{t=0}^m \binom{m}{t} e_1^{\mathsf T} C^{n+t} v_0=\sum_{t=0}^m \binom{m}{t} u_{n+t}.$$
وبذلك يكون كل صف تحويلا ثنائيا للمتتالية الحدية \(u_n\). التطبيقات لا توسع هذه الصيغة حرفيا، لكنها توضح بجلاء ان الوصف بالمصفوفات والوصف بالعلاقات العودية يصفان الشيء نفسه.
باستخدام \(u_0=0\) و\(u_1=1\) و\(u_2=1\) و\(u_3=4\)، تصبح الصفوف الاولى
$$ \begin{array}{c|cccc} A(m,n) & n=0 & n=1 & n=2 & n=3 \\ \hline m=0 & 0 & 1 & 1 & 4 \\ m=1 & 1 & 2 & 5 & 11 \\ m=2 & 3 & 7 & 16 & 37 \end{array} $$
فعلى سبيل المثال يمكن التحقق من \(A(2,2)=16\) بطريقتين مستقلتين. من العلاقة الافقية:
$$A(2,2)=A(1,2)+A(1,3)=5+11=16.$$
ومن العلاقة الراسية:
$$A(2,2)=A(2,1)+3A(2,0)=7+3\cdot 3=16.$$
وهذا مثال صغير لكنه يثبت انسجام العوديتين داخل الجدول نفسه.
لتكن \(F_0=0\) و\(F_1=1\) و\(F_{r+2}=F_{r+1}+F_r\). المطلوب هو حساب
$$S(k)=\sum_{i=2}^k \sum_{j=2}^k A(F_i,F_j),$$
والهدف النهائي هو \(S(50)\pmod{1123581313}\).
هذه الفهارس تنمو بسرعة كبيرة، ولذلك لا يمكن عمليا بناء الجدول خلية بعد خلية حتى \(m,n=F_{50}\). اما الاس المصفوفي السريع فيوصل مباشرة الى \(M^{F_i}\) و\(C^{F_j}\) بزمن لوغاريتمي في قيمة الاس، وهذا هو سبب امكان تنفيذ الحساب.
تبدأ تطبيقات C++ وPython وJava بتوليد اعداد فيبوناتشي المطلوبة. بعد ذلك تستخدم الرفع السريع تحت الترديد \(1123581313\) للمصفوفتين الثابتتين \(M\) و\(C\) من الحجم \(2\times 2\).
لكل فهرس فيبوناتشي \(F_i\)، تخزن التطبيقات شيئين يمكن اعادة استخدامهما: الصف الاول المستخرج من \(M^{F_i}\)، والمتجه \(C^{F_i}v_0\). بعد هذا التحضير يصبح كل حد في المجموع المزدوج مجرد حاصل ضرب قياسي بين كائنين صغيرين من بعدين:
$$A(F_i,F_j)=r_i\cdot c_j,$$
حيث يمثل \(r_i\) الصف الاول من \(M^{F_i}\)، ويمثل \(c_j=C^{F_j}v_0\).
وبذلك لا حاجة الى اعادة حساب قوى المصفوفات داخل الحلقة النهائية. فالمرحلة الاخيرة لا تحتوي الا على جمع وضرب بترديد ثابت فوق بيانات ثنائية المركبات سبق تجهيزها.
كما تتحقق احدى النسخ من قيم صغيرة مثل \(A(1,1)=2\) و\(A(2,2)=16\) و\(S(3)=30\) و\(S(5)=10396\)، وهي تتفق تماما مع الجدول المشتق اعلاه.
توليد قائمة فيبوناتشي يحتاج الى \(O(k)\). بعد ذلك يحسب الكود \(k-1\) قوة للمصفوفة \(M\) و\(k-1\) قوة للمصفوفة \(C\). كل قوة تُحسب بالرفع السريع، ولذلك تتطلب \(O(\log F_k)\) من ضربات المصفوفات \(2\times 2\)، وكل ضربة لها كلفة ثابتة.
إذن مرحلة التحضير هي \(O(k\log F_k)\)، اما الجمع النهائي على جميع الازواج المرتبة \((i,j)\) حيث \(2\le i,j\le k\) فهو \(O(k^2)\). واستهلاك الذاكرة هو \(O(k)\) لتخزين قيم فيبوناتشي والمصفوفات المخزنة والمتجهات المخزنة. وبالنسبة للحالة الفعلية \(k=50\)، فهذه التكاليف صغيرة جدا.