The task is to compute the sum of the first \(10^{18}\) terms of the fractal sequence, modulo \(10^9\). The key observation used by the implementations is that a prefix of length \(n\) does not need to be generated term by term: it can be decomposed into an inherited prefix plus a fresh consecutive tail. The difficulty is therefore not summing values directly, but locating the exact split point where the inherited self-similar part ends and the new tail begins.
Let \(T(n)\) denote the sum of the first \(n\) terms of the sequence. We also introduce two auxiliary quantities:
\(B(n)\), the length of the largest fully resolved inherited prefix contained in the first \(n\) terms;
\(R(n)\), the total number of copied terms forced by the fresh values \(1,2,\dots,n\).
Set the base values
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$$
Once \(B(n)\) is known, write
$$c=n-B(n).$$
The first \(n\) terms then split into the first \(B(n)\) terms of the same sequence, followed by the clean block \(1,2,\dots,c\).
After the fresh values \(1,2,\dots,k\) have all appeared, they have also generated \(R(k)\) copied terms. So the total occupied prefix length at that stage is
$$k+R(k).$$
Therefore the correct inherited prefix length is
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$$
This formula means that \(B(n)\) is the largest fully completed stage that still fits inside the first \(n\) positions. Because \(R(k)\) is nondecreasing, the predicate \(k+R(k)\le n\) is monotone in \(k\), which is why the implementations can find \(B(n)\) by search rather than by scanning.
Suppose the fresh tail has length \(c=n-B(n)\). The inherited part has already contributed \(R(B(n))\) copied terms. The new tail is exactly the consecutive block \(1,2,\dots,c\), and each fresh value \(i\) contributes a copied prefix of length
$$\lfloor\sqrt{i}\rfloor.$$
Hence the copied-term count satisfies the recurrence
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
This is the structural heart of the solution: the self-similarity is pushed into the smaller argument \(B(n)\), while the new work depends only on the simple consecutive tail.
Computing \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) term by term would be too slow. Let
$$s=\lfloor\sqrt{c}\rfloor.$$
For a fixed threshold \(t\), the inequality \(\lfloor\sqrt{i}\rfloor\ge t\) is equivalent to \(i\ge t^2\). So for each \(t\in\{1,\dots,s\}\), exactly \(c-t^2+1\) indices contribute at least \(t\). Counting by thresholds gives
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$$
Using
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6},$$
we obtain the closed form
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$$
This turns the expensive tail update into \(O(1)\) arithmetic once \(s\) is known.
The tail \(1,2,\dots,c\) contributes the triangular number
$$1+2+\cdots+c=\frac{c(c+1)}{2}.$$
Therefore
$$T(n)=T(B(n))+\frac{c(c+1)}{2}.$$
So the whole problem reduces to repeatedly shrinking \(n\) to the smaller argument \(B(n)\), while adding one triangular contribution per level. No explicit sequence construction is needed.
The local checkpoint is \(T(20)=86\). The split point is determined by
$$9+R(9)=20,\qquad 10+R(10)=22>20,$$
so
$$B(20)=9,\qquad c=20-9=11.$$
Hence
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
Apply the same decomposition again:
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
Combining everything,
$$T(20)=1+1+3+15+66=86,$$
which matches the checkpoint used by the implementations. The same recursion also gives the larger checkpoints \(T(10^3)=364089\) and \(T(10^9)=498676527978348241\).
The C++, Python, and Java implementations memoize three kinds of information for previously solved prefix lengths: the split point \(B(n)\), the exact copied-term count \(R(n)\), and the required prefix sum \(T(n)\) modulo \(10^9\). For a new query \(n\), the implementation first brackets the answer for \(B(n)\) by repeated doubling, then performs binary search on the monotone condition \(k+R(k)\le n\).
Once the split point is known, the implementation computes the floor-square-root sum with the closed formula above, so no \(O(c)\) loop appears. The structural quantities used for comparisons are kept exact, while the running prefix sum is reduced modulo \(10^9\) after each triangular contribution. The non-Python versions also use wider intermediate arithmetic for the square-sum and triangular formulas so that large products remain exact before the final reduction.
Let \(M\) be the number of distinct prefix lengths that are actually memoized while evaluating the target. Each such state is solved once. Determining its split point requires exponential bracketing and then binary search, so the search overhead is \(O(\log n_{\max})\) per new state, where \(n_{\max}\) is the largest queried prefix length. The floor-square-root contribution and the triangular contribution are both \(O(1)\).
Therefore the overall running time is \(O(M\log n_{\max})\), and the memory usage is \(O(M)\). In practice the recursion contracts quickly because every call replaces \(n\) by the smaller value \(B(n)\), which is exactly what makes a target as large as \(10^{18}\) feasible.
Gesucht ist die Summe der ersten \(10^{18}\) Glieder der Fraktalsequenz modulo \(10^9\). Die Implementierungen erzeugen diese Folge nicht explizit. Stattdessen nutzen sie die Beobachtung, dass jedes Präfix der Länge \(n\) in ein geerbtes selbstähnliches Präfix und einen neuen aufeinanderfolgenden Endblock zerfällt. Die eigentliche Schwierigkeit besteht also nicht im Addieren einzelner Werte, sondern darin, die genaue Trennstelle zwischen altem Präfix und neuem Endblock zu bestimmen.
Sei \(T(n)\) die Summe der ersten \(n\) Folgenglieder. Zusätzlich führen wir zwei Hilfsgrößen ein:
\(B(n)\), die Länge des größten vollständig aufgelösten geerbten Präfixes innerhalb der ersten \(n\) Positionen;
\(R(n)\), die Gesamtzahl der kopierten Glieder, die von den frischen Werten \(1,2,\dots,n\) erzwungen werden.
Als Anfangswerte gilt
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$$
Sobald \(B(n)\) bekannt ist, setzen wir
$$c=n-B(n).$$
Dann bestehen die ersten \(n\) Glieder aus den ersten \(B(n)\) Gliedern derselben Folge plus dem sauberen Block \(1,2,\dots,c\).
Nachdem die frischen Werte \(1,2,\dots,k\) vollständig erschienen sind, haben sie zugleich \(R(k)\) kopierte Glieder erzeugt. Die bis dahin belegte Präfixlänge ist also
$$k+R(k).$$
Darum ist die richtige Präfixlänge des geerbten Teils
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$$
Das bedeutet: \(B(n)\) ist die größte vollständig abgeschlossene Stufe, die noch in die ersten \(n\) Positionen passt. Da \(R(k)\) monoton nicht fallend ist, ist auch die Bedingung \(k+R(k)\le n\) monoton in \(k\). Deshalb kann man \(B(n)\) per Suche statt per linearem Durchlauf bestimmen.
Der neue Endblock habe Länge \(c=n-B(n)\). Der geerbte Teil hat bereits \(R(B(n))\) kopierte Glieder beigetragen. Der neue Endblock ist genau \(1,2,\dots,c\), und jeder frische Wert \(i\) erzwingt ein kopiertes Präfix der Länge
$$\lfloor\sqrt{i}\rfloor.$$
Daher erfüllt die Zahl der kopierten Glieder die Rekursion
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
Hier steckt die eigentliche Selbstähnlichkeit: Der rekursive Anteil wandert in das kleinere Argument \(B(n)\), während die neue Arbeit nur vom einfachen Endblock abhängt.
Die Summe \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) direkt auszurechnen wäre zu langsam. Setze
$$s=\lfloor\sqrt{c}\rfloor.$$
Für einen festen Schwellenwert \(t\) ist \(\lfloor\sqrt{i}\rfloor\ge t\) genau dann erfüllt, wenn \(i\ge t^2\). Für jedes \(t\in\{1,\dots,s\}\) gibt es also genau \(c-t^2+1\) passende Indizes. Durch Schwellenzählung erhält man
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$$
Mit
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6}$$
folgt die geschlossene Formel
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$$
Damit wird ein potentiell linearer Update-Schritt zu einer \(O(1)\)-Berechnung, sobald \(s\) bekannt ist.
Der Endblock \(1,2,\dots,c\) trägt die Dreieckszahl
$$1+2+\cdots+c=\frac{c(c+1)}{2}$$
bei. Also gilt
$$T(n)=T(B(n))+\frac{c(c+1)}{2}.$$
Damit reduziert sich das ganze Problem darauf, \(n\) immer wieder auf das kleinere Argument \(B(n)\) zurückzuführen und pro Rekursionsebene genau einen Dreieckszahl-Beitrag zu addieren. Eine explizite Konstruktion der Folge ist unnötig.
Ein lokaler Kontrollwert ist \(T(20)=86\). Die Trennstelle ergibt sich aus
$$9+R(9)=20,\qquad 10+R(10)=22>20,$$
also
$$B(20)=9,\qquad c=20-9=11.$$
Damit folgt
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
Nun dieselbe Zerlegung rekursiv:
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
Zusammengesetzt ergibt das
$$T(20)=1+1+3+15+66=86,$$
genau den Kontrollwert der Implementierungen. Dieselbe Rekursion liefert auch die größeren Prüfwerte \(T(10^3)=364089\) und \(T(10^9)=498676527978348241\).
Die C++-, Python- und Java-Implementierungen speichern für bereits gelöste Präfixlängen drei Arten von Informationen zwischen: die Trennstelle \(B(n)\), die exakte Zahl kopierter Glieder \(R(n)\) und die benötigte Präfixsumme \(T(n)\) modulo \(10^9\). Für eine neue Anfrage \(n\) wird zunächst durch wiederholtes Verdoppeln ein Suchintervall für \(B(n)\) gefunden; anschließend bestimmt eine Binärsuche anhand der monotonen Bedingung \(k+R(k)\le n\) den exakten Wert.
Ist die Trennstelle bekannt, wird die Wurzel-Ganzteilsumme sofort mit der geschlossenen Formel berechnet, sodass kein \(O(c)\)-Durchlauf entsteht. Die Strukturgrößen für Vergleiche bleiben exakt, während die laufende Präfixsumme nach jedem Dreieckszahl-Beitrag modulo \(10^9\) reduziert wird. Die nicht-Python-Versionen verwenden zusätzlich breitere Zwischenarithmetik, damit große Produkte in der Quadratsummen- und Dreieckszahlformel vor der Reduktion exakt bleiben.
Sei \(M\) die Zahl der tatsächlich memoisierten Präfixlängen bei der Auswertung des Ziels. Jeder dieser Zustände wird genau einmal gelöst. Das Bestimmen der Trennstelle benötigt exponentielles Eingrenzen und danach eine Binärsuche, also \(O(\log n_{\max})\) Suchaufwand pro neuem Zustand, wobei \(n_{\max}\) die größte abgefragte Präfixlänge ist. Sowohl der Wurzel-Ganzteil-Beitrag als auch die Dreieckszahl sind dann \(O(1)\).
Damit beträgt die Gesamtlaufzeit \(O(M\log n_{\max})\), und der Speicherbedarf ist \(O(M)\). Praktisch schrumpft die Rekursion schnell, weil jeder Aufruf \(n\) durch den kleineren Wert \(B(n)\) ersetzt. Genau das macht ein Ziel wie \(10^{18}\) überhaupt handhabbar.
Amaç, fraktal dizinin ilk \(10^{18}\) teriminin toplamını \(10^9\) modunda hesaplamaktır. Uygulamalar bu diziyi terim terim üretmez. Bunun yerine, uzunluğu \(n\) olan her önekin kalıtsal bir kendine-benzer önek ile yeni bir ardışık kuyruk bloğuna ayrılabildiği gözlemini kullanırlar. Dolayısıyla asıl zorluk değerleri tek tek toplamak değil, eski önekin nerede bittiğini ve yeni kuyruğun nerede başladığını doğru bulmaktır.
\(T(n)\), dizinin ilk \(n\) teriminin toplamı olsun. Ayrıca iki yardımcı büyüklük tanımlayalım:
\(B(n)\), ilk \(n\) konum içinde tamamen çözülmüş en büyük kalıtsal önekin uzunluğu;
\(R(n)\), taze değerler \(1,2,\dots,n\) tarafından zorlanan kopya terimlerin toplam sayısı.
Başlangıç değerleri
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0$$
olarak alınır. \(B(n)\) bilindiğinde
$$c=n-B(n)$$
yazarız. Böylece ilk \(n\) terim, aynı dizinin ilk \(B(n)\) terimi ile temiz kuyruk bloğu \(1,2,\dots,c\) olarak ayrılır.
Taze değerler \(1,2,\dots,k\) tamamen ortaya çıktıktan sonra bunlar aynı zamanda \(R(k)\) adet kopya terim üretmiş olur. O aşamadaki toplam kaplanan önek uzunluğu
$$k+R(k)$$
olur. Bu yüzden doğru kalıtsal önek uzunluğu
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}$$
şeklindedir. Yani \(B(n)\), ilk \(n\) pozisyon içine sığan en büyük tamamlanmış aşamadır. \(R(k)\) azalmayan bir fonksiyon olduğu için \(k+R(k)\le n\) koşulu da \(k\)'ye göre monotondur; bu nedenle \(B(n)\) doğrusal tarama yerine arama ile bulunabilir.
Yeni kuyruğun uzunluğu \(c=n-B(n)\) olsun. Kalıtsal kısım zaten \(R(B(n))\) adet kopya terim üretmiştir. Yeni kuyruk tam olarak \(1,2,\dots,c\) bloğudur ve her taze değer \(i\), uzunluğu
$$\lfloor\sqrt{i}\rfloor$$
olan bir kopya önek üretir. Dolayısıyla kopya terim sayısı şu özyinelemeyi sağlar:
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
Çözümün özü budur: kendine-benzer kısım daha küçük argüman \(B(n)\)'e taşınır, yeni iş yükü ise yalnızca basit ardışık kuyruktan gelir.
\(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) toplamını tek tek hesaplamak yavaş olur. Şunu tanımlayalım:
$$s=\lfloor\sqrt{c}\rfloor.$$
Sabit bir \(t\) eşiği için \(\lfloor\sqrt{i}\rfloor\ge t\) eşitsizliği ancak ve ancak \(i\ge t^2\) iken doğrudur. Bu yüzden \(t\in\{1,\dots,s\}\) için tam olarak \(c-t^2+1\) adet uygun indeks vardır. Eşik sayımı ile
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1)$$
elde edilir. Ayrıca
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6}$$
olduğundan kapalı form
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}$$
şeklindedir. Böylece kuyruğun katkısı \(s\) bulunduğu anda \(O(1)\) zamanda hesaplanır.
Kuyruk bloğu \(1,2,\dots,c\), üçgensel toplamı
$$1+2+\cdots+c=\frac{c(c+1)}{2}$$
kadar katkı verir. Dolayısıyla
$$T(n)=T(B(n))+\frac{c(c+1)}{2}$$
olur. Böylece tüm problem, \(n\)'yi tekrar tekrar daha küçük \(B(n)\) değerine indirgeyip her seviyede bir üçgensel katkı eklemeye dönüşür. Diziyi açıkça üretmeye gerek kalmaz.
Yerel kontrol değerlerinden biri \(T(20)=86\)'dır. Ayrım noktası
$$9+R(9)=20,\qquad 10+R(10)=22>20$$
olduğundan
$$B(20)=9,\qquad c=20-9=11$$
elde edilir. O halde
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
Aynı ayrışımı özyinelemeli olarak sürdürürsek
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
Hepsini birleştirince
$$T(20)=1+1+3+15+66=86$$
çıkar; bu da uygulamalardaki kontrol değeriyle aynıdır. Aynı özyineleme daha büyük kontrol noktalarını da verir: \(T(10^3)=364089\) ve \(T(10^9)=498676527978348241\).
C++, Python ve Java uygulamaları, daha önce çözülmüş önek uzunlukları için üç tür bilgi saklar: ayrım noktası \(B(n)\), tam kopya-terim sayısı \(R(n)\) ve istenen önek toplamı \(T(n)\) mod \(10^9\). Yeni bir \(n\) sorgusunda önce tekrar tekrar ikiye katlayarak \(B(n)\) için bir aralık bulunur, ardından \(k+R(k)\le n\) monoton koşulu üzerinde ikili arama yapılarak kesin değer belirlenir.
Ayrım noktası bulunduktan sonra karekök taban toplamı kapalı formülle hesaplanır; böylece \(O(c)\) boyutunda bir döngü hiç oluşmaz. Karşılaştırmalarda kullanılan yapısal büyüklükler tam doğrulukla tutulur, önek toplamı ise her üçgensel katkıdan sonra \(10^9\) moduna göre azaltılır. Python dışındaki sürümler büyük çarpımların taşmaması için ara hesaplarda daha geniş aritmetik de kullanır.
\(M\), hedef hesaplanırken gerçekten memoize edilen farklı önek uzunluğu sayısı olsun. Bu durumların her biri yalnızca bir kez çözülür. Ayrım noktasını bulmak için üstel aralık genişletme ve ardından ikili arama gerekir; dolayısıyla yeni durum başına arama maliyeti \(O(\log n_{\max})\) olur. Burada \(n_{\max}\), sorgulanan en büyük önek uzunluğudur. Karekök taban katkısı da üçgensel katkı da \(O(1)\) zamanda hesaplanır.
Sonuç olarak toplam çalışma süresi \(O(M\log n_{\max})\), bellek kullanımı ise \(O(M)\)'dir. Uygulamada özyineleme hızlı küçülür, çünkü her çağrı \(n\)'yi daha küçük olan \(B(n)\)'e indirger. \(10^{18}\) kadar büyük bir hedefin mümkün hale gelmesinin nedeni tam olarak budur.
Hay que calcular la suma de los primeros \(10^{18}\) términos de la secuencia fractal, módulo \(10^9\). Las implementaciones no generan la secuencia completa. En su lugar usan la observación de que cualquier prefijo de longitud \(n\) puede descomponerse en un prefijo heredado y autosimilar, más una cola nueva formada por enteros consecutivos. Por eso, la dificultad real no es sumar término por término, sino localizar con precisión el punto donde termina la parte heredada y empieza la cola nueva.
Sea \(T(n)\) la suma de los primeros \(n\) términos. Introducimos además dos cantidades auxiliares:
\(B(n)\), la longitud del mayor prefijo heredado completamente resuelto dentro de las primeras \(n\) posiciones;
\(R(n)\), el número total de términos copiados forzados por los valores nuevos \(1,2,\dots,n\).
Tomamos como bases
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$$
Una vez conocido \(B(n)\), escribimos
$$c=n-B(n).$$
Entonces los primeros \(n\) términos se separan en los primeros \(B(n)\) términos de la misma secuencia, seguidos del bloque limpio \(1,2,\dots,c\).
Cuando ya han aparecido por completo los valores nuevos \(1,2,\dots,k\), estos también han generado \(R(k)\) términos copiados. Por tanto, la longitud total ocupada en ese momento es
$$k+R(k).$$
De ahí que la longitud correcta del prefijo heredado sea
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$$
En otras palabras, \(B(n)\) es la mayor etapa ya cerrada que todavía cabe dentro de las primeras \(n\) posiciones. Como \(R(k)\) es no decreciente, la condición \(k+R(k)\le n\) es monótona en \(k\), y por eso puede resolverse con búsqueda en vez de recorrer todos los valores.
Supongamos que la cola nueva tiene longitud \(c=n-B(n)\). La parte heredada ya aporta \(R(B(n))\) términos copiados. La cola nueva es exactamente el bloque \(1,2,\dots,c\), y cada valor nuevo \(i\) añade un prefijo copiado de longitud
$$\lfloor\sqrt{i}\rfloor.$$
Por ello, el número de términos copiados satisface la recurrencia
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
Aquí está la idea central: toda la autosimilitud queda empujada al argumento menor \(B(n)\), mientras que el trabajo nuevo depende solo de la cola consecutiva.
Calcular \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) uno por uno sería demasiado lento. Definimos
$$s=\lfloor\sqrt{c}\rfloor.$$
Para un umbral fijo \(t\), la desigualdad \(\lfloor\sqrt{i}\rfloor\ge t\) equivale a \(i\ge t^2\). Así, para cada \(t\in\{1,\dots,s\}\), exactamente \(c-t^2+1\) índices aportan al menos \(t\). Contando por umbrales obtenemos
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$$
Usando
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6},$$
llegamos a la forma cerrada
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$$
Así, una actualización que parecía lineal pasa a ser aritmética de \(O(1)\) una vez conocido \(s\).
La cola \(1,2,\dots,c\) contribuye con el número triangular
$$1+2+\cdots+c=\frac{c(c+1)}{2}.$$
Por tanto,
$$T(n)=T(B(n))+\frac{c(c+1)}{2}.$$
De este modo, todo el problema se reduce a reemplazar repetidamente \(n\) por el argumento menor \(B(n)\), añadiendo una contribución triangular en cada nivel. No hace falta construir la secuencia explícitamente.
Un valor de control local es \(T(20)=86\). El punto de corte viene dado por
$$9+R(9)=20,\qquad 10+R(10)=22>20,$$
de modo que
$$B(20)=9,\qquad c=20-9=11.$$
Entonces
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
Repitiendo la misma descomposición:
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
Al combinar todo,
$$T(20)=1+1+3+15+66=86,$$
que coincide con el valor de comprobación usado por las implementaciones. La misma recurrencia produce también los controles mayores \(T(10^3)=364089\) y \(T(10^9)=498676527978348241\).
Las implementaciones en C++, Python y Java memorizan tres tipos de datos para longitudes de prefijo ya resueltas: el punto de corte \(B(n)\), el número exacto de términos copiados \(R(n)\) y la suma prefija requerida \(T(n)\) módulo \(10^9\). Para una nueva consulta \(n\), primero acotan \(B(n)\) duplicando repetidamente el extremo superior y después aplican búsqueda binaria sobre la condición monótona \(k+R(k)\le n\).
Una vez conocido el corte, la suma de pisos de raíz se evalúa con la fórmula cerrada anterior, así que no aparece ningún bucle \(O(c)\). Las cantidades estructurales que gobiernan la recursión se mantienen exactas, mientras que la suma prefija se reduce módulo \(10^9\) después de cada contribución triangular. Las versiones no escritas en Python también usan aritmética intermedia más amplia para que los productos grandes sigan siendo exactos antes de la reducción final.
Sea \(M\) el número de longitudes de prefijo distintas que realmente se memorizan al evaluar el objetivo. Cada uno de esos estados se resuelve una sola vez. Encontrar el punto de corte requiere acotación exponencial y luego búsqueda binaria, de modo que el coste de búsqueda por estado nuevo es \(O(\log n_{\max})\), donde \(n_{\max}\) es la mayor longitud consultada. Tanto la contribución de pisos de raíz como la triangular son \(O(1)\).
En consecuencia, el tiempo total es \(O(M\log n_{\max})\) y la memoria es \(O(M)\). En la práctica la recursión se contrae con rapidez, porque cada llamada reemplaza \(n\) por el valor menor \(B(n)\). Justamente eso es lo que vuelve manejable un objetivo tan grande como \(10^{18}\).
目标是求出这条分形序列前 \(10^{18}\) 项的和，并对 \(10^9\) 取模。实现并不会把整条序列逐项生成出来，而是利用一个等价分解：任意长度为 \(n\) 的前缀，都可以拆成一个“已经完全解析好的继承前缀”，再加上一个“新出现的连续尾块”。因此真正困难的部分不是逐项相加，而是精确找出旧前缀结束、新尾块开始的那个分界点。
设 \(T(n)\) 表示前 \(n\) 项的和。再引入两个辅助量：
\(B(n)\)，表示前 \(n\) 个位置中，已经完全闭合的最大继承前缀长度；
\(R(n)\)，表示新值 \(1,2,\dots,n\) 一共强制生成了多少个复制项。
初始条件取为
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$$
一旦知道了 \(B(n)\)，令
$$c=n-B(n).$$
那么前 \(n\) 项就可以写成：同一序列的前 \(B(n)\) 项，再接上一个干净的连续块 \(1,2,\dots,c\)。
当新值 \(1,2,\dots,k\) 已经全部出现之后，它们同时也会生成 \(R(k)\) 个复制项。所以在这一阶段，总共占据的前缀长度就是
$$k+R(k).$$
因此，正确的继承前缀长度满足
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$$
这句话的含义是：\(B(n)\) 是仍然能够完整塞进前 \(n\) 个位置中的最大“已完成阶段”。由于 \(R(k)\) 是单调不减的，所以条件 \(k+R(k)\le n\) 对 \(k\) 也是单调的，这就允许我们用搜索而不是顺序枚举去求 \(B(n)\)。
设新尾块长度为 \(c=n-B(n)\)。继承部分已经贡献了 \(R(B(n))\) 个复制项。新尾块恰好就是连续整数
$$1,2,\dots,c.$$
其中每个新值 \(i\) 都会额外触发一个长度为
$$\lfloor\sqrt{i}\rfloor$$
的复制前缀。因此复制项总数满足递推式
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
这正是题目的核心结构：自相似部分全部缩回到更小的参数 \(B(n)\) 上，而新增加的工作量只取决于连续尾块本身。
如果逐项计算 \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\)，代价会很高。令
$$s=\lfloor\sqrt{c}\rfloor.$$
对固定阈值 \(t\) 而言，不等式 \(\lfloor\sqrt{i}\rfloor\ge t\) 等价于 \(i\ge t^2\)。因此对每个 \(t\in\{1,\dots,s\}\)，恰好有 \(c-t^2+1\) 个下标会贡献至少一个 \(t\)。按阈值计数可得
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$$
再利用
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6},$$
就得到闭式
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$$
这样一来，只要知道整数平方根 \(s\)，整段尾块的复制长度就能在 \(O(1)\) 时间内求出。
尾块 \(1,2,\dots,c\) 对总和的贡献就是三角数
$$1+2+\cdots+c=\frac{c(c+1)}{2}.$$
于是有
$$T(n)=T(B(n))+\frac{c(c+1)}{2}.$$
因此整个问题就变成：不断把 \(n\) 缩到更小的 \(B(n)\)，并在每一层加上一个三角数贡献。整个过程中完全不需要显式构造原序列。
本地校验点之一是 \(T(20)=86\)。分界点由下面的不等式决定：
$$9+R(9)=20,\qquad 10+R(10)=22>20.$$
所以
$$B(20)=9,\qquad c=20-9=11.$$
于是
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
继续递归拆分：
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
合并后得到
$$T(20)=1+1+3+15+66=86,$$
与实现中的校验值完全一致。用同样的递推还可以得到更大的检查点 \(T(10^3)=364089\) 和 \(T(10^9)=498676527978348241\)。
C++、Python 和 Java 实现都会对已经求过的前缀长度做记忆化，分别保存三类信息：分界点 \(B(n)\)、精确的复制项数量 \(R(n)\)，以及所需的前缀和 \(T(n)\bmod 10^9\)。对于新的查询 \(n\)，实现先用不断翻倍的方式把 \(B(n)\) 的范围括住，再对单调条件 \(k+R(k)\le n\) 做二分搜索，从而精确找出分界点。
分界点一旦确定，\(\lfloor\sqrt{i}\rfloor\) 的求和就用上面的闭式直接计算，因此不会出现按 \(c\) 线性扫描的慢步骤。控制递归结构的量保持精确值，而最终的前缀和在每次加入三角数贡献后都对 \(10^9\) 取模。非 Python 版本还会在平方和公式和三角数公式里使用更宽的中间算术，以确保大乘法在取模前仍然精确。
设 \(M\) 为在求目标值时实际被记忆化的不同前缀长度个数。每个状态只会真正求解一次。确定其分界点需要一次指数扩张加一次二分搜索，因此每个新状态的搜索开销是 \(O(\log n_{\max})\)，其中 \(n_{\max}\) 是被查询到的最大前缀长度。根号下取整求和和三角数贡献都可以在 \(O(1)\) 时间内完成。
所以总体时间复杂度为 \(O(M\log n_{\max})\)，空间复杂度为 \(O(M)\)。在实际运行中，递归会很快收缩，因为每一层都会把 \(n\) 替换成更小的 \(B(n)\)。这正是 \(10^{18}\) 这样的大目标仍然可行的原因。
Нужно вычислить сумму первых \(10^{18}\) членов фрактальной последовательности по модулю \(10^9\). Реализации не строят эту последовательность явно. Вместо этого используется эквивалентное разложение: любой префикс длины \(n\) состоит из унаследованного самоподобного префикса и нового хвоста, который является подряд идущим блоком чисел. Поэтому главная трудность не в прямом суммировании, а в точном нахождении границы между старой унаследованной частью и новым хвостом.
Пусть \(T(n)\) обозначает сумму первых \(n\) членов последовательности. Введем также две вспомогательные величины:
\(B(n)\) — длина наибольшего полностью разрешенного унаследованного префикса внутри первых \(n\) позиций;
\(R(n)\) — общее число скопированных членов, которые порождаются новыми значениями \(1,2,\dots,n\).
Базовые значения таковы:
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$$
Когда \(B(n)\) уже найдено, положим
$$c=n-B(n).$$
Тогда первые \(n\) членов раскладываются на первые \(B(n)\) членов той же последовательности и чистый хвостовой блок \(1,2,\dots,c\).
После того как новые значения \(1,2,\dots,k\) полностью появились, они успевают породить еще \(R(k)\) скопированных членов. Значит, общая занятая длина префикса на этой стадии равна
$$k+R(k).$$
Следовательно, правильная длина унаследованного префикса определяется формулой
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$$
То есть \(B(n)\) — это наибольшая полностью завершенная стадия, которая еще помещается в первые \(n\) позиций. Поскольку \(R(k)\) не убывает, предикат \(k+R(k)\le n\) монотонен по \(k\), и потому \(B(n)\) можно искать не перебором, а бинарным поиском.
Пусть длина нового хвоста равна \(c=n-B(n)\). Унаследованная часть уже породила \(R(B(n))\) скопированных членов. Сам новый хвост — это блок
$$1,2,\dots,c,$$
и каждое новое значение \(i\) создает скопированный префикс длины
$$\lfloor\sqrt{i}\rfloor.$$
Поэтому число скопированных членов удовлетворяет рекуррентному соотношению
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
Именно здесь сосредоточена самоподобная структура: вся рекурсия уходит в меньшее значение \(B(n)\), а новый вклад зависит только от простого последовательного хвоста.
Считать \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) по членам было бы слишком дорого. Обозначим
$$s=\lfloor\sqrt{c}\rfloor.$$
Для фиксированного порога \(t\) неравенство \(\lfloor\sqrt{i}\rfloor\ge t\) эквивалентно условию \(i\ge t^2\). Значит, для каждого \(t\in\{1,\dots,s\}\) ровно \(c-t^2+1\) индексов дают вклад хотя бы \(t\). Считая по порогам, получаем
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$$
Используя тождество
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6},$$
приходим к закрытой формуле
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$$
Таким образом, обновление хвоста вычисляется за \(O(1)\) после нахождения целой части квадратного корня.
Хвост \(1,2,\dots,c\) дает вклад, равный треугольному числу
$$1+2+\cdots+c=\frac{c(c+1)}{2}.$$
Поэтому
$$T(n)=T(B(n))+\frac{c(c+1)}{2}.$$
Весь расчет сводится к многократной замене \(n\) на меньшее значение \(B(n)\) с добавлением одного треугольного вклада на каждом уровне рекурсии. Явно строить саму последовательность не нужно.
Одна из локальных проверок — это значение \(T(20)=86\). Точка разбиения определяется так:
$$9+R(9)=20,\qquad 10+R(10)=22>20.$$
Следовательно,
$$B(20)=9,\qquad c=20-9=11.$$
Тогда
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
Повторяя разложение рекурсивно, получаем
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
Собирая все вместе, получаем
$$T(20)=1+1+3+15+66=86,$$
что совпадает с контрольным значением реализаций. Та же рекурсия дает и более крупные проверки: \(T(10^3)=364089\) и \(T(10^9)=498676527978348241\).
Реализации на C++, Python и Java мемоизируют три вида информации для уже вычисленных длин префикса: точку разбиения \(B(n)\), точное число скопированных членов \(R(n)\) и требуемую префиксную сумму \(T(n)\) по модулю \(10^9\). Для нового запроса \(n\) сначала строится грубая верхняя граница для \(B(n)\) методом удвоения, а затем выполняется бинарный поиск по монотонному условию \(k+R(k)\le n\).
После нахождения точки разбиения сумма \(\lfloor\sqrt{i}\rfloor\) вычисляется по закрытой формуле, поэтому медленного цикла длины \(c\) не возникает. Структурные величины, управляющие рекурсией, хранятся точно, а префиксная сумма уменьшается по модулю \(10^9\) после каждого треугольного вклада. В версиях не на Python дополнительно используется более широкая промежуточная арифметика, чтобы большие произведения в формулах квадратов и треугольных чисел не переполнялись до взятия модуля.
Пусть \(M\) — число различных длин префикса, которые действительно попадают в мемоизацию при вычислении целевого ответа. Каждый такой состояние решается ровно один раз. Поиск точки разбиения требует экспоненциального расширения диапазона и затем бинарного поиска, то есть \(O(\log n_{\max})\) на новый состояние, где \(n_{\max}\) — максимальная запрошенная длина префикса. И вклад суммы \(\lfloor\sqrt{i}\rfloor\), и треугольный вклад считаются за \(O(1)\).
Следовательно, полное время работы равно \(O(M\log n_{\max})\), а память — \(O(M)\). На практике рекурсия быстро сжимается, потому что каждый вызов заменяет \(n\) меньшим значением \(B(n)\). Именно это делает достижимым расчет для \(10^{18}\).
المطلوب هو حساب مجموع أول \(10^{18}\) حدًا من المتتالية الكسيرية، ثم أخذ الناتج بترديد \(10^9\). التنفيذات لا تبني المتتالية كاملةً حدًا حدًا، بل تعتمد على ملاحظة مكافئة: أي بادئة طولها \(n\) يمكن تفكيكها إلى بادئة موروثة ذاتية التشابه، ثم ذيل جديد مكوّن من كتلة متتالية من الأعداد. لذلك فالصعوبة الحقيقية ليست في الجمع المباشر، بل في تحديد نقطة الفصل بدقة بين الجزء الموروث والذيل الجديد.
لنرمز بـ \(T(n)\) إلى مجموع أول \(n\) حدًا. كما نعرّف كميتين مساعدتين:
\(B(n)\): طول أكبر بادئة موروثة مكتملة تمامًا داخل أول \(n\) موضعًا؛
\(R(n)\): العدد الكلي للحدود المنسوخة التي تفرضها القيم الجديدة \(1,2,\dots,n\).
نأخذ القيم الابتدائية
$$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$$
وبمجرد معرفة \(B(n)\) نكتب
$$c=n-B(n).$$
عندئذٍ تنقسم أول \(n\) حدود إلى أول \(B(n)\) حدًا من المتتالية نفسها، متبوعةً بالكتلة النظيفة \(1,2,\dots,c\).
بعد أن تظهر القيم الجديدة \(1,2,\dots,k\) كاملةً، تكون قد أنشأت أيضًا \(R(k)\) حدًا منسوخًا. إذن طول البادئة المشغولة عند تلك المرحلة يساوي
$$k+R(k).$$
ومن ثم فإن طول البادئة الموروثة الصحيح هو
$$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$$
هذا يعني أن \(B(n)\) هو أكبر طور مكتمل لا يزال كله داخل أول \(n\) موضعًا. وبما أن \(R(k)\) غير متناقص، فإن الشرط \(k+R(k)\le n\) أحادي في \(k\)، ولهذا يمكن إيجاد \(B(n)\) بالبحث بدل الفحص الخطي.
لنفترض أن طول الذيل الجديد هو \(c=n-B(n)\). الجزء الموروث قد ساهم مسبقًا بـ \(R(B(n))\) حدًا منسوخًا. أمّا الذيل الجديد فهو بالضبط الكتلة
$$1,2,\dots,c,$$
وكل قيمة جديدة \(i\) تضيف بادئة منسوخة طولها
$$\lfloor\sqrt{i}\rfloor.$$
لذلك يحقق عدد الحدود المنسوخة العلاقة العودية
$$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$$
هنا تظهر البنية الذاتية للمسألة: الجزء الكسيري كله يعود إلى الوسيط الأصغر \(B(n)\)، بينما يعتمد العمل الجديد فقط على الذيل المتتالي البسيط.
حساب \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) حدًا حدًا سيكون بطيئًا جدًا. لنضع
$$s=\lfloor\sqrt{c}\rfloor.$$
ولعتبة ثابتة \(t\)، فإن الشرط \(\lfloor\sqrt{i}\rfloor\ge t\) يكافئ \(i\ge t^2\). لذلك، لكل \(t\in\{1,\dots,s\}\) يوجد بالضبط \(c-t^2+1\) فهرسًا يساهم بما لا يقل عن \(t\). وبالعد حسب العتبات نحصل على
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$$
وباستخدام الهوية
$$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6},$$
نصل إلى الصيغة المغلقة
$$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$$
وهكذا يصبح تحديث الذيل عملية حسابية من رتبة \(O(1)\) بمجرد معرفة الجذر الصحيح \(s\).
الذيل \(1,2,\dots,c\) يضيف العدد المثلثي
$$1+2+\cdots+c=\frac{c(c+1)}{2}.$$
ومن ثم
$$T(n)=T(B(n))+\frac{c(c+1)}{2}.$$
وبذلك تختزل المسألة كلها إلى استبدال \(n\) مرارًا بالقيمة الأصغر \(B(n)\)، مع إضافة مساهمة مثلثية واحدة في كل مستوى من مستويات العودية. لا توجد حاجة إلى بناء المتتالية صراحةً.
إحدى نقاط التحقق المحلية هي \(T(20)=86\). تُحدد نقطة الفصل من خلال
$$9+R(9)=20,\qquad 10+R(10)=22>20.$$
إذًا
$$B(20)=9,\qquad c=20-9=11.$$
ومن ثم
$$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$$
ثم نكرر التفكيك نفسه:
$$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$$
$$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$$
$$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$$
$$B(1)=0,\qquad T(1)=1.$$
وبجمع هذه الحدود نحصل على
$$T(20)=1+1+3+15+66=86,$$
وهو نفس مقدار التحقق المستخدم في التنفيذات. وتنتج العودية نفسها أيضًا القيم الأكبر \(T(10^3)=364089\) و\(T(10^9)=498676527978348241\).
تقوم تنفيذات C++ وPython وJava بحفظ ثلاث فئات من المعلومات للقيم التي حُلّت مسبقًا: نقطة الفصل \(B(n)\)، والعدد الدقيق للحدود المنسوخة \(R(n)\)، ومجموع البادئة المطلوب \(T(n)\) بترديد \(10^9\). وعند طلب قيمة جديدة \(n\)، تُحاط قيمة \(B(n)\) أولًا بمجال مناسب عبر مضاعفة الحد الأعلى تدريجيًا، ثم يُطبَّق بحث ثنائي على الشرط الأحادي \(k+R(k)\le n\).
وبعد معرفة نقطة الفصل، يُحسب مجموع \(\lfloor\sqrt{i}\rfloor\) مباشرةً من الصيغة المغلقة السابقة، فلا يظهر أي تكرار من رتبة \(O(c)\). وتُحفَظ الكميات البنيوية التي تتحكم في المقارنات بدقة كاملة، بينما يُختزل مجموع البادئة بترديد \(10^9\) بعد كل مساهمة مثلثية. أما التنفيذات غير المكتوبة ببايثون فتستخدم أيضًا حسابات وسيطة أوسع لتبقى الضروب الكبيرة دقيقةً قبل الاختزال النهائي.
ليكن \(M\) عدد أطوال البوادئ المختلفة التي تُحفَظ فعليًا أثناء تقييم الهدف. كل حالة من هذه الحالات تُحل مرة واحدة فقط. إيجاد نقطة الفصل يحتاج إلى توسيع أسي للمجال ثم بحث ثنائي، ولذلك تكون كلفة البحث لكل حالة جديدة \(O(\log n_{\max})\)، حيث \(n_{\max}\) هو أكبر طول بادئة مطلوب. أمّا مساهمة مجموع \(\lfloor\sqrt{i}\rfloor\) والمساهمة المثلثية فكلتاهما من رتبة \(O(1)\).
إذًا الزمن الكلي هو \(O(M\log n_{\max})\)، والذاكرة هي \(O(M)\). وعمليًا تنكمش العودية بسرعة لأن كل استدعاء يستبدل \(n\) بالقيمة الأصغر \(B(n)\). وهذا بالضبط ما يجعل هدفًا بحجم \(10^{18}\) ممكنًا.