The target quantity for Problem 739 is evaluated modulo \(M=10^9+7\) for \(n=10^8\). After simplifying the repeated-summation construction, the required value can be written as a single weighted sum of Lucas numbers:
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
The real difficulty is the size of \(r\). A direct quadratic summation is hopeless, and even an \(O(n)\) scan becomes too slow if it performs one modular exponentiation per term. The successful approach is to stream the coefficients backward, update Lucas values in lockstep, and batch the modular inverses.
The solution combines Lucas-number identities, a ballot-number coefficient sequence, and blockwise modular inversion.
The Lucas sequence satisfies \(L_0=2\), \(L_1=1\), and
$$L_{k+1}=L_k+L_{k-1}.$$
The implementations do not build this sequence from the beginning. Instead, they first obtain the Fibonacci pair \((F_k,F_{k+1})\) by fast doubling and then use
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k.$$
That gives the starting values \(L_r\) and \(L_{r+1}\) in \(O(\log n)\) time, which is small compared with the main scan.
The required sum uses coefficients \(T_t\) generated backward from the endpoint:
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
This is not an arbitrary recurrence. It is exactly the ratio of ballot-number, or Catalan-triangle, coefficients. A closed form is
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$$
So the repeated-summation problem collapses to a Lucas sum with very structured combinatorial weights.
Because both the coefficients and the Lucas sequence admit backward updates, the whole computation can be done in one descending pass \(t=r,r-1,\dots,1\). Rearranging the Lucas recurrence gives
$$L_{t-1}=L_{t+1}-L_t\pmod{M}.$$
During the scan, one term contributes
$$T_tL_{t+1}\pmod{M},$$
then the coefficient is multiplied by the rational step factor above, and the Lucas pair is shifted backward by one index. No table of all coefficients or all Lucas numbers is needed.
For \(n=8\), we have \(r=7\). Starting from \(T_7=1\), the recurrence yields
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
The required Lucas values are
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
Therefore
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
which matches the sample check used by the implementations.
The denominator in the coefficient update is
$$d_t=t(r-t+1).$$
Since \(r=10^8-1\lt M\), both factors are nonzero modulo \(M\), so every \(d_t\) is invertible. Computing each inverse separately would be far too expensive. Instead, the denominators are grouped into blocks. For one block \(d_1,\dots,d_m\), a single inverse of the total product is enough:
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
This replaces \(m\) costly modular exponentiations by one exponentiation plus \(O(m)\) multiplications.
The C++, Python, and Java implementations all follow the same plan. First they compute the Lucas starting pair with fast doubling under modulo \(M\). Then they process the coefficient recurrence from high \(t\) down to low \(t\) in fixed-size blocks, materializing the denominators \(t(r-t+1)\) for the current block and batch-inverting them.
Inside each block, the implementation adds the current contribution \(T_tL_{t+1}\), updates the coefficient using the precomputed inverse for that step, and moves the Lucas pair backward using \(L_{t-1}=L_{t+1}-L_t\). This streaming design keeps the memory footprint small while still reproducing the validation checkpoints \(f(8)=2663\) and \(f(20)=742296999\).
Fast doubling costs \(O(\log n)\) time. The main scan visits each \(t\) once, so the total work is \(O(n)\) modular multiplications. Batch inversion keeps the number of modular exponentiations proportional to the number of blocks rather than the number of terms. With block size \(B\), the memory usage is \(O(B)\), and the total runtime is linear in \(n\) apart from the tiny logarithmic startup cost.
Die gesuchte Größe zu Problem 739 wird für \(n=10^8\) modulo \(M=10^9+7\) berechnet. Nach der Vereinfachung der wiederholten Summationskonstruktion lässt sich der Zielwert als gewichtete Summe von Lucas-Zahlen schreiben:
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
Die eigentliche Schwierigkeit ist die Größe von \(r\). Eine quadratische Auswertung ist ausgeschlossen, und selbst ein linearer Durchlauf wäre zu langsam, wenn pro Term eine eigene modulare Inversion berechnet würde. Deshalb arbeitet die Lösung mit einem Rückwärtslauf, gekoppelten Lucas-Updates und Block-Inversionen.
Die Methode verbindet Lucas-Identitäten, eine Ballot-Zahlen-Folge und blockweise modulare Inversion.
Die Lucas-Folge erfüllt \(L_0=2\), \(L_1=1\) und
$$L_{k+1}=L_k+L_{k-1}.$$
Die Implementierungen erzeugen diese Folge nicht von vorn. Stattdessen bestimmen sie per Fast Doubling zunächst das Fibonacci-Paar \((F_k,F_{k+1})\) und nutzen dann
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k.$$
So erhält man die Startwerte \(L_r\) und \(L_{r+1}\) in \(O(\log n)\) Zeit.
Die Koeffizienten \(T_t\) werden rückwärts vom Endpunkt aus erzeugt:
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
Diese Rekursion ist nicht zufällig. Sie ist genau das Verhältnis von Ballot-Zahlen beziehungsweise Einträgen aus dem Catalan-Dreieck. Eine geschlossene Formel lautet
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$$
Damit reduziert sich das ursprüngliche Summationsproblem auf eine Lucas-Summe mit stark strukturierten kombinatorischen Gewichten.
Weil sowohl die Koeffizienten als auch die Lucas-Zahlen rückwärts aktualisiert werden können, genügt ein einziger Abstieg \(t=r,r-1,\dots,1\). Aus der Lucas-Rekursion folgt
$$L_{t-1}=L_{t+1}-L_t\pmod{M}.$$
In jedem Schritt wird also zuerst
$$T_tL_{t+1}\pmod{M}$$
zum Ergebnis addiert, danach der Koeffizient mit dem rationalen Übergangsfaktor aktualisiert und schließlich das Lucas-Paar um einen Index nach links verschoben. Weder alle Gewichte noch alle Lucas-Werte müssen gespeichert werden.
Für \(n=8\) gilt \(r=7\). Ausgehend von \(T_7=1\) liefert die Rekursion
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
Die benötigten Lucas-Werte sind
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
Also erhält man
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
genau den Kontrollwert der Implementierungen.
Der Nenner im Koeffizienten-Update ist
$$d_t=t(r-t+1).$$
Da \(r=10^8-1\lt M\), sind beide Faktoren modulo \(M\) ungleich null, also ist jedes \(d_t\) invertierbar. Würde man für jedes \(t\) separat invertieren, wäre das zu teuer. Stattdessen werden die Nenner blockweise verarbeitet. Für einen Block \(d_1,\dots,d_m\) genügt eine einzige Inversion des Gesamtprodukts:
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
So werden \(m\) teure Potenzierungen durch eine Potenzierung und \(O(m)\) Multiplikationen ersetzt.
Die C++-, Python- und Java-Implementierungen folgen demselben Schema. Zuerst berechnen sie per Fast Doubling das Lucas-Startpaar modulo \(M\). Anschließend laufen sie die Rekursion von großem \(t\) nach kleinem \(t\) in Blöcken fester Größe ab, erzeugen für jeden Block die Nenner \(t(r-t+1)\) und invertieren den ganzen Block gemeinsam.
Innerhalb eines Blocks addiert die Implementierung jeweils den aktuellen Beitrag \(T_tL_{t+1}\), aktualisiert den Koeffizienten mit der vorbereiteten Inversen und verschiebt das Lucas-Paar per \(L_{t-1}=L_{t+1}-L_t\) um einen Schritt zurück. Dieses Streaming-Verfahren hält den Speicherbedarf klein und reproduziert zugleich die Prüfpunkte \(f(8)=2663\) und \(f(20)=742296999\).
Fast Doubling benötigt \(O(\log n)\) Zeit. Der Hauptlauf besucht jedes \(t\) genau einmal, also insgesamt \(O(n)\) modulare Multiplikationen. Durch Block-Inversion ist die Zahl der modularen Potenzierungen proportional zur Anzahl der Blöcke statt zur Anzahl der Terme. Bei Blockgröße \(B\) beträgt der Speicherverbrauch \(O(B)\), und die Gesamtlaufzeit ist bis auf einen sehr kleinen logarithmischen Startaufwand linear in \(n\).
Problem 739 için istenen değer, \(n=10^8\) iken \(M=10^9+7\) modunda hesaplanır. Tekrarlı toplama yapısı sadeleştirildiğinde hedef ifade, Lucas sayılarının ağırlıklı tek bir toplamına dönüşür:
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
Asıl zorluk \(r\)'nin çok büyük olmasıdır. Doğrudan karesel bir yöntem imkansızdır; hatta lineer tarama bile her adımda ayrı bir modüler ters hesaplarsa pratik olmaz. Bu yüzden çözüm katsayıları geriye doğru akıtır, Lucas değerlerini aynı anda günceller ve tersleri blok halinde üretir.
Çözüm üç parçayı birleştirir: Lucas özdeşlikleri, ballot sayıları türünden bir ağırlık dizisi ve blok bazlı modüler ters alma.
Lucas dizisi \(L_0=2\), \(L_1=1\) ile başlar ve
$$L_{k+1}=L_k+L_{k-1}$$
bağıntısını sağlar. Uygulamalar bu diziyi baştan sona üretmez. Önce Fibonacci çifti \((F_k,F_{k+1})\) hızlı ikiye-katlama yöntemiyle bulunur, sonra
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k$$
kimliği kullanılır. Böylece \(L_r\) ve \(L_{r+1}\) başlangıç değerleri \(O(\log n)\) sürede elde edilir.
Toplamdaki \(T_t\) katsayıları sondan başlanarak geriye doğru üretilir:
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
Bu bağıntı rastgele değildir. Ballot sayıları ya da Catalan üçgeni katsayılarının tam oranıdır. Kapalı biçim
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}$$
şeklindedir. Yani problem, düzensiz katsayılı bir toplam değil; çok düzenli kombinatorik ağırlıklara sahip bir Lucas toplamıdır.
Hem katsayılar hem de Lucas sayıları geriye doğru güncellenebildiği için \(t=r,r-1,\dots,1\) şeklinde tek bir iniş yeterlidir. Lucas bağıntısı yeniden düzenlenirse
$$L_{t-1}=L_{t+1}-L_t\pmod{M}$$
elde edilir. Her adımda önce
$$T_tL_{t+1}\pmod{M}$$
cevaba eklenir, sonra katsayı yukarıdaki rasyonel çarpanla güncellenir ve Lucas çifti bir indeks geriye taşınır. Böylece tüm katsayıları ya da tüm Lucas değerlerini saklamaya gerek kalmaz.
\(n=8\) olduğunda \(r=7\) olur. \(T_7=1\) ile başlayınca bağıntı şu değerleri verir:
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
Gerekli Lucas sayıları ise
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
Dolayısıyla
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
ve bu değer uygulamaların doğrulama kontrolüyle aynıdır.
Katsayı güncellemesindeki payda
$$d_t=t(r-t+1)$$
şeklindedir. \(r=10^8-1\lt M\) olduğundan her iki çarpan da \(M\) modunda sıfır değildir; dolayısıyla tüm \(d_t\) değerleri terslenebilir. Her bir ters ayrı ayrı hesaplanırsa maliyet çok büyür. Bunun yerine paydalar bloklar halinde işlenir. Bir blok \(d_1,\dots,d_m\) için toplam çarpımın tek bir tersi yeterlidir:
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
Böylece \(m\) pahalı üs alma işlemi yerine bir üs alma ve \(O(m)\) çarpım yeterli olur.
C++, Python ve Java uygulamaları aynı planı izler. Önce Lucas başlangıç çifti \(M\) modunda hızlı ikiye-katlama ile hesaplanır. Sonra büyük \(t\)'den küçük \(t\)'ye doğru sabit boyutlu bloklar halinde gidilir; her blok için \(t(r-t+1)\) paydaları oluşturulur ve birlikte terslenir.
Blok içinde uygulama mevcut katkı \(T_tL_{t+1}\) değerini toplama ekler, o adıma ait hazır ters ile katsayıyı günceller ve \(L_{t-1}=L_{t+1}-L_t\) bağıntısıyla Lucas çiftini bir adım geriye taşır. Bu akışkan yapı belleği küçük tutar ve aynı zamanda \(f(8)=2663\) ile \(f(20)=742296999\) kontrol noktalarını yeniden üretir.
Hızlı ikiye-katlama \(O(\log n)\) zaman alır. Ana döngü her \(t\) değerine tam bir kez uğradığı için toplam çalışma \(O(n)\) modüler çarpımdır. Blok tersleme sayesinde modüler üs alma sayısı terim sayısına değil blok sayısına bağlı kalır. Blok boyutu \(B\) ise bellek kullanımı \(O(B)\), toplam süre ise küçük bir logaritmik başlangıç maliyeti dışında lineerdir.
La cantidad pedida en el Problema 739 se evalúa para \(n=10^8\) módulo \(M=10^9+7\). Tras simplificar la construcción de sumaciones repetidas, el valor buscado queda como una sola suma ponderada de números de Lucas:
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
La dificultad real es el tamaño de \(r\). Un método cuadrático es imposible, e incluso un recorrido lineal se vuelve caro si hace una exponenciación modular por término. La estrategia correcta es recorrer los pesos hacia atrás, actualizar los valores de Lucas al mismo tiempo y agrupar las inversiones modulares.
La solución combina identidades de Lucas, una sucesión de coeficientes de tipo ballot y una inversión modular por bloques.
La sucesión de Lucas cumple \(L_0=2\), \(L_1=1\) y
$$L_{k+1}=L_k+L_{k-1}.$$
Las implementaciones no generan toda la sucesión desde el principio. Primero obtienen el par de Fibonacci \((F_k,F_{k+1})\) mediante fast doubling y luego usan
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k.$$
Así se consiguen los valores iniciales \(L_r\) y \(L_{r+1}\) en tiempo \(O(\log n)\).
Los coeficientes \(T_t\) se generan hacia atrás desde el extremo final:
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
Esta recurrencia no es accidental. Coincide exactamente con la razón de los números ballot, o de la tabla triangular relacionada con los números de Catalan. Una forma cerrada es
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$$
Por tanto, el problema se reduce a sumar términos de Lucas contra pesos combinatorios muy estructurados.
Como tanto los coeficientes como los números de Lucas admiten actualización hacia atrás, basta un solo barrido descendente \(t=r,r-1,\dots,1\). Reordenando la recurrencia de Lucas se obtiene
$$L_{t-1}=L_{t+1}-L_t\pmod{M}.$$
En cada paso se añade
$$T_tL_{t+1}\pmod{M}$$
al resultado, luego se actualiza el coeficiente con el factor racional anterior y finalmente se desplaza el par de Lucas una posición hacia atrás. No hace falta almacenar todos los pesos ni todos los valores de Lucas.
Si \(n=8\), entonces \(r=7\). Partiendo de \(T_7=1\), la recurrencia produce
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
Los valores de Lucas necesarios son
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
Por lo tanto,
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
que coincide con la comprobación usada por las implementaciones.
El denominador de la actualización del coeficiente es
$$d_t=t(r-t+1).$$
Como \(r=10^8-1\lt M\), ambos factores son no nulos módulo \(M\), así que cada \(d_t\) es invertible. Calcular un inverso distinto para cada término sería demasiado costoso. En su lugar, los denominadores se procesan por bloques. Para un bloque \(d_1,\dots,d_m\), basta invertir el producto total una sola vez:
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
Esto reemplaza \(m\) exponenciaciones modulares caras por una sola exponenciación y \(O(m)\) multiplicaciones.
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan. Primero calculan el par inicial de Lucas mediante fast doubling bajo módulo \(M\). Después recorren la recurrencia desde \(t\) grande hasta \(t\) pequeño en bloques de tamaño fijo, construyen los denominadores \(t(r-t+1)\) del bloque actual y obtienen todos sus inversos a la vez.
Dentro de cada bloque, la implementación suma la contribución actual \(T_tL_{t+1}\), actualiza el coeficiente usando el inverso ya preparado para ese paso y mueve el par de Lucas hacia atrás con \(L_{t-1}=L_{t+1}-L_t\). Ese diseño en flujo mantiene poca memoria y también reproduce los puntos de control \(f(8)=2663\) y \(f(20)=742296999\).
Fast doubling cuesta \(O(\log n)\) tiempo. El bucle principal visita cada \(t\) una sola vez, de modo que el trabajo total es \(O(n)\) multiplicaciones modulares. La inversión por bloques hace que el número de exponenciaciones modulares dependa del número de bloques y no del número de términos. Con tamaño de bloque \(B\), la memoria usada es \(O(B)\) y el tiempo total es lineal en \(n\), salvo un coste inicial logarítmico muy pequeño.
Problem 739 要求的量在 \(n=10^8\) 时按模 \(M=10^9+7\) 计算。把反复做“求和的求和”这一构造化简之后，目标值可以写成一条 Lucas 数加权和：
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
真正的难点不是 Lucas 数本身，而是 \(r\) 的规模太大。二次算法完全不可行；即使做一次线性扫描，如果每一项都单独做一次模逆，也会慢得不可接受。可行做法是把系数按索引从大到小流式更新，同时同步维护 Lucas 值，并把模逆改成按块批量处理。
这套方法把三个部分结合在一起：Lucas 数恒等式、ballot 数型的组合系数，以及按块的模逆计算。
Lucas 数列满足 \(L_0=2\)、\(L_1=1\)，并且
$$L_{k+1}=L_k+L_{k-1}.$$
实现并不会从 \(L_0\) 一直推到 \(L_r\)。它先用 Fibonacci 的快速倍增得到 \((F_k,F_{k+1})\)，再利用
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k$$
直接得到所需的 \(L_r\) 和 \(L_{r+1}\)。因此初始化只需要 \(O(\log n)\) 时间。
求和中的系数 \(T_t\) 是从尾部往前递推的：
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
这个递推并不是随意拼出来的，它正好对应 ballot 数，也就是 Catalan 三角形中的一类系数。它的闭式写法为
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$$
换句话说，原问题最终变成了一个 Lucas 数列与高度结构化的组合权重之间的卷积式求和。
由于系数和 Lucas 数都能反向更新，所以只需要一次从 \(t=r\) 递减到 \(1\) 的扫描。把 Lucas 递推式改写一下，就有
$$L_{t-1}=L_{t+1}-L_t\pmod{M}.$$
于是每一步只做三件事：先把
$$T_tL_{t+1}\pmod{M}$$
加到答案中，再用上面的有理比值更新系数，最后把当前的 Lucas 二元组整体向后退一位。整个过程中不需要保存全部系数，也不需要保存整段 Lucas 数列。
当 \(n=8\) 时，\(r=7\)。从 \(T_7=1\) 出发，递推得到
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
所需的 Lucas 值为
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
因此
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
这与实现中的校验值完全一致。
系数更新时分母是
$$d_t=t(r-t+1).$$
由于 \(r=10^8-1\lt M\)，这两个因子在模 \(M\) 下都不为零，所以每个 \(d_t\) 都可逆。如果对每个 \(t\) 单独用快速幂求逆，代价会非常高。实现改为按块处理分母。对一整块 \(d_1,\dots,d_m\)，只需求总乘积的一次逆元：
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
这样就把 \(m\) 次昂贵的模逆，降成一次快速幂加上 \(O(m)\) 次乘法。
C++、Python 和 Java 实现采用完全相同的流程。首先通过快速倍增在模 \(M\) 下得到初始 Lucas 二元组。然后按固定块大小，从大的 \(t\) 向小的 \(t\) 扫描；在每一块中先生成当前所有分母 \(t(r-t+1)\)，再一次性求出这一块里全部分母的逆元。
进入块内循环后，程序把当前项 \(T_tL_{t+1}\) 加入答案，用已经准备好的逆元更新系数，再用 \(L_{t-1}=L_{t+1}-L_t\) 把 Lucas 二元组向后推进一位。整个算法始终是流式的，所以内存占用很小，同时还能复现校验点 \(f(8)=2663\) 和 \(f(20)=742296999\)。
快速倍增的初始化代价是 \(O(\log n)\)。主循环对每个 \(t\) 只访问一次，因此总工作量是 \(O(n)\) 次模乘。批量求逆让模幂运算的次数与块数成正比，而不是与项数成正比。若块大小为 \(B\)，则空间复杂度为 \(O(B)\)，总时间复杂度在一个很小的对数级启动成本之外基本是线性的。
Искомая величина в Problem 739 вычисляется при \(n=10^8\) по модулю \(M=10^9+7\). После упрощения конструкции с многократными суммированиями целевое значение записывается как одна взвешенная сумма чисел Лукаса:
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
Главная трудность состоит в размере \(r\). Квадратичный подход невозможен, а даже линейный проход становится слишком дорогим, если на каждом шаге отдельно находить модульный обратный. Поэтому решение идет по индексам назад, синхронно обновляет числа Лукаса и вычисляет обратные по блокам.
Метод объединяет тождества для чисел Лукаса, последовательность коэффициентов типа ballot numbers и блочное вычисление модульных обратных.
Последовательность Лукаса задается условиями \(L_0=2\), \(L_1=1\) и
$$L_{k+1}=L_k+L_{k-1}.$$
Реализации не строят всю последовательность с нуля. Сначала через fast doubling получается пара Фибоначчи \((F_k,F_{k+1})\), после чего используется формула
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k.$$
Так сразу находятся стартовые значения \(L_r\) и \(L_{r+1}\) за \(O(\log n)\) времени.
Коэффициенты \(T_t\) порождаются назад от правого края:
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
Эта рекурсия не случайна. Она совпадает с отношением ballot numbers, то есть коэффициентов из треугольника Каталана. Замкнутая формула имеет вид
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$$
Тем самым исходная задача сводится к сумме по числам Лукаса с очень регулярными комбинаторными весами.
Поскольку и веса, и числа Лукаса можно обновлять в обратном направлении, достаточно одного прохода \(t=r,r-1,\dots,1\). Из рекурсии Лукаса следует
$$L_{t-1}=L_{t+1}-L_t\pmod{M}.$$
На каждом шаге к ответу добавляется
$$T_tL_{t+1}\pmod{M},$$
после чего коэффициент умножается на рациональный переходный множитель, а пара Lucas сдвигается на один индекс назад. Хранить все коэффициенты и все значения Лукаса не нужно.
При \(n=8\) имеем \(r=7\). Начиная с \(T_7=1\), рекурсия дает
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
Нужные числа Лукаса равны
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
Следовательно,
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
что совпадает с проверкой, используемой в реализациях.
Знаменатель в обновлении коэффициента равен
$$d_t=t(r-t+1).$$
Так как \(r=10^8-1\lt M\), оба множителя ненулевые по модулю \(M\), значит каждое \(d_t\) обратимо. Если находить обратный для каждого шага отдельно, получится слишком дорого. Поэтому знаменатели обрабатываются блоками. Для блока \(d_1,\dots,d_m\) достаточно одного обратного к общему произведению:
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
Так \(m\) дорогих возведений в степень заменяются одним возведением и \(O(m)\) умножениями.
Реализации на C++, Python и Java следуют одному и тому же плану. Сначала они получают стартовую пару чисел Лукаса с помощью fast doubling по модулю \(M\). Затем рекурсия по коэффициентам обрабатывается от больших \(t\) к меньшим \(t\) блоками фиксированного размера: внутри блока строятся знаменатели \(t(r-t+1)\), после чего их обратные вычисляются все сразу.
Далее внутри блока реализация добавляет текущий вклад \(T_tL_{t+1}\), обновляет коэффициент с использованием уже подготовленного обратного и сдвигает пару Lucas назад по формуле \(L_{t-1}=L_{t+1}-L_t\). Такой потоковый подход сохраняет маленькое потребление памяти и одновременно воспроизводит контрольные значения \(f(8)=2663\) и \(f(20)=742296999\).
Fast doubling требует \(O(\log n)\) времени. Основной цикл посещает каждый индекс \(t\) ровно один раз, поэтому суммарная работа составляет \(O(n)\) модульных умножений. Блочная инверсия делает число модульных возведений в степень пропорциональным числу блоков, а не числу слагаемых. При размере блока \(B\) память равна \(O(B)\), а итоговое время линейно по \(n\) с очень маленькой логарифмической фазой запуска.
القيمة المطلوبة في Problem 739 تُحسب عند \(n=10^8\) بترديد \(M=10^9+7\). بعد تبسيط بناء التكرار المتتالي لعمليات الجمع، يمكن كتابة المطلوب على شكل مجموع موزون واحد لأعداد لوكاس:
$$f(n)=\sum_{t=1}^{r} T_t\,L_{t+1}\pmod{M},\qquad r=n-1.$$
الصعوبة الحقيقية ليست في أعداد لوكاس نفسها، بل في كبر \(r\). أي طريقة تربيعية مستحيلة، وحتى المرور الخطي يصبح بطيئاً جداً إذا احتاج كل حد إلى معكوس ضربي مستقل. لذلك تعتمد الفكرة الصحيحة على تحديث الأوزان من الخلف، وتحريك قيم لوكاس بالتزامن، وحساب المعكوسات على شكل كتل.
الحل يجمع بين هويات أعداد لوكاس، ومتتالية أوزان من نوع أعداد ballot، وطريقة عكس معياري على دفعات.
متتالية لوكاس تحقق \(L_0=2\) و \(L_1=1\) والعلاقة
$$L_{k+1}=L_k+L_{k-1}.$$
التطبيقات لا تبني المتتالية من بدايتها. بدلاً من ذلك تحسب أولاً زوج فيبوناتشي \((F_k,F_{k+1})\) بطريقة fast doubling ثم تستخدم
$$L_k=F_{k-1}+F_{k+1}=2F_{k+1}-F_k.$$
وبهذا نحصل على القيم الابتدائية \(L_r\) و \(L_{r+1}\) في زمن \(O(\log n)\).
المعاملات \(T_t\) تُولد عكسياً ابتداءً من الطرف الأخير:
$$T_r=1,$$
$$T_{t-1}=T_t\cdot \frac{(t-1)(2r-t)}{t(r-t+1)}\qquad (2\le t\le r).$$
هذه العلاقة ليست اعتباطية، بل هي بالضبط نسبة معاملات أعداد ballot أو صف من مثلث كاتالان. والصيغة المغلقة هي
$$T_t=\frac{t}{r}\binom{2r-t-1}{r-1}=\binom{2r-t-1}{r-1}-\binom{2r-t-1}{r}.$$
إذن المشكلة تنقلب إلى جمع قيم لوكاس مع أوزان توافقية منتظمة جداً.
بما أن الأوزان وأعداد لوكاس يمكن تحديثها عكسياً، فمرور واحد من \(t=r\) نزولاً إلى \(1\) يكفي. وبإعادة ترتيب علاقة لوكاس نحصل على
$$L_{t-1}=L_{t+1}-L_t\pmod{M}.$$
في كل خطوة نضيف أولاً
$$T_tL_{t+1}\pmod{M}$$
إلى الجواب، ثم نحدث المعامل بالعامل النسبي أعلاه، ثم نرجع زوج لوكاس خطوة واحدة إلى الخلف. لذلك لا حاجة لتخزين كل المعاملات أو كل أعداد لوكاس.
عندما \(n=8\) يكون \(r=7\). انطلاقاً من \(T_7=1\) تعطي العلاقة
$$T_7=1,\quad T_6=6,\quad T_5=20,\quad T_4=48,\quad T_3=90,\quad T_2=132,\quad T_1=132.$$
أما قيم لوكاس المطلوبة فهي
$$L_2=3,\quad L_3=4,\quad L_4=7,\quad L_5=11,\quad L_6=18,\quad L_7=29,\quad L_8=47.$$
وعليه
$$f(8)=132\cdot 3+132\cdot 4+90\cdot 7+48\cdot 11+20\cdot 18+6\cdot 29+1\cdot 47=2663,$$
وهو تماماً مقدار التحقق المستخدم في التطبيقات.
المقام في تحديث المعامل هو
$$d_t=t(r-t+1).$$
ولأن \(r=10^8-1\lt M\)، فإن كلا العاملين غير صفريين بترديد \(M\)، وبالتالي كل \(d_t\) قابل للعكس. حساب معكوس مستقل لكل خطوة سيكون مكلفاً جداً. لذلك تُجمع المقامات في كتل. فإذا كانت لدينا كتلة \(d_1,\dots,d_m\)، فإن معكوس حاصل الضرب الكلي يكفي:
$$d_i^{-1}=\left(\prod_{j=1}^{m} d_j\right)^{-1}\prod_{j\ne i} d_j \pmod{M}.$$
وبهذا نستبدل \(m\) عملية أسية معيارية مكلفة بعملية أسية واحدة مع \(O(m)\) عملية ضرب.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولاً تُحسب القيمتان الابتدائيتان من أعداد لوكاس باستخدام fast doubling تحت الترديد \(M\). بعد ذلك تُعالج علاقة المعاملات من \(t\) الكبير إلى \(t\) الصغير على شكل كتل ذات حجم ثابت، حيث تُبنى مقامات الكتلة \(t(r-t+1)\) ثم تُستخرج جميع معكوساتها دفعة واحدة.
داخل كل كتلة تضيف الشيفرة الحد الحالي \(T_tL_{t+1}\)، ثم تحدّث المعامل باستعمال المعكوس الجاهز لهذه الخطوة، ثم ترجع زوج لوكاس خطوة إلى الخلف باستخدام \(L_{t-1}=L_{t+1}-L_t\). هذا التصميم المتدفق يحافظ على استهلاك ذاكرة صغير، ويعيد أيضاً نقاط التحقق \(f(8)=2663\) و \(f(20)=742296999\).
التهيئة بطريقة fast doubling تكلف \(O(\log n)\). الحلقة الرئيسية تزور كل قيمة \(t\) مرة واحدة فقط، لذلك يكون العمل الكلي \(O(n)\) من الضربيات المعيارية. وبفضل العكس على شكل كتل، يصبح عدد عمليات الأس المعياري متناسباً مع عدد الكتل لا مع عدد الحدود. إذا كان حجم الكتلة \(B\)، فالاستهلاك التخزيني هو \(O(B)\)، والزمن الكلي خطي في \(n\) مع كلفة ابتدائية لوغاريتمية صغيرة جداً.