Let \(a_1 \lt a_2 \lt \cdots\) be the increasing sequence of positive integers whose binary expansion never contains the substring \(111\). The problem asks for the value of \(F(10^{16})\), where
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
The square is applied to the rank \(i\), not to the admissible integer \(a_i\). So the real question is: among the first \(N\) valid binary strings, which positions correspond to odd values? A brute-force scan is hopeless at \(N=10^{16}\), so the solution has to count whole families of valid strings at once.
The key idea is to order the admissible integers by bit-length, describe allowed suffixes with a tiny automaton, and attach enough statistics to each suffix block that an entire block can be added to the answer in one formula.
Every positive integer with \(L\) bits is larger than every positive integer with fewer than \(L\) bits. Therefore the global ordering of the sequence naturally splits into consecutive blocks: first all admissible 1-bit numbers, then all admissible 2-bit numbers, then all admissible 3-bit numbers, and so on.
Inside a fixed bit-length, ordinary numerical order is exactly lexicographic order on the remaining bits once the leading \(1\) is fixed. That observation is what makes a left-child/right-child recursion possible: all completions beginning with the next bit \(0\) come before all completions beginning with the next bit \(1\).
When a binary word is being built from left to right, the only information needed to avoid the forbidden pattern \(111\) is the current length of the trailing run of \(1\)'s. Let
$$c\in\{0,1,2\}$$
be that run length. Appending a \(0\) is always legal and resets the state to \(0\). Appending a \(1\) is legal only when \(c\lt 2\), and then moves the state to \(c+1\):
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
For each state \(c\) and each remaining length \(r\), define \(\mathcal{B}_{c,r}\) to be the ordered block of all valid \(r\)-bit suffixes that can be appended from state \(c\). The full block of admissible \(L\)-bit positive integers is therefore \(\mathcal{B}_{1,L-1}\), because the leading bit is forced to be \(1\), so before the suffix starts the trailing-ones count is already \(1\).
When \(r=0\), the block contains exactly one finished number. That number is odd precisely when its final bit is \(1\), which in this state description is equivalent to \(c\gt 0\).
For a block \(\mathcal{B}_{c,r}\), let \(J_{c,r}\) be the set of local positions occupied by odd elements inside that block, using positions \(1,2,\dots,|\mathcal{B}_{c,r}|\). The implementations keep four aggregates:
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
These are exactly the data needed later. \(C_{c,r}\) tells us how large the block is, \(Q_{c,r}\) counts its odd elements, and \(A_{c,r},B_{c,r}\) are the first and second moments of their local positions.
The base case is immediate:
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
If the finished number is odd, its unique local position is \(1\), so both the first and second moments are also \(1\).
For \(r\gt 0\), the block \(\mathcal{B}_{c,r}\) splits according to the next bit. The left child is always \(\mathcal{B}_{0,r-1}\). The right child exists only when \(c\lt 2\), in which case it is \(\mathcal{B}_{c+1,r-1}\). Let
$$\Delta=C_{0,r-1}$$
be the size of the left child. Since every left-child completion is numerically smaller than every right-child completion, all local positions from the right child are shifted upward by \(\Delta\) when the two children are concatenated.
That gives the block-size and odd-count recurrences
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}.$$
For the position moments, each odd local position \(j\) in the right child becomes \(\Delta+j\), so
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right).$$
As a side consequence, the total sizes \(T_L=C_{1,L-1}\) begin
$$1,\,2,\,3,\,6,\,11,\,20,\dots,$$
and satisfy a tribonacci-type recurrence. The code does not need that closed form, but it explains why the number of relevant bit-lengths grows only logarithmically with \(N\).
When we sum the first \(N\) admissible integers, every bit-length block before the last one is taken completely, but the last block may be needed only partially. So the same statistics must also be available for the first \(k\) elements of a block. Denote this prefix aggregate by
$$\operatorname{Pref}(c,r,k).$$
If \(\Lambda=C_{0,r-1}\) is the left-child size, then the prefix follows the block structure exactly:
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
where \(\oplus\) means “put the whole left block before the chosen prefix of the right block” and use the same index shift by \(\Lambda\) as above. This is the crucial step that avoids enumerating the elements inside the final partial block.
Suppose all shorter bit-length blocks together contain \(P\) admissible numbers, and suppose the chosen part of the current block has local odd positions \(j\). Their global ranks are then \(P+j\). If that chosen part has statistics \((C,Q,A,B)\), its total contribution is
$$\sum (P+j)^2=QP^2+2PA+B.$$
This identity is the reason for storing the first and second moments of the odd positions. Once \((Q,A,B)\) are known for a whole block or for a prefix block, the entire contribution of that piece is obtained immediately.
The first admissible positive integers are
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
in binary, that is
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots$$
in decimal. Among these first ten terms, the odd ones occur at ranks
$$1,\ 3,\ 5,\ 8,\ 10.$$
Therefore
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
The block view reproduces this exactly. The 1-bit block is just \(1\), so it contributes the global rank \(1\). The 2-bit block is \(10,11\); its only odd local position is \(2\), which shifts to global rank \(3\). The 3-bit block is \(100,101,110\); again the only odd local position is \(2\), which shifts to global rank \(5\).
The 4-bit block is \(1000,1001,1010,1011,1100,1101\), whose odd local positions are \(2,4,6\). But to reach the first ten admissible integers we need only the first four members of this block, namely \(1000,1001,1010,1011\). Their odd local positions are \(2\) and \(4\), and after shifting by the previous six admissible numbers they become global ranks \(8\) and \(10\). That miniature example is exactly what the prefix routine does at large scale.
The C++, Python, and Java implementations memoize every state \((c,r)\) exactly once. For each state they keep the exact block size, the exact odd count, and modular versions of the odd count and the first two position moments. Exact sizes are needed to decide how a prefix splits between the two children; modular moments are enough for the final sum modulo \(10^9+7\).
If the requested \(N\) stops in the middle of some bit-length block, the implementation recursively descends through that block. At each level it compares the desired prefix length with the left-child size. If the prefix fits entirely inside the left child, it keeps descending left. Otherwise it takes the whole left child, subtracts its size from the prefix length, and continues inside the right child before merging the two pieces with the shift formulas above.
The outer loop scans bit-lengths in increasing order. It keeps a running value \(P\) for how many admissible integers have already been accounted for. For each complete block, or for the one partial block at the end, it reads the statistics \((Q,A,B)\) and adds
$$QP^2+2PA+B \pmod{10^9+7}.$$
No implementation enumerates the admissible integers up to rank \(10^{16}\); they all work only with block sizes and position moments. One implementation also verifies small cases such as \(F(10)=199\) against brute force before evaluating the large target.
Let \(L_\ast\) be the largest bit-length needed before the first \(N\) admissible integers are covered. There are only \(3(L_\ast+1)\) full automaton states, and each one is computed once. The sweep over complete bit-length blocks costs \(O(L_\ast)\), and the recursive descent for the final partial block also costs \(O(L_\ast)\).
So the total running time is \(O(L_\ast)\), and the memory usage is also \(O(L_\ast)\). Because the block sizes grow exponentially with \(L\) in tribonacci fashion, we have \(L_\ast=O(\log N)\). For the actual problem, that means both time and space are \(O(\log N)\).
Sei \(a_1 \lt a_2 \lt \cdots\) die aufsteigende Folge positiver ganzer Zahlen, deren Binärdarstellung nirgends das Teilwort \(111\) enthält. Gesucht ist der Wert von \(F(10^{16})\), wobei
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
Quadriert werden also nicht die Werte \(a_i\), sondern ihre Positionen \(i\), und zwar nur dann, wenn der zugehörige zulässige Wert ungerade ist. Die eigentliche Aufgabe besteht deshalb darin, die Positionen der ungeraden Elemente in der geordneten Menge aller gültigen Binärwörter zu finden, ohne bis zum Rang \(10^{16}\) explizit aufzuzählen.
Die Lösung zerlegt die zulässigen Zahlen nach Bitlänge, beschreibt erlaubte Fortsetzungen mit einem kleinen Automaten und speichert zu jedem Block genau die Statistiken, die für den Gesamtbeitrag der ungeraden Positionen gebraucht werden.
Jede positive Zahl mit \(L\) Bits ist größer als jede positive Zahl mit weniger als \(L\) Bits. Daher zerfällt die globale Reihenfolge der Folge automatisch in aufeinanderfolgende Blöcke: zuerst alle zulässigen 1-Bit-Zahlen, dann alle zulässigen 2-Bit-Zahlen, dann alle zulässigen 3-Bit-Zahlen usw.
Innerhalb fester Bitlänge stimmt die numerische Ordnung genau mit der lexikographischen Ordnung der restlichen Bits überein, sobald das führende \(1\) feststeht. Dadurch entsteht die Links-rechts-Struktur: Alle Fortsetzungen mit nächstem Bit \(0\) kommen vor allen Fortsetzungen mit nächstem Bit \(1\).
Beim Aufbau eines Binärworts von links nach rechts genügt eine einzige Zustandsinformation, um das verbotene Muster \(111\) zu vermeiden: die aktuelle Länge des abschließenden Eins-Blocks. Sei
$$c\in\{0,1,2\}$$
diese Länge. Das Anhängen einer \(0\) ist immer erlaubt und setzt den Zustand auf \(0\) zurück. Das Anhängen einer \(1\) ist nur bei \(c\lt 2\) erlaubt und führt dann zu \(c+1\):
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
Für jeden Zustand \(c\) und jede Restlänge \(r\) bezeichne \(\mathcal{B}_{c,r}\) den geordneten Block aller gültigen Suffixe der Länge \(r\), die aus Zustand \(c\) angehängt werden dürfen. Der vollständige Block aller zulässigen positiven \(L\)-Bit-Zahlen ist also \(\mathcal{B}_{1,L-1}\), weil das führende Bit fest \(1\) ist und damit die Zahl bereits mit einem Eins-Block der Länge \(1\) beginnt.
Für \(r=0\) enthält der Block genau eine fertige Zahl. Diese ist genau dann ungerade, wenn ihr letztes Bit \(1\) ist, was in dieser Zustandsbeschreibung äquivalent zu \(c\gt 0\) ist.
Für einen Block \(\mathcal{B}_{c,r}\) sei \(J_{c,r}\) die Menge der lokalen Positionen, an denen ungerade Elemente auftreten, gezählt als \(1,2,\dots,|\mathcal{B}_{c,r}|\). Die Implementierungen speichern vier Aggregatgrößen:
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
Damit ist alles Wesentliche festgehalten: \(C_{c,r}\) ist die Blockgröße, \(Q_{c,r}\) zählt die ungeraden Elemente, und \(A_{c,r},B_{c,r}\) sind erster und zweiter Moment ihrer lokalen Positionen.
Im Basisfall gilt sofort
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
Ist die fertige Zahl ungerade, dann liegt sie an der einzigen lokalen Position \(1\), also sind erster und zweiter Moment beide gleich \(1\).
Für \(r\gt 0\) zerfällt \(\mathcal{B}_{c,r}\) nach dem nächsten Bit. Das linke Kind ist immer \(\mathcal{B}_{0,r-1}\). Das rechte Kind existiert nur bei \(c\lt 2\) und ist dann \(\mathcal{B}_{c+1,r-1}\). Setze
$$\Delta=C_{0,r-1}$$
als Größe des linken Kindes. Da jede linke Fortsetzung numerisch kleiner als jede rechte ist, werden alle lokalen Positionen aus dem rechten Kind beim Aneinanderhängen um \(\Delta\) verschoben.
Daraus folgen die Rekurrenzen
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}.$$
Für die Positionsmomente gilt wegen \(j\mapsto \Delta+j\) im rechten Kind
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right).$$
Nebenbei erhält man so auch die Gesamtgrößen \(T_L=C_{1,L-1}\) der vollständigen Bitlängenblöcke:
$$1,\,2,\,3,\,6,\,11,\,20,\dots,$$
also ein tribonacci-artiges Wachstum. Der Code braucht keine explizite geschlossene Formel, aber dieses Wachstum erklärt, warum nur logarithmisch viele Bitlängen relevant sind.
Beim Summieren der ersten \(N\) zulässigen Zahlen werden alle Bitlängenblöcke vor dem letzten vollständig genommen, der letzte Block aber eventuell nur als Präfix. Deshalb müssen dieselben Statistiken auch für die ersten \(k\) Elemente eines Blocks verfügbar sein. Dieses Präfixaggregat sei
$$\operatorname{Pref}(c,r,k).$$
Mit \(\Lambda=C_{0,r-1}\) als Größe des linken Kindes folgt die Präfixstruktur direkt aus dem Blockaufbau:
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
wobei \(\oplus\) bedeutet, dass der vollständige linke Block vor das gewählte Präfix des rechten Blocks gestellt und derselbe Indexversatz \(\Lambda\) benutzt wird. Genau dadurch muss der letzte Teilblock nicht elementweise erzeugt werden.
Angenommen, alle kürzeren Bitlängenblöcke zusammen enthalten \(P\) zulässige Zahlen und der gewählte Teil des aktuellen Blocks besitzt lokale ungerade Positionen \(j\). Dann lauten die globalen Ränge \(P+j\). Hat der gewählte Teil die Statistiken \((C,Q,A,B)\), dann ist sein Gesamtbeitrag
$$\sum (P+j)^2=QP^2+2PA+B.$$
Darum speichert die Lösung die ersten beiden Momente der ungeraden Positionen. Sobald \((Q,A,B)\) für einen ganzen Block oder ein Blockpräfix bekannt sind, ist der gesamte Beitrag sofort verfügbar.
Die ersten zulässigen positiven Zahlen lauten
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
in Binärdarstellung, also
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots$$
im Dezimalsystem. Unter diesen ersten zehn Termen liegen die ungeraden an den Rängen
$$1,\ 3,\ 5,\ 8,\ 10.$$
Daher ist
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
Die Blocksicht liefert exakt dasselbe. Der 1-Bit-Block ist nur \(1\) und gibt daher den globalen Rang \(1\). Der 2-Bit-Block ist \(10,11\); seine einzige ungerade lokale Position ist \(2\), was nach Verschiebung den globalen Rang \(3\) ergibt. Der 3-Bit-Block ist \(100,101,110\); auch hier ist die einzige ungerade lokale Position \(2\), also global \(5\).
Der 4-Bit-Block lautet \(1000,1001,1010,1011,1100,1101\) und hat die ungeraden lokalen Positionen \(2,4,6\). Um aber die ersten zehn zulässigen Zahlen zu erreichen, braucht man nur die ersten vier Elemente dieses Blocks, also \(1000,1001,1010,1011\). Dort bleiben nur die lokalen ungeraden Positionen \(2\) und \(4\), die nach Verschiebung um die sechs früheren zulässigen Zahlen zu den globalen Rängen \(8\) und \(10\) werden. Genau dieses Präfixprinzip wird im großen Fall verwendet.
Die Implementierungen in C++, Python und Java memoizieren jeden Zustand \((c,r)\) genau einmal. Gespeichert werden die exakte Blockgröße, die exakte Anzahl ungerader Elemente sowie modulare Versionen der ungeraden Anzahl und der ersten beiden Positionsmomente. Exakte Größen werden benötigt, um ein Präfix korrekt zwischen linkem und rechtem Kind aufzuteilen; für die Endsummen genügen die modularen Momente.
Wenn das gewünschte \(N\) mitten in einem Bitlängenblock endet, steigt die Implementierung rekursiv in diesen Block ab. Auf jeder Ebene wird die gewünschte Präfixlänge mit der Größe des linken Kindes verglichen. Liegt das ganze Präfix links, geht der Abstieg nur dorthin weiter. Andernfalls wird das vollständige linke Kind übernommen, seine Größe von der Präfixlänge abgezogen und im rechten Kind weitergerechnet, bevor beide Teile mit dem passenden Indexversatz zusammengeführt werden.
Die äußere Schleife durchläuft die Bitlängen in aufsteigender Reihenfolge. Dabei wird ein laufender Wert \(P\) geführt, der angibt, wie viele zulässige Zahlen bereits verarbeitet wurden. Für jeden vollständigen Block, beziehungsweise für den letzten Teilblock, werden die Werte \((Q,A,B)\) gelesen und der Ausdruck
$$QP^2+2PA+B \pmod{10^9+7}$$
zum Ergebnis addiert. Keine der Implementierungen erzeugt alle zulässigen Zahlen bis Rang \(10^{16}\); stattdessen arbeiten sie ausschließlich mit Blockgrößen und Positionsmomenten. Eine Implementierung prüft zusätzlich kleine Fälle wie \(F(10)=199\) noch gegen brute force.
Sei \(L_\ast\) die größte benötigte Bitlänge, bis die ersten \(N\) zulässigen Zahlen abgedeckt sind. Dann gibt es nur \(3(L_\ast+1)\) vollständige Automatenzustände, und jeder davon wird genau einmal berechnet. Der Durchlauf über die vollständigen Bitlängenblöcke kostet \(O(L_\ast)\), und auch der rekursive Abstieg für den letzten Teilblock kostet \(O(L_\ast)\).
Damit beträgt die Gesamtlaufzeit \(O(L_\ast)\), und der Speicherverbrauch ist ebenfalls \(O(L_\ast)\). Da die Blockgrößen tribonacci-artig exponentiell wachsen, gilt \(L_\ast=O(\log N)\). Für das eigentliche Problem bedeutet das insgesamt \(O(\log N)\) Zeit und \(O(\log N)\) Speicher.
\(a_1 \lt a_2 \lt \cdots\), ikilik yazımında hiçbir yerde \(111\) alt dizisini içermeyen pozitif tam sayıların artan dizisi olsun. İstenen büyüklük \(F(10^{16})\)'dır; burada
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
Karesi alınan şey \(a_i\) değerleri değil, sıralamadaki konumları olan \(i\) indisleridir. Üstelik bu kareler yalnızca ilgili geçerli sayı tek olduğunda toplanır. Dolayısıyla asıl mesele, ilk \(N\) geçerli ikilik sayı arasında tek olanların hangi konumlarda durduğunu, \(N=10^{16}\) gibi dev bir hedefe kadar tek tek üretmeden sayabilmektir.
Çözüm, geçerli sayıları bit uzunluğuna göre bloklara ayırır, izin verilen son ekleri üç durumlu küçük bir otomatla tanımlar ve her blok için cevaba tek adımda katkı verecek istatistikleri saklar.
\(L\) bitli her pozitif sayı, daha kısa bit uzunluğuna sahip bütün pozitif sayılardan büyüktür. Bu nedenle dizinin genel sırası doğal olarak bloklara ayrılır: önce tüm geçerli 1-bit sayılar, sonra tüm geçerli 2-bit sayılar, sonra tüm geçerli 3-bit sayılar ve böyle devam eder.
Sabit bir bit uzunluğu içinde, baştaki \(1\) sabitlendikten sonra kalan bitler üzerindeki leksikografik sıra tam olarak sayısal sıraya eşittir. Böylece her blok bir sol çocuk ve bir sağ çocuk olarak ayrılabilir: sonraki biti \(0\) olan tüm tamamlamalar, sonraki biti \(1\) olan tüm tamamlamalardan önce gelir.
Bir ikilik sözcük soldan sağa kurulurken, \(111\) deseninden kaçınmak için gereken tek bilgi sondaki ardışık \(1\) sayısıdır. Bu sayıyı
$$c\in\{0,1,2\}$$
ile gösterelim. Yeni bir \(0\) eklemek her zaman serbesttir ve durumu \(0\)'a sıfırlar. Yeni bir \(1\) eklemek ise yalnızca \(c\lt 2\) iken mümkündür; o zaman durum \(c+1\) olur:
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
Her \(c\) durumu ve her kalan uzunluk \(r\) için, \(\mathcal{B}_{c,r}\) bu durumdan sonra eklenebilecek bütün geçerli \(r\)-bit son eklerin sıralı bloğu olsun. O halde tüm geçerli \(L\)-bit pozitif sayıların bloğu \(\mathcal{B}_{1,L-1}\)'dir; çünkü en soldaki bit zorunlu olarak \(1\)'dir ve daha baştan sondaki \(1\) serisinin uzunluğu \(1\) olur.
\(r=0\) olduğunda blokta tam bir adet tamamlanmış sayı vardır. Bu sayı ancak son biti \(1\) ise tektir; bu da bu durum tanımında doğrudan \(c\gt 0\) koşuluna eşdeğerdir.
\(\mathcal{B}_{c,r}\) bloğu için, blok içindeki tek elemanların yerel konum kümesini \(J_{c,r}\) ile gösterelim. Konumlar \(1,2,\dots,|\mathcal{B}_{c,r}|\) biçiminde numaralanır. Uygulamalar şu dört büyüklüğü tutar:
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
Böylece gereken bütün bilgi elde tutulmuş olur: \(C_{c,r}\) blok boyudur, \(Q_{c,r}\) tek eleman sayısıdır, \(A_{c,r}\) ile \(B_{c,r}\) ise tek konumların birinci ve ikinci momentleridir.
Başlangıç durumu hemen yazılır:
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
Bitmiş sayı tekse, bulunduğu tek yerel konum \(1\) olduğu için hem birinci hem ikinci moment \(1\) olur.
\(r\gt 0\) için \(\mathcal{B}_{c,r}\) sonraki bite göre ayrılır. Sol çocuk her zaman \(\mathcal{B}_{0,r-1}\)'dir. Sağ çocuk ise yalnızca \(c\lt 2\) olduğunda vardır ve \(\mathcal{B}_{c+1,r-1}\)'e eşittir. Sol çocuğun boyunu
$$\Delta=C_{0,r-1}$$
olarak yazalım. Sol çocuktaki bütün tamamlamalar sayısal olarak sağ çocuktakilerden önce geldiği için, sağ çocuktan gelen bütün yerel konumlar birleştirme sırasında \(\Delta\) kadar kayar.
Bu yüzden blok boyu ve tek eleman sayısı için
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}$$
elde edilir. Sağ çocuktaki her tek konum \(j\), birleştirilmiş blokta \(\Delta+j\) konumuna gittiği için momentler de
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right)$$
olur. Buradan tam bit-uzunluğu bloklarının boyları olan \(T_L=C_{1,L-1}\) dizisi de çıkar:
$$1,\,2,\,3,\,6,\,11,\,20,\dots$$
Bu dizi tribonacci benzeri büyür. Kodun kapalı forma ihtiyacı yoktur, ama bu büyüme neden yalnızca logaritmik sayıda bit uzunluğunun önemli olduğunu açıklar.
İlk \(N\) geçerli sayı toplanırken, son blok dışındaki bütün bit-uzunluğu blokları tamamen alınır; yalnızca son blok kısmi olabilir. Bu yüzden aynı istatistiklerin bir bloğun ilk \(k\) elemanı için de hesaplanabilmesi gerekir. Bu önek istatistiğini
$$\operatorname{Pref}(c,r,k)$$
ile gösterelim. Sol çocuğun boyu \(\Lambda=C_{0,r-1}\) ise önek yapısı doğrudan blok yapısını izler:
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
Buradaki \(\oplus\), tam sol bloğu seçilmiş sağ önekten önce koyup aynı \(\Lambda\) kaydırmasını uygulamak demektir. Böylece son kısmi blok içindeki elemanlar tek tek üretilmeden tam istatistik elde edilir.
Daha kısa bit-uzunluğu bloklarının toplamda \(P\) adet geçerli sayı içerdiğini varsayalım. O halde mevcut blok parçasındaki yerel tek konumlar \(j\), global sıralamada \(P+j\) olur. Seçilen parçanın istatistikleri \((C,Q,A,B)\) ise bu parçanın katkısı
$$\sum (P+j)^2=QP^2+2PA+B$$
biçimindedir. Algoritmanın tek konumların momentlerini saklamasının nedeni tam olarak budur. \((Q,A,B)\) bilindiği anda, tüm blok ya da blok öneği tek hamlede cevaba eklenebilir.
İlk geçerli pozitif sayılar şunlardır:
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
Yani onluk tabanda
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots$$
elde edilir. İlk on terim arasında tek olanlar şu sıralarda görünür:
$$1,\ 3,\ 5,\ 8,\ 10.$$
Böylece
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
Blok yaklaşımı da aynı sonucu üretir. 1-bit bloğu yalnızca \(1\)'dir ve global sıra \(1\)'i verir. 2-bit bloğu \(10,11\)'dir; tek yerel konum \(2\) olduğundan globalde \(3\) elde edilir. 3-bit bloğu \(100,101,110\)'dur; yine tek yerel konum \(2\) olup globalde \(5\) olur.
4-bit bloğu \(1000,1001,1010,1011,1100,1101\) şeklindedir ve tek yerel konumları \(2,4,6\)'dır. Fakat ilk on geçerli sayıya ulaşmak için bu bloktan yalnızca ilk dört eleman gerekir: \(1000,1001,1010,1011\). Bu önekte tek yerel konumlar \(2\) ve \(4\)'tür; önceki altı geçerli sayı kadar kaydırılınca global sıralar \(8\) ve \(10\) olur. Büyük girdide önek yordamı tam olarak bunu yapar.
C++, Python ve Java uygulamaları her \((c,r)\) durumunu tam bir kez memoize eder. Her durum için tam blok boyu, tam tek eleman sayısı ve tek sayısının modüler kopyasıyla birlikte birinci ve ikinci konum momentlerinin modüler değerleri saklanır. Tam boy bilgisi, bir öneğin iki çocuk arasında nasıl bölüneceğini belirlemek için gerekir; son cevabı toplarken ise modüler momentler yeterlidir.
Eğer istenen \(N\), bir bit-uzunluğu bloğunun ortasında bitiyorsa, uygulama bu bloğun içinde özyinelemeli olarak aşağı iner. Her seviyede istenen önek uzunluğu sol çocuğun boyuyla karşılaştırılır. Önek tamamen solda kalıyorsa yalnızca sol tarafa gidilir. Aksi halde tam sol blok alınır, onun boyu önek uzunluğundan çıkarılır ve sağ çocukta devam edilir; sonra iki parça yukarıdaki kaydırma formülleriyle birleştirilir.
Dış döngü bit uzunluklarını artan sırayla gezer. O ana kadar hesaba katılmış geçerli sayı sayısını gösteren \(P\) değeri tutulur. Her tam blok ya da sonda kalan tek kısmi blok için \((Q,A,B)\) istatistikleri okunur ve
$$QP^2+2PA+B \pmod{10^9+7}$$
ifadesi cevaba eklenir. Hiçbir uygulama \(10^{16}\). sıraya kadar bütün geçerli sayıları üretmez; tamamı yalnızca blok boyları ve konum momentleriyle çalışır. Uygulamalardan biri ayrıca \(F(10)=199\) gibi küçük değerleri brute force ile doğrular.
İlk \(N\) geçerli sayıyı kapsamak için gereken en büyük bit uzunluğuna \(L_\ast\) diyelim. O zaman yalnızca \(3(L_\ast+1)\) tam otomat durumu vardır ve her biri bir kez hesaplanır. Tam bit-uzunluğu blokları üzerinden yapılan tarama \(O(L_\ast)\) sürer; son kısmi blok içindeki önek inişi de \(O(L_\ast)\) sürer.
Dolayısıyla toplam çalışma süresi \(O(L_\ast)\), bellek kullanımı da \(O(L_\ast)\) olur. Blok boyları tribonacci tarzında üstel büyüdüğü için \(L_\ast=O(\log N)\) elde edilir. Bu problem için sonuç, hem zamanın hem belleğin \(O(\log N)\) olmasıdır.
Sea \(a_1 \lt a_2 \lt \cdots\) la sucesión creciente de enteros positivos cuya representación binaria nunca contiene la subcadena \(111\). El problema pide calcular \(F(10^{16})\), donde
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
No se elevan al cuadrado los valores \(a_i\), sino sus posiciones \(i\), y solo cuando el término válido correspondiente es impar. Así que la cuestión central es localizar en qué posiciones aparecen los números impares dentro de los primeros \(N\) binarios admisibles, sin enumerar uno por uno hasta \(N=10^{16}\).
La solución agrupa los enteros válidos por longitud en bits, describe los sufijos permitidos mediante un autómata diminuto y asocia a cada bloque las estadísticas exactas que permiten sumar su contribución de una sola vez.
Cualquier entero positivo de \(L\) bits es mayor que cualquier entero positivo con menos de \(L\) bits. Por eso el orden global de la sucesión se descompone naturalmente en bloques consecutivos: primero todos los válidos de 1 bit, después todos los válidos de 2 bits, luego los de 3 bits, etcétera.
Dentro de una longitud fija, una vez fijado el bit inicial \(1\), el orden numérico coincide exactamente con el orden lexicográfico sobre los bits restantes. Esa observación crea la estructura izquierda-derecha: todas las completaciones cuyo siguiente bit es \(0\) aparecen antes que todas las completaciones cuyo siguiente bit es \(1\).
Mientras se construye una palabra binaria de izquierda a derecha, para evitar el patrón prohibido \(111\) solo hace falta saber cuántos unos consecutivos hay al final del prefijo actual. Sea
$$c\in\{0,1,2\}$$
esa longitud final. Añadir un \(0\) siempre es válido y reinicia el estado a \(0\). Añadir un \(1\) solo es posible cuando \(c\lt 2\), y entonces el nuevo estado es \(c+1\):
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
Para cada estado \(c\) y cada longitud restante \(r\), definimos \(\mathcal{B}_{c,r}\) como el bloque ordenado de todos los sufijos válidos de longitud \(r\) que se pueden añadir desde el estado \(c\). El bloque completo de enteros positivos válidos de \(L\) bits es, por tanto, \(\mathcal{B}_{1,L-1}\), porque el bit más significativo ya está fijado en \(1\), así que antes del sufijo la racha final de unos vale \(1\).
Cuando \(r=0\), el bloque contiene exactamente un número terminado. Ese número es impar precisamente cuando su último bit es \(1\), lo cual en esta descripción de estados equivale a \(c\gt 0\).
Para un bloque \(\mathcal{B}_{c,r}\), sea \(J_{c,r}\) el conjunto de posiciones locales ocupadas por los elementos impares dentro del bloque, numeradas como \(1,2,\dots,|\mathcal{B}_{c,r}|\). Las implementaciones guardan cuatro agregados:
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
Con esto queda resumida toda la información útil: \(C_{c,r}\) es el tamaño del bloque, \(Q_{c,r}\) cuenta cuántos impares contiene, y \(A_{c,r},B_{c,r}\) son el primer y segundo momento de sus posiciones locales.
El caso base es inmediato:
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
Si el número terminado es impar, ocupa la única posición local posible, la \(1\), por lo que ambos momentos valen también \(1\).
Para \(r\gt 0\), el bloque \(\mathcal{B}_{c,r}\) se divide según el siguiente bit. El hijo izquierdo siempre es \(\mathcal{B}_{0,r-1}\). El hijo derecho solo existe cuando \(c\lt 2\), y entonces es \(\mathcal{B}_{c+1,r-1}\). Sea
$$\Delta=C_{0,r-1}$$
el tamaño del hijo izquierdo. Como todas las completaciones del lado izquierdo son numéricamente menores que todas las del lado derecho, cualquier posición local procedente del hijo derecho se desplaza en \(\Delta\) al concatenar ambos bloques.
De ahí salen las recurrencias para tamaño y cantidad de impares:
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}.$$
Y, como cada posición impar \(j\) del hijo derecho se convierte en \(\Delta+j\), los momentos cumplen
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right).$$
Como consecuencia adicional, los tamaños completos \(T_L=C_{1,L-1}\) empiezan como
$$1,\,2,\,3,\,6,\,11,\,20,\dots,$$
y siguen un crecimiento de tipo tribonacci. El programa no necesita una fórmula cerrada, pero sí aprovecha el hecho de que el número de longitudes relevantes crece solo de forma logarítmica.
Al sumar los primeros \(N\) enteros admisibles, todos los bloques anteriores al último se toman completos, mientras que el bloque final quizá solo se necesite parcialmente. Por eso las mismas estadísticas deben poder calcularse también para los primeros \(k\) elementos de un bloque. Denotemos ese agregado por
$$\operatorname{Pref}(c,r,k).$$
Si \(\Lambda=C_{0,r-1}\) es el tamaño del hijo izquierdo, la estructura del prefijo sigue exactamente la estructura del bloque:
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
donde \(\oplus\) significa colocar todo el bloque izquierdo antes del prefijo elegido del bloque derecho y aplicar el mismo desplazamiento \(\Lambda\). Así se evita enumerar los elementos del último bloque parcial.
Supongamos que los bloques de menor longitud contienen en total \(P\) enteros admisibles. Entonces las posiciones locales impares \(j\) de la porción elegida del bloque actual pasan a ser rangos globales \(P+j\). Si esa porción tiene estadísticas \((C,Q,A,B)\), su contribución total es
$$\sum (P+j)^2=QP^2+2PA+B.$$
Esa identidad es la razón de guardar el primer y segundo momento de las posiciones impares. Una vez conocidos \((Q,A,B)\) para un bloque entero o para un prefijo de bloque, toda su contribución queda determinada de inmediato.
Los primeros enteros positivos admisibles son
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
en binario, es decir
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots$$
en decimal. Entre estos primeros diez términos, los impares aparecen en los rangos
$$1,\ 3,\ 5,\ 8,\ 10.$$
Por lo tanto,
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
La visión por bloques produce exactamente lo mismo. El bloque de 1 bit es solo \(1\), así que aporta el rango global \(1\). El bloque de 2 bits es \(10,11\); su única posición impar local es \(2\), que tras el desplazamiento se convierte en el rango global \(3\). El bloque de 3 bits es \(100,101,110\); otra vez la única posición impar local es \(2\), que pasa al rango \(5\).
El bloque de 4 bits es \(1000,1001,1010,1011,1100,1101\), con posiciones impares locales \(2,4,6\). Pero para llegar a los primeros diez enteros admisibles solo hacen falta los cuatro primeros elementos del bloque: \(1000,1001,1010,1011\). En ese prefijo, las posiciones impares locales son \(2\) y \(4\), y al desplazarlas por los seis términos válidos anteriores se convierten en los rangos globales \(8\) y \(10\). Eso es exactamente lo que hace la rutina de prefijos en la entrada grande.
Las implementaciones en C++, Python y Java memorizan cada estado \((c,r)\) una sola vez. Para cada uno guardan el tamaño exacto del bloque, la cuenta exacta de elementos impares y versiones modulares de esa cuenta y de los dos primeros momentos de las posiciones impares. Los tamaños exactos son necesarios para saber cómo se reparte un prefijo entre los dos hijos; los momentos modulares bastan para ensamblar la respuesta final.
Si el \(N\) pedido termina en mitad de un bloque de cierta longitud, la implementación desciende recursivamente por ese bloque. En cada nivel compara la longitud del prefijo deseado con el tamaño del hijo izquierdo. Si todo cabe a la izquierda, sigue solo por ese lado. Si no, toma el hijo izquierdo completo, resta su tamaño a la longitud pendiente y continúa en el hijo derecho, para luego fusionar ambas partes con las fórmulas de desplazamiento.
El bucle exterior recorre las longitudes de bit en orden creciente. Mantiene un valor \(P\) que cuenta cuántos enteros admisibles ya se han procesado. Para cada bloque completo, o para el único bloque parcial final, lee \((Q,A,B)\) y añade
$$QP^2+2PA+B \pmod{10^9+7}.$$
Ninguna implementación enumera los enteros admisibles hasta el rango \(10^{16}\); todas trabajan únicamente con tamaños de bloque y momentos de posiciones. Una de ellas también comprueba casos pequeños, como \(F(10)=199\), por fuerza bruta antes de evaluar el objetivo grande.
Sea \(L_\ast\) la mayor longitud de bits necesaria para cubrir los primeros \(N\) enteros admisibles. Solo existen \(3(L_\ast+1)\) estados completos del autómata, y cada uno se calcula una sola vez. El barrido de los bloques completos cuesta \(O(L_\ast)\), y el descenso recursivo del último bloque parcial también cuesta \(O(L_\ast)\).
Así, el tiempo total es \(O(L_\ast)\) y la memoria también es \(O(L_\ast)\). Como los tamaños de bloque crecen exponencialmente con una pauta tribonacci, se tiene \(L_\ast=O(\log N)\). En términos de \(N\), el algoritmo usa \(O(\log N)\) tiempo y \(O(\log N)\) espacio.
设 \(a_1 \lt a_2 \lt \cdots\) 是一个递增的正整数序列，其中每个数的二进制表示都不含子串 \(111\)。题目要求计算 \(F(10^{16})\)，其中
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
被平方的不是数值 \(a_i\) 本身，而是它在合法序列中的排名 \(i\)。并且只有当对应的合法整数是奇数时，这个平方项才进入总和。因此核心问题不是“把前 \(N\) 个合法数找出来”，而是“在前 \(N\) 个合法数中，奇数恰好落在什么位置上”。对于 \(N=10^{16}\) 这样的规模，逐项枚举显然不可行，必须按整块计数。
解法把所有合法整数按二进制位长分成连续块，用一个只有三个状态的自动机描述某个前缀之后还能接哪些后缀，再为每个块保存足以直接算出贡献的统计量。
任何一个 \(L\) 位正整数都大于所有位数少于 \(L\) 的正整数，所以整个递增序列天然按位长分块：先是所有合法的 1 位数，再是所有合法的 2 位数，然后是 3 位数，如此继续。
在固定位长内部，一旦最高位 \(1\) 已经固定，剩余比特上的字典序就和普通数值大小完全一致。这一点非常关键，因为它意味着每个块都可以按“下一位取 \(0\)”和“下一位取 \(1\)”拆成左右两个子块，而且左子块中的所有元素一定整体排在右子块之前。
从左到右构造一个二进制串时，为了保证不出现禁用模式 \(111\)，只需要知道当前前缀末尾连续 \(1\) 的长度。记这个长度为
$$c\in\{0,1,2\}.$$
如果再补一个 \(0\)，状态总是回到 \(0\)。如果再补一个 \(1\)，只有在 \(c\lt 2\) 时才合法，此时状态变成 \(c+1\)：
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
对每个状态 \(c\) 和剩余长度 \(r\)，定义 \(\mathcal{B}_{c,r}\) 为：从当前状态出发，还要补上 \(r\) 位时，所有合法补法按数值顺序形成的有序块。于是，所有合法的 \(L\) 位正整数对应的完整块就是 \(\mathcal{B}_{1,L-1}\)，因为最高位必须是 \(1\)，也就是说在开始处理后缀之前，末尾连续 \(1\) 的长度已经是 \(1\) 了。
当 \(r=0\) 时，块里恰好只有一个已经完成的整数。这个整数是不是奇数，只取决于最后一位是不是 \(1\)；在这种状态表示下，这与 \(c\gt 0\) 完全等价。
对于块 \(\mathcal{B}_{c,r}\)，记 \(J_{c,r}\) 为块内所有奇数元素所占据的局部位置集合，局部位置按 \(1,2,\dots,|\mathcal{B}_{c,r}|\) 编号。实现中保存下面四个量：
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
这四个量各司其职：\(C_{c,r}\) 是块大小，\(Q_{c,r}\) 是块内奇数个数，\(A_{c,r}\) 和 \(B_{c,r}\) 则分别是奇数位置的一阶矩和二阶矩。后面把局部位置平移成全局排名时，恰好只需要这些信息。
边界条件非常直接：
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
原因是：如果这个唯一完成的数是奇数，它所在的局部位置就是 \(1\)，因此一阶矩和二阶矩都等于 \(1\)。
对于 \(r\gt 0\)，块 \(\mathcal{B}_{c,r}\) 会按下一位拆开。左子块总是 \(\mathcal{B}_{0,r-1}\)。右子块只有在 \(c\lt 2\) 时才存在，这时右子块为 \(\mathcal{B}_{c+1,r-1}\)。令
$$\Delta=C_{0,r-1}$$
表示左子块大小。由于左子块中的所有补法都比右子块中的所有补法小，所以右子块中的局部位置在合并之后都会整体加上一个偏移量 \(\Delta\)。
因此，块大小和奇数个数满足
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}.$$
而右子块中任意一个奇数局部位置 \(j\) 合并后都会变成 \(\Delta+j\)，所以矩的递推式是
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right).$$
顺便还可以看出，完整位长块的大小 \(T_L=C_{1,L-1}\) 从
$$1,\,2,\,3,\,6,\,11,\,20,\dots$$
开始，呈现出 tribonacci 型增长。代码并不需要把这个闭式写出来，但正是这种增长保证了需要处理的位长数量只有对数量级。
在求前 \(N\) 个合法整数时，除了最后一个位长块之外，前面的块都会整块取完；只有最后一个块可能只取前一部分。因此同样的统计量必须能够对“块的前 \(k\) 个元素”返回结果。记这个前缀统计为
$$\operatorname{Pref}(c,r,k).$$
如果左子块大小 \(\Lambda=C_{0,r-1}\)，那么前缀的结构和整块结构完全一致：
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
其中 \(\oplus\) 表示“完整左块在前，右边只取所需前缀在后”，并且对右边继续施加与前面相同的偏移量 \(\Lambda\)。这一点非常重要，因为它使得最后一个块即使只需要一部分，也不必把里面的数逐个列出来。
假设所有更短位长的块一共已经贡献了 \(P\) 个合法整数，而当前选中的块部分内部，奇数所在的局部位置是 \(j\)。那么这些奇数对应的全局排名就是 \(P+j\)。如果这块部分的统计是 \((C,Q,A,B)\)，则它对最终答案的贡献为
$$\sum (P+j)^2=QP^2+2PA+B.$$
这正是实现中保存奇数位置一阶矩和二阶矩的原因。一旦知道某个整块或某个前缀块的 \((Q,A,B)\)，就可以立刻把这一整块的贡献加入总和。
最开始的合法正整数依次为
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
也就是十进制的
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots$$
在这前十项中，奇数出现在以下排名：
$$1,\ 3,\ 5,\ 8,\ 10.$$
因此
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
从分块角度看也完全一致。1 位块只有 \(1\)，所以给出全局排名 \(1\)。2 位块是 \(10,11\)，其中唯一的奇数局部位置是 \(2\)，平移后变成全局排名 \(3\)。3 位块是 \(100,101,110\)，同样只有局部位置 \(2\) 是奇数，因此平移后得到全局排名 \(5\)。
4 位完整块是 \(1000,1001,1010,1011,1100,1101\)，奇数局部位置为 \(2,4,6\)。但为了凑够前十个合法整数，我们只需要这个块的前四项：\(1000,1001,1010,1011\)。在这个前缀中，奇数局部位置只剩 \(2\) 和 \(4\)。再加上前面已经有的 6 个合法整数，它们就变成全局排名 \(8\) 和 \(10\)。这正是代码中的前缀递归在大规模输入时所做的事情。
C++、Python 和 Java 实现都会把每个状态 \((c,r)\) 只计算一次并缓存下来。对每个状态，它们保存完整块大小、完整块中的奇数个数，以及奇数个数和奇数位置一阶矩、二阶矩在模 \(10^9+7\) 下的值。精确的块大小用于判断某个前缀应该全部落在左子块，还是跨到右子块；而最终答案只需要模意义下的统计量。
如果目标 \(N\) 停在某个位长块的中间，程序就对这个块做一次递归下降。每一层都会把所需前缀长度与左子块大小比较：如果整个前缀都在左边，就继续向左；否则先整块拿走左子块，再把剩余需求递归交给右子块，最后按照上面的位移公式把两部分重新合并。
外层过程按位长从小到大扫描，并维护一个计数 \(P\)，表示当前之前已经处理了多少个合法整数。对于每个完整块，或者最后那个不完整块，读取对应的 \((Q,A,B)\)，再把
$$QP^2+2PA+B \pmod{10^9+7}$$
加入结果即可。三个实现都不会把直到第 \(10^{16}\) 个合法整数的所有值显式生成出来；它们始终只处理块大小与位置矩。还有一个实现会在正式求大输入之前，用暴力方式检查 \(F(10)=199\) 等小例子。
设覆盖前 \(N\) 个合法整数所需的最大位长为 \(L_\ast\)。那么完整自动机状态只有 \(3(L_\ast+1)\) 个，并且每个状态只会计算一次。顺次扫描所有完整位长块需要 \(O(L_\ast)\) 时间，而处理最后一个不完整块的前缀递归也只需要 \(O(L_\ast)\) 时间。
因此总时间复杂度是 \(O(L_\ast)\)，空间复杂度也是 \(O(L_\ast)\)。由于完整块大小按 tribonacci 方式指数增长，所以 \(L_\ast=O(\log N)\)。换成 \(N\) 的规模来看，整个算法就是 \(O(\log N)\) 时间和 \(O(\log N)\) 空间。
Пусть \(a_1 \lt a_2 \lt \cdots\) — возрастающая последовательность положительных целых чисел, в двоичной записи которых нигде не встречается подслово \(111\). Требуется вычислить \(F(10^{16})\), где
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
Возводятся в квадрат не сами значения \(a_i\), а их позиции \(i\) в упорядоченной последовательности, и только тогда, когда соответствующее допустимое число нечетно. Поэтому реальная задача состоит в том, чтобы определить, на каких местах среди первых \(N\) допустимых двоичных чисел стоят нечетные элементы, не перечисляя все значения вплоть до \(N=10^{16}\).
Решение разбивает допустимые числа на блоки по битовой длине, описывает разрешенные продолжения с помощью маленького автомата и хранит для каждого блока ровно те статистики, которые позволяют прибавить вклад целого блока одной формулой.
Любое положительное число длины \(L\) бит больше любого положительного числа с меньшим количеством бит. Значит, глобальный порядок автоматически распадается на последовательные блоки: сначала все допустимые 1-битные числа, затем все допустимые 2-битные, потом 3-битные и так далее.
Внутри фиксированной битовой длины, после того как старший бит \(1\) уже зафиксирован, числовой порядок точно совпадает с лексикографическим порядком по оставшимся битам. Именно поэтому блок естественно делится на левую и правую часть: все завершения с очередным битом \(0\) стоят раньше всех завершений с очередным битом \(1\).
Если двоичное слово строится слева направо, то для запрета шаблона \(111\) достаточно знать только длину текущего хвоста из подряд идущих единиц. Обозначим ее через
$$c\in\{0,1,2\}.$$
Добавление \(0\) всегда разрешено и сбрасывает состояние в \(0\). Добавление \(1\) разрешено только при \(c\lt 2\), после чего состояние становится равным \(c+1\):
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
Для каждого состояния \(c\) и каждой оставшейся длины \(r\) обозначим через \(\mathcal{B}_{c,r}\) упорядоченный блок всех допустимых суффиксов длины \(r\), которые можно дописать из состояния \(c\). Тогда полный блок всех допустимых положительных чисел длины \(L\) бит — это \(\mathcal{B}_{1,L-1}\), потому что старший бит обязан быть равен \(1\), а значит перед началом суффикса хвост из единиц уже имеет длину \(1\).
При \(r=0\) блок содержит ровно одно завершенное число. Оно нечетно тогда и только тогда, когда последний бит равен \(1\); в этой модели состояний это равносильно условию \(c\gt 0\).
Для блока \(\mathcal{B}_{c,r}\) пусть \(J_{c,r}\) — множество локальных позиций, на которых стоят нечетные элементы блока, если нумеровать позиции как \(1,2,\dots,|\mathcal{B}_{c,r}|\). Реализации хранят четыре агрегата:
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
Это ровно то, что нужно дальше: \(C_{c,r}\) — размер блока, \(Q_{c,r}\) — число нечетных элементов, а \(A_{c,r}\) и \(B_{c,r}\) — первый и второй моменты их локальных позиций.
Базовый случай записывается сразу:
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
Если единственное завершенное число нечетно, то оно находится на локальной позиции \(1\), поэтому оба момента тоже равны \(1\).
При \(r\gt 0\) блок \(\mathcal{B}_{c,r}\) разбивается по следующему биту. Левая ветвь всегда равна \(\mathcal{B}_{0,r-1}\). Правая ветвь существует только если \(c\lt 2\), и тогда это \(\mathcal{B}_{c+1,r-1}\). Обозначим через
$$\Delta=C_{0,r-1}$$
размер левой ветви. Поскольку все левые завершения численно меньше всех правых, любая локальная позиция из правой ветви после склейки сдвигается на \(\Delta\).
Отсюда получаются рекуррентные формулы для размера блока и количества нечетных элементов:
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}.$$
А так как каждая нечетная локальная позиция \(j\) из правой ветви превращается в \(\Delta+j\), моменты удовлетворяют формулам
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right).$$
Побочно отсюда видно, что размеры полных блоков \(T_L=C_{1,L-1}\) начинаются так:
$$1,\,2,\,3,\,6,\,11,\,20,\dots,$$
то есть растут по tribonacci-подобному закону. Явная формула коду не нужна, но именно это объясняет, почему число существенных битовых длин растет только логарифмически.
При суммировании первых \(N\) допустимых чисел все блоки, кроме последнего, берутся целиком, а последний блок может понадобиться только частично. Поэтому те же статистики должны уметь возвращаться и для первых \(k\) элементов блока. Обозначим такой префиксный агрегат через
$$\operatorname{Pref}(c,r,k).$$
Если \(\Lambda=C_{0,r-1}\) — размер левого дочернего блока, то структура префикса в точности повторяет структуру блока:
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
где \(\oplus\) означает «взять весь левый блок, затем нужный префикс правого» и применить тот же индексный сдвиг \(\Lambda\). Именно это позволяет обойтись без поэлементного перебора внутри последнего неполного блока.
Пусть все блоки меньшей битовой длины вместе содержат \(P\) допустимых чисел. Тогда локальные нечетные позиции \(j\) в выбранной части текущего блока становятся глобальными рангами \(P+j\). Если выбранная часть имеет статистики \((C,Q,A,B)\), то ее суммарный вклад равен
$$\sum (P+j)^2=QP^2+2PA+B.$$
Именно ради этой формулы реализация и хранит первый и второй моменты нечетных позиций. Как только известны \((Q,A,B)\) для целого блока или префикса блока, вклад этого фрагмента можно прибавить сразу.
Первые допустимые положительные числа таковы:
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
то есть в десятичной записи
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots.$$
Среди этих первых десяти членов нечетные стоят на рангах
$$1,\ 3,\ 5,\ 8,\ 10.$$
Следовательно,
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
Блочная картина дает то же самое. Блок длины 1 бит — это просто \(1\), значит он дает глобальный ранг \(1\). Блок длины 2 бита — это \(10,11\); его единственная локальная нечетная позиция равна \(2\), а после сдвига она становится глобальным рангом \(3\). Блок длины 3 бита — это \(100,101,110\); снова единственная локальная нечетная позиция равна \(2\), то есть глобально это ранг \(5\).
Полный 4-битный блок равен \(1000,1001,1010,1011,1100,1101\), и его локальные нечетные позиции равны \(2,4,6\). Но чтобы покрыть только первые десять допустимых чисел, нужно взять из этого блока лишь первые четыре элемента: \(1000,1001,1010,1011\). В таком префиксе локальные нечетные позиции — это \(2\) и \(4\). После сдвига на шесть уже пройденных допустимых чисел они превращаются в глобальные ранги \(8\) и \(10\). Именно такую операцию и выполняет префиксная процедура на больших данных.
Реализации на C++, Python и Java вычисляют каждый статус \((c,r)\) ровно один раз и затем переиспользуют его. Для каждого статуса хранятся точный размер блока, точное число нечетных элементов, а также модульные версии числа нечетных элементов и первых двух моментов их позиций. Точные размеры нужны для выбора ветви при разборе префикса; для финального ответа достаточно модульных моментов.
Если искомое \(N\) заканчивается внутри некоторого битового блока, программа рекурсивно спускается по этому блоку. На каждом уровне она сравнивает нужную длину префикса с размером левого дочернего блока. Если весь префикс помещается слева, спуск продолжается только туда. Иначе берется весь левый блок, его размер вычитается из нужной длины, и вычисление продолжается в правой ветви, после чего обе части склеиваются с нужным сдвигом.
Внешний цикл идет по битовым длинам в возрастающем порядке и поддерживает число \(P\) уже учтенных допустимых элементов. Для каждого полного блока, либо для последнего частичного блока, он берет статистики \((Q,A,B)\) и добавляет
$$QP^2+2PA+B \pmod{10^9+7}.$$
Ни одна реализация не перечисляет допустимые числа до ранга \(10^{16}\) по одному; все они работают только с размерами блоков и моментами позиций. Одна из реализаций дополнительно проверяет маленькие случаи вроде \(F(10)=199\) прямым перебором.
Пусть \(L_\ast\) — максимальная битовая длина, необходимая, чтобы покрыть первые \(N\) допустимых чисел. Тогда полных состояний автомата всего \(3(L_\ast+1)\), и каждое состояние вычисляется один раз. Проход по полным битовым блокам стоит \(O(L_\ast)\), а разбор последнего частичного блока через префиксный спуск тоже стоит \(O(L_\ast)\).
Следовательно, полное время работы равно \(O(L_\ast)\), и память равна \(O(L_\ast)\). Поскольку размеры блоков растут экспоненциально по tribonacci-типу, получаем \(L_\ast=O(\log N)\). Значит, в терминах \(N\) алгоритм работает за \(O(\log N)\) времени и использует \(O(\log N)\) памяти.
لتكن \(a_1 \lt a_2 \lt \cdots\) هي المتتالية المتزايدة للأعداد الصحيحة الموجبة التي لا يظهر في تمثيلها الثنائي أي مقطع من الشكل \(111\). المطلوب هو حساب \(F(10^{16})\)، حيث
$$F(N)=\sum_{i=1}^{N} i^2\,\mathbf{1}_{\{a_i\equiv 1\pmod 2\}} \pmod{10^9+7}.$$
الكمية التي نربّعها ليست القيم \(a_i\) نفسها، بل رتبها \(i\) داخل الترتيب الصاعد، وذلك فقط عندما يكون العدد الموافق فرديًا. لذلك فالمسألة الحقيقية هي تحديد المواضع التي تظهر فيها الحدود الفردية بين أول \(N\) عددًا ثنائيًا مسموحًا، من دون تعدادها واحدًا واحدًا حتى \(N=10^{16}\).
يقسم الحل الأعداد المسموح بها إلى كتل بحسب طولها الثنائي، ويستعمل آلة حالات صغيرة لوصف اللواحق المسموح بها، ثم يحتفظ لكل كتلة بإحصاءات تكفي لإضافة مساهمتها كلها إلى الجواب دفعة واحدة.
كل عدد صحيح موجب طوله \(L\) بتات أكبر من أي عدد موجب أقصر منه. لهذا ينقسم الترتيب العام تلقائيًا إلى كتل متتالية: أولًا جميع الأعداد المسموح بها ذات 1 بت، ثم ذات 2 بت، ثم ذات 3 بت، وهكذا.
وعند تثبيت البت الأعلى \(1\)، يصبح الترتيب العددي داخل طول ثابت مطابقًا تمامًا للترتيب المعجمي على البتات المتبقية. ومن هنا تظهر بنية الفرعين: كل الإكمالات التي يبدأ بتها التالي بـ \(0\) تأتي قبل كل الإكمالات التي يبدأ بتها التالي بـ \(1\).
عند بناء كلمة ثنائية من اليسار إلى اليمين، يكفي لمعرفة ما إذا كان النمط الممنوع \(111\) سيظهر أم لا أن نعرف طول السلسلة النهائية من الواحدات في البادئة الحالية. لنرمز إلى هذا الطول بـ
$$c\in\{0,1,2\}.$$
إضافة \(0\) مسموحة دائمًا وتعيد الحالة إلى \(0\). أما إضافة \(1\) فلا تُسمح إلا إذا كان \(c\lt 2\)، وعندها تصبح الحالة الجديدة \(c+1\):
$$c\xrightarrow{0}0,\qquad c\xrightarrow{1}c+1\quad(c=0,1).$$
ولكل حالة \(c\) ولكل طول متبقٍّ \(r\)، نعرّف \(\mathcal{B}_{c,r}\) بأنها الكتلة المرتبة لجميع اللواحق الصحيحة بطول \(r\) التي يمكن إلحاقها من الحالة \(c\). وبذلك تكون الكتلة الكاملة لكل الأعداد الصحيحة الموجبة المسموح بها ذات الطول \(L\) هي \(\mathcal{B}_{1,L-1}\)، لأن البت الأعلى يجب أن يكون \(1\)، وهذا يعني أن طول ذيل الواحدات قبل بدء اللاحقة يساوي \(1\).
عندما \(r=0\)، تحتوي الكتلة على عدد مكتمل واحد فقط. ويكون هذا العدد فرديًا إذا وفقط إذا كان بتّه الأخير \(1\)، وهذا في لغة الحالات يكافئ تمامًا الشرط \(c\gt 0\).
للكتلة \(\mathcal{B}_{c,r}\)، لتكن \(J_{c,r}\) مجموعة المواضع المحلية التي تشغلها العناصر الفردية داخل الكتلة، مع ترقيم المواضع محليًا على الصورة \(1,2,\dots,|\mathcal{B}_{c,r}|\). تحتفظ التطبيقات بأربع كميات:
$$C_{c,r}=|\mathcal{B}_{c,r}|,$$
$$Q_{c,r}=|J_{c,r}|,$$
$$A_{c,r}=\sum_{j\in J_{c,r}} j,$$
$$B_{c,r}=\sum_{j\in J_{c,r}} j^2.$$
وهذه الإحصاءات هي كل ما نحتاجه لاحقًا: \(C_{c,r}\) هو حجم الكتلة، و\(Q_{c,r}\) هو عدد عناصرها الفردية، أما \(A_{c,r}\) و\(B_{c,r}\) فهما العزم الأول والعزم الثاني لمواضع العناصر الفردية داخل الكتلة.
وحالة الأساس مباشرة هي
$$C_{c,0}=1,\qquad Q_{c,0}=\mathbf{1}_{\{c\gt 0\}},\qquad A_{c,0}=Q_{c,0},\qquad B_{c,0}=Q_{c,0}.$$
فإذا كان العدد المكتمل الوحيد فرديًا، فإن موضعه المحلي الوحيد هو \(1\)، ولذلك يكون كل من العزمين مساويًا أيضًا لـ \(1\).
إذا كان \(r\gt 0\)، فإن الكتلة \(\mathcal{B}_{c,r}\) تنقسم بحسب البت التالي. الفرع الأيسر هو دائمًا \(\mathcal{B}_{0,r-1}\). أما الفرع الأيمن فلا يوجد إلا عندما \(c\lt 2\)، وعندئذ يساوي \(\mathcal{B}_{c+1,r-1}\). ولنكتب
$$\Delta=C_{0,r-1}$$
لحجم الفرع الأيسر. وبما أن كل عناصر الفرع الأيسر أصغر عدديًا من كل عناصر الفرع الأيمن، فإن أي موضع محلي قادم من الفرع الأيمن ينزاح بمقدار \(\Delta\) بعد الدمج.
ومن ثم نحصل على علاقتي الحجم وعدد العناصر الفردية:
$$C_{c,r}=C_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,C_{c+1,r-1},$$
$$Q_{c,r}=Q_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\,Q_{c+1,r-1}.$$
وبما أن كل موضع فردي \(j\) في الفرع الأيمن يصبح \(\Delta+j\) بعد الدمج، فإن العزوم تحقق
$$A_{c,r}=A_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(A_{c+1,r-1}+\Delta\,Q_{c+1,r-1}\right),$$
$$B_{c,r}=B_{0,r-1}+\mathbf{1}_{\{c\lt 2\}}\left(B_{c+1,r-1}+2\Delta\,A_{c+1,r-1}+\Delta^2Q_{c+1,r-1}\right).$$
ومن النتائج الجانبية أن أحجام الكتل الكاملة \(T_L=C_{1,L-1}\) تبدأ بالقيم
$$1,\,2,\,3,\,6,\,11,\,20,\dots,$$
وهي تنمو بنمط يشبه أعداد tribonacci. لا يحتاج الكود إلى صيغة مغلقة، لكن هذا النمو هو ما يجعل عدد أطوال البتات المهمة ينمو لوغاريتميًا فقط مع \(N\).
عند جمع أول \(N\) عددًا مسموحًا، تؤخذ كل الكتل السابقة كاملة، بينما قد نحتاج من الكتلة الأخيرة إلى بادئة فقط. لذلك يجب أن نستطيع استخراج الإحصاءات نفسها لأول \(k\) عنصرًا من أي كتلة. نرمز إلى ذلك بـ
$$\operatorname{Pref}(c,r,k).$$
إذا كان حجم الفرع الأيسر هو \(\Lambda=C_{0,r-1}\)، فإن بنية البادئة تتبع بنية الكتلة نفسها تمامًا:
$$\operatorname{Pref}(c,r,k)= \begin{cases} (0,0,0,0),&k=0,\\ (C_{c,r},Q_{c,r},A_{c,r},B_{c,r}),&k\ge C_{c,r},\\ \operatorname{Pref}(0,r-1,k),&1\le k\le \Lambda,\\ (C_{0,r-1},Q_{0,r-1},A_{0,r-1},B_{0,r-1})\oplus \operatorname{Pref}(c+1,r-1,k-\Lambda),&k\gt \Lambda, \end{cases}$$
حيث يرمز \(\oplus\) إلى أخذ الكتلة اليسرى كاملة أولًا ثم بادئة مناسبة من الكتلة اليمنى، مع تطبيق الإزاحة نفسها بمقدار \(\Lambda\). وبهذه الآلية لا حاجة إلى تعداد عناصر الكتلة الجزئية الأخيرة عنصرًا عنصرًا.
لنفترض أن جميع الكتل الأقصر تحتوي معًا على \(P\) عددًا مسموحًا. عندئذ تصبح المواضع الفردية المحلية \(j\) في الجزء المختار من الكتلة الحالية مراتب عالمية \(P+j\). وإذا كانت إحصاءات هذا الجزء هي \((C,Q,A,B)\)، فإن مساهمته الكلية تساوي
$$\sum (P+j)^2=QP^2+2PA+B.$$
ولهذا السبب بالتحديد تحفظ الخوارزمية العزمين الأول والثاني لمواضع العناصر الفردية. فبمجرد معرفة \((Q,A,B)\) لكتلة كاملة أو لبادئة من كتلة، يصبح من الممكن إضافة مساهمة هذا الجزء فورًا.
أول الأعداد الصحيحة الموجبة المسموح بها هي
$$1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 1000,\ 1001,\ 1010,\ 1011,\dots$$
بالثنائي، أي
$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 11,\dots$$
بالعشري. وبين هذه الحدود العشرة الأولى تظهر الحدود الفردية عند الرتب
$$1,\ 3,\ 5,\ 8,\ 10.$$
إذن
$$F(10)=1^2+3^2+5^2+8^2+10^2=199.$$
وتعطي رؤية الكتل النتيجة نفسها. فكتلة الطول 1 هي فقط \(1\)، ولذلك تعطي الرتبة العالمية \(1\). وكتلة الطول 2 هي \(10,11\)، وموضعها الفردي المحلي الوحيد هو \(2\)، الذي يصبح بعد الإزاحة الرتبة العالمية \(3\). وكتلة الطول 3 هي \(100,101,110\)، وفيها أيضًا الموضع الفردي المحلي الوحيد هو \(2\)، وبالتالي نحصل على الرتبة العالمية \(5\).
أما كتلة الطول 4 الكاملة فهي \(1000,1001,1010,1011,1100,1101\)، ومواضعها الفردية المحلية هي \(2,4,6\). ولكن للوصول إلى أول عشرة أعداد مسموح بها يكفي أخذ أول أربعة عناصر فقط من هذه الكتلة: \(1000,1001,1010,1011\). في هذه البادئة تكون المواضع الفردية المحلية \(2\) و\(4\) فقط، وبعد إزاحتها بمقدار الأعداد الستة السابقة تصبح الرتب العالمية \(8\) و\(10\). وهذا بالضبط ما تفعله روتين البادئة في الحالة الكبيرة.
تقوم تطبيقات C++ وPython وJava بحساب كل حالة \((c,r)\) مرة واحدة فقط ثم تخزينها. ولكل حالة تُحفظ قيمة الحجم الدقيقة للكتلة، والعدد الدقيق لعناصرها الفردية، والنسخ المأخوذة بترديد \(10^9+7\) من عدد العناصر الفردية ومن العزمين الأول والثاني لمواضعها. الأحجام الدقيقة مطلوبة لكي نقرر كيف تنقسم البادئة بين الفرعين، أما العزوم المعيارية فتكفي لتجميع الجواب النهائي.
إذا انتهت القيمة المطلوبة \(N\) في منتصف كتلة ذات طول معين، فإن التنفيذ يهبط عوديًا داخل تلك الكتلة. في كل مستوى يقارن طول البادئة المطلوبة بحجم الفرع الأيسر. فإذا كانت البادئة كلها في اليسار، تابع النزول هناك فقط. وإن لم تكن كذلك، أُخذ الفرع الأيسر كاملًا، ثم طُرح حجمه من الطول المتبقي، واستمر النزول في الفرع الأيمن، وبعدها تُدمج القطعتان بإزاحة الفهارس المناسبة.
تمر الحلقة الخارجية على أطوال البتات تصاعديًا، وتحافظ على قيمة \(P\) تمثل عدد الأعداد المسموح بها التي حُسبت بالفعل. ولكل كتلة كاملة، أو للكتلة الجزئية الأخيرة، تقرأ الإحصاءات \((Q,A,B)\) ثم تضيف
$$QP^2+2PA+B \pmod{10^9+7}.$$
ولا يقوم أي تنفيذ بتوليد جميع الأعداد المسموح بها حتى الرتبة \(10^{16}\) صراحةً؛ بل تعمل جميعها حصريًا بإحصاءات الكتل وعزوم المواضع. كما يتحقق أحد التنفيذات أيضًا من حالات صغيرة مثل \(F(10)=199\) بالمقارنة مع العد المباشر.
لتكن \(L_\ast\) أكبر طول بتات نحتاجه لكي نغطي أول \(N\) عددًا مسموحًا. عندئذ لا يوجد إلا \(3(L_\ast+1)\) حالة كاملة للآلة، وكل حالة تُحسب مرة واحدة فقط. والمسح عبر الكتل الكاملة يكلف \(O(L_\ast)\)، كما أن النزول العودي داخل الكتلة الجزئية الأخيرة يكلف \(O(L_\ast)\) أيضًا.
لذلك فإن الزمن الكلي هو \(O(L_\ast)\)، واستهلاك الذاكرة كذلك \(O(L_\ast)\). وبما أن أحجام الكتل تنمو أسيًا بنمط شبيه بـ tribonacci، فإن \(L_\ast=O(\log N)\). أي أن الخوارزمية تعمل، بدلالة \(N\)، في \(O(\log N)\) زمنًا و\(O(\log N)\) ذاكرة.