For the bound \(L=7^{10}\), the bounded binary-search model is encoded by a capped capacity function \(T(m,d)\). Here \(m\) is the remaining number of search steps and \(d\) is the current bound parameter. For each fixed \(d\), the quantity of interest is the smallest \(m\) that lets the search distinguish at least \(N\) possibilities.
Define that inverse threshold by
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}.$$
The required total is
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}.$$
The difficulty is that \(T(m,d)\) is recursive, but the implementations exploit three facts: every value is capped at \(L\), the sequence is monotone in \(m\), and the inverse thresholds can be summed by jump intervals rather than one query at a time.
The implementations work with the following capped recurrence:
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
together with boundary rules that make the recursion finite and allow an efficient inversion.
The boundary conditions are
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1).$$
These rules say that once there is no remaining search depth, or once the parameter has reached the terminal boundary \(-1\), only one outcome is still distinguishable. If the parameter falls below that boundary, the branch contributes nothing.
Every value is truncated at \(L\). This cap is mathematically safe because the final sum only asks about thresholds \(1\le N\le L\), so any larger capacity is indistinguishable from \(L\).
When the bound parameter is already large compared with the remaining depth, the restriction disappears and the search becomes a full binary tree. In that regime,
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
This shortcut is one of the key optimizations. Since
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
any completely unrestricted branch reaches the cap by depth \(29\).
For fixed \(d\), the sequence \(T(0,d),T(1,d),T(2,d),\dots\) is nondecreasing in \(m\). Intuitively, allowing one more search step cannot reduce the number of distinguishable outcomes, and the recurrence only combines previously computed nonnegative capacities.
Therefore the inverse threshold
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
is well defined for every \(1\le N\le L\). The problem is thus a sum of inverse threshold values, not a sum of the capacities themselves.
Substituting \(d=0\) into the recurrence gives
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0),$$
with initial value \(T(0,0)=1\). Hence
$$T(m,0)=m+1.$$
Inverting this linear sequence yields
$$R_0(N)=N-1.$$
That is why the \(d=0\) contribution is handled separately as the arithmetic series
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}.$$
Suppose
$$T(m-1,d)<N\le T(m,d).$$
Then the smallest admissible depth for that \(N\) is exactly \(m\), so every \(N\) in the jump interval \((T(m-1,d),T(m,d)]\) contributes \(m\) to the total. If we define \(T(-1,d)=0\), then
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr).$$
This identity is the main computational trick. Instead of asking for \(R_d(N)\) separately for every \(N\), one scans \(m=0,1,2,\dots\) until \(T(m,d)=L\) and adds one weighted jump per step.
The first two nontrivial parameters already illustrate the pattern.
For \(d=1\), the values are
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12. \end{aligned}$$
So the thresholds break into intervals
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3. \end{aligned}$$
In particular, \(R_1(7)=3\).
For \(d=2\), once \(m\ge 4\), the second recursive branch is already in the unrestricted regime, so
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4).$$
Using \(T(9,1)=265\), we get
$$T(10,2)=T(9,1)+2^9=265+512=777,$$
hence \(R_2(777)=10\), matching the checkpoint used by the implementations.
The C++, Python, and Java implementations memoize each previously computed state, indexed by the current depth and the effective bound parameter. Each lookup first applies the boundary rules above. If the unrestricted branch condition \(d\ge m-1\) is met, the value is returned immediately as \(\min(2^m,L)\); otherwise the program evaluates the two smaller recursive states, adds them, and caps the sum at \(L\).
After that memoized engine is available, the implementation handles \(d=0\) through the closed form \(\frac{L(L-1)}2\). For each \(d=1,\dots,7\), it increases \(m\) from \(0\) upward, keeps the previous capacity value, and accumulates
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
until the cap \(L\) is reached. The final accumulation uses integer types large enough to avoid overflow in every language.
Fix a parameter \(d\), and let \(M_d\) be the first depth for which \(T(M_d,d)=L\). Let \(S_d\) be the set of distinct memoized states visited while evaluating the capacities for depths \(0\) through \(M_d\). Because each state is computed at most once and later reused, the running time for that \(d\) is \(O(|S_d|)\), and the memo storage is also \(O(|S_d|)\).
Therefore the full program costs
$$O\left(\sum_{d=1}^{7}|S_d|\right)$$
time and
$$O\left(\max_{1\le d\le 7}|S_d|\right)$$
auxiliary memory, plus negligible overhead for the final big-integer style additions. The cap at \(L\) and the closed binary-search branch keep the explored state space far smaller than the naive recursion tree.
Für die Schranke \(L=7^{10}\) wird das Modell der beschränkten Binärsuche durch eine abgeschnittene Kapazitätsfunktion \(T(m,d)\) beschrieben. Dabei ist \(m\) die verbleibende Anzahl von Suchschritten und \(d\) der aktuelle Grenzparameter. Für festes \(d\) sucht man die kleinste Tiefe \(m\), mit der sich mindestens \(N\) Möglichkeiten unterscheiden lassen.
Diese inverse Schwelle sei
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}.$$
Gesucht ist also
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}.$$
Die Schwierigkeit liegt darin, dass \(T(m,d)\) rekursiv definiert ist. Die Lösung nutzt jedoch drei Eigenschaften aus: alle Werte werden bei \(L\) abgeschnitten, die Folge ist in \(m\) monoton, und die Inversen lassen sich über Sprungintervalle summieren statt über Einzelanfragen.
Die Implementierungen verwenden die folgende abgeschnittene Rekurrenz:
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
zusammen mit Randfällen, die die Rekursion endlich und effizient invertierbar machen.
Die Randbedingungen lauten
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1).$$
Das bedeutet: Ohne verbleibende Suchtiefe oder am terminalen Rand \(-1\) bleibt genau ein unterscheidbarer Fall übrig. Fällt der Parameter noch weiter, trägt dieser Zweig nichts mehr bei.
Jeder Wert wird zusätzlich bei \(L\) gekappt. Das ist mathematisch korrekt, weil im Endausdruck nur Schwellen \(1\le N\le L\) vorkommen; jede größere Kapazität ist für die Aufgabe äquivalent zu \(L\).
Ist der Grenzparameter im Verhältnis zur verbleibenden Tiefe bereits groß genug, verschwindet die Zusatzbeschränkung, und man erhält einen vollständigen Binärbaum. Dann gilt
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
Diese Abkürzung ist zentral. Denn
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
also erreicht jeder völlig unbeschränkte Zweig die Kappung schon bei Tiefe \(29\).
Für festes \(d\) ist die Folge \(T(0,d),T(1,d),T(2,d),\dots\) in \(m\) nicht fallend. Anschaulich kann ein zusätzlicher Suchschritt die Zahl unterscheidbarer Ergebnisse nicht verringern, und die Rekurrenz kombiniert nur bereits berechnete nichtnegative Kapazitäten.
Daher ist die inverse Schwelle
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
für jedes \(1\le N\le L\) wohldefiniert. Gesucht ist also eine Summe solcher inverser Schwellenwerte und nicht eine Summe der Kapazitäten selbst.
Setzt man \(d=0\) in die Rekurrenz ein, so erhält man
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0),$$
mit \(T(0,0)=1\). Also
$$T(m,0)=m+1.$$
Die Inversion liefert
$$R_0(N)=N-1.$$
Deshalb wird der Beitrag für \(d=0\) separat als arithmetische Summe
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}$$
behandelt.
Gelte
$$T(m-1,d)<N\le T(m,d).$$
Dann ist \(m\) genau die kleinste zulässige Tiefe für dieses \(N\), also trägt jedes \(N\) aus dem Sprungintervall \((T(m-1,d),T(m,d)]\) den Wert \(m\) bei. Mit der Konvention \(T(-1,d)=0\) folgt
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr).$$
Das ist der wesentliche Rechentrick: Statt für jedes \(N\) die Inverse separat zu bestimmen, läuft man nur die Tiefen \(m=0,1,2,\dots\) durch, bis \(T(m,d)=L\) erreicht ist, und addiert pro Schritt genau einen gewichteten Sprung.
Schon die ersten beiden nichttrivialen Parameter zeigen das Muster deutlich.
Für \(d=1\) gilt
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12. \end{aligned}$$
Daraus folgen die Intervalle
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3. \end{aligned}$$
Insbesondere ist also \(R_1(7)=3\).
Für \(d=2\) liegt ab \(m\ge 4\) der zweite Rekursionszweig bereits im unbeschränkten Bereich, also
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4).$$
Mit \(T(9,1)=265\) erhält man
$$T(10,2)=T(9,1)+2^9=265+512=777,$$
und damit \(R_2(777)=10\), genau wie in den Kontrollwerten der Implementierungen.
Die C++-, Python- und Java-Implementierungen memoizieren jeden bereits berechneten Zustand, bestimmt durch die aktuelle Tiefe und den effektiven Grenzparameter. Vor jedem Rekursionsschritt werden zuerst die Randregeln geprüft. Falls die Bedingung \(d\ge m-1\) erfüllt ist, wird der Wert sofort als \(\min(2^m,L)\) zurückgegeben; andernfalls werden die beiden kleineren Zustände ausgewertet, addiert und bei \(L\) gekappt.
Sobald diese memoizierte Rechenmaschine bereitsteht, behandelt das Programm \(d=0\) direkt über die geschlossene Formel \(\frac{L(L-1)}2\). Für jedes \(d=1,\dots,7\) erhöht es \(m\) von \(0\) an, merkt sich den vorherigen Kapazitätswert und addiert
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
bis die Kappung \(L\) erreicht ist. Die Endsumme verwendet in jeder Sprache ausreichend große Ganzzahltypen, sodass kein Überlauf entsteht.
Fixiere einen Parameter \(d\), und sei \(M_d\) die erste Tiefe mit \(T(M_d,d)=L\). Bezeichne mit \(S_d\) die Menge aller verschiedenen memoisierten Zustände, die beim Auswerten der Tiefen \(0\) bis \(M_d\) besucht werden. Weil jeder Zustand höchstens einmal berechnet und danach wiederverwendet wird, beträgt die Laufzeit für dieses \(d\) \(O(|S_d|)\), und auch der Speicherbedarf ist \(O(|S_d|)\).
Insgesamt kostet das Verfahren also
$$O\left(\sum_{d=1}^{7}|S_d|\right)$$
Zeit und
$$O\left(\max_{1\le d\le 7}|S_d|\right)$$
Hilfsspeicher, plus vernachlässigbaren Aufwand für die abschließenden Additionen mit großen Ganzzahlen. Die Kappung bei \(L\) und der geschlossene Binärsuchzweig halten den tatsächlich besuchten Zustandsraum deutlich kleiner als den naiven Rekursionsbaum.
\(L=7^{10}\) sınırı için, sınırlı ikili arama modeli üstten kesilmiş bir kapasite fonksiyonu \(T(m,d)\) ile ifade edilir. Burada \(m\) kalan arama adımı sayısı, \(d\) ise o andaki sınır parametresidir. Sabit bir \(d\) için aranan büyüklük, en az \(N\) olasılığı ayırt etmeye yeten en küçük \(m\) değeridir.
Bu ters eşik fonksiyonunu
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}$$
şeklinde tanımlayalım. İstenen toplam
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}$$
olur. Zorluk, \(T(m,d)\)'nin özyinelemeli olmasıdır; ancak uygulamalar üç yapıyı kullanır: tüm değerler \(L\) ile sınırlandırılır, dizi \(m\)'ye göre monotondur ve ters eşikler tek tek sorgulanmak yerine sıçrama aralıkları üzerinden toplanabilir.
Uygulamalarda kullanılan kesilmiş özyineleme şudur:
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
ve buna eşlik eden taban durumları, özyinelemeyi sonlu ve terslenebilir hale getirir.
Taban koşulları
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1)$$
şeklindedir. Yani artık arama derinliği kalmadığında ya da parametre son sınır olan \(-1\)'e indiğinde tek bir sonuç ayırt edilebilir; bunun da altına inen dallar hiç katkı vermez.
Her değer ayrıca \(L\) ile kesilir. Bu matematiksel olarak güvenlidir, çünkü son toplam yalnızca \(1\le N\le L\) eşiklerini sorar; \(L\)'den büyük her kapasite bu problem açısından \(L\) ile aynı etkiyi yapar.
Sınır parametresi kalan derinliğe göre yeterince büyük olduğunda ek kısıt kaybolur ve tam bir ikili arama ağacı elde edilir. Bu durumda
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
Bu kısa yol çok önemlidir. Çünkü
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
dolayısıyla tamamen serbest bir dal en geç \(29\). derinlikte üst sınıra ulaşır.
Sabit \(d\) için \(T(0,d),T(1,d),T(2,d),\dots\) dizisi \(m\)'ye göre azalmayan bir dizidir. Sezgi olarak, ek bir arama adımı ayırt edilebilen durum sayısını azaltamaz; ayrıca özyineleme yalnızca daha önce hesaplanmış ve negatif olmayan kapasiteleri birleştirir.
Bu yüzden
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
her \(1\le N\le L\) için iyi tanımlıdır. Problem doğrudan kapasite toplamı değil, bu ters eşik değerlerinin toplamıdır.
\(d=0\) yazılırsa
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0)$$
elde edilir ve başlangıç değeri \(T(0,0)=1\)'dir. Buradan
$$T(m,0)=m+1$$
çıkar. Tersi ise
$$R_0(N)=N-1$$
olur. Bu nedenle \(d=0\) katkısı ayrı olarak
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}$$
aritmetik serisiyle hesaplanır.
Eğer
$$T(m-1,d)<N\le T(m,d)$$
ise, bu \(N\) için gereken en küçük derinlik tam olarak \(m\)'dir. Dolayısıyla \((T(m-1,d),T(m,d)]\) aralığındaki her \(N\), toplama \(m\) katkısı yapar. \(T(-1,d)=0\) tanımıyla
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr)$$
eşitliği elde edilir. Ana hesap hilesi budur: her \(N\) için ayrı ayrı ters aramak yerine, yalnızca \(m=0,1,2,\dots\) boyunca ilerlenir ve her adımda tek bir ağırlıklı sıçrama eklenir.
İlk iki anlamlı parametre bile yapıyı açıkça gösterir.
\(d=1\) için
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12 \end{aligned}$$
olur. Böylece eşik aralıkları
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3 \end{aligned}$$
şeklindedir. Özellikle \(R_1(7)=3\).
\(d=2\) için, \(m\ge 4\) olduğunda ikinci özyinelemeli dal artık serbest bölgededir ve
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4)$$
yazılabilir. \(T(9,1)=265\) olduğundan
$$T(10,2)=T(9,1)+2^9=265+512=777,$$
dolayısıyla \(R_2(777)=10\) elde edilir; bu da uygulamaların kullandığı kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları, mevcut derinlik ile etkin sınır parametresinin belirlediği her durumu önbelleğe alır. Her hesaplamada önce yukarıdaki taban koşulları uygulanır. Eğer \(d\ge m-1\) ise değer doğrudan \(\min(2^m,L)\) olarak döndürülür; aksi halde iki küçük özyinelemeli durum hesaplanır, toplanır ve sonuç \(L\) ile kesilir.
Bu memoizasyon altyapısı kurulduktan sonra uygulama, \(d=0\) için \(\frac{L(L-1)}2\) kapalı formunu kullanır. Ardından her \(d=1,\dots,7\) için \(m\) değerini \(0\)'dan başlayarak artırır, bir önceki kapasiteyi saklar ve
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
ifadesini \(L\) sınırına ulaşana kadar toplar. Son toplama her dilde taşmayı önleyecek kadar geniş tamsayı aritmetiği kullanır.
Sabit bir \(d\) için, \(T(M_d,d)=L\) eşitliğini sağlayan ilk derinliğe \(M_d\) diyelim. \(0\) ile \(M_d\) arasındaki kapasiteler hesaplanırken ziyaret edilen farklı memoize durumların kümesine de \(S_d\) diyelim. Her durum en fazla bir kez hesaplanıp sonra tekrar kullanıldığı için, bu \(d\) için zaman maliyeti \(O(|S_d|)\), bellek maliyeti de \(O(|S_d|)\) olur.
Dolayısıyla toplam çalışma süresi
$$O\left(\sum_{d=1}^{7}|S_d|\right)$$
ve ek bellek kullanımı
$$O\left(\max_{1\le d\le 7}|S_d|\right)$$
şeklindedir. Son büyük tamsayı toplamaları bu maliyetin yanında ihmal edilebilir. Asıl önemli nokta, \(L\) kesmesi ile kapalı ikili arama dalının, gezilen durum uzayını saf özyineleme ağacına göre çok küçültmesidir.
Para la cota \(L=7^{10}\), el modelo de búsqueda binaria acotada se describe mediante una función de capacidad truncada \(T(m,d)\). Aquí \(m\) es el número de pasos de búsqueda restantes y \(d\) es el parámetro de cota actual. Para cada \(d\) fijo, se busca el menor \(m\) capaz de distinguir al menos \(N\) posibilidades.
Definimos ese umbral inverso por
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}.$$
La cantidad pedida es
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}.$$
La dificultad es que \(T(m,d)\) es recursiva. La solución se apoya en tres hechos: todos los valores se saturan en \(L\), la sucesión es monótona en \(m\), y las inversas pueden sumarse por intervalos de salto en lugar de consultarse una por una.
Las implementaciones usan la siguiente recurrencia saturada:
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
acompañada de condiciones de borde que vuelven finita la recursión y permiten invertirla con eficiencia.
Las condiciones iniciales son
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1).$$
Esto significa que, si ya no queda profundidad de búsqueda o si el parámetro llega al borde terminal \(-1\), sólo queda un resultado distinguible. Si el parámetro cae por debajo de ese borde, la rama ya no aporta nada.
Además, todo valor se recorta a \(L\). Esa saturación es correcta porque la suma final sólo pregunta por umbrales \(1\le N\le L\); cualquier capacidad mayor es indistinguible de \(L\) para el problema.
Cuando el parámetro de cota ya es grande en comparación con la profundidad restante, la restricción desaparece y el proceso se convierte en un árbol binario completo. En ese régimen,
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
Este atajo es crucial. Como
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
cualquier rama totalmente libre alcanza la saturación a más tardar en la profundidad \(29\).
Para \(d\) fijo, la sucesión \(T(0,d),T(1,d),T(2,d),\dots\) es no decreciente en \(m\). Añadir un paso extra de búsqueda no puede reducir el número de resultados distinguibles, y la recurrencia sólo combina capacidades previamente calculadas y no negativas.
Por tanto,
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
está bien definida para todo \(1\le N\le L\). El problema consiste entonces en sumar umbrales inversos, no en sumar las capacidades directamente.
Si sustituimos \(d=0\) en la recurrencia, obtenemos
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0),$$
con \(T(0,0)=1\). Luego
$$T(m,0)=m+1.$$
Al invertir esta sucesión lineal se llega a
$$R_0(N)=N-1.$$
Por eso la contribución de \(d=0\) se maneja aparte como la serie aritmética
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}.$$
Si se cumple
$$T(m-1,d)<N\le T(m,d),$$
entonces la menor profundidad admisible para ese \(N\) es exactamente \(m\). Por lo tanto, todo \(N\) en el intervalo \((T(m-1,d),T(m,d)]\) aporta \(m\) a la suma. Con la convención \(T(-1,d)=0\), resulta
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr).$$
Este es el truco central: en vez de invertir por separado para cada \(N\), basta recorrer \(m=0,1,2,\dots\) hasta que \(T(m,d)=L\), añadiendo un salto ponderado en cada paso.
Los dos primeros parámetros no triviales ya muestran la estructura.
Para \(d=1\), se tiene
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12. \end{aligned}$$
Así, los intervalos son
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3. \end{aligned}$$
En particular, \(R_1(7)=3\).
Para \(d=2\), a partir de \(m\ge 4\) la segunda rama recursiva ya cae en el régimen no restringido, y por eso
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4).$$
Usando \(T(9,1)=265\), obtenemos
$$T(10,2)=T(9,1)+2^9=265+512=777,$$
de modo que \(R_2(777)=10\), exactamente el valor de comprobación usado por las implementaciones.
Las implementaciones en C++, Python y Java memoizan cada estado ya calculado, identificado por la profundidad actual y el parámetro de cota efectivo. Antes de ramificar, aplican las reglas de borde. Si se cumple \(d\ge m-1\), devuelven inmediatamente \(\min(2^m,L)\); en caso contrario, evalúan los dos estados recursivos más pequeños, suman sus valores y vuelven a saturar en \(L\).
Una vez disponible ese motor memoizado, el caso \(d=0\) se resuelve con la forma cerrada \(\frac{L(L-1)}2\). Para cada \(d=1,\dots,7\), el programa incrementa \(m\) desde \(0\), conserva la capacidad anterior y acumula
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
hasta que la capacidad alcanza \(L\). La suma final usa enteros suficientemente grandes en cada lenguaje para evitar desbordamientos.
Fijemos \(d\), y sea \(M_d\) la primera profundidad con \(T(M_d,d)=L\). Denotemos por \(S_d\) el conjunto de estados memoizados distintos visitados al evaluar las capacidades desde la profundidad \(0\) hasta \(M_d\). Como cada estado se calcula a lo sumo una vez y luego se reutiliza, el tiempo para ese \(d\) es \(O(|S_d|)\), y la memoria también es \(O(|S_d|)\).
En consecuencia, el programa completo requiere
$$O\left(\sum_{d=1}^{7}|S_d|\right)$$
tiempo y
$$O\left(\max_{1\le d\le 7}|S_d|\right)$$
memoria auxiliar, más un costo despreciable para las sumas finales con enteros grandes. Lo importante es que la saturación en \(L\) y la rama cerrada de búsqueda binaria hacen que el espacio de estados real sea mucho menor que el árbol recursivo ingenuo.
当上界取为 \(L=7^{10}\) 时，这个“有界二分搜索”模型可以写成一个带截断的容量函数 \(T(m,d)\)。其中 \(m\) 表示剩余的搜索步数，\(d\) 表示当前的边界参数。对固定的 \(d\) 来说，我们真正需要的是：至少区分出 \(N\) 种可能性时，所需的最小步数 \(m\) 是多少。
把这个反向阈值函数记为
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}.$$
题目要求计算
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}.$$
难点在于 \(T(m,d)\) 不是显式公式，而是一个递推定义的量。不过实现利用了三个关键事实：所有值都会被截断到 \(L\)，对固定 \(d\) 而言它关于 \(m\) 单调不减，而且这些反向阈值不必逐个 \(N\) 去求，而可以通过相邻容量值之间的“跳跃区间”一次性累加。
三种语言的实现都基于同一个截断递推：
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
再配合若干边界规则，使递归既能终止，也能高效求逆。
边界条件是
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1).$$
它们的含义是：如果已经没有剩余搜索深度，或者边界参数已经到达终止层 \(-1\)，那么这一分支最多只能区分出一种结果；如果参数继续下降到 \(-1\) 以下，这条分支就不再贡献任何容量。
此外，所有值都要再与 \(L\) 取最小值。这样做在数学上是安全的，因为最终总和只涉及 \(1\le N\le L\) 的阈值；一旦容量超过 \(L\)，对题目而言它和正好等于 \(L\) 没有区别。
当边界参数相对剩余深度已经足够大时，额外约束会消失，递推就退化成完整的二叉搜索树。在这种情况下有
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
这是实现中的一个核心快捷分支。因为
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
所以任何完全不受限制的分支，最多到深度 \(29\) 就已经达到上界 \(L\) 了。
对固定的 \(d\)，序列 \(T(0,d),T(1,d),T(2,d),\dots\) 关于 \(m\) 是单调不减的。直观上说，允许多做一步搜索，不可能让可区分的结果数变少；而递推右侧只会把已经得到的非负容量重新组合起来。
因此
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
对每个 \(1\le N\le L\) 都有良好定义。于是题目本质上是在求这些“反向阈值”的总和，而不是直接求容量值的总和。
把 \(d=0\) 代入递推，可以得到
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0),$$
同时 \(T(0,0)=1\)。于是立刻有
$$T(m,0)=m+1.$$
反演后得到
$$R_0(N)=N-1.$$
这就解释了为什么实现会先单独加上
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}$$
这一段等差数列，而把 \(d=1,\dots,7\) 放到后面统一处理。
如果某个 \(N\) 满足
$$T(m-1,d)<N\le T(m,d),$$
那么达到这个 \(N\) 所需的最小深度就恰好是 \(m\)。也就是说，区间 \((T(m-1,d),T(m,d)]\) 里的每个 \(N\) 都为总和贡献一个 \(m\)。约定 \(T(-1,d)=0\) 后，可以把整段和写成
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr).$$
这一步就是实现的核心技巧。原本如果逐个 \(N\) 去求 \(R_d(N)\)，代价会很高；但改成按 \(m=0,1,2,\dots\) 顺序扫描，只要每次记录容量增量，就能一次性把整段区间的贡献全部算进去，并且在 \(T(m,d)=L\) 时立即停止。
前两个非平凡参数已经足以说明整个机制。
先看 \(d=1\)。前几个值是
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12. \end{aligned}$$
因此阈值区间可以直接写成
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3. \end{aligned}$$
特别地，\(R_1(7)=3\)。这说明一旦容量跨过 \(7\)，最小深度正好是 \(3\)。
再看 \(d=2\)。从 \(m\ge 4\) 开始，第二个递归分支已经落入“普通二分搜索区域”，所以满足
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4).$$
而前面算出的 \(d=1\) 序列告诉我们 \(T(9,1)=265\)，于是
$$T(10,2)=T(9,1)+2^9=265+512=777.$$
因此有
$$R_2(777)=10,$$
这恰好对应实现中的检查值，也说明这种递推反演的思路和程序行为完全一致。
C++、Python 和 Java 版本都对“当前深度 + 当前有效边界参数”这对状态做记忆化。每次请求一个状态时，先检查边界条件；如果满足 \(d\ge m-1\)，就直接返回 \(\min(2^m,L)\)；否则递归求出两个更小状态，把它们相加，再用 \(L\) 做一次截断。
有了这个记忆化引擎之后，程序对 \(d=0\) 直接使用闭式 \(\frac{L(L-1)}2\)。对于每个 \(d=1,\dots,7\)，它从 \(m=0\) 开始逐步增加深度，保存前一个容量值，并累加
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
直到容量达到 \(L\)。最终的总和在三种语言里都使用足够宽的整数表示，以避免溢出。
固定一个参数 \(d\)，记 \(M_d\) 为满足 \(T(M_d,d)=L\) 的最小深度。再记 \(S_d\) 为在计算深度 \(0\) 到 \(M_d\) 这些容量值时真正访问到的不同记忆化状态集合。由于每个状态最多只会被计算一次，随后都直接复用，所以这个 \(d\) 的时间复杂度是 \(O(|S_d|)\)，空间复杂度也是 \(O(|S_d|)\)。
于是整个程序的总时间复杂度可以写成
$$O\left(\sum_{d=1}^{7}|S_d|\right),$$
辅助空间复杂度为
$$O\left(\max_{1\le d\le 7}|S_d|\right).$$
和朴素地展开整棵递归树相比，真正访问到的状态要少得多，因为一方面所有值都会在 \(L\) 处截断，另一方面一旦进入普通二分搜索区域，就能直接走闭式分支。
При ограничении \(L=7^{10}\) модель ограниченного бинарного поиска удобно описывать через усеченную функцию мощности \(T(m,d)\). Здесь \(m\) обозначает число оставшихся шагов поиска, а \(d\) — текущий параметр границы. Для каждого фиксированного \(d\) нас интересует минимальное \(m\), которое позволяет различить не менее \(N\) вариантов.
Определим соответствующую обратную пороговую функцию:
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}.$$
Тогда требуется вычислить
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}.$$
Главная трудность в том, что \(T(m,d)\) задается рекурсивно. Однако решение опирается на три свойства: все значения насыщаются на уровне \(L\), последовательность по \(m\) монотонна, а сумму обратных порогов можно считать по интервалам скачков, не обращаясь к каждому \(N\) отдельно.
Во всех реализациях используется одна и та же рекуррентная формула с насыщением:
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
а также набор граничных случаев, делающих рекурсию конечной и удобной для инверсии.
Граничные условия таковы:
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1).$$
Смысл простой: если глубины больше не осталось или параметр дошел до терминальной границы \(-1\), ветвь может различить только один исход. Если параметр падает еще ниже, такая ветвь уже ничего не добавляет.
Кроме того, каждое значение сверху обрезается числом \(L\). Это корректно, потому что в итоговой сумме рассматриваются только пороги \(1\le N\le L\); любая большая мощность для задачи эквивалентна ровно \(L\).
Если параметр границы уже достаточно велик по сравнению с оставшейся глубиной, дополнительное ограничение исчезает, и процесс превращается в полный бинарный дерево-поиск. Тогда
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
Это ключевое ускорение. Поскольку
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
любая полностью свободная ветвь достигает насыщения не позднее глубины \(29\).
Для фиксированного \(d\) последовательность \(T(0,d),T(1,d),T(2,d),\dots\) не убывает по \(m\). Дополнительный шаг поиска не может уменьшить число различимых исходов, а правая часть рекурсии складывает только ранее полученные неотрицательные мощности.
Следовательно,
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
корректно определена для каждого \(1\le N\le L\). Значит, задача состоит в суммировании именно этих обратных порогов, а не значений мощности напрямую.
Подставляя \(d=0\) в рекурсию, получаем
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0),$$
при начальном значении \(T(0,0)=1\). Поэтому
$$T(m,0)=m+1.$$
После инверсии имеем
$$R_0(N)=N-1.$$
Именно поэтому вклад для \(d=0\) вычисляется отдельно как арифметическая сумма
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}.$$
Пусть
$$T(m-1,d)<N\le T(m,d).$$
Тогда минимальная допустимая глубина для этого \(N\) равна ровно \(m\). Значит, каждое \(N\) из интервала \((T(m-1,d),T(m,d)]\) вносит в сумму вклад \(m\). Если договориться, что \(T(-1,d)=0\), то
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr).$$
Это и есть главный вычислительный прием. Вместо того чтобы искать обратное значение для каждого \(N\) отдельно, достаточно идти по \(m=0,1,2,\dots\) до тех пор, пока \(T(m,d)\) не достигнет \(L\), и на каждом шаге добавлять взвешенный размер скачка.
Уже первые два нетривиальных параметра хорошо показывают всю структуру.
Для \(d=1\) имеем
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12. \end{aligned}$$
Отсюда сразу следуют интервалы
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3. \end{aligned}$$
В частности, \(R_1(7)=3\).
Для \(d=2\), начиная с \(m\ge 4\), вторая рекурсивная ветвь уже попадает в свободный режим, поэтому
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4).$$
Так как \(T(9,1)=265\), получаем
$$T(10,2)=T(9,1)+2^9=265+512=777,$$
а значит, \(R_2(777)=10\). Это совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java мемоизируют каждое уже вычисленное состояние, которое определяется текущей глубиной и эффективным параметром границы. Перед любым ветвлением сначала применяются граничные правила. Если выполнено \(d\ge m-1\), значение немедленно возвращается как \(\min(2^m,L)\); иначе вычисляются два меньших рекурсивных состояния, их сумма снова ограничивается сверху числом \(L\).
После построения этого мемоизированного механизма случай \(d=0\) обрабатывается по закрытой формуле \(\frac{L(L-1)}2\). Для каждого \(d=1,\dots,7\) программа увеличивает \(m\), хранит предыдущее значение мощности и добавляет
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
до тех пор, пока значение не достигнет \(L\). В каждой из трех языковых версий итоговая сумма накапливается в достаточно широком целочисленном типе, чтобы избежать переполнения.
Зафиксируем \(d\) и обозначим через \(M_d\) первую глубину, на которой \(T(M_d,d)=L\). Пусть \(S_d\) — множество различных мемоизированных состояний, реально посещенных при вычислении значений от глубины \(0\) до \(M_d\). Поскольку каждое состояние вычисляется не более одного раза, а затем только переиспользуется, время работы для данного \(d\) равно \(O(|S_d|)\), и столько же памяти требуется для хранения кэша.
Следовательно, полная программа имеет временную сложность
$$O\left(\sum_{d=1}^{7}|S_d|\right)$$
и дополнительную память
$$O\left(\max_{1\le d\le 7}|S_d|\right).$$
По сравнению с наивным раскрытием всего дерева рекурсии это очень существенно: насыщение на уровне \(L\) и закрытая ветвь обычного бинарного поиска резко уменьшают число реально посещаемых состояний.
عند الحد \(L=7^{10}\)، يمكن تمثيل نموذج البحث الثنائي المقيَّد بدالة سعة مقصوصة \(T(m,d)\). هنا يمثّل \(m\) عدد خطوات البحث المتبقية، ويمثّل \(d\) معامل الحد الحالي. ولكل قيمة ثابتة من \(d\)، نريد أصغر \(m\) يسمح بتمييز ما لا يقل عن \(N\) من الاحتمالات.
لنعرّف دالة العتبة العكسية على الصورة
$$R_d(N)=\min\{m\ge 0: T(m,d)\ge N\}.$$
إذن المطلوب هو حساب
$$A=\sum_{N=1}^{L}R_0(N)+\sum_{d=1}^{7}\sum_{N=1}^{L}R_d(N),\qquad L=7^{10}.$$
الصعوبة الأساسية أن \(T(m,d)\) معرفة بعلاقة عودية. لكن الحل يستفيد من ثلاث حقائق: كل القيم تُشبَع عند \(L\)، والمتتالية بالنسبة إلى \(m\) أحادية غير متناقصة، ويمكن جمع القيم العكسية عبر فترات القفز بدلاً من قلب الدالة لكل \(N\) على حدة.
تعتمد جميع التطبيقات على العلاقة العودية المقطوعة التالية:
$$T(m,d)=\min\left(L,\ T(m-1,d-1)+T\left(m-1,\ T(m-1,d-1)+d-1\right)\right),$$
مع حالات حدية تجعل العودية منتهية وقابلة للعكس بكفاءة.
الشروط الحدية هي
$$T(0,d)=1\quad(d\ge -1),\qquad T(m,-1)=1,\qquad T(m,d)=0\quad(d<-1).$$
ومعناها أنه إذا لم تبق أي عمق بحثي، أو إذا وصل المعامل إلى الحد النهائي \(-1\)، فلن يبقى سوى ناتج واحد يمكن تمييزه. أما إذا هبط المعامل إلى ما دون ذلك، فإن هذا الفرع لا يضيف أي سعة.
كذلك تُقصّ كل قيمة عند \(L\). وهذا صحيح رياضياً لأن المجموع النهائي لا يسأل إلا عن عتبات \(1\le N\le L\)، فأي سعة أكبر من \(L\) تعادل تماماً \(L\) من منظور المسألة.
إذا أصبح معامل الحد كبيراً بما يكفي مقارنة بالعمق المتبقي، تختفي القيود الإضافية وتتحول العملية إلى شجرة بحث ثنائية كاملة. عندئذ نحصل على
$$T(m,d)=\min(2^m,L),\qquad d\ge m-1.$$
هذا الاختصار جوهري جداً. فبما أن
$$2^{29}=536{,}870{,}912>7^{10}=282{,}475{,}249,$$
فإن أي فرع غير مقيَّد تماماً يصل إلى حد الإشباع \(L\) في عمق لا يتجاوز \(29\).
عند تثبيت \(d\)، تكون المتتالية \(T(0,d),T(1,d),T(2,d),\dots\) غير متناقصة بالنسبة إلى \(m\). فإضافة خطوة بحث جديدة لا يمكن أن تنقص عدد النتائج القابلة للتمييز، كما أن العلاقة العودية تجمع فقط قيماً غير سالبة سبق حسابها.
لذلك تكون
$$R_d(N)=\min\{m\ge 0:T(m,d)\ge N\}$$
معرّفة جيداً لكل \(1\le N\le L\). وبذلك تصبح المسألة مسألة جمع لهذه العتبات العكسية، لا جمعاً مباشراً لقيم السعة نفسها.
عند التعويض بـ \(d=0\) في العلاقة العودية نحصل على
$$T(m,0)=T(m-1,-1)+T(m-1,0)=1+T(m-1,0),$$
مع القيمة الابتدائية \(T(0,0)=1\). ومن ثم
$$T(m,0)=m+1.$$
وبعكس هذه المتتالية الخطية نجد
$$R_0(N)=N-1.$$
ولهذا السبب يُحسب إسهام \(d=0\) منفصلاً على صورة المتسلسلة الحسابية
$$\sum_{N=1}^{L}(N-1)=\frac{L(L-1)}{2}.$$
إذا تحقق
$$T(m-1,d)<N\le T(m,d),$$
فإن أصغر عمق يحقق هذا \(N\) هو بالضبط \(m\). وعليه فإن كل \(N\) داخل الفترة \((T(m-1,d),T(m,d)]\) يضيف مقدار \(m\) إلى المجموع. وإذا عرّفنا \(T(-1,d)=0\)، نحصل على
$$\sum_{N=1}^{L}R_d(N)=\sum_{m\ge 0} m\bigl(T(m,d)-T(m-1,d)\bigr).$$
وهذه هي الفكرة الحسابية الأساسية. فبدلاً من عكس الدالة لكل \(N\) على حدة، نمر على \(m=0,1,2,\dots\) حتى نصل إلى \(T(m,d)=L\)، وفي كل خطوة نضيف حجم القفزة مضروباً في رقم العمق.
حتى أول حالتين غير بسيطتين تكشفان شكل البنية بوضوح.
عندما \(d=1\)، تكون القيم الأولى
$$\begin{aligned} T(0,1)&=1,\\ T(1,1)&=2,\\ T(2,1)&=4,\\ T(3,1)&=T(2,0)+T(2,3)=3+4=7,\\ T(4,1)&=T(3,0)+T(3,4)=4+8=12. \end{aligned}$$
ومن ثم نحصل على الفترات
$$\begin{aligned} (0,1]&\Rightarrow R_1(N)=0,\\ (1,2]&\Rightarrow R_1(N)=1,\\ (2,4]&\Rightarrow R_1(N)=2,\\ (4,7]&\Rightarrow R_1(N)=3. \end{aligned}$$
وبصورة خاصة، \(R_1(7)=3\).
أما عندما \(d=2\)، فمنذ \(m\ge 4\) يكون الفرع العودي الثاني قد دخل بالفعل في النظام غير المقيَّد، ولذلك
$$T(m,2)=T(m-1,1)+2^{m-1}\qquad(m\ge 4).$$
وباستخدام \(T(9,1)=265\) نجد
$$T(10,2)=T(9,1)+2^9=265+512=777,$$
ومن ثم \(R_2(777)=10\)، وهو نفس مقدار التحقق الذي تستخدمه التطبيقات.
تقوم تطبيقات C++ وPython وJava بحفظ كل حالة محسوبة سابقاً، والمحددة بعمق البحث الحالي ومعامل الحد الفعّال. في كل طلب جديد تُفحص الشروط الحدية أولاً. فإذا تحقق \(d\ge m-1\) أُعيدت القيمة مباشرة على صورة \(\min(2^m,L)\)؛ وإلا تُحسب الحالتان العوديتان الأصغر، ثم يُجمع الناتجان وتُطبَّق عليهما عملية القص عند \(L\).
بعد بناء هذا المحرك المعتمد على الحفظ، تُعالج حالة \(d=0\) بالصيغة المغلقة \(\frac{L(L-1)}2\). ثم لكل \(d=1,\dots,7\) تزيد الشفرة قيمة \(m\) بدءاً من الصفر، وتحتفظ بالقيمة السابقة للسعة، وتضيف
$$m\bigl(T(m,d)-T(m-1,d)\bigr)$$
إلى أن تصل السعة إلى \(L\). ويستعمل الجمع النهائي أنماط أعداد صحيحة واسعة بما يكفي لتجنب الفيض في كل لغة.
لنفترض أن \(M_d\) هو أول عمق يحقق \(T(M_d,d)=L\) من أجل قيمة ثابتة لـ \(d\). ولتكن \(S_d\) مجموعة الحالات المميزة المخزنة التي تُزار فعلاً أثناء حساب القيم من العمق \(0\) حتى \(M_d\). بما أن كل حالة تُحسب مرة واحدة على الأكثر ثم يُعاد استخدامها، فإن الزمن اللازم لهذه القيمة من \(d\) هو \(O(|S_d|)\)، والذاكرة كذلك \(O(|S_d|)\).
وبالتالي فإن البرنامج كله يستهلك
$$O\left(\sum_{d=1}^{7}|S_d|\right)$$
زمنًا و
$$O\left(\max_{1\le d\le 7}|S_d|\right)$$
ذاكرة إضافية، مع كلفة مهملة للجمع النهائي باستخدام أعداد صحيحة كبيرة. والأهم من ذلك أن الإشباع عند \(L\) والفرع المغلق الخاص بالبحث الثنائي العادي يقلّصان عدد الحالات الفعلية كثيراً مقارنة بشجرة العودية الخام.