Starting from \(S_0=0\), \(S_1=01\), and \(S_n=S_{n-1}S_{n-2}\), every finite factor of the resulting infinite Fibonacci word is called a Fibonacci subword. For each positive \(k\), exactly \(k+1\) distinct factors have length \(k\). Reading each factor as a base-10 integer, leading zeros included harmlessly, we must compute the sum of their squares
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2$$
for \(k=10^{18}\), modulo \(M=101001001\). Neither a word of that length nor its \(k+1\) factors can be constructed explicitly.
Let \(f_n=|S_n|\). Then \(f_0=1\), \(f_1=2\), and
$$f_n=f_{n-1}+f_{n-2}.$$
Choose the smallest \(n\) for which \(L=f_n\gt k\), and put \(W=S_n=w_0w_1\cdots w_{L-1}\). A standard factor property of the Fibonacci word says that the \(L\) cyclic windows of length \(k\) in \(W\) contain all \(k+1\) distinct length-\(k\) factors. Since \(L\) windows represent only \(k+1\) values,
$$\delta=L-k-1$$
of those occurrences are redundant. With the standard indexing used here, one extra copy of each of the first \(\delta\) consecutive windows must be removed. Thus the problem becomes
$$\Psi(k)=\text{sum over all cyclic windows of }W -\text{sum of squares of the first }\delta\text{ windows}.$$
For \(k=10^{18}\), the index \(n\) is only \(O(\log k)\), although \(L\) itself is enormous.
The implementation never expands \(S_n\). A leaf stores one bit, and an internal node stores two child identifiers and their total length. The recurrence \(S_n=S_{n-1}S_{n-2}\) therefore adds just one concatenation node per Fibonacci level. A prefix of any required length is obtained recursively: it lies wholly in the left child, or it is the entire left child followed by a prefix of the right child.
Concatenations and prefixes are memoized. Consequently, a prefix whose numerical length may be near \(10^{18}\) is still represented by only \(O(\log k)\) nodes.
Work modulo \(M\), with \(b=10\). Because \(\gcd(10,M)=\gcd(99,M)=1\), both \(b^{-1}\) and \((b^2-1)^{-1}\) exist modulo \(M\). For a word \(X=x_0x_1\cdots x_{m-1}\), define
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i.$$
\(R_b(X)\) is exactly the usual decimal value of \(X\) modulo \(M\). The pair summary \(P_b\) groups every pair of 1-bits by their distance.
If \(X=UV\), \(a=|U|\), and \(c=|V|\), all four values combine without inspecting a digit:
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V).$$
The cross term in \(P_b\) is correct because a bit \(i\) in \(U\) and a bit \(j\) in \(V\) are separated by \(a+j-i\) positions. The code caches these summaries for both bases \(b\) and \(b^{-1}\).
Two additional recursive queries filter pairs without opening the word. The difference query computes
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
and the sum-index query computes
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}.$$
When the requested range covers an entire node pair, the answer factors into two cached polynomial summaries. Otherwise the longer node is split, the interval is shifted by the child offset, and the two answers are combined. Memoization prevents the same node-pair/range state from being solved twice.
For \(1\le d\lt L\), define the cyclic correlation
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}.$$
All nonzero cyclic distances can be packed into one polynomial:
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W).$$
The first term counts pairs that do not cross the end of \(W\); the second turns a linear distance \(j-i\) into its wrapped distance \(L-(j-i)\).
A length-\(k\) window can contain two positions only when their forward distance is \(1,\dots,k-1\). Put \(g=L-k\). The unwanted distances \(k,\dots,L-1\) are the reversals \(L-r\) of \(r=1,\dots,g\). Difference queries compute
$$E_b=\sum_{r=1}^{g}C_rb^r,$$
including both the ordinary and wrapped pieces. Hence the correlations actually used by windows are
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b.$$
Let \(V_s\) be the decimal value of the cyclic length-\(k\) window starting at \(s\). On expanding \(V_s^2\), diagonal digit terms and pairs of distinct positions separate cleanly.
Every 1-bit of \(W\) occupies every decimal place once across all cyclic windows. Its diagonal contribution is therefore
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}.$$
For a fixed cyclic distance \(d\), \(1\le d\lt k\), a pair appears in \(k-d\) relative placements. The sum of its place-value products is
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}.$$
After summing over all correlations, the square sum of all \(L\) cyclic windows is
$$T_{\mathrm{cyc}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M.$$
This identity is the central compression step: exponentially many digit products collapse into two correlation evaluations and modular exponentiation.
If \(\delta=0\), the cyclic total already contains each factor once. Otherwise let \(V_0,\dots,V_{\delta-1}\) be the redundant prefix windows. The first value is \(R_b\) of a compressed prefix of length \(k\).
Put \(m=\delta-1\), and call the outgoing prefix \(x_0,\dots,x_{m-1}\). On this redundant run the entering block is the reversal of that prefix, so the bit entering at transition \(t\) is \(x_{m-1-t}\). The rolling decimal recurrence is therefore
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m.$$
Expanding this recurrence expresses every \(V_t\) in terms of \(V_0\), the outgoing prefix, and its reversal. Squaring and summing needs only counts of 1-bits, weighted bit pairs, the reversal diagonal \(\sum_t x_tx_{m-1-t}\), and two triangular index ranges. Those are precisely the cached summaries and \(A_b\) range queries. The method duplicated_window_sum evaluates the resulting telescoping/geometric expression modulo \(M\), then the final answer is
$$\Psi(k)\equiv T_{\mathrm{cyc}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M.$$
The first standard word longer than 3 is \(W=S_3=01001\), with \(L=5\) and \(\delta=5-3-1=1\). Its five cyclic windows are
$$010, 100, 001, 010, 101.$$
The first window \(010\) is the one redundant occurrence. Subtracting one copy leaves \(001,010,100,101\), so
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
FibonacciSubwords builds the logarithmic standard-word DAG and caches powers of \(10\) and \(10^{-1}\). summarize implements the four concatenation formulas; difference_query filters correlations by \(j-i\), while sum_query handles the triangular products needed by the duplicate correction.
solve selects \(L\), forms \(Q_b\), removes separations too large for a \(k\)-window, evaluates \(T_{\mathrm{cyc}}\), and subtracts duplicated_window_sum. All arithmetic is reduced modulo \(101001001\).
The checkpoint suite constructs actual Fibonacci strings only for small inputs. It confirms \(\Psi(3)=20302\), compares the compressed solver with direct set enumeration for every \(1\le k\le50\), and verifies the supplied value \(\Psi(10)\equiv10699667\pmod M\).
There are \(O(\log k)\) Fibonacci levels and prefix nodes. The memoized two-word range queries visit at most a quadratic number of relevant node-pair states, giving \(O(\log^2 k)\) structural work and \(O(\log^2 k)\) cached memory; modular exponentiation contributes \(O(\log k)\) multiplications per previously unseen exponent.
No operation is linear in \(k\), and no length-\(k\) string is stored. This is what makes \(k=10^{18}\) practical.
Aus \(S_0=0\), \(S_1=01\) und \(S_n=S_{n-1}S_{n-2}\) entsteht das unendliche Fibonacci-Wort. Jeder endliche Faktor davon heißt Fibonacci-Teilwort. Für jedes positive \(k\) gibt es genau \(k+1\) verschiedene Faktoren der Länge \(k\). Als Dezimalzahlen gelesen sollen ihre Quadrate summiert werden:
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2.$$
Gesucht ist dieser Wert für \(k=10^{18}\) modulo \(M=101001001\). Ein Wort dieser Länge oder seine \(k+1\) Faktoren dürfen also niemals explizit aufgebaut werden.
Mit \(f_n=|S_n|\) gilt \(f_0=1\), \(f_1=2\) und
$$f_n=f_{n-1}+f_{n-2}.$$
Sei \(n\) minimal mit \(L=f_n\gt k\), und sei \(W=S_n=w_0w_1\cdots w_{L-1}\). Eine Standardeigenschaft des Fibonacci-Wortes besagt: Die \(L\) zyklischen Fenster der Länge \(k\) in \(W\) enthalten alle \(k+1\) verschiedenen Faktoren dieser Länge. Daher sind
$$\delta=L-k-1$$
Vorkommen redundant. Bei der hier verwendeten Standardindexierung muss je eine zusätzliche Kopie der ersten \(\delta\) aufeinanderfolgenden Fenster entfernt werden. Somit gilt
$$\Psi(k)=\text{Quadratsumme aller zyklischen Fenster von }W -\text{Quadratsumme der ersten }\delta\text{ Fenster}.$$
Obwohl \(L\) riesig sein kann, besitzt sein Fibonacci-Index nur Größe \(O(\log k)\).
Die Implementierung expandiert \(S_n\) nicht. Ein Blatt speichert ein Bit, ein innerer Knoten zwei Kindkennungen und die Gesamtlänge. Wegen \(S_n=S_{n-1}S_{n-2}\) genügt ein neuer Verkettungsknoten pro Fibonacci-Stufe. Ein Präfix gegebener Länge liegt entweder vollständig im linken Kind oder besteht aus dem ganzen linken Kind und einem Präfix des rechten.
Verkettungen und Präfixe werden gespeichert. Damit braucht selbst ein Präfix numerischer Länge nahe \(10^{18}\) nur \(O(\log k)\) DAG-Knoten.
Alle Rechnungen erfolgen modulo \(M\), mit \(b=10\). Weil \(\gcd(10,M)=\gcd(99,M)=1\), existieren \(b^{-1}\) und \((b^2-1)^{-1}\) modulo \(M\). Für \(X=x_0x_1\cdots x_{m-1}\) definieren wir
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i.$$
\(R_b(X)\) ist der übliche Dezimalwert des Wortes modulo \(M\). \(P_b(X)\) fasst alle Paare von Eins-Bits nach ihrem Abstand zusammen.
Für \(X=UV\), \(a=|U|\) und \(c=|V|\) gelten die Verkettungsformeln
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V).$$
Im Kreuzterm von \(P_b\) beträgt der Abstand zwischen Position \(i\) in \(U\) und Position \(j\) in \(V\) genau \(a+j-i\). Der Code speichert diese Zusammenfassungen sowohl für \(b\) als auch für \(b^{-1}\).
Zwei rekursive Abfragen filtern Bitpaare, ohne das Wort zu öffnen. Die Differenzabfrage berechnet
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
die Indexsummenabfrage dagegen
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}.$$
Deckt das Intervall ein ganzes Knotenpaar ab, faktorisiert das Ergebnis in zwei gespeicherte Polynomsummen. Andernfalls wird der längere Knoten geteilt, das Intervall um den Kindversatz verschoben und beide Teilergebnisse werden addiert. Memoisierung verhindert doppelte Arbeit.
Für \(1\le d\lt L\) sei
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}.$$
Alle nichttrivialen zyklischen Abstände stecken im Polynom
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W).$$
Der erste Summand zählt nicht umlaufende Paare. Der zweite ersetzt einen linearen Abstand \(j-i\) durch den umlaufenden Abstand \(L-(j-i)\).
In ein Fenster der Länge \(k\) passen nur Vorwärtsabstände \(1,\dots,k-1\). Setze \(g=L-k\). Die unerwünschten Abstände \(k,\dots,L-1\) sind die Umkehrungen \(L-r\) für \(r=1,\dots,g\). Mit Differenzabfragen wird
$$E_b=\sum_{r=1}^{g}C_rb^r$$
berechnet. Die wirklich benötigten Korrelationen sind daher
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b.$$
Sei \(V_s\) der Dezimalwert des bei \(s\) beginnenden zyklischen Fensters der Länge \(k\). Beim Ausmultiplizieren von \(V_s^2\) trennen sich Diagonalterme und Paare verschiedener Positionen.
Über alle zyklischen Fenster erscheint jedes Eins-Bit von \(W\) genau einmal an jeder Dezimalstelle. Der Diagonalbeitrag ist
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}.$$
Ein Paar mit festem zyklischen Abstand \(d\), \(1\le d\lt k\), tritt in \(k-d\) relativen Lagen auf. Seine Stellenwertprodukte summieren sich zu
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}.$$
Damit lautet die Quadratsumme aller \(L\) zyklischen Fenster
$$T_{\mathrm{zykl}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M.$$
Diese Identität ist der zentrale Kompressionsschritt: Alle Ziffernprodukte werden auf zwei Korrelationswerte und modulare Potenzen reduziert.
Für \(\delta=0\) enthält die zyklische Summe schon jeden Faktor genau einmal. Sonst seien \(V_0,\dots,V_{\delta-1}\) die redundanten Präfixfenster. \(V_0\) erhält man als \(R_b\) eines komprimierten Präfixes der Länge \(k\).
Setze \(m=\delta-1\) und nenne das austretende Präfix \(x_0,\dots,x_{m-1}\). Im redundanten Abschnitt ist die Folge der eintretenden Bits die Umkehrung dieses Präfixes; beim Übergang \(t\) tritt also \(x_{m-1-t}\) ein. Damit gilt
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m.$$
Nach dem Auflösen dieser Rekurrenz hängt jedes \(V_t\) nur von \(V_0\), dem austretenden Präfix und seiner Umkehrung ab. Zum Quadrieren und Summieren braucht man nur die Anzahl der Einsen, gewichtete Bitpaare, die Umkehrdiagonale \(\sum_t x_tx_{m-1-t}\) und zwei dreieckige Indexbereiche. Genau diese Größen liefern die Zusammenfassungen und \(A_b\)-Abfragen. duplicated_window_sum wertet die entstehende Teleskop- und geometrische Formel modulo \(M\) aus.
Schließlich gilt
$$\Psi(k)\equiv T_{\mathrm{zykl}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M.$$
Das erste Standardwort mit Länge größer als 3 ist \(W=S_3=01001\). Also \(L=5\) und \(\delta=5-3-1=1\). Seine zyklischen Fenster sind
$$010, 100, 001, 010, 101.$$
Das erste \(010\) ist das redundante Vorkommen. Übrig bleiben \(001,010,100,101\), und damit
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
FibonacciSubwords baut den logarithmischen DAG der Standardwörter und speichert Potenzen von \(10\) und \(10^{-1}\). summarize implementiert die vier Verkettungsformeln. difference_query filtert nach \(j-i\), während sum_query die dreieckigen Produkte der Duplikatkorrektur liefert.
solve wählt \(L\), konstruiert \(Q_b\), entfernt zu große Abstände, berechnet \(T_{\mathrm{zykl}}\) und zieht duplicated_window_sum ab. Jede Operation wird modulo \(101001001\) ausgeführt.
Die Kontrolltests erzeugen echte Fibonacci-Wörter nur für kleine Werte. Sie prüfen \(\Psi(3)=20302\), vergleichen den komprimierten Algorithmus für jedes \(1\le k\le50\) mit direkter Mengenerzeugung und bestätigen \(\Psi(10)\equiv10699667\pmod M\).
Es gibt \(O(\log k)\) Fibonacci-Stufen und Präfixknoten. Die gespeicherten Zweiwort-Abfragen besuchen höchstens quadratisch viele relevante Knotenpaarzustände, also \(O(\log^2 k)\) strukturelle Arbeit und \(O(\log^2 k)\) Speicher. Eine neue modulare Potenz kostet \(O(\log k)\) Multiplikationen.
Keine Operation läuft linear in \(k\), und kein Wort der Länge \(k\) wird gespeichert. Deshalb ist \(k=10^{18}\) praktisch berechenbar.
\(S_0=0\), \(S_1=01\) ve \(S_n=S_{n-1}S_{n-2}\) ile sonsuz Fibonacci sözcüğü elde edilir. Bu sözcüğün her sonlu faktörüne Fibonacci alt sözcüğü denir. Her pozitif \(k\) için uzunluğu \(k\) olan tam \(k+1\) farklı faktör vardır. Bunları onluk sayı olarak okuyup karelerini topluyoruz:
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2.$$
İstenen, \(k=10^{18}\) için bu toplamın \(M=101001001\) modundaki değeridir. Bu büyüklükteki sözcüğü ya da \(k+1\) faktörü açıkça üretmek olanaksızdır.
\(f_n=|S_n|\) dersek \(f_0=1\), \(f_1=2\) ve
$$f_n=f_{n-1}+f_{n-2}$$
olur. \(L=f_n\gt k\) koşulunu sağlayan en küçük \(n\)'yi seçip \(W=S_n=w_0w_1\cdots w_{L-1}\) yazalım. Fibonacci sözcüğünün standart bir faktör özelliğine göre \(W\)'deki \(L\) adet döngüsel \(k\)-penceresi, uzunluğu \(k\) olan \(k+1\) farklı faktörün hepsini içerir. Dolayısıyla
$$\delta=L-k-1$$
adet oluşum fazladır. Kullanılan standart indekslemede ilk \(\delta\) ardışık pencerenin birer fazladan kopyası çıkarılmalıdır. Yani
$$\Psi(k)=W\text{'nin tüm döngüsel pencerelerinin kare toplamı} -\text{ilk }\delta\text{ pencerenin kare toplamı}.$$
\(L\) devasa olsa da onu belirleyen Fibonacci indeksi yalnızca \(O(\log k)\) büyüklüğündedir.
Uygulama \(S_n\)'yi hiçbir zaman açmaz. Yaprak düğüm tek bit, iç düğüm iki çocuk kimliği ve toplam uzunluk saklar. \(S_n=S_{n-1}S_{n-2}\) bağıntısı her Fibonacci düzeyinde yalnızca bir yeni birleştirme düğümü gerektirir. İstenen bir önek ya bütünüyle sol çocuktadır ya da sol çocuğun tamamıyla sağ çocuğun bir öneğinin birleşimidir.
Birleştirme ve önek sonuçları önbelleğe alınır. Böylece sayısal uzunluğu \(10^{18}\)'e yakın bir önek bile \(O(\log k)\) düğümle temsil edilir.
\(b=10\) olmak üzere tüm işlemler \(M\) modunda yapılır. \(\gcd(10,M)=\gcd(99,M)=1\) olduğundan \(b^{-1}\) ile \((b^2-1)^{-1}\) bu modda vardır. \(X=x_0x_1\cdots x_{m-1}\) için
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i$$
tanımlarını kullanalım. \(R_b(X)\), \(X\)'in alışılmış onluk değeridir; \(P_b(X)\) ise 1-bit çiftlerini aralarındaki uzaklığa göre toplar.
\(X=UV\), \(a=|U|\), \(c=|V|\) ise rakamlara bakmadan
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V)$$
elde edilir. \(P_b\)'deki çapraz terim doğrudur; çünkü \(U\)'daki \(i\) ile \(V\)'deki \(j\) konumları arasındaki uzaklık \(a+j-i\)'dir. Kod bu özetleri hem \(b\) hem \(b^{-1}\) tabanı için saklar.
İki özyinelemeli sorgu, sözcüğü açmadan bit çiftlerini süzer. Fark sorgusu
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
indeks-toplamı sorgusu ise
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}$$
değerini hesaplar. Aralık iki düğümün tüm çiftlerini kapsıyorsa sonuç iki önbellekli polinom özetine ayrışır. Aksi halde uzun düğüm bölünür, aralık çocuk ofseti kadar kaydırılır ve iki parça birleştirilir. Aynı durum ikinci kez çözülmez.
\(1\le d\lt L\) için
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}$$
döngüsel korelasyonunu tanımlayalım. Tüm sıfır olmayan döngüsel uzaklıklar
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W)$$
polinomunda toplanır. İlk terim sınırı aşmayan çiftleri sayar; ikinci terim doğrusal \(j-i\) uzaklığını sarılmış \(L-(j-i)\) uzaklığına dönüştürür.
Uzunluğu \(k\) olan bir pencere yalnız \(1,\dots,k-1\) ileri uzaklıklarını barındırabilir. \(g=L-k\) olsun. İstenmeyen \(k,\dots,L-1\) uzaklıkları, \(r=1,\dots,g\) için \(L-r\) biçimindedir. Fark sorguları
$$E_b=\sum_{r=1}^{g}C_rb^r$$
değerini verir. Böylece gerçekten kullanılan korelasyonlar
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b$$
olur.
\(V_s\), \(s\)'de başlayan döngüsel \(k\)-penceresinin onluk değeri olsun. \(V_s^2\) açıldığında köşegen rakam terimleriyle farklı konum çiftleri ayrılır.
\(W\)'deki her 1-bit, bütün döngüsel pencereler boyunca her onluk basamakta tam bir kez bulunur. Köşegen katkısı
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}$$
olur. Sabit \(d\) döngüsel uzaklığındaki bir çift, \(1\le d\lt k\), \(k-d\) göreli yerleşimde görünür. Basamak değeri çarpımlarının toplamı
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}$$
olduğundan tüm \(L\) döngüsel pencerenin kare toplamı
$$T_{\mathrm{dong}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M$$
şeklindedir. Böylece sayısız rakam çarpımı iki korelasyon değeriyle modüler üs almaya indirgenir.
\(\delta=0\) ise döngüsel toplam her faktörü zaten bir kez içerir. Aksi halde \(V_0,\dots,V_{\delta-1}\) yinelenen önek pencereleri olsun. \(V_0\), uzunluğu \(k\) olan sıkıştırılmış öneğin \(R_b\) özetidir.
\(m=\delta-1\) olsun ve çıkan öneği \(x_0,\dots,x_{m-1}\) diye adlandıralım. Yinelenen bölümde giren bit dizisi bu öneğin tersidir; \(t\) geçişinde giren bit \(x_{m-1-t}\) olur. Kayan onluk değer bağıntısı
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m$$
biçimindedir. Bağıntı açıldığında her \(V_t\), yalnız \(V_0\), çıkan önek ve onun tersine bağlıdır. Kareleri toplamak için gereken 1-bit sayısı, ağırlıklı bit çiftleri, ters çifti köşegeni \(\sum_t x_tx_{m-1-t}\) ve iki üçgensel indeks aralığı; özetler ile \(A_b\) sorgularından doğrudan gelir. duplicated_window_sum ortaya çıkan teleskopik/geometrik ifadeyi \(M\) modunda hesaplar.
Sonuç
$$\Psi(k)\equiv T_{\mathrm{dong}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M$$
olur.
3'ten uzun ilk standart sözcük \(W=S_3=01001\)'dir; \(L=5\), \(\delta=5-3-1=1\). Beş döngüsel pencere
$$010, 100, 001, 010, 101$$
olur. İlk \(010\) fazladan oluşumdur. \(001,010,100,101\) kaldığı için
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
FibonacciSubwords, standart sözcüklerin logaritmik DAG'ını kurar ve \(10\) ile \(10^{-1}\) kuvvetlerini önbelleğe alır. summarize dört birleştirme formülünü uygular. difference_query çiftleri \(j-i\)'ye göre, sum_query ise yinelenen pencere düzeltmesinde gerekli \(i+j\)'ye göre süzer.
solve, \(L\)'yi seçer, \(Q_b\)'yi kurar, \(k\)-penceresine sığmayan uzaklıkları çıkarır, \(T_{\mathrm{dong}}\)'ü hesaplar ve duplicated_window_sum değerini düşer. Bütün aritmetik \(101001001\) modundadır.
Kontrol noktaları yalnız küçük girdiler için gerçek Fibonacci dizgileri üretir. \(\Psi(3)=20302\) doğrulanır; sıkıştırılmış çözücü \(1\le k\le50\) aralığındaki her değer için doğrudan küme üretimiyle karşılaştırılır ve verilen \(\Psi(10)\equiv10699667\pmod M\) değeri denetlenir.
\(O(\log k)\) Fibonacci düzeyi ve önek düğümü vardır. Önbellekli iki-sözcük sorguları en fazla karesel sayıda ilgili düğüm-çifti durumu ziyaret eder; yapısal zaman ve bellek \(O(\log^2 k)\)'dir. İlk kez istenen modüler kuvvet \(O(\log k)\) çarpım gerektirir.
Hiçbir işlem \(k\)'de doğrusal değildir ve uzunluğu \(k\) olan hiçbir dizgi saklanmaz. Bu yüzden \(k=10^{18}\) uygulanabilirdir.
A partir de \(S_0=0\), \(S_1=01\) y \(S_n=S_{n-1}S_{n-2}\) se obtiene la palabra infinita de Fibonacci. Cada factor finito suyo es una subpalabra de Fibonacci. Para cada \(k\) positivo existen exactamente \(k+1\) factores distintos de longitud \(k\). Interpretándolos como enteros decimales, debemos sumar sus cuadrados:
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2.$$
Se pide el resultado para \(k=10^{18}\), módulo \(M=101001001\). No es posible materializar una palabra de esa longitud ni sus \(k+1\) factores.
Sea \(f_n=|S_n|\). Entonces \(f_0=1\), \(f_1=2\) y
$$f_n=f_{n-1}+f_{n-2}.$$
Elegimos el menor \(n\) tal que \(L=f_n\gt k\), y escribimos \(W=S_n=w_0w_1\cdots w_{L-1}\). Una propiedad estándar de los factores de la palabra de Fibonacci afirma que las \(L\) ventanas cíclicas de longitud \(k\) de \(W\) contienen los \(k+1\) factores distintos. Por tanto hay
$$\delta=L-k-1$$
apariciones redundantes. Con la indexación estándar usada aquí hay que retirar una copia adicional de cada una de las primeras \(\delta\) ventanas consecutivas. En consecuencia,
$$\Psi(k)=\text{suma de cuadrados de todas las ventanas cíclicas de }W -\text{suma de cuadrados de las primeras }\delta\text{ ventanas}.$$
Aunque \(L\) sea enorme, su índice de Fibonacci solo tiene tamaño \(O(\log k)\).
La implementación nunca expande \(S_n\). Una hoja guarda un bit; un nodo interno guarda sus dos hijos y la longitud total. La recurrencia \(S_n=S_{n-1}S_{n-2}\) añade un único nodo por nivel. Un prefijo solicitado está enteramente en el hijo izquierdo, o es el hijo izquierdo completo seguido de un prefijo del derecho.
Las concatenaciones y los prefijos se memorizan. Así, incluso un prefijo de longitud numérica cercana a \(10^{18}\) necesita solo \(O(\log k)\) nodos.
Trabajamos módulo \(M\), con \(b=10\). Como \(\gcd(10,M)=\gcd(99,M)=1\), existen \(b^{-1}\) y \((b^2-1)^{-1}\) módulo \(M\). Para \(X=x_0x_1\cdots x_{m-1}\), definimos
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i.$$
\(R_b(X)\) es el valor decimal habitual de \(X\). \(P_b(X)\) agrupa cada pareja de bits 1 por su distancia.
Si \(X=UV\), \(a=|U|\) y \(c=|V|\), los resúmenes se combinan sin recorrer dígitos:
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V).$$
El término cruzado de \(P_b\) usa que las posiciones \(i\) de \(U\) y \(j\) de \(V\) están separadas por \(a+j-i\). El código conserva cada resumen tanto para \(b\) como para \(b^{-1}\).
Dos consultas recursivas filtran parejas sin abrir la palabra. La consulta de diferencias calcula
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
y la consulta de suma de índices calcula
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}.$$
Si el intervalo cubre por completo una pareja de nodos, la respuesta factoriza en dos resúmenes ya calculados. En caso contrario se divide el nodo más largo, se desplaza el intervalo según el hijo y se combinan los resultados. La memoización evita repetir estados.
Para \(1\le d\lt L\), sea
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}.$$
Todas las distancias cíclicas no nulas se codifican como
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W).$$
El primer término cuenta parejas que no cruzan el final; el segundo convierte una distancia lineal \(j-i\) en la distancia envuelta \(L-(j-i)\).
Una ventana de longitud \(k\) solo puede contener distancias hacia delante \(1,\dots,k-1\). Sea \(g=L-k\). Las distancias no deseadas \(k,\dots,L-1\) son \(L-r\), para \(r=1,\dots,g\). Las consultas de diferencias proporcionan
$$E_b=\sum_{r=1}^{g}C_rb^r,$$
y las correlaciones necesarias quedan
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b.$$
Sea \(V_s\) el valor decimal de la ventana cíclica de longitud \(k\) que comienza en \(s\). Al expandir \(V_s^2\), se separan los términos diagonales y las parejas de posiciones distintas.
Cada bit 1 de \(W\) ocupa una vez cada posición decimal al recorrer todas las ventanas. Su contribución diagonal es
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}.$$
Una pareja a distancia cíclica fija \(d\), con \(1\le d\lt k\), aparece en \(k-d\) posiciones relativas. Sus productos de valores posicionales suman
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}.$$
Así, la suma de cuadrados de las \(L\) ventanas cíclicas es
$$T_{\mathrm{cic}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M.$$
Esta identidad reduce todos los productos de dígitos a dos correlaciones y potencias modulares.
Si \(\delta=0\), el total cíclico ya cuenta cada factor una vez. En otro caso, sean \(V_0,\dots,V_{\delta-1}\) las ventanas redundantes del prefijo. \(V_0\) es el resumen \(R_b\) de un prefijo comprimido de longitud \(k\).
Sea \(m=\delta-1\), y llamemos \(x_0,\dots,x_{m-1}\) al prefijo saliente. En este tramo redundante, el bloque entrante es el reverso de ese prefijo; en la transición \(t\) entra \(x_{m-1-t}\). Por tanto, la recurrencia decimal es
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m.$$
Al desarrollar la recurrencia, cada \(V_t\) depende solo de \(V_0\), del prefijo saliente y de su reverso. Para elevar y sumar se requieren el número de unos, parejas ponderadas, la diagonal invertida \(\sum_t x_tx_{m-1-t}\) y dos intervalos triangulares; son exactamente los resúmenes y las consultas \(A_b\). duplicated_window_sum evalúa la expresión telescópica y geométrica resultante módulo \(M\).
Finalmente,
$$\Psi(k)\equiv T_{\mathrm{cic}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M.$$
La primera palabra estándar más larga que 3 es \(W=S_3=01001\). Tenemos \(L=5\) y \(\delta=1\). Sus ventanas cíclicas son
$$010, 100, 001, 010, 101.$$
La primera ventana \(010\) es la aparición redundante. Quedan \(001,010,100,101\), y
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
FibonacciSubwords construye el DAG logarítmico de palabras estándar y memoriza potencias de \(10\) y \(10^{-1}\). summarize aplica las cuatro fórmulas de concatenación; difference_query filtra por \(j-i\), y sum_query obtiene los productos triangulares de la corrección de duplicados.
solve elige \(L\), forma \(Q_b\), elimina las distancias que no caben en una ventana, calcula \(T_{\mathrm{cic}}\) y resta duplicated_window_sum. Toda la aritmética se reduce módulo \(101001001\).
Las validaciones construyen palabras reales solo para entradas pequeñas. Comprueban \(\Psi(3)=20302\), comparan el método comprimido con enumeración directa para cada \(1\le k\le50\), y verifican \(\Psi(10)\equiv10699667\pmod M\).
Hay \(O(\log k)\) niveles de Fibonacci y nodos de prefijo. Las consultas memorizadas visitan como máximo un número cuadrático de estados relevantes de parejas de nodos: \(O(\log^2 k)\) de trabajo estructural y memoria. Cada potencia modular nueva cuesta \(O(\log k)\) multiplicaciones.
Ninguna operación es lineal en \(k\), y nunca se almacena una cadena de longitud \(k\). Por eso \(k=10^{18}\) es viable.
从 \(S_0=0\)、\(S_1=01\) 以及 \(S_n=S_{n-1}S_{n-2}\) 出发，可以得到无限 Fibonacci 词。它的每个有限因子都称为 Fibonacci 子词。对每个正整数 \(k\)，长度为 \(k\) 的不同因子恰好有 \(k+1\) 个。把每个因子当作十进制整数，目标是计算
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2.$$
题目要求 \(k=10^{18}\) 时的结果模 \(M=101001001\)。显然不能显式构造如此长的词，也不能逐个枚举 \(k+1\) 个因子。
令 \(f_n=|S_n|\)，则 \(f_0=1\)、\(f_1=2\)，并且
$$f_n=f_{n-1}+f_{n-2}.$$
取满足 \(L=f_n\gt k\) 的最小 \(n\)，并记 \(W=S_n=w_0w_1\cdots w_{L-1}\)。Fibonacci 词的一个标准因子性质表明：\(W\) 的 \(L\) 个长度为 \(k\) 的循环窗口包含全部 \(k+1\) 个不同因子。因此有
$$\delta=L-k-1$$
个多余出现。按这里的标准编号，需要从最前面的 \(\delta\) 个连续窗口各删去一个额外副本。所以
$$\Psi(k)=W\text{ 的全部循环窗口的平方和} -\text{前 }\delta\text{ 个窗口的平方和}.$$
虽然 \(L\) 本身极大，但它的 Fibonacci 下标只有 \(O(\log k)\) 的规模。
程序从不展开 \(S_n\)。叶节点保存一个比特；内部节点保存两个子节点编号以及总长度。递推式 \(S_n=S_{n-1}S_{n-2}\) 在每一层只增加一个连接节点。求指定长度的前缀时，它要么完全落在左子节点中，要么等于完整左子节点再连接右子节点的一个前缀。
连接和前缀都被缓存。因此，即使前缀的数值长度接近 \(10^{18}\)，它仍只需 \(O(\log k)\) 个节点表示。
令 \(b=10\)，所有计算均在模 \(M\) 下进行。由于 \(\gcd(10,M)=\gcd(99,M)=1\)，\(b^{-1}\) 和 \((b^2-1)^{-1}\) 都存在。对 \(X=x_0x_1\cdots x_{m-1}\)，定义
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i.$$
\(R_b(X)\) 就是 \(X\) 的通常十进制值模 \(M\)；\(P_b(X)\) 按距离汇总所有两个 1 比特组成的对。
若 \(X=UV\)、\(a=|U|\)、\(c=|V|\)，则无需访问任何单独字符即可合并摘要：
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V).$$
\(P_b\) 的交叉项来自这样一个事实：\(U\) 中位置 \(i\) 与 \(V\) 中位置 \(j\) 的距离为 \(a+j-i\)。代码对底数 \(b\) 和 \(b^{-1}\) 都缓存这些摘要。
两个递归查询无需展开词就能筛选比特对。差值查询计算
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
下标和查询计算
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}.$$
若区间覆盖一对节点的全部组合，答案可分解成两个已缓存的多项式摘要。否则拆分较长节点，按子节点偏移平移区间，再合并两个结果。记忆化保证同一节点对和区间状态只求解一次。
对 \(1\le d\lt L\)，定义
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}.$$
所有非零循环距离可压入一个多项式：
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W).$$
第一项统计不跨越词尾的比特对；第二项把线性距离 \(j-i\) 转成绕回后的距离 \(L-(j-i)\)。
长度为 \(k\) 的窗口只能同时包含前向距离 \(1,\dots,k-1\) 的位置。令 \(g=L-k\)。不需要的距离 \(k,\dots,L-1\) 正是 \(r=1,\dots,g\) 对应的 \(L-r\)。差值查询得到
$$E_b=\sum_{r=1}^{g}C_rb^r,$$
因此窗口真正使用的相关量为
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b.$$
令 \(V_s\) 为从位置 \(s\) 开始的循环 \(k\)-窗口的十进制值。展开 \(V_s^2\) 后，对角数字项与两个不同位置的配对项可以分开处理。
遍历全部循环窗口时，\(W\) 中每个 1 比特在每个十进制位上恰好出现一次。因此对角贡献为
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}.$$
对固定循环距离 \(d\)，其中 \(1\le d\lt k\)，一个比特对有 \(k-d\) 种相对位置。位值乘积之和是
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}.$$
所以全部 \(L\) 个循环窗口的平方和为
$$T_{\mathrm{cyc}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M.$$
这个恒等式是关键压缩：海量数字乘积被化成两个相关量与若干模幂。
若 \(\delta=0\)，循环总和已经把每个因子计算一次。否则令 \(V_0,\dots,V_{\delta-1}\) 为多余的前缀窗口。\(V_0\) 可由长度为 \(k\) 的压缩前缀的 \(R_b\) 摘要直接得到。
令 \(m=\delta-1\)，并把离开窗口的前缀记作 \(x_0,\dots,x_{m-1}\)。在重复区间中，进入窗口的比特块是该前缀的逆序，所以第 \(t\) 次转移进入的是 \(x_{m-1-t}\)。十进制滑动递推为
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m.$$
展开递推后，每个 \(V_t\) 只依赖 \(V_0\)、离开的前缀及其逆序。平方求和所需的信息只有 1 的个数、加权比特对、逆序对角线 \(\sum_t x_tx_{m-1-t}\) 和两个三角形下标区间，恰好都能由摘要及 \(A_b\) 查询给出。duplicated_window_sum 在模 \(M\) 下计算由此得到的望远镜式和等比式。
最终
$$\Psi(k)\equiv T_{\mathrm{cyc}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M.$$
第一个长度大于 3 的标准词是 \(W=S_3=01001\)，故 \(L=5\)、\(\delta=1\)。五个循环窗口为
$$010,\ 100,\ 001,\ 010,\ 101.$$
第一个 \(010\) 是多余出现。留下 \(001,010,100,101\)，于是
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
FibonacciSubwords 建立标准词的对数规模 DAG，并缓存 \(10\) 与 \(10^{-1}\) 的幂。summarize 实现四个连接公式；difference_query 按 \(j-i\) 筛选，而 sum_query 处理重复窗口修正所需的三角形乘积。
solve 选择 \(L\)，构造 \(Q_b\)，删去装不进 \(k\)-窗口的距离，计算 \(T_{\mathrm{cyc}}\)，再减去 duplicated_window_sum。全部算术均模 \(101001001\)。
检查点只对小输入构造真实 Fibonacci 字符串。它验证 \(\Psi(3)=20302\)，对每个 \(1\le k\le50\) 将压缩算法与直接集合枚举比较，并检查题目给出的 \(\Psi(10)\equiv10699667\pmod M\)。
Fibonacci 层数和前缀节点数都是 \(O(\log k)\)。记忆化双词查询至多访问二次数量的相关节点对状态，因此结构计算时间和缓存空间均为 \(O(\log^2 k)\)；每个首次出现的模幂需要 \(O(\log k)\) 次乘法。
没有任何操作与 \(k\) 成线性关系，也不会保存长度为 \(k\) 的字符串，所以 \(k=10^{18}\) 可以快速处理。
Из \(S_0=0\), \(S_1=01\) и \(S_n=S_{n-1}S_{n-2}\) получается бесконечное слово Фибоначчи. Каждый его конечный фактор называется подсловом Фибоначчи. Для любого положительного \(k\) существует ровно \(k+1\) различных факторов длины \(k\). Считая их десятичными числами, требуется найти
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2.$$
Нужен результат для \(k=10^{18}\) по модулю \(M=101001001\). Явно строить слово такой длины или перечислять его \(k+1\) факторов невозможно.
Положим \(f_n=|S_n|\). Тогда \(f_0=1\), \(f_1=2\) и
$$f_n=f_{n-1}+f_{n-2}.$$
Выберем минимальное \(n\), для которого \(L=f_n\gt k\), и обозначим \(W=S_n=w_0w_1\cdots w_{L-1}\). Стандартное свойство факторов слова Фибоначчи утверждает, что \(L\) циклических окон длины \(k\) в \(W\) содержат все \(k+1\) различных факторов. Поэтому
$$\delta=L-k-1$$
вхождений лишние. При используемой стандартной индексации надо вычесть по одной дополнительной копии первых \(\delta\) последовательных окон. Следовательно,
$$\Psi(k)=\text{сумма квадратов всех циклических окон }W -\text{сумма квадратов первых }\delta\text{ окон}.$$
Само \(L\) огромно, но его индекс Фибоначчи имеет размер лишь \(O(\log k)\).
Реализация никогда не раскрывает \(S_n\). Лист хранит один бит, внутренний узел — два дочерних идентификатора и общую длину. Рекурсия \(S_n=S_{n-1}S_{n-2}\) добавляет всего один узел на уровень. Префикс заданной длины либо целиком лежит в левом потомке, либо состоит из всего левого потомка и префикса правого.
Конкатенации и префиксы мемоизируются. Поэтому даже префикс численной длины около \(10^{18}\) представляется \(O(\log k)\) узлами.
Работаем по модулю \(M\), где \(b=10\). Так как \(\gcd(10,M)=\gcd(99,M)=1\), обратные \(b^{-1}\) и \((b^2-1)^{-1}\) существуют. Для \(X=x_0x_1\cdots x_{m-1}\) определим
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i.$$
\(R_b(X)\) — обычное десятичное значение \(X\) по модулю \(M\), а \(P_b(X)\) группирует пары единичных битов по расстоянию.
Если \(X=UV\), \(a=|U|\), \(c=|V|\), то без просмотра символов получаем
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V).$$
Перекрёстный член в \(P_b\) следует из того, что позиции \(i\) в \(U\) и \(j\) в \(V\) разделены расстоянием \(a+j-i\). Сводки кэшируются для оснований \(b\) и \(b^{-1}\).
Два рекурсивных запроса фильтруют пары битов, не раскрывая слово. Разностный запрос вычисляет
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
а запрос по сумме индексов —
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}.$$
Если диапазон покрывает всю пару узлов, ответ раскладывается в произведение двух готовых полиномиальных сводок. Иначе более длинный узел делится, границы сдвигаются на смещение дочернего узла, а результаты складываются. Мемоизация исключает повторное решение состояния.
Для \(1\le d\lt L\) определим
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}.$$
Все ненулевые циклические расстояния упаковываются в полином
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W).$$
Первый член учитывает пары без перехода через конец \(W\); второй превращает линейное расстояние \(j-i\) в циклическое \(L-(j-i)\).
В окно длины \(k\) помещаются только прямые расстояния \(1,\dots,k-1\). Пусть \(g=L-k\). Ненужные расстояния \(k,\dots,L-1\) имеют вид \(L-r\), где \(r=1,\dots,g\). Разностные запросы вычисляют
$$E_b=\sum_{r=1}^{g}C_rb^r.$$
Нужные корреляции равны
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b.$$
Пусть \(V_s\) — десятичное значение циклического окна длины \(k\), начинающегося в \(s\). При раскрытии \(V_s^2\) диагональные цифровые члены отделяются от пар различных позиций.
Во всех циклических окнах каждый единичный бит \(W\) один раз занимает каждый десятичный разряд. Поэтому диагональный вклад равен
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}.$$
Пара с фиксированным циклическим расстоянием \(d\), \(1\le d\lt k\), встречается в \(k-d\) относительных положениях. Сумма произведений разрядных весов равна
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}.$$
Итак, сумма квадратов всех \(L\) циклических окон:
$$T_{\mathrm{cyc}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M.$$
Это ключевое сжатие: все произведения цифр заменяются двумя корреляциями и модульными степенями.
Если \(\delta=0\), циклическая сумма уже содержит каждый фактор один раз. Иначе пусть \(V_0,\dots,V_{\delta-1}\) — лишние префиксные окна. \(V_0\) получается как \(R_b\) сжатого префикса длины \(k\).
Пусть \(m=\delta-1\), а выходящий префикс равен \(x_0,\dots,x_{m-1}\). На повторяющемся участке входящий блок является обращением этого префикса, поэтому при переходе \(t\) входит \(x_{m-1-t}\). Рекурсия скользящего десятичного значения имеет вид
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m.$$
После раскрытия каждое \(V_t\) зависит только от \(V_0\), выходящего префикса и его обращения. Для суммы квадратов требуются лишь число единиц, взвешенные пары, обратная диагональ \(\sum_t x_tx_{m-1-t}\) и два треугольных диапазона индексов. Их дают сводки и запросы \(A_b\). Метод duplicated_window_sum вычисляет получившееся телескопическое и геометрическое выражение по модулю \(M\).
Окончательно
$$\Psi(k)\equiv T_{\mathrm{cyc}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M.$$
Первое стандартное слово длиннее 3 — \(W=S_3=01001\). Здесь \(L=5\), \(\delta=1\). Его циклические окна:
$$010,\ 100,\ 001,\ 010,\ 101.$$
Первое \(010\) — лишнее вхождение. Остаются \(001,010,100,101\), поэтому
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
FibonacciSubwords строит логарифмический DAG стандартных слов и кэширует степени \(10\) и \(10^{-1}\). summarize реализует четыре формулы конкатенации; difference_query фильтрует по \(j-i\), а sum_query даёт треугольные произведения для коррекции повторов.
solve выбирает \(L\), строит \(Q_b\), удаляет слишком большие расстояния, вычисляет \(T_{\mathrm{cyc}}\) и вычитает duplicated_window_sum. Вся арифметика выполняется по модулю \(101001001\).
Проверки строят настоящие строки Фибоначчи лишь для малых входов. Они подтверждают \(\Psi(3)=20302\), сравнивают сжатый алгоритм с прямым множеством для каждого \(1\le k\le50\) и проверяют данное \(\Psi(10)\equiv10699667\pmod M\).
Число уровней Фибоначчи и префиксных узлов равно \(O(\log k)\). Мемоизированные запросы посещают не более квадратичного числа существенных состояний пар узлов, то есть требуют \(O(\log^2 k)\) структурного времени и памяти. Новая модульная степень требует \(O(\log k)\) умножений.
Нет операций, линейных по \(k\), и строка длины \(k\) не хранится. Поэтому \(k=10^{18}\) обрабатывается практически.
نبدأ من \(S_0=0\) و\(S_1=01\)، ثم نعرّف \(S_n=S_{n-1}S_{n-2}\)، فنحصل على كلمة فيبوناتشي اللانهائية. كل عامل متصل محدود منها يسمى كلمة فيبوناتشي فرعية. لكل \(k\) موجب يوجد بالضبط \(k+1\) عامل مختلف بطول \(k\). نقرأ كل عامل عدداً عشرياً، ثم نحسب
$$\Psi(k)=\sum_{u\in\mathcal F_k}\operatorname{val}_{10}(u)^2.$$
المطلوب هو القيمة عند \(k=10^{18}\) بترديد \(M=101001001\). لا يمكن بناء كلمة بهذا الطول أو تعداد عواملها \(k+1\) صراحةً.
لنضع \(f_n=|S_n|\). عندئذ \(f_0=1\)، و\(f_1=2\)، و
$$f_n=f_{n-1}+f_{n-2}.$$
نختار أصغر \(n\) يحقق \(L=f_n\gt k\)، ونكتب \(W=S_n=w_0w_1\cdots w_{L-1}\). من خواص عوامل كلمة فيبوناتشي أن النوافذ الدورية \(L\) ذات الطول \(k\) في \(W\) تحتوي العوامل المختلفة \(k+1\) كلها. لذلك يوجد
$$\delta=L-k-1$$
ظهور زائد. مع الفهرسة القياسية المستعملة هنا يجب حذف نسخة إضافية من كل نافذة من النوافذ المتتالية الأولى وعددها \(\delta\). إذن
إذا رمزنا إلى مجموع النوافذ الدورية بـ \(T_{\mathrm{cyc}}\)، وإلى تصحيح التكرار بـ \(D_\delta\)، فإن الاختزال البنيوي هو
$$\Psi(k)=T_{\mathrm{cyc}}-D_\delta,\qquad D_\delta=\sum_{t=0}^{\delta-1}V_t^2.$$
مع أن \(L\) هائل، فإن فهرسه في متتالية فيبوناتشي لا يتجاوز حجماً من رتبة \(O(\log k)\).
لا يوسّع التطبيق \(S_n\) أبداً. تخزن الورقة بتاً واحداً، وتخزن العقدة الداخلية معرفي ابنيها وطولها الكلي. لذلك تضيف العلاقة \(S_n=S_{n-1}S_{n-2}\) عقدة وصل واحدة فقط في كل مستوى. أما البادئة بطول مطلوب فتقع كاملة في الابن الأيسر، أو تتكون من الابن الأيسر كله متبوعاً ببادئة من الابن الأيمن.
تُحفظ نتائج الوصل والبادئات مؤقتاً. وهكذا تُمثّل حتى بادئة طولها العددي قريب من \(10^{18}\) بعدد \(O(\log k)\) فقط من العقد.
نعمل بترديد \(M\) ونضع \(b=10\). بما أن \(\gcd(10,M)=\gcd(99,M)=1\)، فإن \(b^{-1}\) و\((b^2-1)^{-1}\) موجودان بترديد \(M\). للكلمة \(X=x_0x_1\cdots x_{m-1}\) نعرّف
$$H_b(X)=\sum_{i=0}^{m-1}x_i b^i,\qquad R_b(X)=\sum_{i=0}^{m-1}x_i b^{m-1-i},$$
$$P_b(X)=\sum_{0\le i\lt j\lt m}x_i x_j b^{j-i},\qquad O(X)=\sum_{i=0}^{m-1}x_i.$$
\(R_b(X)\) هو القيمة العشرية المعتادة للكلمة \(X\) بترديد \(M\)، بينما يجمع \(P_b(X)\) كل زوج من بتات الواحد بحسب المسافة بينهما.
إذا كان \(X=UV\)، و\(a=|U|\)، و\(c=|V|\)، فإن الملخصات تندمج من دون فحص البتات:
$$H_b(UV)=H_b(U)+b^aH_b(V),$$
$$R_b(UV)=b^cR_b(U)+R_b(V),$$
$$P_b(UV)=P_b(U)+P_b(V)+bR_b(U)H_b(V),$$
$$O(UV)=O(U)+O(V).$$
الحد المتقاطع في \(P_b\) صحيح لأن المسافة بين الموضع \(i\) في \(U\) والموضع \(j\) في \(V\) هي \(a+j-i\). يخزن الكود الملخصات للأساسين \(b\) و\(b^{-1}\).
يرشّح استعلامان عوديان أزواج البتات من دون فتح الكلمة. استعلام الفرق يحسب
$$D_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le j-i\le h}}x_i y_j b^{j-i},$$
واستعلام مجموع الفهرسين يحسب
$$A_b(X,Y;\ell,h)= \sum_{\substack{i,j\\ \ell\le i+j\le h}}x_i y_j b^{i+j}.$$
إذا غطى المجال زوج العقد كاملاً، تتحلل الإجابة إلى ملخصين كثيري الحدود محفوظين. وإلا تُقسم العقدة الأطول، ويُزاح المجال بمقدار إزاحة الابن، ثم تُجمع النتيجتان. تمنع الذاكرة المؤقتة حل الحالة نفسها مرتين.
لكل \(1\le d\lt L\) نعرّف
$$C_d=\sum_{i=0}^{L-1}w_iw_{(i+d)\bmod L}.$$
تُجمع المسافات الدورية غير الصفرية كلها في كثير الحدود
$$Q_b=\sum_{d=1}^{L-1}C_db^d =P_b(W)+b^LP_{b^{-1}}(W).$$
يعد الحد الأول الأزواج التي لا تتجاوز نهاية \(W\)، ويحوّل الحد الثاني المسافة الخطية \(j-i\) إلى المسافة الملتفة \(L-(j-i)\).
لا تستطيع نافذة طولها \(k\) احتواء إلا المسافات الأمامية \(1,\dots,k-1\). لنضع \(g=L-k\). المسافات غير المطلوبة \(k,\dots,L-1\) هي \(L-r\) حيث \(r=1,\dots,g\). تعطي استعلامات الفرق
$$E_b=\sum_{r=1}^{g}C_rb^r,$$
ومن ثم تكون الارتباطات المستخدمة فعلاً
$$U_b=Q_b-b^LE_{b^{-1}},\qquad U_{b^{-1}}=Q_{b^{-1}}-b^{-L}E_b.$$
لتكن \(V_s\) القيمة العشرية لنافذة الطول \(k\) الدورية التي تبدأ عند \(s\). عند نشر \(V_s^2\) تنفصل حدود الأرقام القطرية عن أزواج المواضع المختلفة.
يشغل كل بت واحد في \(W\) كل منزلة عشرية مرة واحدة عبر جميع النوافذ الدورية. لذلك مساهمته القطرية هي
$$O(W)\sum_{t=0}^{k-1}b^{2t} =O(W)\frac{b^{2k}-1}{b^2-1}.$$
يظهر الزوج ذو المسافة الدورية الثابتة \(d\)، حيث \(1\le d\lt k\)، في \(k-d\) موضعاً نسبياً. ومجموع جداءات أوزان المنازل هو
$$\sum_{t=0}^{k-d-1}b^{2t+d} =\frac{b^{2k-d}-b^d}{b^2-1}.$$
إذن مجموع مربعات النوافذ الدورية \(L\) يساوي
$$T_{\mathrm{cyc}}=O(W)\frac{b^{2k}-1}{b^2-1} +\frac{2}{b^2-1}\left(b^{2k}U_{b^{-1}}-U_b\right)\pmod M.$$
هذه هي خطوة الضغط الأساسية: تتحول جميع جداءات الأرقام إلى ارتباطين وعدة قوى بترديد \(M\).
إذا كان \(\delta=0\)، فالمجموع الدوري يحسب كل عامل مرة واحدة. وإلا فلتكن \(V_0,\dots,V_{\delta-1}\) نوافذ البادئة الزائدة. نحصل على \(V_0\) من ملخص \(R_b\) لبادئة مضغوطة طولها \(k\).
لنضع \(m=\delta-1\)، ولتكن البادئة الخارجة \(x_0,\dots,x_{m-1}\). في الجزء المكرر تكون كتلة البتات الداخلة معكوس هذه البادئة، ولذلك يدخل عند الانتقال \(t\) البت \(x_{m-1-t}\). تصبح علاقة القيمة العشرية المنزلقة
$$V_{t+1}=bV_t-b^kx_t+x_{m-1-t},\qquad 0\le t\lt m.$$
بعد نشر العلاقة يعتمد كل \(V_t\) على \(V_0\)، وعلى البادئة الخارجة ومعكوسها فقط. ويحتاج جمع المربعات إلى عدد بتات الواحد، وأزواج موزونة، والقطر المعكوس \(\sum_t x_tx_{m-1-t}\)، ومجالين مثلثيين للفهرسين؛ وهذه بالضبط ما تعطيه الملخصات واستعلامات \(A_b\). تحسب duplicated_window_sum العبارة التلسكوبية والهندسية الناتجة بترديد \(M\).
وأخيراً
$$\Psi(k)\equiv T_{\mathrm{cyc}}-\sum_{t=0}^{\delta-1}V_t^2\pmod M.$$
أول كلمة قياسية أطول من 3 هي \(W=S_3=01001\)، ولذلك \(L=5\) و\(\delta=1\). نوافذها الدورية هي
$$010,\ 100,\ 001,\ 010,\ 101.$$
النافذة الأولى \(010\) هي الظهور الزائد. يبقى \(001,010,100,101\)، ومن ثم
$$\Psi(3)=1^2+10^2+100^2+101^2=20302.$$
تبني FibonacciSubwords رسم DAG اللوغاريتمي للكلمات القياسية، وتخزن قوى \(10\) و\(10^{-1}\). تطبق summarize صيغ الوصل الأربع؛ ترشّح difference_query بحسب \(j-i\)، بينما تحسب sum_query الجداءات المثلثية اللازمة لتصحيح التكرار.
تختار solve القيمة \(L\)، وتبني \(Q_b\)، وتحذف المسافات التي لا تتسع لها نافذة \(k\)، وتحسب \(T_{\mathrm{cyc}}\)، ثم تطرح duplicated_window_sum. كل الحساب بترديد \(101001001\).
تبني نقاط التحقق سلاسل فيبوناتشي الفعلية للمدخلات الصغيرة فقط. تتحقق من \(\Psi(3)=20302\)، وتقارن الحل المضغوط بالتعداد المباشر لكل \(1\le k\le50\)، وتثبت القيمة المعطاة \(\Psi(10)\equiv10699667\pmod M\).
عدد مستويات فيبوناتشي وعقد البادئات هو \(O(\log k)\). تزور الاستعلامات المحفوظة عدداً تربيعياً على الأكثر من حالات أزواج العقد المهمة، فتحتاج \(O(\log^2 k)\) وقتاً بنيوياً وذاكرة. وتحتاج كل قوة معيارية جديدة \(O(\log k)\) عملية ضرب.
لا توجد عملية خطية في \(k\)، ولا تُخزن سلسلة طولها \(k\). لذلك تصبح القيمة \(k=10^{18}\) عملية.