Let \(q=2^{60}\) and \(M=q-1\). The problem builds a masked integer sequence \(u_k\) from a binary recurrence and then asks for a game value \(A(n)\) obtained from a truncated binary descendant tree.
For a fixed \(n\), the terminal indices are the integers in \([n,2n-1]\). Each terminal index \(k\) contributes the masked sequence value \(u_k\), and the tree is folded upward by alternating \(\max\) and \(\min\) from the bottom layer toward the root.
A direct recursive expansion is infeasible for \(n=10^{12}\). The implementation therefore computes sequence states from the bits of the index, evaluates only a small collection of dyadic blocks, uses complement symmetry on the right side of the terminal band, and applies alpha-beta pruning inside each subtree.
The key observation is that the sequence generation and the minimax-style tree evaluation can both be written in a form that depends only on binary structure. That makes it possible to skip almost all of the implicit tree.
Write \(u_0=0\) and \(u_1=1\), and package the current value together with the value at the parent index:
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
Then the two possible binary extensions of \(k\) are
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
So the first coordinate gives
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
Because each new bit of the binary expansion of \(k\) selects one of these two matrices, \(u_k\) can be computed by scanning the bits of \(k\) from most significant to least significant. That costs \(O(\log k)\) time instead of filling every previous term.
For any index \(k\) and any nonnegative height \(d\), define the complete binary subtree value
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ odd},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ even}. \end{cases}$$
This matches the bottom-up pattern used by the implementation: the first layer above leaves takes a maximum, the next layer takes a minimum, and the alternation continues upward.
For a given \(n\), the real terminal band is \([n,2n-1]\), which is usually not a complete power-of-two layer. The algorithm therefore embeds the irregular tree into one complete layer and evaluates only the pieces that matter.
Let
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
Then
$$B\le 2n-1\lt 2B,$$
so the complete leaf layer at depth \(h\) is the interval \([B,2B-1]\), and the terminal cutoff \(2n\) splits that layer only once.
Every maximal dyadic block in \([B,2B)\) is therefore of one of two types:
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{or}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
If a block lies entirely on the left, it corresponds to an ordinary complete subtree. Its value is simply
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right).$$
Since a single boundary is being decomposed, the number of blocks is only \(O(h)=O(\log n)\).
A block lying entirely in \([2n,2B)\) sits one level below a subtree that has already terminated in the original problem. The extra level added by the complete-tree embedding is artificial, and both children of that artificial level carry the same complemented value.
With \(M=q-1\), the right-side block value becomes
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1).$$
In other words, a right block of height \(d\) can be evaluated as the complement of a genuine subtree of height \(d-1\). This is the symmetry that removes one whole layer from every block lying completely to the right of \(2n\).
The formal definition of \(F(k,d)\) is still exponential in \(d\) if expanded blindly. The implementation therefore uses alpha-beta bounds while recursing through the two children.
At a maximizing node it explores the larger immediate child first; at a minimizing node it explores the smaller immediate child first. That improves the chance that the second branch is provably irrelevant and can be pruned.
This does not change the mathematics, but it changes the practical running time dramatically for the depths that appear in the real input.
After every maximal dyadic block has a value, the missing parents are rebuilt upward with the same alternation rule:
$$R(s,0)=\text{value of the block starting at }s,$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ odd},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ even}. \end{cases}$$
Let \(Z=R(0,h)\). The complete-tree embedding and the original problem differ by one final parity flip, so the answer is
$$A(n)= \begin{cases} Z, & h\text{ even},\\[4pt] M-Z, & h\text{ odd}. \end{cases}$$
Here
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
So the leaf layer \([16,32)\) splits into the maximal dyadic blocks
$$[16,20),\qquad [20,24),\qquad [24,32).$$
The first few sequence values needed here are
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
The left block is an ordinary height-2 subtree rooted at \(4\):
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
The middle block is on the right, so one layer collapses:
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
The last block is also on the right:
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
Now combine the three block values upward:
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
Because \(h=4\) is even, no final flip is needed, and therefore
$$A(10)=M-33,$$
which matches the checkpoint used by the implementation.
The C++ implementation contains the core algorithm. It computes the masked sequence state directly from the binary digits of an index, so obtaining \(u_k\) needs only logarithmic work. The Python and Java implementations delegate to the same compiled logic, so all three languages follow the same mathematics.
Each dyadic block is evaluated independently. Left blocks call the ordinary alternating subtree evaluator \(F(k,d)\); right blocks use the complemented form \(G(k,d)\). Inside each subtree the recursion is guarded by alpha-beta bounds, and the child order is chosen to improve pruning.
Once the block values are known, the implementation stores them by segment position and height, reconstructs any missing parents with alternating \(\max\) and \(\min\), and finally applies the parity correction determined by \(h\). The C++ version also evaluates the independent blocks in parallel, which helps on the largest input.
Computing one sequence value \(u_k\) costs \(O(\log k)\) arithmetic operations because the index is processed bit by bit. The dyadic split of the leaf layer creates only \(O(\log n)\) maximal blocks, and recombining those blocks is also \(O(\log n)\).
The hard part is the subtree evaluation. In the worst case a raw minimax tree of height \(d\) would need \(O(2^d)\) leaf visits, but the implementation avoids most of that cost through two structural reductions: every right-side block loses one full level by complement symmetry, and alpha-beta pruning cuts many recursive branches inside the remaining subtrees. That combination is what makes the target value feasible.
Sei \(q=2^{60}\) und \(M=q-1\). Das Problem erzeugt zunächst eine maskierte Folge \(u_k\) aus einer binären Rekurrenz und verlangt danach einen Spielwert \(A(n)\), der aus einem abgeschnittenen binären Nachfahrenbaum entsteht.
Für festes \(n\) sind die terminalen Indizes genau die Zahlen aus \([n,2n-1]\). Jeder solche Index \(k\) trägt den maskierten Folgenwert \(u_k\), und beim Aufsteigen zum Wurzelknoten wechseln sich von unten nach oben \(\max\) und \(\min\) ab.
Eine direkte vollständige Rekursion ist für \(n=10^{12}\) unbrauchbar. Die Implementierung berechnet deshalb Zustände direkt aus den Bits des Index, wertet nur wenige dyadische Blöcke aus, nutzt rechts vom Rand \(2n\) eine Komplementsymmetrie und beschleunigt jede Teilbaumauswertung mit Alpha-Beta-Pruning.
Der entscheidende Punkt ist, dass sowohl die Folgengenerierung als auch die Minimax-artige Baumauswertung rein von der Binärstruktur abhängen. Dadurch muss nur ein sehr kleiner Teil des impliziten Baums tatsächlich betrachtet werden.
Setze \(u_0=0\) und \(u_1=1\), und fasse den aktuellen Wert zusammen mit dem Wert am Elternindex zu einem Zustand zusammen:
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
Dann gelten für die beiden binären Erweiterungen von \(k\)
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
Für die erste Koordinate folgt also
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
Jedes neue Bit der Binärdarstellung von \(k\) wählt genau eine dieser beiden Matrizen. Daher lässt sich \(u_k\) durch einen Scan über die Bits von oben nach unten in \(O(\log k)\) Zeit berechnen, statt alle vorherigen Folgenglieder zu erzeugen.
Für jeden Index \(k\) und jede nichtnegative Höhe \(d\) definieren wir den Wert eines vollständigen binären Teilbaums durch
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ ungerade},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ gerade}. \end{cases}$$
Das ist genau das in der Implementierung verwendete Muster: Die erste Ebene über den Blättern nimmt ein Maximum, die nächste ein Minimum und dann geht die Alternation so weiter.
Für ein gegebenes \(n\) liegt das echte terminale Band in \([n,2n-1]\). Dieses Band ist im Allgemeinen keine vollständige Potenz-von-zwei-Ebene, deshalb bettet der Algorithmus den unregelmäßigen Baum in eine einzige vollständige Ebene ein.
Definiere
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
Dann gilt
$$B\le 2n-1\lt 2B,$$
also ist die vollständige Blattebene der Tiefe \(h\) gerade das Intervall \([B,2B-1]\), und der terminale Schnittpunkt \(2n\) teilt diese Ebene nur ein einziges Mal.
Jeder maximale dyadische Block in \([B,2B)\) ist deshalb von genau einem der beiden Typen
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{oder}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
Liegt ein Block vollständig links, so entspricht er einem gewöhnlichen vollständigen Teilbaum. Sein Wert ist einfach
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right).$$
Da nur ein einzelner Rand zerlegt wird, gibt es insgesamt nur \(O(h)=O(\log n)\) solcher Blöcke.
Ein Block, der vollständig in \([2n,2B)\) liegt, befindet sich eine Ebene unterhalb eines Teilbaums, der im ursprünglichen Problem bereits terminal war. Die zusätzliche Ebene stammt nur aus der Einbettung in den vollständigen Baum, und beide Kinder dieser künstlichen Ebene tragen denselben komplementierten Wert.
Mit \(M=q-1\) ergibt sich für einen rechten Block
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1).$$
Ein rechter Block der Höhe \(d\) ist also gerade das Komplement eines echten Teilbaums der Höhe \(d-1\). Genau diese Symmetrie entfernt auf der rechten Seite eine ganze Ebene aus jeder Auswertung.
Die Definition von \(F(k,d)\) wäre bei naiver Auswertung weiterhin exponentiell in \(d\). Deshalb verwendet die Implementierung beim rekursiven Abstieg Alpha-Beta-Schranken.
Bei einem maximierenden Knoten wird zuerst das größere unmittelbare Kind besucht, bei einem minimierenden Knoten zuerst das kleinere. Dadurch steigt die Wahrscheinlichkeit, dass der zweite Ast schon vorab als irrelevant erkannt und abgeschnitten werden kann.
Die mathematische Definition bleibt dadurch unverändert, aber die tatsächliche Laufzeit sinkt für die realen Eingaben erheblich.
Sobald jeder maximale dyadische Block einen Wert hat, werden die fehlenden Eltern mit derselben Alternationsregel nach oben rekonstruiert:
$$R(s,0)=\text{Wert des bei }s\text{ beginnenden Blocks},$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ ungerade},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ gerade}. \end{cases}$$
Sei \(Z=R(0,h)\). Zwischen dem vollständig eingebetteten Baum und dem ursprünglichen Problem bleibt genau ein abschließender Paritätswechsel übrig, also
$$A(n)= \begin{cases} Z, & h\text{ gerade},\\[4pt] M-Z, & h\text{ ungerade}. \end{cases}$$
Hier ist
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
Damit zerfällt die Blattebene \([16,32)\) in die maximalen dyadischen Blöcke
$$[16,20),\qquad [20,24),\qquad [24,32).$$
Die hier benötigten Folgenwerte sind
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
Der linke Block ist ein gewöhnlicher Teilbaum der Höhe \(2\) mit Wurzel \(4\):
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
Der mittlere Block liegt rechts, also fällt eine Ebene weg:
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
Der letzte Block liegt ebenfalls rechts:
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
Beim Zusammensetzen nach oben erhält man
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
Da \(h=4\) gerade ist, braucht man keinen letzten Flip, also
$$A(10)=M-33,$$
genau der Kontrollwert aus der Implementierung.
Die eigentliche numerische Arbeit steckt in der C++-Implementierung. Sie berechnet den maskierten Folgenzustand direkt aus den Binärbits eines Index, sodass ein einzelner Wert \(u_k\) nur logarithmische Arbeit kostet. Die Python- und Java-Implementierungen delegieren an dieselbe kompilierte Logik, daher beruht alles auf derselben Mathematik.
Jeder dyadische Block wird unabhängig ausgewertet. Linke Blöcke verwenden den gewöhnlichen alternierenden Teilbaumwert \(F(k,d)\), rechte Blöcke die komplementierte Form \(G(k,d)\). Innerhalb jedes Teilbaums wird die Rekursion durch Alpha-Beta-Schranken begrenzt, und die Reihenfolge der Kinder ist so gewählt, dass möglichst viel abgeschnitten werden kann.
Sobald alle Blockwerte vorliegen, speichert die Implementierung sie nach Segmentposition und Höhe, rekonstruiert die fehlenden Eltern wieder mit abwechselndem \(\max\) und \(\min\) und wendet am Ende noch die von \(h\) bestimmte Paritätskorrektur an. Die C++-Version wertet die unabhängigen Blöcke zusätzlich parallel aus, was beim größten Eingabewert hilft.
Die Berechnung eines einzelnen Folgenwerts \(u_k\) benötigt \(O(\log k)\) arithmetische Operationen, weil der Index bitweise verarbeitet wird. Die dyadische Zerlegung der Blattebene erzeugt nur \(O(\log n)\) maximale Blöcke, und auch ihr anschließendes Zusammensetzen kostet nur \(O(\log n)\).
Der teure Teil ist die Teilbaumauswertung. Im schlimmsten Fall würde ein roher Minimax-Baum der Höhe \(d\) \(O(2^d)\) Blattbesuche erfordern. Die Implementierung vermeidet jedoch den Großteil davon durch zwei strukturelle Effekte: Jeder rechte Block verliert wegen der Komplementsymmetrie eine ganze Ebene, und Alpha-Beta-Pruning schneidet viele rekursive Äste im verbleibenden Baum ab. Erst diese Kombination macht die Zielrechnung praktikabel.
\(q=2^{60}\) ve \(M=q-1\) olsun. Problem önce ikili bir reküranstan maske altında tanımlanan \(u_k\) dizisini üretir, sonra da kesilmiş bir ikili torun ağacından gelen \(A(n)\) oyun değerini ister.
Sabit bir \(n\) için terminal indisler \([n,2n-1]\) aralığındaki tam sayılardır. Her terminal \(k\) için katkı \(u_k\) olur; yapraklardan köke çıkarken seviyeler sırayla \(\max\) ve \(\min\) uygular.
\(n=10^{12}\) için tüm ağacı doğrudan açmak mümkün değildir. Bu yüzden uygulama indis bitlerinden durum üretir, sadece az sayıda dyadic blok değerlendirir, \(2n\)'nin sağındaki bloklarda tümleyici simetri kullanır ve her alt ağaçta alpha-beta budaması yapar.
Esas nokta şudur: hem dizi üretimi hem de minimax benzeri ağaç değerlendirmesi tamamen ikili yapıya göre yazılabilir. Böylece örtük ağacın neredeyse tamamı atlanır.
\(u_0=0\) ve \(u_1=1\) alalım; güncel değeri ebeveyn indisindeki değerle birlikte şu durumda toplayalım:
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
O zaman \(k\)'nin iki olası ikili uzantısı için
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
İlk bileşenler ise
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
\(k\)'nin ikili gösterimindeki her yeni bit bu iki matristen birini seçtiği için \(u_k\), bitler en anlamlı bitten en az anlamlı bite doğru taranarak \(O(\log k)\) zamanda bulunabilir. Yani önceki tüm terimleri üretmeye gerek kalmaz.
Her \(k\) indisi ve her sıfırdan büyük veya eşit \(d\) yüksekliği için tam ikili alt ağaç değerini
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ tek},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ çift}. \end{cases}$$
Bu, uygulamanın alttan üste kullandığı örüntünün aynısıdır: yaprakların hemen üstündeki seviye maksimum alır, bir üstü minimum alır ve bu şekilde sürer.
Verilen bir \(n\) için gerçek terminal bant \([n,2n-1]\) olur. Bu bant çoğu zaman tam bir iki kuvveti katmanı değildir; bu yüzden algoritma düzensiz ağacı tek bir tam katmana gömüp sadece gerekli parçaları hesaplar.
Şöyle tanımlayalım:
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
Böylece
$$B\le 2n-1\lt 2B,$$
olur; yani derinliği \(h\) olan tam yaprak katmanı \([B,2B-1]\) aralığıdır ve terminal sınır \(2n\) bu katmanı yalnızca bir kez keser.
Bu yüzden \([B,2B)\) içindeki her maksimal dyadic blok iki tipten biridir:
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{veya}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
Bir blok bütünüyle soldaysa sıradan bir tam alt ağaçtır ve değeri doğrudan
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right)$$
şeklindedir. Tek bir sınır ayrıştırıldığı için toplam blok sayısı sadece \(O(h)=O(\log n)\) olur.
Bütünüyle \([2n,2B)\) içinde kalan bir blok, özgün problemde zaten terminal olmuş bir alt ağacın bir seviye altında durur. Tam ağaca gömme sırasında eklenen bu fazladan seviye yapaydır ve o seviyedeki iki çocuk aynı tümleyici değeri taşır.
\(M=q-1\) ile sağ blok değeri
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1)$$
olur. Yani yüksekliği \(d\) olan bir sağ blok, yüksekliği \(d-1\) olan gerçek bir alt ağacın tümleyenidir. Sağ taraftaki her bloktan bir seviyeyi düşüren simetri tam olarak budur.
\(F(k,d)\)'nin tanımı doğrudan açılırsa yine \(d\)'ye göre üstel olur. Bu nedenle uygulama, iki çocuğa inerken alpha-beta sınırları kullanır.
Maksimizasyon düğümünde önce büyük olan çocuk, minimizasyon düğümünde önce küçük olan çocuk değerlendirilir. Böylece ikinci dalın artık sonucu değiştiremeyeceği daha erken anlaşılır ve budama artar.
Bu teknik matematiği değiştirmez; fakat gerçek girdi için pratik çalışma süresini ciddi biçimde azaltır.
Her maksimal dyadic blok için değer bulunduktan sonra eksik ebeveynler aynı sırayla yukarı doğru yeniden kurulur:
$$R(s,0)=s\text{ konumunda başlayan bloğun değeri},$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ tek},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ çift}. \end{cases}$$
\(Z=R(0,h)\) olsun. Tam ağaç gömmesi ile özgün problem arasında son bir parite farkı kaldığı için cevap
$$A(n)= \begin{cases} Z, & h\text{ çift},\\[4pt] M-Z, & h\text{ tek} \end{cases}$$
şeklinde elde edilir.
Burada
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
Dolayısıyla \([16,32)\) yaprak katmanı şu maksimal dyadic bloklara ayrılır:
$$[16,20),\qquad [20,24),\qquad [24,32).$$
Gereken dizi değerleri şunlardır:
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
Sol blok, kökü \(4\) olan yükseklik \(2\)'lik sıradan bir alt ağaçtır:
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
Ortadaki blok sağdadır; bu yüzden bir katman çöker:
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
Son blok da sağdadır:
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
Şimdi yukarı doğru birleştirirsek
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
\(h=4\) çift olduğundan son bir çevrim gerekmez; dolayısıyla
$$A(10)=M-33,$$
ve bu da uygulamanın kullandığı doğrulama değeriyle aynıdır.
Asıl algoritma C++ uygulamasındadır. Bir indisin ikili bitlerinden doğrudan maskeli dizi durumu üretildiği için \(u_k\) değerini bulmak yalnızca logaritmik maliyet taşır. Python ve Java uygulamaları da aynı derlenmiş mantığa delege eder; dolayısıyla üç dildeki hesap aynı matematiğe dayanır.
Her dyadic blok bağımsız değerlendirilir. Sol bloklar sıradan alternanslı alt ağaç değeri \(F(k,d)\) ile, sağ bloklar ise tümleyici biçim \(G(k,d)\) ile hesaplanır. Her alt ağaç içinde özyineleme alpha-beta sınırlarıyla korunur ve çocuk sırası budamayı artıracak şekilde seçilir.
Blok değerleri bulunduktan sonra uygulama bunları segment başlangıcı ve yükseklik bilgisiyle saklar, eksik ebeveynleri \(\max\) ve \(\min\) dönüşümüyle yukarı doğru kurar ve en sonda \(h\)'nin paritesine göre son düzeltmeyi yapar. C++ sürümü bağımsız blokları paralel de değerlendirdiği için en büyük girdi daha rahat hesaplanır.
Tek bir \(u_k\) değeri, indis bit bit işlendiği için \(O(\log k)\) aritmetik işlemde bulunur. Yaprak katmanının dyadic ayrıştırması yalnızca \(O(\log n)\) maksimal blok üretir; bu blokların yeniden birleştirilmesi de \(O(\log n)\) sürer.
Zor kısım alt ağaç değerlendirmesidir. Ham minimax yaklaşımı, yükseklik \(d\) için en kötü durumda \(O(2^d)\) yaprak ziyareti ister. Fakat uygulama bunun çoğunu iki yapısal kısaltma sayesinde önler: sağ bloklar tümleyici simetri nedeniyle bir tam seviye kaybeder ve alpha-beta budaması kalan alt ağaçlarda çok sayıda özyinelemeli dalı keser. Hedef hesabı uygulanabilir yapan şey bu birleşimdir.
Sea \(q=2^{60}\) y \(M=q-1\). El problema primero construye una sucesión enmascarada \(u_k\) mediante una recurrencia binaria y luego pide un valor de juego \(A(n)\) obtenido a partir de un árbol binario truncado de descendientes.
Para un \(n\) fijo, los índices terminales son exactamente los enteros de \([n,2n-1]\). Cada índice terminal \(k\) aporta el valor \(u_k\), y al subir desde las hojas hacia la raíz se alternan operaciones \(\max\) y \(\min\).
Expandir todo el árbol es inviable para \(n=10^{12}\). Por eso la implementación calcula estados directamente desde los bits del índice, evalúa solo unos pocos bloques diádicos, usa una simetría por complemento a la derecha de \(2n\) y aplica poda alfa-beta dentro de cada subárbol.
La idea central es que tanto la generación de la sucesión como la evaluación tipo minimax del árbol dependen solo de la estructura binaria. Eso permite saltarse casi todo el árbol implícito.
Tomamos \(u_0=0\) y \(u_1=1\), y agrupamos el valor actual junto con el valor del índice padre:
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
Entonces las dos extensiones binarias posibles de \(k\) son
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
La primera coordenada satisface
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
Cada nuevo bit de la expansión binaria de \(k\) elige una de esas dos matrices. Por eso \(u_k\) puede calcularse recorriendo los bits de \(k\) desde el más significativo al menos significativo, en \(O(\log k)\) tiempo.
Para cualquier índice \(k\) y cualquier altura no negativa \(d\), definimos el valor del subárbol binario completo por
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ impar},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ par}. \end{cases}$$
Esto coincide con el patrón usado por la implementación: la primera capa sobre las hojas toma un máximo, la siguiente toma un mínimo y luego la alternancia continúa.
Para un \(n\) dado, la banda terminal real es \([n,2n-1]\), que normalmente no forma una capa completa de potencia de dos. El algoritmo, por tanto, incrusta el árbol irregular en una única capa completa y solo evalúa las piezas necesarias.
Definimos
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
Entonces
$$B\le 2n-1\lt 2B,$$
de modo que la capa completa de hojas a profundidad \(h\) es \([B,2B-1]\), y el corte terminal \(2n\) parte esa capa una sola vez.
Cada bloque diádico maximal de \([B,2B)\) es por tanto de uno de estos dos tipos:
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{o}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
Si el bloque queda totalmente a la izquierda, corresponde a un subárbol completo ordinario y su valor es
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right).$$
Como solo se descompone una frontera, el número total de bloques es \(O(h)=O(\log n)\).
Un bloque contenido por completo en \([2n,2B)\) queda una capa por debajo de un subárbol que ya era terminal en el problema original. Esa capa extra solo aparece por la incrustación en el árbol completo, y sus dos hijos llevan el mismo valor complementado.
Con \(M=q-1\), el valor de un bloque derecho es
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1).$$
Es decir, un bloque derecho de altura \(d\) se evalúa como el complemento de un subárbol genuino de altura \(d-1\). Esa simetría elimina una capa completa en todos los bloques situados totalmente a la derecha de \(2n\).
La definición formal de \(F(k,d)\) sigue siendo exponencial en \(d\) si se expande sin control. Por eso la implementación usa cotas alfa-beta durante la recursión sobre los dos hijos.
En un nodo maximizador visita antes el hijo inmediato mayor; en un nodo minimizador visita antes el hijo inmediato menor. Eso aumenta la probabilidad de demostrar pronto que la segunda rama no puede cambiar el resultado.
La matemática no cambia, pero el tiempo práctico sí mejora mucho para las profundidades que aparecen en la entrada real.
Una vez que cada bloque diádico maximal tiene valor, los padres que faltan se reconstruyen hacia arriba con la misma regla alternante:
$$R(s,0)=\text{valor del bloque que empieza en }s,$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ impar},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ par}. \end{cases}$$
Sea \(Z=R(0,h)\). Entre el árbol completo incrustado y el problema original queda un último ajuste de paridad, así que
$$A(n)= \begin{cases} Z, & h\text{ par},\\[4pt] M-Z, & h\text{ impar}. \end{cases}$$
Aquí
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
Por lo tanto la capa de hojas \([16,32)\) se divide en los bloques diádicos maximales
$$[16,20),\qquad [20,24),\qquad [24,32).$$
Los valores de la sucesión que hacen falta son
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
El bloque izquierdo es un subárbol ordinario de altura \(2\) con raíz \(4\):
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
El bloque central queda a la derecha, así que una capa colapsa:
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
El último bloque también está a la derecha:
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
Al combinar hacia arriba obtenemos
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
Como \(h=4\) es par, no hace falta un último giro, y por tanto
$$A(10)=M-33,$$
que coincide con el valor de comprobación usado por la implementación.
La implementación en C++ contiene el algoritmo numérico principal. Calcula el estado de la sucesión enmascarada directamente a partir de los bits del índice, así que obtener \(u_k\) requiere solo trabajo logarítmico. Las implementaciones en Python y Java delegan en esa misma lógica compilada, de modo que las tres versiones siguen exactamente la misma matemática.
Cada bloque diádico se evalúa de manera independiente. Los bloques izquierdos usan el evaluador alternante \(F(k,d)\); los bloques derechos usan la forma complementada \(G(k,d)\). Dentro de cada subárbol la recursión está protegida por cotas alfa-beta y el orden de visita de los hijos se elige para favorecer la poda.
Cuando los valores de los bloques ya están disponibles, la implementación los guarda por posición y altura del segmento, reconstruye los padres que faltan con \(\max\) y \(\min\) alternados y al final aplica la corrección de paridad determinada por \(h\). La versión en C++ además evalúa en paralelo los bloques independientes, lo que ayuda en la entrada más grande.
Calcular un valor individual \(u_k\) cuesta \(O(\log k)\) operaciones aritméticas porque el índice se procesa bit a bit. La partición diádica de la capa de hojas genera solo \(O(\log n)\) bloques maximales, y recomponerlos también cuesta \(O(\log n)\).
La parte costosa es la evaluación de subárboles. En el peor caso, un árbol minimax bruto de altura \(d\) requeriría \(O(2^d)\) visitas a hojas. Sin embargo, la implementación evita gran parte de ese coste gracias a dos reducciones estructurales: cada bloque derecho pierde una capa completa por la simetría de complemento y la poda alfa-beta corta muchas ramas recursivas en los subárboles restantes. Esa combinación es la que vuelve viable el cálculo buscado.
记 \(q=2^{60}\)，并设 \(M=q-1\)。这道题先用一个依赖二进制结构的递推关系生成带掩码的整数序列 \(u_k\)，再要求一个由截断二叉后代树得到的博弈值 \(A(n)\)。
对于固定的 \(n\)，终止索引正好是区间 \([n,2n-1]\) 中的所有整数。每个终止索引 \(k\) 的叶子值都是对应的 \(u_k\)，然后从底层往上依次交替执行 \(\max\)、\(\min\)、\(\max\)、\(\min\)。
如果把整棵隐式树完全展开，那么对 \(n=10^{12}\) 这样的输入根本不可行。实现真正依赖的是四个结构性简化：按索引的二进制位直接生成状态，只计算极少数必要的 dyadic 块，对 \(2n\) 右侧的整块使用补值对称性，并在每个子树内部配合 alpha-beta 剪枝。
核心思想是：序列生成和 minimax 风格的树求值都可以完全写成“按二进制结构递推”的形式。一旦做到这一点，就不再需要显式遍历绝大多数节点。
取初值 \(u_0=0\)、\(u_1=1\)，并把当前项与父索引对应的项一起打包成
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
这样，索引 \(k\) 向二进制后代扩展时只有两种情况：
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
因此第一坐标满足
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
这说明：只要从最高位到最低位扫描 \(k\) 的二进制表示，每读到一个新比特，就在这两个矩阵里选一个乘上去。于是 \(u_k\) 的计算代价是 \(O(\log k)\)，而不是先把前面所有项都算出来。
对任意索引 \(k\) 与任意非负高度 \(d\)，定义一个完整二叉子树的值
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ 为奇数},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ 为偶数}. \end{cases}$$
这正好对应实现里的自底向上规则：离叶子最近的一层取最大值，再上一层取最小值，然后继续交替。
但对给定的 \(n\)，真正的终止带是 \([n,2n-1]\)，它通常不是完整的 \(2\) 的幂层。算法的做法不是硬算这棵不规则树，而是先把它嵌入到某一层完整的二叉层里，再只处理那层上真正有贡献的块。
令
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
于是有
$$B\le 2n-1\lt 2B,$$
所以深度 \(h\) 的完整叶层就是区间 \([B,2B-1]\)，而终止边界 \(2n\) 只会把这层切开一次。
因此，\([B,2B)\) 中的每个极大 dyadic 块都只可能是下面两种之一：
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{或}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
如果一个块完全落在左边，它对应的就是一个普通的完整子树，其值直接等于
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right).$$
因为这里只是在一条边界上做分裂，所以极大块的总数只有 \(O(h)=O(\log n)\)。这一步把“巨大叶层”压缩成了“很少几个整块”。
如果一个块完全位于 \([2n,2B)\)，它在原问题里其实已经处在“真实终止子树”的下一层。换句话说，这一层是为了凑成完整二叉层才额外加出来的人工层。
在这层人工结构里，两个孩子携带的是同一个补值，所以可以把整块直接写成更浅一层真实子树的补值。记 \(M=q-1\)，则
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1).$$
这条关系非常重要。它表示：右侧一个高度为 \(d\) 的块，不必真的去算高度 \(d\) 的完整树，而只要算一个高度 \(d-1\) 的普通子树，然后再做一次 \(M-\cdot\) 的变换即可。也正因为如此，所有完全落在右侧的块都会少一整层搜索深度。
即使有了上面的结构，若把 \(F(k,d)\) 直接暴力展开，仍然会随着 \(d\) 指数增长。所以实现对子树递归时加入了 alpha-beta 上下界。
在取最大值的节点，先搜索两个直接孩子里较大的那个；在取最小值的节点，先搜索较小的那个。这样更容易提前证明第二个分支不可能改变答案，于是可以直接剪掉。
从数学定义上看，\(F(k,d)\) 没有任何变化；变化的只是搜索顺序和实际访问的节点数。对真实输入来说，这个差别非常大。
当每个极大 dyadic 块都已经有了自己的值以后，剩余缺失的父节点就可以用同样的交替规则向上恢复：
$$R(s,0)=\text{从位置 }s\text{ 开始的块值},$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ 为奇数},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ 为偶数}. \end{cases}$$
设 \(Z=R(0,h)\)。由于“完整层嵌入”与“原始问题定义”之间还差最后一个由奇偶性决定的翻转，所以最终答案是
$$A(n)= \begin{cases} Z, & h\text{ 为偶数},\\[4pt] M-Z, & h\text{ 为奇数}. \end{cases}$$
先算出
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
因此完整叶层 \([16,32)\) 被切成三个极大 dyadic 块：
$$[16,20),\qquad [20,24),\qquad [24,32).$$
这里需要的序列值为
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
左侧块是一个普通的高度 \(2\) 子树，根索引为 \(4\)：
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
中间块完全在右边，所以可以少算一层：
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
最后一个块也在右边：
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
接下来把三个块向上合并：
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
因为 \(h=4\) 是偶数，不需要最后一次翻转，所以
$$A(10)=M-33,$$
这和实现里使用的校验点完全一致。
C++ 实现包含了核心数值算法。它直接根据索引的二进制位生成带掩码的状态，因此求单个 \(u_k\) 只需要对数级工作量。Python 和 Java 版本都委托给同一套编译后的核心逻辑，所以三种语言在数学上完全一致。
每个 dyadic 块都可以独立求值。左侧块调用普通的交替子树求值 \(F(k,d)\)，右侧块调用补值形式 \(G(k,d)\)。在每个子树内部，递归搜索都带有 alpha-beta 边界，并且会优先访问更有利于剪枝的那个孩子。
等所有块值都算好以后，实现会按“区间起点 + 高度”的方式保存这些值，再把缺失的父节点用交替的 \(\max\) 与 \(\min\) 逐层补回去，最后依据 \(h\) 的奇偶性做一次终结性的修正。C++ 版本还会把彼此独立的块并行求值，这对最大输入尤其重要。
单次计算 \(u_k\) 的代价是 \(O(\log k)\)，因为索引只需要按位扫描。叶层的 dyadic 分裂只会产生 \(O(\log n)\) 个极大块，而把这些块重新合并回根节点也只需要 \(O(\log n)\) 的额外工作。
真正昂贵的是子树求值。如果完全不做剪枝，高度为 \(d\) 的 minimax 树在最坏情况下会访问 \(O(2^d)\) 个叶子。实现之所以可行，靠的是两层削减：所有右侧块都因补值对称性而少一整层，剩余部分又能被 alpha-beta 剪枝大量截断。正是这两点共同把目标输入压到了可计算范围内。
Положим \(q=2^{60}\) и \(M=q-1\). Сначала задача строит маскированную последовательность \(u_k\) по двоичной рекуррентной схеме, а затем требует вычислить игровой корневой результат \(A(n)\), получаемый из усеченного двоичного дерева потомков.
Для фиксированного \(n\) терминальными являются все индексы из интервала \([n,2n-1]\). Каждому терминальному индексу \(k\) соответствует лист со значением \(u_k\), а при подъеме от листьев к корню операции \(\max\) и \(\min\) чередуются.
Полное раскрытие такого дерева невозможно для \(n=10^{12}\). Поэтому реализация вычисляет состояние прямо по битам индекса, рассматривает лишь небольшое число двоичных блоков, использует комплементарную симметрию справа от границы \(2n\) и применяет alpha-beta-отсечение внутри каждого поддерева.
Главная идея состоит в том, что и генерация последовательности, и minimax-подобная оценка дерева полностью определяются двоичной структурой. Благодаря этому почти весь неявный деревообразный перебор удается выбросить.
Пусть \(u_0=0\) и \(u_1=1\). Объединим текущий элемент и значение на родительском индексе в вектор состояния
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
Тогда для двух возможных двоичных продолжений индекса \(k\) имеем
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
Следовательно, первая координата удовлетворяет формулам
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
Каждый следующий бит двоичной записи \(k\) выбирает одну из двух матриц. Значит, \(u_k\) можно получить, просто проходя по битам индекса от старшего к младшему, то есть за \(O(\log k)\), без предварительного вычисления всех предыдущих членов.
Для любого индекса \(k\) и любой неотрицательной высоты \(d\) определим значение полного двоичного поддерева так:
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ нечетно},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ четно}. \end{cases}$$
Это ровно тот порядок, который использует реализация: слой непосредственно над листьями берет максимум, следующий слой берет минимум, затем снова максимум и так далее.
Для фиксированного \(n\) реальная терминальная полоса равна \([n,2n-1]\). Обычно это не полная степень двойки, поэтому алгоритм сначала встраивает неравномерное дерево в один полный слой фиксированной глубины, а затем вычисляет только нужные части.
Положим
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
Тогда
$$B\le 2n-1\lt 2B,$$
то есть полный листовой слой глубины \(h\) равен интервалу \([B,2B-1]\), а граница \(2n\) пересекает его только один раз.
Отсюда любой максимальный двоичный блок в \([B,2B)\) имеет один из двух видов:
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{или}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
Если блок целиком лежит слева, то это обычное полное поддерево, и его значение равно
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right).$$
Так как разрезается лишь одна граница, общее число блоков равно всего лишь \(O(h)=O(\log n)\).
Блок, полностью лежащий в \([2n,2B)\), находится на один уровень ниже поддерева, которое в исходной задаче уже было терминальным. Этот лишний уровень возникает только из-за встраивания в полный слой, и оба ребенка на нем несут одно и то же комплементарное значение.
Если \(M=q-1\), то для правого блока получается
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1).$$
То есть правый блок высоты \(d\) вычисляется как дополнение до \(M\) от настоящего поддерева высоты \(d-1\). Именно эта симметрия снимает один целый уровень со всех блоков, лежащих полностью справа от \(2n\).
Даже после описанных преобразований определение \(F(k,d)\) при наивном раскрытии оставалось бы экспоненциальным по \(d\). Поэтому реализация рекурсивно спускается по детям с alpha-beta-границами.
В максимизирующем узле сначала рассматривается больший непосредственный ребенок, а в минимизирующем узле - меньший. Это повышает шанс быстро понять, что вторая ветвь уже не может изменить итог, и ее можно отсечь.
С математической точки зрения значение не меняется, но практически число реально посещаемых узлов уменьшается очень сильно.
Когда каждому максимальному двоичному блоку уже присвоено значение, отсутствующие родительские узлы восстанавливаются вверх по той же чередующейся схеме:
$$R(s,0)=\text{значение блока, начинающегося в }s,$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ нечетно},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ четно}. \end{cases}$$
Пусть \(Z=R(0,h)\). Между встроенным полным деревом и исходной постановкой остается один финальный переворот по четности, поэтому
$$A(n)= \begin{cases} Z, & h\text{ четно},\\[4pt] M-Z, & h\text{ нечетно}. \end{cases}$$
В этом случае
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
Следовательно, листовой слой \([16,32)\) распадается на три максимальных двоичных блока:
$$[16,20),\qquad [20,24),\qquad [24,32).$$
Нужные здесь значения последовательности таковы:
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
Левый блок - это обычное поддерево высоты \(2\) с корнем \(4\):
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
Средний блок лежит справа, поэтому один уровень схлопывается:
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
Последний блок тоже находится справа:
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
Далее поднимаемся вверх:
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
Так как \(h=4\) четно, дополнительного переворота нет, и поэтому
$$A(10)=M-33,$$
что совпадает с контрольным значением, используемым реализацией.
Основной численный алгоритм находится в C++-реализации. Она строит маскированное состояние последовательности прямо по двоичным битам индекса, так что получение одного значения \(u_k\) требует лишь логарифмического числа шагов. Реализации на Python и Java делегируют ту же скомпилированную логику, поэтому математическая схема у всех трех языков одна и та же.
Каждый двоичный блок вычисляется независимо. Для левых блоков используется обычный чередующийся оцениватель \(F(k,d)\), для правых - комплементарная форма \(G(k,d)\). Внутри каждого поддерева рекурсия ограничивается alpha-beta-границами, а порядок обхода детей выбирается так, чтобы увеличить отсечение.
После получения значений блоков реализация хранит их по позиции сегмента и высоте, восстанавливает недостающих родителей с чередованием \(\max\) и \(\min\), а затем делает финальную поправку на четность \(h\). Версия на C++ также распараллеливает независимые вычисления блоков, что помогает на самом большом входе.
Вычисление одного значения \(u_k\) требует \(O(\log k)\) арифметических действий, потому что индекс обрабатывается побитово. Двоичное разбиение листового слоя создает лишь \(O(\log n)\) максимальных блоков, и их последующее объединение тоже занимает \(O(\log n)\).
Самая дорогая часть - оценка поддеревьев. В худшем случае необрезанное minimax-дерево высоты \(d\) потребовало бы \(O(2^d)\) посещений листьев. Однако реализация снимает значительную часть этой цены двумя структурными приемами: каждый правый блок теряет один целый уровень из-за комплементарной симметрии, а alpha-beta-отсечение убирает многие рекурсивные ветви в оставшихся поддеревьях. Именно это сочетание и делает задачу вычислимой на нужном размере.
لنكتب \(q=2^{60}\) و\(M=q-1\). تبدأ المسألة ببناء متتالية مقنَّعة \(u_k\) من علاقة عودية ثنائية البنية، ثم تطلب قيمة لعب \(A(n)\) ناتجة عن شجرة نسل ثنائية مقطوعة.
عند تثبيت \(n\)، تكون الفهارس النهائية هي الأعداد الواقعة في المجال \([n,2n-1]\). كل فهرس نهائي \(k\) يزوِّدنا بالقيمة \(u_k\)، ثم نطوي الشجرة من الأسفل إلى الأعلى بالتناوب بين \(\max\) و\(\min\).
التوسيع المباشر للشجرة كلها غير عملي عندما يكون \(n=10^{12}\). لذلك تعتمد الخوارزمية على أربع أفكار بنيوية: توليد الحالة مباشرة من بتات الفهرس، تقييم عدد صغير فقط من الكتل الثنائية dyadic، استعمال تناظر المتمم في الجهة اليمنى من الحد \(2n\)، ثم استخدام تقليم alpha-beta داخل كل شجرة فرعية.
الفكرة الأساسية هي أن توليد المتتالية وتقييم الشجرة بأسلوب minimax يمكن كتابتهما بالكامل بدلالة البنية الثنائية فقط. وعندها لا نحتاج إلى زيارة معظم الشجرة الضمنية إطلاقًا.
نأخذ \(u_0=0\) و\(u_1=1\)، ثم نجمع القيمة الحالية مع قيمة فهرس الأب في متجه حالة:
$$s_k=\begin{pmatrix}u_k\\u_{\lfloor k/2\rfloor}\end{pmatrix}.$$
عندئذ يكون الامتدادان الثنائيان الممكنان للفهرس \(k\) كما يلي:
$$s_{2k}\equiv \begin{pmatrix}3&2\\1&0\end{pmatrix}s_k \pmod{q},\qquad s_{2k+1}\equiv \begin{pmatrix}2&3\\1&0\end{pmatrix}s_k \pmod{q}.$$
ومن ثم تحقق المركبة الأولى
$$u_{2k}\equiv 3u_k+2u_{\lfloor k/2\rfloor}\pmod{q},\qquad u_{2k+1}\equiv 2u_k+3u_{\lfloor k/2\rfloor}\pmod{q}.$$
كل بت جديد في التمثيل الثنائي لـ \(k\) يختار إحدى هاتين المصفوفتين. لذلك يمكن حساب \(u_k\) بالمرور على البتات من الأعلى إلى الأسفل في \(O(\log k)\) زمنًا، بدل توليد جميع الحدود السابقة.
لكل فهرس \(k\) ولكل ارتفاع غير سالب \(d\)، نعرّف قيمة الشجرة الثنائية الكاملة كما يلي:
$$F(k,0)=u_k,$$
$$F(k,d)= \begin{cases} \max\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ odd},\\[4pt] \min\bigl(F(2k,d-1),F(2k+1,d-1)\bigr), & d\text{ even}. \end{cases}$$
وهذا يطابق تمامًا ما تفعله الخوارزمية: المستوى الأقرب إلى الأوراق يأخذ قيمة عظمى، والمستوى الذي فوقه يأخذ قيمة صغرى، ثم يستمر التناوب صعودًا.
لكن الحزمة النهائية الحقيقية عند قيمة \(n\) معطاة بالمجال \([n,2n-1]\)، وهي في العادة ليست طبقة كاملة من حجم قوة للعدد \(2\). لذلك تقوم الطريقة بتمثيل هذه الشجرة غير المنتظمة داخل طبقة كاملة واحدة، ثم تحسب فقط الأجزاء الضرورية.
لنضع
$$h=\left\lfloor \log_2(2n-1)\right\rfloor,\qquad B=2^h.$$
وعندئذ
$$B\le 2n-1\lt 2B,$$
أي إن طبقة الأوراق الكاملة عند العمق \(h\) هي المجال \([B,2B-1]\)، والحد \(2n\) يشق هذه الطبقة مرة واحدة فقط.
وبالتالي فإن كل كتلة dyadic عظمى داخل \([B,2B)\) لا بد أن تكون من أحد الشكلين:
$$[j_0,j_0+2^d)\subseteq [B,2n)\quad\text{or}\quad [j_0,j_0+2^d)\subseteq [2n,2B).$$
إذا كانت الكتلة تقع كلها في الجهة اليسرى، فهي تمثل شجرة فرعية كاملة عادية، وقيمتها ببساطة هي
$$F\!\left(\left\lfloor \frac{j_0}{2^d}\right\rfloor,d\right).$$
ولأننا لا نفكك إلا حدًا واحدًا فقط، فإن عدد الكتل كلها لا يتجاوز \(O(h)=O(\log n)\).
إذا كانت الكتلة كلها ضمن \([2n,2B)\)، فهي تقع مستوى واحدًا تحت شجرة فرعية كانت قد انتهت بالفعل في المسألة الأصلية. هذا المستوى الزائد ظهر فقط بسبب التمثيل داخل الشجرة الكاملة، ويحمل ولداه القيمة المتممة نفسها.
إذا كتبنا \(M=q-1\)، فإن قيمة الكتلة اليمنى تصبح
$$G(k,0)=M-u_k,$$
$$G(k,d)=M-F(k,d-1)\qquad(d\ge 1).$$
ومعنى ذلك أن الكتلة اليمنى ذات الارتفاع \(d\) يمكن تقييمها على أنها متمم شجرة فرعية حقيقية ذات ارتفاع \(d-1\). وهذا هو السبب في اختفاء مستوى كامل من كل كتلة تقع بالكامل إلى يمين \(2n\).
حتى بعد هذه البنية، فإن التوسيع الساذج لتعريف \(F(k,d)\) يبقى أسيًا في \(d\). لهذا تستعمل الخوارزمية حدود alpha-beta أثناء النزول العودي إلى الولدين.
في عقدة التعظيم تُفحَص أولًا القيمة المباشرة الأكبر، وفي عقدة التصغير تُفحَص أولًا القيمة الأصغر. هذا يزيد فرصة اكتشاف أن الفرع الثاني لن يغيّر النتيجة، وبالتالي يمكن قصّه مبكرًا.
الصيغة الرياضية نفسها لا تتبدل، لكن عدد العقد التي تُزار فعليًا ينخفض كثيرًا في التطبيق العملي.
بعد أن نحصل على قيمة كل كتلة dyadic عظمى، نعيد بناء الآباء الناقصين صعودًا بالقاعدة المتناوبة نفسها:
$$R(s,0)=\text{block value starting at }s,$$
$$R(s,d)= \begin{cases} \max\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ odd},\\[4pt] \min\bigl(R(s,d-1),R(s+2^{d-1},d-1)\bigr), & d\text{ even}. \end{cases}$$
إذا كانت \(Z=R(0,h)\)، فهناك في النهاية قلب واحد إضافي تحدده فردية \(h\) أو زوجيته، ولذلك يكون الجواب
$$A(n)= \begin{cases} Z, & h\text{ even},\\[4pt] M-Z, & h\text{ odd}. \end{cases}$$
في هذه الحالة
$$h=\left\lfloor \log_2(19)\right\rfloor=4,\qquad B=16,\qquad 2n=20.$$
ومن ثم تنقسم طبقة الأوراق \([16,32)\) إلى الكتل dyadic العظمى التالية:
$$[16,20),\qquad [20,24),\qquad [24,32).$$
قيم المتتالية اللازمة هنا هي
$$u_{10}=33,\ u_{11}=27,\ u_{12}=28,\ u_{13}=22,\ u_{14}=25,\ u_{15}=20,$$
$$u_{16}=139,\ u_{17}=111,\ u_{18}=115,\ u_{19}=95.$$
الكتلة اليسرى هي شجرة فرعية عادية بارتفاع \(2\) وجذرها \(4\):
$$F(4,2)=\min\bigl(\max(139,111),\max(115,95)\bigr)=115.$$
الكتلة الوسطى تقع في اليمين، ولذلك ينهار مستوى كامل:
$$G(5,2)=M-F(5,1)=M-\max(33,27)=M-33.$$
والكتلة الأخيرة أيضًا تقع في اليمين:
$$F(3,2)=\min\bigl(\max(28,22),\max(25,20)\bigr)=25,$$
$$G(3,3)=M-F(3,2)=M-25.$$
وعند الدمج صعودًا نحصل على
$$\max(115,M-33)=M-33,$$
$$\min(M-33,M-25)=M-33.$$
وبما أن \(h=4\) زوجي فلا نحتاج إلى قلب أخير، ومن ثم
$$A(10)=M-33,$$
وهو نفس مقدار التحقق الذي تعتمده الخوارزمية.
الجزء العددي الأساسي موجود في تنفيذ C++. فهو يبني حالة المتتالية المقنَّعة مباشرة من البتات الثنائية للفهرس، ولذلك فإن إيجاد \(u_k\) يتطلب عملًا لوغاريتميًا فقط. أما تنفيذا Python وJava فيفوِّضان الحساب إلى المنطق المترجم نفسه، لذا فإن اللغات الثلاث تعمل كلها على الرياضيات نفسها.
كل كتلة dyadic تُقيَّم بصورة مستقلة. الكتل اليسرى تستعمل المقيم العادي \(F(k,d)\)، والكتل اليمنى تستعمل الصيغة المتممة \(G(k,d)\). وداخل كل شجرة فرعية تُحاط العودية بحدود alpha-beta، كما يُختار ترتيب الأبناء بحيث يزيد احتمال التقليم.
بعد حساب قيم الكتل، تُحفظ هذه القيم بحسب موضع المقطع وارتفاعه، ثم يُعاد بناء الآباء الناقصين بالتناوب بين \(\max\) و\(\min\)، وفي النهاية تُطبَّق التصحيحة المرتبطة بزوجية \(h\). كما أن تنفيذ C++ يوزع تقييم الكتل المستقلة على عدة مهام متوازية، وهو ما يساعد عند الإدخال الأكبر.
حساب قيمة واحدة \(u_k\) يكلف \(O(\log k)\) عملية حسابية لأن الفهرس يُعالَج بتًا بتًا. كما أن تقسيم طبقة الأوراق إلى كتل dyadic يولِّد فقط \(O(\log n)\) كتل عظمى، وإعادة دمجها تكلف هي الأخرى \(O(\log n)\).
أما الجزء المكلف فعلًا فهو تقييم الأشجار الفرعية. ففي أسوأ الأحوال تحتاج شجرة minimax خام بارتفاع \(d\) إلى \(O(2^d)\) زيارة أوراق. لكن الخوارزمية تتجاوز معظم هذا العبء عبر تقليصين بنيويين: كل كتلة تقع في اليمين تخسر مستوى كامل بسبب تناظر المتمم، ثم يقوم تقليم alpha-beta بحذف كثير من الفروع العودية في الأشجار الباقية. وهذا الجمع هو ما يجعل القيمة المطلوبة قابلة للحساب عمليًا.