Let the Fibonacci numbers be \(f_0=0\), \(f_1=1\), and \(f_n=f_{n-1}+f_{n-2}\). For each integer \(x\), define the truncated polynomial
$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$
The task is to evaluate
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
for the enormous index \(n=10^{15}\). A direct loop over all Fibonacci terms is impossible, so the key is to turn the polynomial sum into a fixed-size linear recurrence that can be exponentiated in logarithmic time.
For a fixed value of \(x\), define
$$a_k=f_k x^k.$$
Using the Fibonacci recurrence,
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$
So once \(x\) is fixed, the sequence \(a_k\) satisfies a second-order linear recurrence with constant coefficients \(x\) and \(x^2\).
The polynomial value itself is the prefix sum of the \(a_k\):
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
Therefore
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
Now combine the recurrence for \(a_k\) with the update for the running sum. With the state vector
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix},$$
we obtain the linear transition
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$
The first row reproduces \(a_{k+1}=x a_k+x^2 a_{k-1}\), the second row shifts \(a_k\) into the next position, and the third row accumulates the new term into the polynomial sum.
For \(k=1\),
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$
Hence the base vector is
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$
For every \(n\ge 1\),
$$v_n=T_x^{\,n-1}v_1,$$
and the desired value \(F_n(x)\) is the third component of \(v_n\). The special case \(n=0\) is immediate because \(F_0(x)=f_0=0\).
The matrix \(T_x\) has fixed size \(3\times 3\), so its \((n-1)\)-st power can be computed by binary exponentiation in \(O(\log n)\) matrix multiplications. Every operation is performed modulo
$$M=15!=1307674368000.$$
This keeps the numbers bounded while matching the modulus required by the problem.
The truncated generating function also satisfies
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
Over the integers this identity is correct and useful, but modulo \(15!\) the factor \(1-x-x^2\) is not always invertible. For example, at \(x=2\) it equals \(-5\), and \(5\) shares a factor with \(15!\). The matrix formulation is therefore preferable: it is division-free and works uniformly for every \(x\in\{0,\dots,100\}\).
Several small cases confirm the recurrence.
First, \(F_n(0)=0\) for all \(n\), because every term contains either \(f_0=0\) or a positive power of \(0\).
Second, for \(n=7\) and \(x=11\),
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
This matches the value produced by the matrix method.
A larger checkpoint is
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$
which is exactly the validation target used by the implementations.
The C++, Python, and Java implementations all follow the same structure. For each \(x\in\{0,\dots,100\}\), they build the transition matrix \(T_x\), raise it to the power \(n-1\) by repeated squaring, multiply by the base vector, and read the third component as \(F_n(x)\). These 101 values are then accumulated modulo \(15!\).
Because \(15!\approx 1.3\times 10^{12}\), an unreduced product of two residues can exceed ordinary 64-bit multiplication in some languages. The implementations therefore perform modular multiplication carefully before each reduction, but the mathematical algorithm itself remains the same in all three languages.
A \(3\times 3\) matrix multiplication has constant cost, and binary exponentiation uses \(O(\log n)\) such multiplications. Therefore each single value \(F_n(x)\) is computed in \(O(\log n)\) time and \(O(1)\) extra space. Since the outer sum runs over exactly 101 values of \(x\), the full computation is still \(O(101\log n)=O(\log n)\) with a very small constant factor, and the memory usage stays \(O(1)\).
Die Fibonacci-Zahlen seien durch \(f_0=0\), \(f_1=1\) und \(f_n=f_{n-1}+f_{n-2}\) definiert. Für jedes ganzzahlige \(x\) betrachten wir das abgeschnittene Polynom
$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$
Gesucht ist
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
für den riesigen Index \(n=10^{15}\). Ein direktes Aufsummieren aller Fibonacci-Terme scheidet aus, daher wird die Summe in eine lineare Rekursion fester Dimension umgeschrieben und dann per schneller Potenzierung ausgewertet.
Für festes \(x\) definieren wir
$$a_k=f_k x^k.$$
Aus der Fibonacci-Rekursion folgt dann
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$
Damit erfüllt \(a_k\) für jedes feste \(x\) eine lineare Rekursion zweiter Ordnung mit konstanten Koeffizienten \(x\) und \(x^2\).
Der Polynomwert ist gerade die Präfixsumme der \(a_k\):
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
Daher gilt
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
Kombiniert man dies mit der Rekursion für \(a_k\), so bietet sich der Zustandsvektor
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix}$$
an. Dann erhält man die lineare Übergangsmatrix
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$
Die erste Zeile erzeugt \(a_{k+1}\), die zweite verschiebt \(a_k\) eine Position weiter, und die dritte addiert den neuen Term zur laufenden Summe.
Für \(k=1\) gilt
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$
Also ist der Startvektor
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$
Für jedes \(n\ge 1\) folgt damit
$$v_n=T_x^{\,n-1}v_1,$$
und \(F_n(x)\) ist die dritte Komponente dieses Vektors. Der Sonderfall \(n=0\) ist trivial, denn \(F_0(x)=f_0=0\).
Die Matrix \(T_x\) hat die feste Größe \(3\times 3\). Deshalb lässt sich \(T_x^{n-1}\) durch binäre Exponentiation in \(O(\log n)\) Matrixmultiplikationen berechnen. Jede Rechnung geschieht modulo
$$M=15!=1307674368000,$$
wodurch die Zahlen klein bleiben und die gewünschte Restklasse direkt entsteht.
Für die abgeschnittene erzeugende Funktion gilt außerdem die Identität
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
Über den ganzen Zahlen ist das korrekt, modulo \(15!\) ist die Division durch \(1-x-x^2\) aber nicht immer erlaubt. Für \(x=2\) ist dieser Faktor gleich \(-5\), und \(5\) ist modulo \(15!\) nicht invertierbar. Die Matrixmethode vermeidet deshalb jede Division und funktioniert für alle \(x\in\{0,\dots,100\}\) einheitlich.
Ein paar kleine Fälle bestätigen die Herleitung.
Zunächst ist \(F_n(0)=0\) für alle \(n\), weil entweder \(f_0=0\) oder eine positive Potenz von \(0\) auftritt.
Ferner erhält man für \(n=7\) und \(x=11\)
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
Genau dieser Wert kommt auch bei der Matrixrechnung heraus.
Ein größerer Prüfwert ist
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$
und auch dieser wird von den Implementierungen reproduziert.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Für jedes \(x\in\{0,\dots,100\}\) wird die Matrix \(T_x\) aufgebaut, dann per wiederholtem Quadrieren auf die Potenz \(n-1\) gebracht, mit dem Startvektor multipliziert und aus der dritten Komponente \(F_n(x)\) abgelesen. Anschließend werden diese 101 Werte modulo \(15!\) aufsummiert.
Da \(15!\approx 1{,}3\times 10^{12}\) ist, kann das Produkt zweier Restklassen in manchen Sprachen größer werden als eine gewöhnliche 64-Bit-Multiplikation sicher erlaubt. Deshalb führen die Implementierungen die modularen Produkte vorsichtig aus, ohne dass sich die zugrunde liegende Mathematik ändert.
Eine Multiplikation zweier \(3\times 3\)-Matrizen kostet konstant viele Operationen, und binäre Exponentiation benötigt \(O(\log n)\) solche Schritte. Damit wird ein einzelner Wert \(F_n(x)\) in \(O(\log n)\) Zeit und \(O(1)\) Zusatzspeicher berechnet. Die äußere Summe läuft nur über 101 Werte von \(x\), also bleibt die Gesamtlaufzeit \(O(101\log n)=O(\log n)\) mit kleinem konstanten Faktor, und der Speicherverbrauch bleibt \(O(1)\).
Fibonacci sayıları \(f_0=0\), \(f_1=1\) ve \(f_n=f_{n-1}+f_{n-2}\) ile tanımlansın. Her tamsayı \(x\) için
$$F_n(x)=\sum_{k=0}^{n} f_k x^k$$
kesik polinomunu ele alıyoruz. İstenen büyüklük
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
olup burada \(n=10^{15}\) gibi çok büyük bir değerdir. Bu yüzden terimleri tek tek üretmek yerine, toplamı sabit boyutlu bir lineer duruma dönüştürüp logaritmik sürede hesaplamak gerekir.
Sabit bir \(x\) için
$$a_k=f_k x^k$$
tanımını yapalım. Fibonacci bağıntısından
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}$$
elde edilir. Böylece \(x\) sabitlenince \(a_k\) dizisi sabit katsayılı ikinci dereceden bir lineer bağıntı sağlar.
Polinom değeri, \(a_k\) terimlerinin önek toplamıdır:
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
Dolayısıyla
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
Bu bağıntıyı önceki reküransla birleştirince
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix}$$
durum vektörü için
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}$$
geçiş matrisi ortaya çıkar. İlk satır yeni ağırlıklı Fibonacci terimini, ikinci satır kaydırmayı, üçüncü satır ise birikimli toplamı günceller.
\(k=1\) için
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x$$
olur. Bu nedenle başlangıç vektörü
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}$$
şeklindedir. O halde her \(n\ge 1\) için
$$v_n=T_x^{\,n-1}v_1$$
ve aranan \(F_n(x)\), bu vektörün üçüncü bileşenidir. \(n=0\) özel durumu da doğrudan \(F_0(x)=f_0=0\) verir.
\(T_x\) matrisi sabit olarak \(3\times 3\) boyutundadır. Bu yüzden \(T_x^{n-1}\) değeri ikili üs alma ile \(O(\log n)\) matris çarpımında bulunur. Tüm işlemler
$$M=15!=1307674368000$$
modunda yapılarak hem sayıların büyümesi kontrol edilir hem de problemde istenen modüler sonuç doğrudan elde edilir.
Kesik üreteç fonksiyonu için şu özdeşlik de geçerlidir:
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
Tamsayılar üzerinde bu doğru bir formüldür; ancak modulo \(15!\) ortamında \(1-x-x^2\) her zaman terslenebilir değildir. Örneğin \(x=2\) için bu çarpan \(-5\) olur ve \(5\), \(15!\) ile aralarında asal değildir. Bu yüzden uygulama bölme gerektirmeyen matris yaklaşımını seçer; yöntem tüm \(x\in\{0,\dots,100\}\) için güvenle çalışır.
Küçük örnekler türetmeyi doğrular.
Önce \(F_n(0)=0\) olur; çünkü her terim ya \(f_0=0\) içerir ya da \(0\)'ın pozitif kuvvetiyle çarpılır.
Ayrıca \(n=7\) ve \(x=11\) için
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
Matris yöntemi de tam olarak bu değeri verir.
Daha büyük bir kontrol noktası ise
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!}$$
eşitliğidir; uygulamalar da aynı sonucu üretir.
C++, Python ve Java implementasyonları aynı algoritmayı izler. Her \(x\in\{0,\dots,100\}\) için önce \(T_x\) matrisi kurulur, sonra tekrar eden kare alma ile \(n-1\). kuvveti hesaplanır, başlangıç vektörü ile çarpılır ve üçüncü bileşenden \(F_n(x)\) okunur. Son olarak bu 101 değer \(15!\) modunda toplanır.
\(15!\approx 1.3\times 10^{12}\) olduğundan, iki kalanın indirgeme yapılmadan çarpımı bazı dillerde sıradan 64 bit çarpımı aşabilir. Bu yüzden implementasyonlar modüler çarpımı dikkatli uygular; ancak kullanılan matematiksel yöntem her üç dilde de aynıdır.
\(3\times 3\) matris çarpımı sabit maliyetlidir ve ikili üs alma \(O(\log n)\) adet böyle çarpım kullanır. Bu nedenle tek bir \(F_n(x)\) değeri \(O(\log n)\) zamanda ve \(O(1)\) ek bellekle hesaplanır. Dış toplam yalnızca 101 farklı \(x\) değeri üzerinde döndüğü için toplam karmaşıklık \(O(101\log n)=O(\log n)\) olarak kalır; bellek kullanımı da \(O(1)\) düzeyindedir.
Sea la sucesion de Fibonacci dada por \(f_0=0\), \(f_1=1\) y \(f_n=f_{n-1}+f_{n-2}\). Para cada entero \(x\), se define el polinomio truncado
$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$
Hay que calcular
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
cuando \(n=10^{15}\). El obstaculo principal es que no se puede recorrer la sucesion termino a termino; hace falta transformar el problema en una recurrencia lineal de dimension fija y luego elevar una matriz por exponenciacion rapida.
Fijado un valor de \(x\), definimos
$$a_k=f_k x^k.$$
La recurrencia de Fibonacci implica
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$
Asi, para cada \(x\), la sucesion \(a_k\) satisface una recurrencia lineal de segundo orden con coeficientes constantes.
El valor del polinomio es la suma acumulada de los \(a_k\):
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
Por tanto,
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
Si reunimos ambas relaciones en el vector de estado
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix},$$
obtenemos la transicion lineal
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$
La primera fila genera el nuevo termino ponderado, la segunda desplaza el termino anterior y la tercera actualiza la suma acumulada.
Para \(k=1\),
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$
Luego el vector base es
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$
Para todo \(n\ge 1\),
$$v_n=T_x^{\,n-1}v_1,$$
y \(F_n(x)\) es la tercera componente. El caso \(n=0\) es inmediato porque \(F_0(x)=f_0=0\).
Como \(T_x\) siempre es una matriz \(3\times 3\), su potencia \(T_x^{n-1}\) puede calcularse con exponenciacion por cuadrados en \(O(\log n)\) multiplicaciones matriciales. Toda la aritmetica se realiza modulo
$$M=15!=1307674368000,$$
de modo que el resultado buscado aparece directamente en la clase residual correcta.
La funcion generadora truncada tambien satisface
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
La identidad es correcta sobre los enteros, pero modulo \(15!\) el factor \(1-x-x^2\) no siempre es invertible. Por ejemplo, para \(x=2\) vale \(-5\), y \(5\) comparte factores con \(15!\). Por eso la implementacion evita divisiones y usa una formulacion matricial valida para todos los \(x\) entre \(0\) y \(100\).
Algunos casos pequenos sirven como verificacion.
Primero, \(F_n(0)=0\) para todo \(n\), ya que cada termino contiene \(f_0=0\) o una potencia positiva de \(0\).
Ademas, para \(n=7\) y \(x=11\),
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
Ese valor coincide exactamente con el producido por la recurrencia matricial.
Un segundo punto de control es
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$
que tambien es reproducido por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma idea. Para cada \(x\in\{0,\dots,100\}\), construyen la matriz \(T_x\), la elevan a la potencia \(n-1\) mediante exponenciacion rapida, multiplican por el vector base y toman la tercera componente como \(F_n(x)\). Luego suman los 101 resultados modulo \(15!\).
Dado que \(15!\approx 1.3\times 10^{12}\), el producto de dos residuos puede sobrepasar la multiplicacion entera ordinaria en algunos lenguajes antes de aplicar el modulo. Por eso cada implementacion usa una multiplicacion modular segura, aunque el algoritmo matematico sea el mismo en los tres casos.
Multiplicar dos matrices \(3\times 3\) cuesta tiempo constante, y la exponenciacion binaria necesita \(O(\log n)\) multiplicaciones de este tipo. En consecuencia, cada valor \(F_n(x)\) se obtiene en \(O(\log n)\) tiempo y \(O(1)\) espacio extra. Como la suma exterior recorre exactamente 101 valores de \(x\), el coste total sigue siendo \(O(101\log n)=O(\log n)\) con una constante pequena, y la memoria permanece en \(O(1)\).
设 Fibonacci 数列满足 \(f_0=0\)、\(f_1=1\)、\(f_n=f_{n-1}+f_{n-2}\)。对每个整数 \(x\)，定义截断多项式
$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$
题目要求计算
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
其中 \(n=10^{15}\)。因为 \(n\) 极大，不能按定义逐项累加，所以必须把问题改写成固定维度的线性递推，再用快速幂求值。
对固定的 \(x\)，定义
$$a_k=f_k x^k.$$
由 Fibonacci 递推立刻得到
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$
也就是说，对每个固定的 \(x\)，序列 \(a_k\) 都满足一个系数为常数的二阶线性递推。
多项式值本身就是这些带权项的前缀和：
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
因此
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
把两条关系合在一起，取状态向量
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix},$$
就得到线性转移
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$
第一行生成新的带权项，第二行把当前项下移为前一项，第三行把新项加入累计和。
当 \(k=1\) 时，
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$
所以初始向量为
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$
于是对所有 \(n\ge 1\)，都有
$$v_n=T_x^{\,n-1}v_1,$$
而 \(F_n(x)\) 就是第三个分量。若 \(n=0\)，则直接有 \(F_0(x)=f_0=0\)。
\(T_x\) 始终是固定的 \(3\times 3\) 矩阵，所以 \(T_x^{n-1}\) 可以通过重复平方在 \(O(\log n)\) 次矩阵乘法内得到。所有运算都在
$$M=15!=1307674368000$$
模下进行，这样既控制了中间数规模，也直接得到题目要求的模值。
这个截断生成函数还满足
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
在整数范围内这是完全正确的，但在模 \(15!\) 的环境里，\(1-x-x^2\) 不一定可逆。例如 \(x=2\) 时该因子等于 \(-5\)，而 \(5\) 与 \(15!\) 不互素。因此实现选择了不需要做除法的矩阵方法，这样对所有 \(x=0,\dots,100\) 都统一有效。
一些小规模结果可以检验推导是否正确。
首先，对任何 \(n\)，都有 \(F_n(0)=0\)，因为每一项不是含有 \(f_0=0\)，就是含有 \(0\) 的正幂。
其次，当 \(n=7\)、\(x=11\) 时，
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
矩阵递推计算出的结果与此完全一致。
另一个检查点是
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$
这也是实现中使用的验证值。
C++、Python 和 Java 实现都遵循同一结构。对每个 \(x\in\{0,\dots,100\}\)，先构造矩阵 \(T_x\)，再用二进制快速幂求出 \(T_x^{n-1}\)，与初始向量相乘，并把第三个分量作为 \(F_n(x)\)。最后把这 101 个值在模 \(15!\) 下累加。
由于 \(15!\approx 1.3\times 10^{12}\)，两个模数代表元相乘后在约简前可能超过某些语言里普通整数乘法的安全范围。因此实现会使用适合各自语言的安全模乘方式，但背后的数学算法完全一致。
一次 \(3\times 3\) 矩阵乘法的代价是常数，而二进制快速幂需要 \(O(\log n)\) 次这样的乘法。因此单个 \(F_n(x)\) 的计算时间是 \(O(\log n)\)，额外空间是 \(O(1)\)。外层求和只遍历 101 个 \(x\) 值，所以总时间仍然是 \(O(101\log n)=O(\log n)\)，常数很小，空间复杂度保持为 \(O(1)\)。
Пусть числа Фибоначчи заданы условиями \(f_0=0\), \(f_1=1\), \(f_n=f_{n-1}+f_{n-2}\). Для каждого целого \(x\) определяется усеченный полином
$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$
Нужно вычислить
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
при \(n=10^{15}\). Поскольку индекс огромен, прямое суммирование по определению невозможно, и задачу нужно свести к линейной рекурсии фиксированной размерности с последующим быстрым возведением матрицы в степень.
Для фиксированного \(x\) положим
$$a_k=f_k x^k.$$
Тогда из рекуррентной формулы Фибоначчи следует
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$
Итак, при фиксированном \(x\) последовательность \(a_k\) удовлетворяет линейной рекурсии второго порядка с постоянными коэффициентами \(x\) и \(x^2\).
Значение полинома есть префиксная сумма членов \(a_k\):
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
Следовательно,
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
Если объединить обе связи в вектор состояния
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix},$$
то получаем матричный переход
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$
Первая строка строит новый взвешенный член, вторая сдвигает старое значение, а третья обновляет накопленную сумму.
При \(k=1\) имеем
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$
Значит, начальный вектор равен
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$
Для любого \(n\ge 1\) получаем
$$v_n=T_x^{\,n-1}v_1,$$
и искомое значение \(F_n(x)\) равно третьей компоненте. Случай \(n=0\) тривиален, потому что \(F_0(x)=f_0=0\).
Матрица \(T_x\) всегда имеет размер \(3\times 3\), поэтому степень \(T_x^{n-1}\) можно найти двоичным возведением в степень за \(O(\log n)\) матричных умножений. Все вычисления выполняются по модулю
$$M=15!=1307674368000,$$
что одновременно ограничивает рост чисел и дает нужный остаток.
Для усеченной производящей функции верно также тождество
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
Над целыми числами это полезная закрытая форма, однако по модулю \(15!\) множитель \(1-x-x^2\) не всегда обратим. Например, при \(x=2\) он равен \(-5\), а число \(5\) имеет общий делитель с \(15!\). Поэтому реализация выбирает безделительный матричный метод, одинаково корректный для всех \(x\) от \(0\) до \(100\).
Небольшие примеры подтверждают вывод.
Во-первых, \(F_n(0)=0\) для любого \(n\), потому что каждый член либо содержит \(f_0=0\), либо умножается на положительную степень нуля.
Во-вторых, при \(n=7\) и \(x=11\)
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
Тот же результат дает и матричная схема.
Еще одна контрольная величина:
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$
и она тоже совпадает с результатом программ.
Реализации на C++, Python и Java устроены одинаково. Для каждого \(x\in\{0,\dots,100\}\) они строят матрицу \(T_x\), возводят ее в степень \(n-1\) методом repeated squaring, умножают на начальный вектор и берут третью компоненту как \(F_n(x)\). После этого все 101 значения суммируются по модулю \(15!\).
Поскольку \(15!\approx 1.3\times 10^{12}\), произведение двух остатков до взятия модуля может выйти за безопасный диапазон обычного целочисленного умножения в некоторых языках. Поэтому реализации аккуратно выполняют модульное умножение, но сама математическая идея везде одна и та же.
Умножение двух матриц \(3\times 3\) имеет постоянную стоимость, а двоичное возведение в степень требует \(O(\log n)\) таких умножений. Следовательно, одно значение \(F_n(x)\) вычисляется за \(O(\log n)\) времени и \(O(1)\) дополнительной памяти. Внешняя сумма проходит лишь по 101 значению \(x\), поэтому полная сложность остается \(O(101\log n)=O(\log n)\) с малой константой, а память остается \(O(1)\).
لتكن أعداد فيبوناتشي معرّفة بالعلاقات \(f_0=0\)، \(f_1=1\)، و \(f_n=f_{n-1}+f_{n-2}\). ولكل عدد صحيح \(x\) نعرّف كثير الحدود المقطوع
$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$
المطلوب هو حساب
$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$
عندما يكون \(n=10^{15}\). وبسبب كبر هذا المؤشر لا يمكن جمع الحدود مباشرة، لذلك يجب تحويل المسألة إلى علاقة خطية ذات بعد ثابت ثم استخدام رفع سريع للمصفوفات.
لـ \(x\) ثابت نعرّف
$$a_k=f_k x^k.$$
ومن علاقة فيبوناتشي نحصل على
$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$
وهكذا تصبح السلسلة \(a_k\) علاقة خطية من الرتبة الثانية ذات معاملات ثابتة بمجرد تثبيت \(x\).
قيمة كثير الحدود نفسها هي مجموع جزئي للحدود \(a_k\):
$$F_k(x)=\sum_{i=0}^{k} a_i.$$
إذن
$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$
وعند جمع هذه العلاقة مع علاقة \(a_k\) السابقة، نأخذ متجه الحالة
$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix},$$
فنحصل على التحويل الخطي
$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$
السطر الأول يولّد الحد الجديد، والسطر الثاني ينقل القيمة الحالية إلى خانة الحد السابق، والسطر الثالث يحدّث المجموع المتراكم.
عند \(k=1\) نجد
$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$
إذن متجه البداية هو
$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$
ولكل \(n\ge 1\) نحصل على
$$v_n=T_x^{\,n-1}v_1,$$
وتكون قيمة \(F_n(x)\) هي المركبة الثالثة. أما الحالة \(n=0\) فهي مباشرة لأن \(F_0(x)=f_0=0\).
المصفوفة \(T_x\) ذات حجم ثابت \(3\times 3\)، ولذلك يمكن حساب \(T_x^{n-1}\) بطريقة التربيع المتكرر خلال \(O(\log n)\) من ضربات المصفوفات. وتُجرى جميع العمليات بترديد
$$M=15!=1307674368000,$$
وبذلك نبقى ضمن المجال المطلوب ونحصل مباشرة على الباقي النهائي.
يمكن أيضا اشتقاق الهوية
$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$
هذه الصيغة صحيحة على الأعداد الصحيحة، لكن العمل modulo \(15!\) يجعل القسمة على \(1-x-x^2\) غير مضمونة دائما، لأن هذا العامل قد لا يكون قابلا للعكس. فعند \(x=2\) مثلا نحصل على \(-5\)، والعدد \(5\) يشترك بعامل مع \(15!\). لذلك تختار التنفيذات صياغة مصفوفية لا تحتاج إلى أي قسمة وتعمل بصورة موحدة لكل \(x\) من \(0\) إلى \(100\).
توجد أمثلة صغيرة تؤكد صحة الاشتقاق.
أولا، \(F_n(0)=0\) لكل \(n\)، لأن كل حد إما يحتوي على \(f_0=0\) أو على قوة موجبة من الصفر.
وثانيا، عندما \(n=7\) و \(x=11\)، فإن
$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$
وهذه هي القيمة نفسها التي تنتجها الطريقة المصفوفية.
كما أن نقطة تحقق أكبر هي
$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$
وهي أيضا مطابقة لما تعطيه التنفيذات.
تنفيذات C++ و Python و Java تتبع الفكرة نفسها. لكل \(x\in\{0,\dots,100\}\) تُبنى المصفوفة \(T_x\)، ثم تُرفع إلى القوة \(n-1\) بالرفع السريع، ثم تُضرب في متجه البداية، وتُؤخذ المركبة الثالثة على أنها \(F_n(x)\). بعد ذلك تُجمع القيم الـ 101 كلها modulo \(15!\).
وبما أن \(15!\approx 1.3\times 10^{12}\)، فإن حاصل ضرب باقيين قبل الاختزال قد يتجاوز الضرب الصحيح العادي في بعض اللغات. لذلك تستخدم التنفيذات ضربا معياريا آمنا يلائم كل لغة، بينما تبقى الفكرة الرياضية نفسها دون تغيير.
ضرب مصفوفتين \(3\times 3\) له كلفة ثابتة، والرفع السريع يحتاج إلى \(O(\log n)\) من هذه الضربات. لذلك تُحسب قيمة واحدة \(F_n(x)\) في زمن \(O(\log n)\) وبمساحة إضافية \(O(1)\). أما المجموع الخارجي فيمر على 101 قيمة فقط من \(x\)، فتظل الكلفة الكلية \(O(101\log n)=O(\log n)\) مع ثابت صغير، وتبقى الذاكرة \(O(1)\).