We build a set in rounds. At round \(r\), let \(a_r\) be the smallest positive integer not yet present. Then choose the smallest positive integer \(b_r\) such that both \(b_r\) and \(c_r=a_r\oplus b_r\) are still absent, and insert the triple \((a_r,b_r,c_r)\). If \(P_r\) denotes the set after \(r\) rounds, the target quantity is
$$M(r)=\sum_{x\in P_r} x,$$
with the final answer required modulo \(10^9+7\).
A direct simulation is hopeless for \(r=10^{18}\). The implementations therefore avoid storing the set explicitly and instead exploit a rigid 4-way self-similar structure hidden inside the generated triples.
Write the construction as
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
The key is that the rounds do not behave randomly: they fall into blocks of lengths \(1,4,16,64,\dots\), and each block is built from four smaller copies of the same pattern.
Let
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
The observed and implemented block theorem is:
After exactly \(T_k\) rounds, the set of inserted numbers is
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$$
This is true for \(k=0\), because the first round inserts \((1,2,3)\). If a block of size \(s\) contributes exactly the three disjoint intervals
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$$
then the special outer blocks use the seeds
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
and therefore fill
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$$
Since all earlier completed blocks already filled \([1,s-1]\), the union becomes \([1,4s-1]\). Hence the next mex is \(4s\), so the next complete block must start at \((4s,8s,12s)\).
Consider a block of size \(s=4^m\) with seed triple \((a,b,c)\). When \(s=1\), the block is just that single triple. For \(s>1\), set
$$q=\frac{s}{4}.$$
The block is the ordered concatenation of four child blocks of size \(q\):
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
Each child has the same internal structure as the parent, only scaled down by a factor of \(4\). This is the fundamental self-similarity exploited by the algorithm.
The quarter-block offsets are not arbitrary. Their leading base-4 digits are
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
In every case, the third digit is the bitwise XOR of the first two:
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
Because \(q\) is a power of \(4\), adding a multiple of \(q\) changes a fresh pair of bits and does not interfere with the lower bits handled inside the recursive child. So if a parent block respects \(c=a\oplus b\), then each child block also respects the same relation after its offset is applied.
This is the reason the same pattern can repeat indefinitely across scales.
Although the triples inside a block are interleaved, the set of first coordinates over the whole block is exactly
$$a,a+1,\dots,a+s-1,$$
the set of second coordinates is exactly
$$b,b+1,\dots,b+s-1,$$
and the set of third coordinates is exactly
$$c,c+1,\dots,c+s-1.$$
Therefore the contribution of the entire block is
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$$
Equivalently,
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
This closed form is why completed blocks can be consumed instantly instead of round by round.
Now suppose we need only the first \(\ell\) rounds of a block of size \(s=4q\). Let
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q).$$
Then the prefix sum is the sum of four child-prefix sums, taken in order:
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
The base cases are immediate: an empty prefix contributes \(0\), a full prefix contributes \(B(a,b,c;s)\), and a block of size \(1\) contributes \(a+b+c\).
The block sizes are \(1,4,16,\dots\). So the first \(10\) rounds consist of
one full block of size \(1\),
one full block of size \(4\),
and the first \(5\) rounds of the next block of size \(16\).
The size-\(1\) block is just
$$ (1,2,3), $$
so its contribution is \(6\).
The next block has seed \((4,8,12)\) and size \(4\). Its four rounds are
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14), $$
which together insert every integer from \(4\) to \(15\). Hence that full block contributes
$$4+5+\cdots+15=114.$$
The next block has seed \((16,32,48)\) and size \(16\). The first quarter is a full child block of size \(4\), so it contributes
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $$
One more round is needed, namely the first round of the second quarter-block, which is \((20,40,60)\) and contributes \(120\).
Therefore
$$M(10)=6+114+402+120=642,$$
matching the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same strategy.
First, they peel off complete outer blocks of sizes \(1,4,16,\dots\). For each completed block they add the arithmetic-progression formula above, then move to the next seed \((4a,4b,4c)\) and the next block size \(4s\).
Once the remaining number of rounds fits inside the current block, the implementation switches to a recursive prefix evaluator. That routine walks the four quarter-blocks in order, adds a full quarter immediately when it is completely covered, skips a quarter when it is untouched, and descends only into the quarter that is partially covered.
All arithmetic is performed modulo \(10^9+7\). The sum of an arithmetic progression is evaluated safely modulo that prime by multiplying with the modular inverse of \(2\), so no floating-point arithmetic is needed.
The outer block loop touches block sizes \(1,4,16,\dots\), so it takes \(O(\log_4 n)\) iterations. The recursive prefix computation descends through at most one genuinely partial branch per level and performs only constant extra work around it. Therefore the total running time is \(O(\log n)\).
The only non-constant auxiliary memory is the recursion stack, whose depth is also \(O(\log n)\). No explicit set of inserted numbers is stored.
Die Menge wird rundenweise aufgebaut. In Runde \(r\) sei \(a_r\) die kleinste positive Zahl, die noch nicht vorkommt. Dann wählt man die kleinste positive Zahl \(b_r\), für die sowohl \(b_r\) als auch \(c_r=a_r\oplus b_r\) noch fehlen, und fügt das Tripel \((a_r,b_r,c_r)\) ein. Mit \(P_r\) als Menge nach \(r\) Runden lautet die gesuchte Größe
$$M(r)=\sum_{x\in P_r} x,$$
wobei das Endergebnis modulo \(10^9+7\) verlangt wird.
Eine direkte Simulation scheitert bei \(r=10^{18}\). Die Implementierungen nutzen deshalb eine starre 4-fache Selbstähnlichkeit der erzeugten Tripel aus, anstatt die Menge explizit aufzubauen.
Die Konstruktion lässt sich so schreiben:
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
Entscheidend ist, dass die Runden nicht chaotisch verteilt sind. Sie zerfallen in Blöcke der Längen \(1,4,16,64,\dots\), und jeder Block besteht wiederum aus vier verkleinerten Kopien desselben Musters.
Setze
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
Der zentrale Satz hinter der Implementierung lautet:
Nach genau \(T_k\) Runden ist die erzeugte Menge
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$$
Für \(k=0\) stimmt das sofort, weil die erste Runde \((1,2,3)\) einfügt. Liefert nun ein Block der Größe \(s\) genau die drei disjunkten Intervalle
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$$
dann benutzen die äußeren Blöcke die Seeds
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
und füllen daher
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$$
Frühere vollständige Blöcke haben bereits \([1,s-1]\) gefüllt, also entsteht zusammen \([1,4s-1]\). Folglich ist die nächste mex-Zahl gleich \(4s\), und der nächste vollständige Block beginnt bei \((4s,8s,12s)\).
Betrachte einen Block der Größe \(s=4^m\) mit Seed-Tripel \((a,b,c)\). Für \(s=1\) besteht der Block nur aus diesem einen Tripel. Für \(s>1\) setzen wir
$$q=\frac{s}{4}.$$
Dann ist der Block die geordnete Verkettung von vier Kindblöcken der Größe \(q\):
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
Jeder Kindblock besitzt dieselbe innere Struktur wie der Elternblock, nur um den Faktor \(4\) verkleinert. Genau diese Selbstähnlichkeit macht die Berechnung möglich.
Die Offsets der Viertelblöcke sind nicht zufällig. Ihre führenden Basis-4-Ziffern lauten
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
In jedem Fall ist die dritte Ziffer das bitweise XOR der ersten beiden:
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
Da \(q\) eine Potenz von \(4\) ist, verändert das Addieren eines Vielfachen von \(q\) ein neues Bitpaar und stört die niedrigeren Bits des rekursiven Kindblocks nicht. Gilt also im Elternblock \(c=a\oplus b\), dann gilt dieselbe Beziehung nach Anwenden des Offsets auch in jedem Kindblock.
Deshalb kann dasselbe Muster auf allen Skalen wiederholt werden.
Obwohl die Tripel innerhalb eines Blocks verschachtelt erscheinen, ist die Menge aller ersten Koordinaten genau
$$a,a+1,\dots,a+s-1,$$
die Menge aller zweiten Koordinaten genau
$$b,b+1,\dots,b+s-1,$$
und die Menge aller dritten Koordinaten genau
$$c,c+1,\dots,c+s-1.$$
Damit ist der Beitrag eines vollständigen Blocks
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$$
Äquivalent dazu:
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
Deshalb können vollständige Blöcke sofort addiert werden, ohne Runde für Runde zu gehen.
Benötigt man nur die ersten \(\ell\) Runden eines Blocks der Größe \(s=4q\), so definiert man
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q).$$
Die Präfixsumme ist dann die Summe der vier Kind-Präfixe in genau dieser Reihenfolge:
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
Die Basisfälle sind unmittelbar: Ein leeres Präfix liefert \(0\), ein vollständiges Präfix liefert \(B(a,b,c;s)\), und ein Block der Größe \(1\) liefert \(a+b+c\).
Die Blockgrößen sind \(1,4,16,\dots\). Die ersten \(10\) Runden bestehen also aus
einem vollständigen Block der Größe \(1\),
einem vollständigen Block der Größe \(4\),
und den ersten \(5\) Runden des nächsten Blocks der Größe \(16\).
Der Block der Größe \(1\) ist einfach
$$ (1,2,3), $$
also mit Beitrag \(6\).
Der nächste Block hat Seed \((4,8,12)\) und Größe \(4\). Seine vier Runden sind
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14), $$
und sie fügen genau alle Zahlen von \(4\) bis \(15\) ein. Daher liefert dieser volle Block
$$4+5+\cdots+15=114.$$
Der nächste Block besitzt Seed \((16,32,48)\) und Größe \(16\). Das erste Viertel ist ein voller Kindblock der Größe \(4\) und trägt bei:
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $$
Danach wird noch genau eine Runde benötigt, nämlich die erste Runde des zweiten Viertelblocks. Sie ist \((20,40,60)\) und trägt \(120\) bei.
Damit ergibt sich
$$M(10)=6+114+402+120=642,$$
genau der Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen verfolgen alle dieselbe Strategie.
Zuerst werden vollständige äußere Blöcke der Größen \(1,4,16,\dots\) abgezogen. Für jeden vollständig abgedeckten Block wird sofort die Formel für arithmetische Folgen addiert; anschließend gehen Seed und Blockgröße zu \((4a,4b,4c)\) beziehungsweise \(4s\) über.
Sobald die verbleibende Rundenzahl in den aktuellen Block passt, wechselt die Implementierung zu einer rekursiven Präfixauswertung. Diese durchläuft die vier Viertelblöcke der Reihe nach, addiert vollständig abgedeckte Viertel sofort, überspringt unberührte Viertel und steigt nur in das teilweise benötigte Viertel rekursiv hinab.
Die gesamte Arithmetik läuft modulo \(10^9+7\). Die Summen arithmetischer Folgen werden dabei mit dem modularen Inversen von \(2\) berechnet, also rein ganzzahlig und ohne Fließkomma.
Die äußere Schleife besucht nur Blockgrößen \(1,4,16,\dots\) und benötigt daher \(O(\log_4 n)\) Iterationen. Die rekursive Präfixberechnung folgt pro Ebene höchstens einem wirklich partiellen Zweig und erledigt nur konstanten Zusatzaufwand. Insgesamt ist die Laufzeit also \(O(\log n)\).
Zusätzlicher Speicher wird nur für den Rekursionsstapel gebraucht, ebenfalls \(O(\log n)\). Eine explizite Speicherung der erzeugten Menge ist nicht notwendig.
Küme turlar halinde kuruluyor. \(r\). turda \(a_r\), henüz kümede bulunmayan en küçük pozitif tamsayıdır. Daha sonra hem \(b_r\) hem de \(c_r=a_r\oplus b_r\) kümede olmayacak şekilde en küçük pozitif \(b_r\) seçilir ve \((a_r,b_r,c_r)\) üçlüsü eklenir. \(P_r\) \(r\) tur sonundaki kümeyi gösterirse hedef büyüklük
$$M(r)=\sum_{x\in P_r} x,$$
olur; nihai cevap da \(10^9+7\) modunda istenir.
\(r=10^{18}\) için doğrudan benzetim yapmak imkansızdır. Bu yüzden uygulamalar kümeyi tek tek kurmak yerine üretilen üçlülerin içindeki katı 4'lü öz-benzer yapıyı kullanır.
Kuruluş şu şekilde yazılabilir:
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
Asıl kritik nokta, turların düzensiz görünmesine rağmen \(1,4,16,64,\dots\) uzunluklu bloklara ayrılması ve her bloğun kendi içinde dört küçük kopyaya bölünmesidir.
Şunu tanımlayalım:
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
Uygulamaların kullandığı temel blok teoremi şudur:
Tam olarak \(T_k\) turdan sonra elde edilen küme
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}$$
olur. \(k=0\) için bu açıktır, çünkü ilk turda \((1,2,3)\) eklenir. Eğer boyutu \(s\) olan bir blok tam olarak şu üç ayrık aralığı dolduruyorsa
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$$
dış bloklar için tohumlar
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
şeklindedir ve böylece blok
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1]$$
aralığını kaplar. Daha önceki tam bloklar zaten \([1,s-1]\) aralığını doldurduğu için birleşim \([1,4s-1]\) olur. Dolayısıyla sonraki mex değeri \(4s\)'dir ve bir sonraki tam blok \((4s,8s,12s)\) ile başlar.
Boyutu \(s=4^m\) olan ve tohum üçlüsü \((a,b,c)\) olan bir blok düşünelim. \(s=1\) ise blok yalnızca bu tek üçlüden oluşur. \(s>1\) için
$$q=\frac{s}{4}$$
yazarız. O zaman blok, boyutu \(q\) olan dört alt bloğun sırayla birleşimidir:
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
Her alt blok, ana bloğun ayni kuralını daha küçük ölçekte tekrar eder. Algoritmanın dayandığı öz-benzerlik budur.
Çeyrek blok ofsetleri rastgele değildir. En üst tabandaki 4'lük basamaklar şunlardır:
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
Her durumda üçüncü basamak, ilk iki basamağın bit düzeyinde XOR'udur:
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
\(q\) bir \(4\) kuvveti olduğu için \(q\)'nun katını eklemek sayının yeni bir iki-bitlik katmanını değiştirir ve rekürsif alt blokta kullanılan daha düşük bitlere karışmaz. Bu nedenle üst blokta \(c=a\oplus b\) ilişkisi geçerliyse, ofset eklendikten sonra aynı ilişki her alt blokta da geçerlidir.
Böylece desen ölçekten bağımsız olarak tekrar eder.
Bir blok içindeki üçlüler karışık sırada görünse de, tüm ilk bileşenlerin kümesi tam olarak
$$a,a+1,\dots,a+s-1,$$
tüm ikinci bileşenlerin kümesi tam olarak
$$b,b+1,\dots,b+s-1,$$
ve tüm üçüncü bileşenlerin kümesi tam olarak
$$c,c+1,\dots,c+s-1$$
olur. Dolayısıyla tam blok katkısı
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t)$$
şeklindedir. Eşdeğer kapalı biçim:
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
Bu yüzden tamamı kapsanan bloklar tek tek tur simüle edilmeden anında toplanabilir.
Boyutu \(s=4q\) olan bir bloğun yalnızca ilk \(\ell\) turu gerekliyse
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q)$$
tanımlarını yaparız. O zaman prefix toplamı dört alt blok prefix'inin sırayla toplamıdır:
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
Taban durumları basittir: boş prefix \(0\) verir, tam prefix \(B(a,b,c;s)\) verir, boyut \(1\) ise katkı doğrudan \(a+b+c\) olur.
Blok boyları \(1,4,16,\dots\) şeklindedir. Bu yüzden ilk \(10\) tur,
boyutu \(1\) olan bir tam bloktan,
boyutu \(4\) olan bir tam bloktan,
ve boyutu \(16\) olan sonraki bloğun ilk \(5\) turundan oluşur.
Boyutu \(1\) olan blok sadece
$$ (1,2,3) $$
olduğu için katkısı \(6\)'dır.
Sonraki blok \((4,8,12)\) tohumu ve \(4\) boyuyla gelir. Dört turu şunlardır:
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14). $$
Bunlar birlikte \(4\) ile \(15\) arasındaki tüm sayıları ekler. Dolayısıyla bu tam bloğun katkısı
$$4+5+\cdots+15=114$$
olur.
Bir sonraki blok \((16,32,48)\) tohumu ve \(16\) boyuyla başlar. İlk çeyrek, boyutu \(4\) olan tam bir alt bloktur ve katkısı
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402 $$
şeklindedir. Bundan sonra bir tur daha gerekir; bu da ikinci çeyrek bloğun ilk turu olan \((20,40,60)\) üçlüsüdür ve \(120\) katkı yapar.
Sonuç olarak
$$M(10)=6+114+402+120=642,$$
ve bu değer uygulamaların kullandığı kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı iskeleti izler.
Önce dış bloklar \(1,4,16,\dots\) boylarıyla sırayla tüketilir. Tamamı kapsanan her blok için yukarıdaki aritmetik dizi formülü eklenir; sonra tohum üçlüsü \((4a,4b,4c)\) biçimine ölçeklenir ve blok boyu \(4s\) olur.
Kalan tur sayısı mevcut bloğun içine sığdığı anda yöntem özyinelemeli prefix hesabına geçer. Bu yordam dört çeyrek bloğu sırayla dolaşır; tamamen kapsanan çeyreği doğrudan toplar, hiç dokunulmayan çeyreği atlar, yalnızca kısmen gereken çeyreğin içine iner.
Tüm işlemler \(10^9+7\) modunda yapılır. Aritmetik dizi toplamında \(\frac{1}{2}\) bölmesi, bu asal mod altında \(2\)'nin modüler tersi kullanılarak güvenli biçimde gerçekleştirilir.
Dış döngü yalnızca \(1,4,16,\dots\) blok boylarını ziyaret ettiği için \(O(\log_4 n)\) adım sürer. Rekürsif prefix hesabı ise her seviyede en fazla bir gerçekten kısmi dala iner ve çevresinde yalnızca sabit ek iş yapar. Bu nedenle toplam süre \(O(\log n)\) olur.
Ek bellek ihtiyacı yalnızca özyineleme yığınıdır ve onun derinliği de \(O(\log n)\) düzeyindedir. Üretilen sayıları tutan açık bir küme yapısına ihtiyaç yoktur.
La construcción avanza por rondas. En la ronda \(r\), \(a_r\) es el menor entero positivo que todavía no aparece. Después se elige el menor entero positivo \(b_r\) tal que ni \(b_r\) ni \(c_r=a_r\oplus b_r\) estén presentes, y se inserta el triple \((a_r,b_r,c_r)\). Si \(P_r\) es el conjunto tras \(r\) rondas, la magnitud pedida es
$$M(r)=\sum_{x\in P_r} x,$$
y la respuesta final debe darse módulo \(10^9+7\).
Simular esto directamente para \(r=10^{18}\) no es viable. Por eso las implementaciones no construyen el conjunto completo, sino que aprovechan una estructura autosimilar de 4 partes dentro de los triples generados.
La definición del proceso es
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
El hecho decisivo es que las rondas no forman un patrón arbitrario: se agrupan en bloques de tamaños \(1,4,16,64,\dots\), y cada bloque se descompone en cuatro copias más pequeñas del mismo esquema.
Definamos
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
El teorema estructural usado por la implementación es:
Después de exactamente \(T_k\) rondas, el conjunto generado es
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$$
Para \(k=0\) esto es inmediato, porque la primera ronda inserta \((1,2,3)\). Si un bloque de tamaño \(s\) aporta exactamente los tres intervalos disjuntos
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$$
entonces los bloques exteriores usan semillas
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
y por tanto rellenan
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$$
Como los bloques completos anteriores ya cubrían \([1,s-1]\), la unión pasa a ser \([1,4s-1]\). Así, el siguiente mex es \(4s\), y el siguiente bloque completo empieza en \((4s,8s,12s)\).
Consideremos un bloque de tamaño \(s=4^m\) con semilla \((a,b,c)\). Si \(s=1\), el bloque es simplemente ese triple. Para \(s>1\), escribimos
$$q=\frac{s}{4}.$$
Entonces el bloque es la concatenación ordenada de cuatro subbloques de tamaño \(q\):
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
Cada subbloque repite exactamente la misma regla que el bloque padre, solo que a una escala cuatro veces menor.
Los desplazamientos de esos cuatro cuartos no son accidentales. Sus dígitos líderes en base \(4\) son
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
En todos los casos, el tercer dígito es el XOR bit a bit de los dos primeros:
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
Como \(q\) es una potencia de \(4\), sumar un múltiplo de \(q\) modifica un par nuevo de bits y no interfiere con los bits bajos que maneja el subbloque recursivo. Por eso, si el bloque padre satisface \(c=a\oplus b\), cada subbloque también lo satisface tras aplicar su desplazamiento.
Aunque el orden interno de los triples parece entrelazado, el conjunto de primeras coordenadas del bloque completo es exactamente
$$a,a+1,\dots,a+s-1,$$
el conjunto de segundas coordenadas es exactamente
$$b,b+1,\dots,b+s-1,$$
y el de terceras coordenadas es exactamente
$$c,c+1,\dots,c+s-1.$$
Por tanto, la contribución del bloque entero es
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$$
En forma cerrada,
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
Esto permite consumir un bloque completo de una sola vez.
Si solo hacen falta las primeras \(\ell\) rondas de un bloque de tamaño \(s=4q\), definimos
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q).$$
La suma de prefijo es entonces la suma de cuatro prefijos hijos en orden:
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
Los casos base son directos: prefijo vacío \(0\), prefijo completo \(B(a,b,c;s)\), y para tamaño \(1\) la contribución es \(a+b+c\).
Los tamaños de bloque son \(1,4,16,\dots\). Por tanto, las primeras \(10\) rondas están formadas por
un bloque completo de tamaño \(1\),
un bloque completo de tamaño \(4\),
y las primeras \(5\) rondas del siguiente bloque de tamaño \(16\).
El bloque de tamaño \(1\) es
$$ (1,2,3), $$
así que aporta \(6\).
El siguiente bloque tiene semilla \((4,8,12)\) y tamaño \(4\). Sus cuatro rondas son
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14), $$
y juntas insertan exactamente todos los enteros entre \(4\) y \(15\). Por ello, ese bloque completo aporta
$$4+5+\cdots+15=114.$$
El siguiente bloque empieza en \((16,32,48)\) y tiene tamaño \(16\). Su primer cuarto es un subbloque completo de tamaño \(4\), con contribución
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $$
Hace falta una ronda más: la primera del segundo cuarto, que es \((20,40,60)\) y aporta \(120\).
En consecuencia,
$$M(10)=6+114+402+120=642,$$
exactamente el valor de verificación usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma idea.
Primero consumen bloques exteriores completos de tamaños \(1,4,16,\dots\). Para cada bloque completamente cubierto se añade de inmediato la fórmula de progresión aritmética y luego se pasa a la siguiente semilla \((4a,4b,4c)\) y al siguiente tamaño \(4s\).
Cuando el número restante de rondas ya cabe dentro del bloque actual, la implementación usa un evaluador recursivo de prefijos. Ese procedimiento recorre los cuatro cuartos en orden, suma al instante un cuarto completo, ignora un cuarto vacío y solo desciende al cuarto parcialmente cubierto.
Toda la aritmética se hace módulo \(10^9+7\). La división entre \(2\) en la suma de progresiones se realiza mediante el inverso modular de \(2\), así que no aparece aritmética en coma flotante.
El bucle exterior visita únicamente tamaños \(1,4,16,\dots\), por lo que necesita \(O(\log_4 n)\) iteraciones. El cálculo recursivo del prefijo sigue como mucho una rama realmente parcial por nivel y solo añade trabajo constante alrededor de ella. En total, el tiempo es \(O(\log n)\).
La memoria auxiliar no constante es solo la pila de recursión, cuya profundidad también es \(O(\log n)\). No hace falta almacenar explícitamente el conjunto de valores insertados.
这个过程按轮进行构造。第 \(r\) 轮时，先取当前集合中尚未出现的最小正整数 \(a_r\)。然后选择最小的正整数 \(b_r\)，使得 \(b_r\) 本身和 \(c_r=a_r\oplus b_r\) 都还没有出现在集合里，于是这一轮插入三元组 \((a_r,b_r,c_r)\)。若 \(P_r\) 表示进行了 \(r\) 轮之后的集合，那么目标函数是
$$M(r)=\sum_{x\in P_r} x,$$
最终答案按 \(10^9+7\) 取模。
当 \(r=10^{18}\) 时，逐轮模拟完全不可行。真正可行的方法是识别这些三元组内部隐藏的 4 路自相似结构，用分块递归来直接求和，而不是显式维护整个集合。
这个构造可以写成
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
表面上看，这个过程像是在不断试探 mex 和 XOR 的相容性；但实现中真正利用的事实是：这些轮次会自然分成长度为 \(1,4,16,64,\dots\) 的块，而且每个块都可以拆成四个更小、结构完全相同的子块。
先定义
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
实现所依赖的核心结论是：
经过恰好 \(T_k\) 轮之后，已经插入的数恰好是
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$$
\(k=0\) 时这显然成立，因为第一轮加入的是 \((1,2,3)\)。现在假设某个大小为 \(s\) 的块，恰好会贡献以下三个互不相交的区间：
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1].$$
对于最外层那些完整块，种子三元组正是
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
于是这个块覆盖的数就是
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$$
而在它之前，所有更小的完整块已经覆盖了 \([1,s-1]\)。因此两部分合并以后，整个集合就变成了 \([1,4s-1]\)。这说明下一个 mex 一定是 \(4s\)，所以下一个完整块自然从 \((4s,8s,12s)\) 开始。
这一步很重要，因为它解释了为什么外层循环只需要按 \(1,4,16,\dots\) 这些块大小前进。
考虑一个大小为 \(s=4^m\) 的块，它的种子三元组是 \((a,b,c)\)。当 \(s=1\) 时，这个块就只有一个三元组。若 \(s>1\)，令
$$q=\frac{s}{4}.$$
那么整个块会按顺序拆成四个大小都是 \(q\) 的子块：
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
这四个子块不是随意拼出来的，它们本身仍然遵循与父块完全相同的构造规律，只是尺度缩小了 \(4\) 倍。也就是说，一旦知道如何处理一个块，就自动知道如何处理更大的块。
上面四个子块的偏移量非常有规律。把它们看成 base-4 的高位数字，对应的是
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
在每一种情况下，第三个数字都等于前两个数字按位 XOR 的结果：
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
又因为 \(q\) 是 \(4\) 的幂，所以加上 \(0q,1q,2q,3q\) 只会修改一对新的二进制位，而不会与子块内部的低位结构发生进位干扰。于是，如果父块满足第三个数等于前两个数的 XOR，那么对子块加上这些偏移后，这个关系仍然成立。
这就是递归结构能够无限向下延续的根本原因，也是整个算法正确性的数学骨架。
虽然块内部三元组的顺序看起来并不简单，但从整个块的角度看，第一坐标恰好是
$$a,a+1,\dots,a+s-1,$$
第二坐标恰好是
$$b,b+1,\dots,b+s-1,$$
第三坐标恰好是
$$c,c+1,\dots,c+s-1.$$
因此，一个完整块的贡献就是
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$$
写成闭式就是
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
这一步把“处理一整块”从逐轮累加变成了常数时间求值，因此巨大输入才有可能被处理。
若只需要一个大小为 \(s=4q\) 的块的前 \(\ell\) 轮，那么把这 \(\ell\) 轮分配到四个子块中。定义
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q).$$
那么这个前缀和满足递推式
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
这里的边界条件很直接：空前缀返回 \(0\)，完整前缀返回整个块的闭式和，而大小为 \(1\) 的块只返回 \(a+b+c\)。
这说明无论要求多少轮，只要把它分解到若干完整块和一个最后的部分块上，就能精确求出总和。
块大小依次是 \(1,4,16,\dots\)。所以前 \(10\) 轮等于：
一个完整的大小 \(1\) 的块，
一个完整的大小 \(4\) 的块，
再加上下一个大小 \(16\) 的块的前 \(5\) 轮。
第一个块就是
$$ (1,2,3), $$
因此贡献为 \(6\)。
第二个块的种子是 \((4,8,12)\)，大小是 \(4\)。它的四轮分别为
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14). $$
这四轮合起来恰好插入了从 \(4\) 到 \(15\) 的所有整数，所以这一整块的贡献是
$$4+5+\cdots+15=114.$$
接下来是种子 \((16,32,48)\)、大小 \(16\) 的块。它的第一个四分之一子块本身就是一个完整的大小 \(4\) 的块，因此贡献为
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $$
还需要再取 1 轮，也就是第二个四分之一子块的第一轮 \((20,40,60)\)，贡献 \(120\)。
所以
$$M(10)=6+114+402+120=642,$$
与实现中使用的校验值完全一致。
C++、Python 和 Java 实现使用的是同一套思路。
首先，它们按 \(1,4,16,\dots\) 的顺序剥离完整外层块。每碰到一个完整覆盖的块，就直接用等差数列求和公式累加，然后把种子更新为 \((4a,4b,4c)\)，同时把块大小扩展为 \(4s\)。
当剩余轮数已经落在当前块内部时，程序改用递归前缀求值。这个过程按顺序查看四个子块：完整覆盖的子块立即用闭式求和，完全不需要的子块直接跳过，只有那个“部分覆盖”的子块继续递归下去。
全部计算都在 \(10^9+7\) 模下进行。等差数列公式中的除以 \(2\) 通过 \(2\) 的模逆元来完成，因此整个过程始终保持整数模运算。
外层完整块循环只会经过 \(1,4,16,\dots\) 这些规模，因此需要 \(O(\log_4 n)\) 次迭代。块前缀递归在每一层最多只会深入一个真正“部分覆盖”的分支，外围只做常数级工作，所以总时间复杂度是 \(O(\log n)\)。
额外空间主要来自递归栈，深度同样是 \(O(\log n)\)。算法完全不需要维护一个显式的大集合。
Построение идёт по раундам. На раунде \(r\) число \(a_r\) равно наименьшему положительному целому, которого ещё нет в множестве. Затем выбирается наименьшее положительное \(b_r\), для которого и \(b_r\), и \(c_r=a_r\oplus b_r\) всё ещё отсутствуют, после чего тройка \((a_r,b_r,c_r)\) добавляется в множество. Если \(P_r\) обозначает множество после \(r\) раундов, то искомая величина равна
$$M(r)=\sum_{x\in P_r} x,$$
а окончательный ответ требуется по модулю \(10^9+7\).
Для \(r=10^{18}\) прямое моделирование невозможно. Поэтому реализации не строят множество явно, а используют жёсткую 4-кратную самоподобную структуру, возникающую в последовательности троек.
Процесс записывается так:
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
Главное наблюдение состоит в том, что раунды организуются не произвольно. Они распадаются на блоки длины \(1,4,16,64,\dots\), и каждый такой блок, в свою очередь, состоит из четырёх уменьшенных копий того же узора.
Определим
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
Ключевая теорема, на которой основана реализация, такова:
после ровно \(T_k\) раундов построенное множество равно
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$$
Для \(k=0\) это очевидно, потому что первый раунд добавляет \((1,2,3)\). Если же блок размера \(s\) даёт ровно три непересекающихся интервала
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$$
то внешние блоки используют семена
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
и тем самым покрывают
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$$
Предыдущие полные блоки уже покрыли \([1,s-1]\), поэтому вместе получается \([1,4s-1]\). Значит, следующий mex равен \(4s\), и следующий полный блок начинается с \((4s,8s,12s)\).
Рассмотрим блок размера \(s=4^m\) с сидом \((a,b,c)\). При \(s=1\) это просто одна тройка. При \(s>1\) положим
$$q=\frac{s}{4}.$$
Тогда блок представляет собой упорядоченную конкатенацию четырёх дочерних блоков размера \(q\):
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
Каждый дочерний блок повторяет ту же внутреннюю структуру, что и родительский, только на масштабе в \(4\) раза меньше.
Смещения этих четырёх четвертей устроены очень специально. Их старшие цифры в системе счисления по основанию \(4\) равны
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
Во всех четырёх случаях третья цифра является побитовым XOR первых двух:
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
Так как \(q\) является степенью \(4\), прибавление кратного \(q\) меняет новую пару битов и не вмешивается в младшие биты, за которые отвечает рекурсивный дочерний блок. Поэтому если в родительском блоке выполняется \(c=a\oplus b\), то после добавления соответствующих смещений то же равенство остаётся верным и для каждого дочернего блока.
Порядок троек внутри блока может выглядеть сложным, но множество первых координат полного блока равно
$$a,a+1,\dots,a+s-1,$$
множество вторых координат равно
$$b,b+1,\dots,b+s-1,$$
а множество третьих координат равно
$$c,c+1,\dots,c+s-1.$$
Следовательно, вклад целого блока равен
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$$
В замкнутом виде это
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
Именно поэтому полный блок можно просуммировать мгновенно, не разбирая отдельные раунды.
Если нужен только префикс длины \(\ell\) внутри блока размера \(s=4q\), вводятся величины
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q).$$
Тогда префиксная сумма выражается через префиксы четырёх дочерних блоков, взятых по порядку:
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
Базовые случаи просты: пустой префикс даёт \(0\), полный префикс даёт \(B(a,b,c;s)\), а блок размера \(1\) даёт просто \(a+b+c\).
Размеры блоков равны \(1,4,16,\dots\). Значит, первые \(10\) раундов состоят из
одного полного блока размера \(1\),
одного полного блока размера \(4\),
и первых \(5\) раундов следующего блока размера \(16\).
Блок размера \(1\) — это
$$ (1,2,3), $$
поэтому его вклад равен \(6\).
Следующий блок имеет сид \((4,8,12)\) и размер \(4\). Его четыре раунда таковы:
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14). $$
Вместе они вставляют все числа от \(4\) до \(15\), так что полный блок даёт
$$4+5+\cdots+15=114.$$
Следующий блок стартует с \((16,32,48)\) и имеет размер \(16\). Его первая четверть — это полный дочерний блок размера \(4\), чей вклад равен
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $$
Нужен ещё один раунд, а именно первый раунд второй четверти: \((20,40,60)\), что даёт вклад \(120\).
Следовательно,
$$M(10)=6+114+402+120=642,$$
и это точно совпадает с контрольным значением из реализаций.
Реализации на C++, Python и Java используют одну и ту же схему.
Сначала они снимают полные внешние блоки размеров \(1,4,16,\dots\). Для каждого полностью покрытого блока сразу добавляется формула для суммы арифметических прогрессий, после чего сид масштабируется в \((4a,4b,4c)\), а размер блока становится равным \(4s\).
Когда оставшееся число раундов уже помещается внутрь текущего блока, управление переходит к рекурсивному вычислению префикса. Эта процедура проходит четыре четверти по порядку: полностью покрытую четверть суммирует сразу, пустую пропускает, а в частично покрытую спускается рекурсивно.
Все вычисления выполняются по модулю \(10^9+7\). Деление на \(2\) в формуле суммы прогрессии заменяется умножением на обратный по модулю элемент, поэтому используются только целочисленные модульные операции.
Внешний цикл проходит только по размерам \(1,4,16,\dots\), следовательно, он делает \(O(\log_4 n)\) шагов. Рекурсивный расчёт префикса на каждом уровне углубляется не более чем в одну действительно частичную ветвь и выполняет лишь константную дополнительную работу. Итого время работы равно \(O(\log n)\).
Дополнительная память — это только стек рекурсии глубины \(O(\log n)\). Явное хранение построенного множества не требуется.
يتم بناء المجموعة على جولات. في الجولة \(r\) يكون \(a_r\) هو أصغر عدد صحيح موجب غير موجود بعد. ثم نختار أصغر عدد موجب \(b_r\) بحيث يكون كل من \(b_r\) و\(c_r=a_r\oplus b_r\) غير موجودين أيضًا، ثم نضيف الثلاثية \((a_r,b_r,c_r)\). إذا كانت \(P_r\) تمثل المجموعة بعد \(r\) جولات، فإن الكمية المطلوبة هي
$$M(r)=\sum_{x\in P_r} x,$$
والجواب النهائي مطلوب بترديد \(10^9+7\).
المحاكاة المباشرة عند \(r=10^{18}\) غير عملية تمامًا. لذلك لا تبني التطبيقات المجموعة صراحة، بل تستغل بنية ذاتية التشابه من أربع جهات تظهر داخل الثلاثيات المتولدة.
يمكن كتابة البناء كما يلي:
$$P_0=\varnothing,$$
$$a_r=\operatorname{mex}(P_{r-1}),$$
$$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$$
$$c_r=a_r\oplus b_r,$$
$$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$$
الفكرة الأساسية أن الجولات لا تتوزع عشوائيًا، بل تنقسم إلى كتل بأحجام \(1,4,16,64,\dots\)، وكل كتلة تتكون من أربع نسخ أصغر من النمط نفسه.
لنعرّف
$$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$$
والحقيقة البنيوية التي تعتمد عليها التطبيقات هي:
بعد \(T_k\) جولات بالضبط تصبح المجموعة المبنية
$$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$$
عند \(k=0\) هذا واضح لأن الجولة الأولى تضيف \((1,2,3)\). وإذا كانت كتلة بحجم \(s\) تضيف بالضبط الفواصل المنفصلة الثلاثة
$$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$$
فإن الكتل الخارجية تستخدم البذور
$$ (s,2s,3s),\qquad s=1,4,16,\dots $$
ومن ثم تملأ
$$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$$
وبما أن الكتل الكاملة السابقة كانت قد ملأت \([1,s-1]\)، فإن الاتحاد يصبح \([1,4s-1]\). وهذا يعني أن قيمة mex التالية هي \(4s\)، ولذلك تبدأ الكتلة الكاملة التالية من \((4s,8s,12s)\).
لننظر إلى كتلة بحجم \(s=4^m\) وبذرة \((a,b,c)\). إذا كان \(s=1\) فالكتلة هي هذه الثلاثية الوحيدة. أما عندما \(s>1\) فنضع
$$q=\frac{s}{4}.$$
عندها تكون الكتلة هي الضم المرتب لأربعة كتل فرعية، كل منها بحجم \(q\):
$$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $$
كل كتلة فرعية تعيد نفس البنية الداخلية للكتلة الأم ولكن على مقياس أصغر بأربع مرات، وهذا هو جوهر التشابه الذاتي الذي يستند إليه الحل.
إزاحات الأرباع الأربع ليست اعتباطية. إذا نظرنا إلى أرقامها الرائدة في الأساس \(4\) وجدناها
$$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $$
وفي كل حالة يكون الرقم الثالث هو XOR البتّي للرقمين الأولين:
$$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$$
ولأن \(q\) قوة للعدد \(4\)، فإن إضافة مضاعف لـ \(q\) تغيّر زوجًا جديدًا من البتات ولا تتداخل مع البتات الدنيا التي تتولاها الكتلة الفرعية التكرارية. لذلك إذا كانت الكتلة الأم تحقق العلاقة \(c=a\oplus b\)، فإن كل كتلة فرعية ستحقق العلاقة نفسها بعد إضافة إزاحتها الخاصة.
رغم أن ترتيب الثلاثيات داخل الكتلة يبدو متشابكًا، فإن مجموعة الإحداثيات الأولى عبر الكتلة كلها هي بالضبط
$$a,a+1,\dots,a+s-1,$$
ومجموعة الإحداثيات الثانية هي
$$b,b+1,\dots,b+s-1,$$
ومجموعة الإحداثيات الثالثة هي
$$c,c+1,\dots,c+s-1.$$
لذلك فإن مساهمة الكتلة الكاملة تساوي
$$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$$
وبالصيغة المغلقة نحصل على
$$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$$
وهذا ما يسمح بالتعامل مع كتلة كاملة دفعة واحدة بدل المرور على جولة بعد أخرى.
إذا احتجنا فقط إلى أول \(\ell\) جولات من كتلة بحجم \(s=4q\)، فنعرّف
$$\ell_1=\min(\ell,q),$$
$$\ell_2=\min(\max(\ell-q,0),q),$$
$$\ell_3=\min(\max(\ell-2q,0),q),$$
$$\ell_4=\min(\max(\ell-3q,0),q).$$
وعندئذ يكون مجموع البادئة هو مجموع بادئات الأبناء الأربعة بالترتيب:
$$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $$
$$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $$
الحالات الأساسية مباشرة: البادئة الفارغة تعطي \(0\)، والبادئة الكاملة تعطي \(B(a,b,c;s)\)، وإذا كان الحجم \(1\) فالمساهمة هي \(a+b+c\) فقط.
أحجام الكتل هي \(1,4,16,\dots\). إذن أول \(10\) جولات تتكون من
كتلة كاملة بحجم \(1\)،
ثم كتلة كاملة بحجم \(4\)،
ثم أول \(5\) جولات من الكتلة التالية ذات الحجم \(16\).
الكتلة الأولى هي
$$ (1,2,3), $$
ولذلك مساهمتها \(6\).
الكتلة التالية بذرتها \((4,8,12)\) وحجمها \(4\)، وجولاتها الأربع هي
$$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14). $$
وهذه الجولات تضيف جميع الأعداد من \(4\) إلى \(15\)، لذا يكون مجموع تلك الكتلة الكاملة
$$4+5+\cdots+15=114.$$
الكتلة التالية تبدأ من \((16,32,48)\) وحجمها \(16\). الربع الأول منها هو كتلة فرعية كاملة بحجم \(4\)، ومساهمتها
$$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $$
ثم نحتاج إلى جولة إضافية واحدة فقط، وهي أول جولة من الربع الثاني: \((20,40,60)\)، ومساهمتها \(120\).
إذن
$$M(10)=6+114+402+120=642,$$
وهو تمامًا مقدار التحقق المستخدم في التطبيقات.
تتبع تطبيقات C++ وPython وJava الفكرة نفسها.
أولاً يتم استهلاك الكتل الخارجية الكاملة ذات الأحجام \(1,4,16,\dots\). ولكل كتلة مغطاة بالكامل يُضاف فورًا مجموع المتتاليات الحسابية، ثم تُحدَّث البذرة إلى \((4a,4b,4c)\) ويصبح الحجم \(4s\).
وعندما يصبح عدد الجولات المتبقية واقعًا داخل الكتلة الحالية، تنتقل الطريقة إلى تقييم بادئة تكراري. هذه العملية تمر على الأرباع الأربعة بالترتيب: تجمع الربع الكامل مباشرة، وتتجاوز الربع غير المستخدم، ولا تنزل تكراريًا إلا إلى الربع المغطى جزئيًا.
جميع العمليات الحسابية تتم بترديد \(10^9+7\). والقسمة على \(2\) في صيغة مجموع المتتالية الحسابية تُنفَّذ باستعمال المعكوس الضربي لـ \(2\) modulo ذلك العدد الأولي.
الحلقة الخارجية تزور فقط الأحجام \(1,4,16,\dots\)، لذا فهي تحتاج إلى \(O(\log_4 n)\) خطوة. أما حساب البادئة التكراري فيتعمق في كل مستوى في فرع جزئي واحد على الأكثر ويقوم بعمل إضافي ثابت حوله، ولذلك يصبح الزمن الكلي \(O(\log n)\).
الذاكرة الإضافية الوحيدة غير الثابتة هي مكدس الاستدعاء التكراري، وعمقه أيضًا \(O(\log n)\). ولا توجد حاجة إلى تخزين المجموعة المبنية صراحة.