For each starting value \(r\), the game distinguishes moves by the parity of the Hamming weight of the chosen subtraction:
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
The goal is to sum all \(r\in[1,2^n]\) for which Oscar loses with perfect play. The brute-force dynamic program in the implementations confirms the game rules for small \(n\), while the production solver exploits a rigid base-4 layer structure and works modulo \(10^9+7\).
The fast solution comes from understanding which positions are losing, not from simulating every move up to \(2^n\).
For a remaining value \(r\), the brute-force derivation tracks two pieces of information: whose turn it is, and a binary flag \(q\in\{0,1\}\) that records the running parity relevant to the win condition. Let
$$O_q(r)\in\{0,1\}$$
mean “Oscar wins from remainder \(r\) when it is Oscar's turn and the flag is \(q\),” and let
$$E_q(r)\in\{0,1\}$$
mean the same when it is Eric's turn.
At \(r=0\), no move is possible, so the terminal outcome is determined only by the flag:
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
For \(r>0\), every legal move chooses some \(x\in[1,r]\), changes the flag by \(t(x)\), and leaves remainder \(r-x\). Oscar uses existential choice, Eric universal choice, so
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
The starting position for a given number \(r\) is \(O_{t(r)}(r)\). Therefore \(r\) contributes to the required sum exactly when \(O_{t(r)}(r)=0\).
The four-state system collapses neatly. From the recurrence above, one obtains
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$$
So it is enough to study the two Oscar-to-move losing sets
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
The final answer is the sum over
$$L=\{r\ge 1: r\in L_{t(r)}\}.$$
This already matches the brute-force tables: the implementation computes the four boolean state arrays, but the actual losing positions depend only on which of the two parity-indexed Oscar states fails.
The parity sequence \(t(x)\) is the Thue-Morse sequence, and powers of \(4\) are the natural scale because
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
Digits \(1\) and \(2\) in base \(4\) contribute odd popcount parity, while digits \(0\) and \(3\) contribute even parity. This is why the losing pattern repeats blockwise.
Now partition the positive integers into alternating base-4 layers:
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
The exact pattern revealed by the brute-force tables and used by the fast solver is:
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
and for the even layers there exists an offset set \(E_k\subseteq[0,4^k-1]\) such that
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
The first few offset sets are
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
When we pass from the even layer at scale \(4^k\) to the next even layer at scale \(4^{k+1}\), the losing offsets follow a precise self-similar rule:
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
Informally, one copy of the previous offsets survives unchanged, another copy is shifted by \(4^k\), and the old extreme point \(4^k-1\) is replaced by the new odd-layer endpoint \(4^{k+1}-1\).
Define
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$$
Then \(N_0=1\), \(T_0=0\), and the set recurrence gives
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$$
Hence
$$N_k=2^k,$$
which is exactly the doubling behavior used by the linear solver.
The total contribution of the even layer \(I_k^{\mathrm{even}}\) is
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$$
The total contribution of the odd layer \(I_k^{\mathrm{odd}}\) is simply
$$4^{k+1}-1.$$
Therefore the answer is obtained by scanning the layers from left to right. If \(n\) is even, the endpoint \(2^n=4^{n/2}\) belongs to the next even layer and must be added separately. This is why the final formula in the implementation has a last \(2^n\) correction exactly when \(n\) is even.
Here we need all losing positions in \([1,64]\).
The odd layers contribute only their endpoints:
$$3,\qquad 15,\qquad 63.$$
The even layers are built from the offset sets:
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
Because \(n=6\) is even, we also add the endpoint
$$2^6=64.$$
So the losing positions are
$$1,3,4,7,15,16,19,20,31,63,64,$$
and their sum is
$$1+3+4+7+15+16+19+20+31+63+64=243.$$
This matches the brute-force dynamic program.
The C++, Python, and Java implementations all use the same fast layer recurrence. They iterate once over the layer index, maintain the current number of even-layer offsets, the sum of those offsets, and the current power \(4^k\), and then add either
$$N_k4^k+T_k$$
for an even layer or
$$4^{k+1}-1$$
for an odd layer. After every even layer, the offset statistics are updated with
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k.$$
At the end, if \(n\) is even, the implementation adds \(2^n\) with modular exponentiation. The C++ version also contains a brute-force verifier for small exponents and checks the recurrence against known checkpoints such as \(n=4\mapsto 46\) and \(n=12\mapsto 54532\).
The brute-force verifier fills game states for every \(r\le 2^n\) and scans every legal move \(x\le r\), so its running time is \(O(4^n)\) and its memory use is \(O(2^n)\). The optimized solver never expands the position graph. It performs one constant-time update per layer, so it runs in \(O(n)\) time and \(O(1)\) memory.
Für jeden Startwert \(r\) werden die erlaubten Züge nach der Parität der Hamming-Gewicht-Funktion des abgezogenen Werts klassifiziert:
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
Gesucht ist die Summe aller \(r\in[1,2^n]\), für die Oscar bei perfektem Spiel verliert. Das vollständige Spiel-DP bestätigt kleine Fälle, aber die eigentliche Lösung nutzt eine starre Struktur auf Basis von Potenzen von \(4\) und rechnet modulo \(10^9+7\).
Die schnelle Lösung entsteht aus der Form der Verlustpositionen, nicht aus dem Durchprobieren aller Züge bis \(2^n\).
Für einen Restwert \(r\) verfolgt die Herleitung zwei Informationen: wer am Zug ist und einen binären Marker \(q\in\{0,1\}\), der die für das Endergebnis relevante laufende Parität trägt. Sei
$$O_q(r)\in\{0,1\}$$
die Aussage „Oscar gewinnt bei Rest \(r\), wenn Oscar am Zug ist und der Marker \(q\) ist“, und entsprechend
$$E_q(r)\in\{0,1\}$$
für Eric am Zug.
Für \(r=0\) gibt es keinen legalen Zug mehr, also hängt das Resultat nur vom Marker ab:
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
Für \(r>0\) wählt ein Zug ein \(x\in[1,r]\), verändert den Marker um \(t(x)\) und lässt \(r-x\) übrig. Oscar maximiert, Eric minimiert, daher
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
Der Startzustand für eine Zahl \(r\) ist \(O_{t(r)}(r)\). Genau dann trägt \(r\) zur gesuchten Summe bei, wenn \(O_{t(r)}(r)=0\) gilt.
Das Vier-Zustands-System vereinfacht sich sofort. Aus der Rekursion folgt
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$$
Es genügt also, die beiden Verlustmengen für Oscar am Zug zu betrachten:
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
Die tatsächlich gesuchten Zahlen sind damit
$$L=\{r\ge 1: r\in L_{t(r)}\}.$$
Das entspricht genau den Brute-Force-Tabellen: berechnet werden vier boolesche Zustände, aber die Verlustpositionen hängen letztlich nur davon ab, welcher der beiden Oscar-Zustände scheitert.
Die Folge \(t(x)\) ist die Thue-Morse-Folge. Potenzen von \(4\) sind die natürliche Skala, denn
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
Die Basis-4-Ziffern \(1\) und \(2\) liefern ungerade Popcount-Parität, \(0\) und \(3\) gerade. Deshalb wiederholt sich das Muster blockweise.
Wir teilen die positiven Zahlen in abwechselnde Basis-4-Schichten:
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
Das exakte Muster aus den Brute-Force-Tabellen, das auch der schnelle Solver verwendet, lautet:
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
und für die geraden Schichten existiert eine Offsetsmenge \(E_k\subseteq[0,4^k-1]\) mit
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
Die ersten Mengen sind
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
Beim Übergang von der geraden Schicht auf Skala \(4^k\) zur nächsten geraden Schicht auf Skala \(4^{k+1}\) gelten für die Verlust-Offsets exakt die Regeln
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
Anschaulich bleibt eine Kopie der alten Offsets erhalten, eine zweite Kopie wird um \(4^k\) verschoben, und der bisherige Extrempunkt \(4^k-1\) wird durch den neuen ungeraden Endpunkt \(4^{k+1}-1\) ersetzt.
Definiere nun
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$$
Dann gilt \(N_0=1\), \(T_0=0\), und aus der Mengenrekursion folgt
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$$
Somit ist
$$N_k=2^k,$$
genau das Verdopplungsverhalten, das der lineare Solver benutzt.
Der Gesamtbeitrag der geraden Schicht \(I_k^{\mathrm{even}}\) ist
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$$
Der Beitrag der ungeraden Schicht \(I_k^{\mathrm{odd}}\) ist einfach
$$4^{k+1}-1.$$
Damit erhält man die Antwort, indem man die Schichten von links nach rechts aufsummiert. Ist \(n\) gerade, dann liegt der Endpunkt \(2^n=4^{n/2}\) bereits in der nächsten geraden Schicht und muss separat addiert werden. Daher erscheint in der Implementierung genau für gerade \(n\) ein letzter Korrekturterm \(2^n\).
Gesucht sind alle Verlustpositionen in \([1,64]\).
Die ungeraden Schichten liefern nur ihre Endpunkte:
$$3,\qquad 15,\qquad 63.$$
Die geraden Schichten werden aus den Offsetmengen aufgebaut:
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
Da \(n=6\) gerade ist, kommt außerdem der Endpunkt hinzu:
$$2^6=64.$$
Damit sind die Verlustpositionen
$$1,3,4,7,15,16,19,20,31,63,64,$$
und ihre Summe beträgt
$$1+3+4+7+15+16+19+20+31+63+64=243.$$
Das stimmt mit dem vollständigen Spiel-DP überein.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe schnelle Schichtenrekursion. Sie laufen einmal über den Schichtindex, halten die aktuelle Anzahl der Offsets in einer geraden Schicht, deren Summenwert und die aktuelle Potenz \(4^k\) vor und addieren dann entweder
$$N_k4^k+T_k$$
für eine gerade Schicht oder
$$4^{k+1}-1$$
für eine ungerade Schicht. Nach jeder geraden Schicht werden die Offset-Statistiken mit
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k$$
aktualisiert. Am Ende addiert die Implementierung bei geradem \(n\) noch \(2^n\) per modularer Potenzierung. Die C++-Version enthält zusätzlich einen Brute-Force-Prüfer für kleine Exponenten und verifiziert die Rekursion etwa mit \(n=4\mapsto 46\) und \(n=12\mapsto 54532\).
Der Brute-Force-Prüfer füllt für jedes \(r\le 2^n\) alle Spielzustände und betrachtet jeden legalen Zug \(x\le r\). Daher benötigt er \(O(4^n)\) Zeit und \(O(2^n)\) Speicher. Der optimierte Solver expandiert den Zustandsgraphen nie vollständig. Er führt pro Schicht nur ein konstantes Update aus und läuft deshalb in \(O(n)\) Zeit und \(O(1)\) Speicher.
Her başlangıç değeri \(r\) için hamleler, çıkarılan sayının Hamming ağırlığının paritesine göre iki sınıfa ayrılır:
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
İstenen şey, \(r\in[1,2^n]\) aralığında Oscar'ın kusursuz oyunda kaybettiği tüm değerlerin toplamıdır. Uygulamalardaki tam dinamik program küçük \(n\) için oyunu doğrular; asıl çözüm ise taban-4 katmanlarında ortaya çıkan düzenli yapıyı kullanıp sonucu \(10^9+7\) modunda hesaplar.
Hızlı çözüm, \(2^n\) seviyesine kadar tüm hamleleri denemekten değil, kayıp konumların şeklini anlamaktan gelir.
Kalan değer \(r\) için türetim iki bilgiyi izler: sıranın kimde olduğu ve sonucu etkileyen yürüyen pariteyi tutan ikili bir bayrak \(q\in\{0,1\}\). Şunu tanımlayalım:
$$O_q(r)\in\{0,1\}$$
“Kalan \(r\) iken sıra Oscar'daysa ve bayrak \(q\) ise Oscar kazanır” anlamına gelsin. Benzer biçimde
$$E_q(r)\in\{0,1\}$$
ifadesi sıra Eric'teyken aynı durumu göstersin.
\(r=0\) olduğunda artık hamle yoktur; bu yüzden sonuç yalnızca bayrağa bağlıdır:
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
\(r>0\) için her hamle \(x\in[1,r]\) seçer, bayrağı \(t(x)\) kadar çevirir ve geride \(r-x\) bırakır. Oscar varoluşsal seçim yapar, Eric evrensel seçim yapar; dolayısıyla
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
Belirli bir \(r\) için başlangıç durumu \(O_{t(r)}(r)\) olur. O halde \(r\), tam olarak \(O_{t(r)}(r)=0\) ise toplama katkı yapar.
Dört durumlu sistem hemen sadeleşir. Yukarıdaki yinelemeden
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r)$$
elde edilir. Böylece sadece Oscar sırasındaki iki kayıp kümesini incelemek yeterlidir:
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
Nihai cevapta toplanan değerler ise
$$L=\{r\ge 1: r\in L_{t(r)}\}$$
kümesidir. Bu, brute-force tablolarıyla da uyumludur: hesaplama dört boole durumu üzerinden ilerler ama gerçek kayıp konumlar yalnızca Oscar'ın hangi parite durumunda kazanamadığına bağlıdır.
\(t(x)\) dizisi Thue-Morse dizisidir. Doğal ölçek \(4\) kuvvetleridir, çünkü
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
Taban-4'te \(1\) ve \(2\) rakamları tek popcount paritesi, \(0\) ve \(3\) rakamları çift popcount paritesi üretir. Bu yüzden kayıp deseni blok bazında kendini tekrar eder.
Pozitif tamsayıları şu dönüşümlü taban-4 katmanlarına ayıralım:
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
Brute-force tablolarının gösterdiği ve hızlı çözücünün kullandığı tam yapı şudur:
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
ve çift katmanlar için \(E_k\subseteq[0,4^k-1]\) olacak şekilde
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
İlk birkaç ofset kümesi şöyledir:
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
\(4^k\) ölçeğindeki çift katmandan \(4^{k+1}\) ölçeğindeki bir sonraki çift katmana geçerken kayıp ofsetler şu tam öz-benzer kurala uyar:
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
Sezgisel olarak eski ofsetlerin bir kopyası aynen kalır, ikinci bir kopya \(4^k\) kadar ötelenir ve önceki uç nokta \(4^k-1\), yeni tek-katman ucu olan \(4^{k+1}-1\) ile yer değiştirir.
Şimdi
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e$$
tanımını yapalım. O zaman \(N_0=1\), \(T_0=0\) ve küme yinelemesinden
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k$$
sonucu çıkar. Böylece
$$N_k=2^k$$
olur; bu da doğrusal çözücünün kullandığı tam ikiye katlanma davranışıdır.
\(I_k^{\mathrm{even}}\) çift katmanının toplam katkısı
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k$$
olur. \(I_k^{\mathrm{odd}}\) tek katmanının katkısı ise yalnızca
$$4^{k+1}-1$$
değeridir. Sonuç olarak cevap, katmanlar soldan sağa taranarak bulunur. Eğer \(n\) çiftse, uç nokta \(2^n=4^{n/2}\) bir sonraki çift katmana ait olur ve ayrıca eklenmelidir. Kodun yalnızca çift \(n\) için son bir \(2^n\) düzeltmesi yapmasının nedeni budur.
Bu durumda \([1,64]\) aralığındaki tüm kayıp konumlar gerekir.
Tek katmanlar yalnızca uç noktalarını verir:
$$3,\qquad 15,\qquad 63.$$
Çift katmanlar ofset kümelerinden kurulur:
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
\(n=6\) çift olduğu için uç nokta da eklenir:
$$2^6=64.$$
Dolayısıyla kayıp konumlar
$$1,3,4,7,15,16,19,20,31,63,64$$
olur ve toplamları
$$1+3+4+7+15+16+19+20+31+63+64=243$$
çıkar. Bu değer brute-force dinamik programıyla aynıdır.
C++, Python ve Java uygulamaları aynı hızlı katman yinelemesini kullanır. Katman indisi üzerinde bir kez dolaşırlar; o andaki çift katman ofset sayısını, ofset toplamını ve mevcut \(4^k\) kuvvetini tutarlar; sonra da ya
$$N_k4^k+T_k$$
ifadesini çift katman için ya da
$$4^{k+1}-1$$
ifadesini tek katman için sonuca eklerler. Her çift katmandan sonra ofset istatistikleri
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k$$
ile güncellenir. Sonda \(n\) çiftse, uygulama modüler üs alma ile \(2^n\) ekler. C++ sürümü ayrıca küçük üsler için tam brute-force doğrulaması içerir ve yinelemeyi \(n=4\mapsto 46\) ile \(n=12\mapsto 54532\) gibi kontrol noktalarıyla sınar.
Brute-force doğrulayıcı, her \(r\le 2^n\) için tüm oyun durumlarını doldurur ve her yasal \(x\le r\) hamlesine bakar; dolayısıyla çalışma süresi \(O(4^n)\), bellek kullanımı \(O(2^n)\) olur. Optimize edilmiş çözücü durum grafiğini hiç açmaz. Katman başına sabit sayıda güncelleme yaptığı için \(O(n)\) zamanda ve \(O(1)\) bellekte çalışır.
Para cada valor inicial \(r\), los movimientos se separan según la paridad del peso de Hamming del número restado:
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
Hay que sumar todos los \(r\in[1,2^n]\) para los que Oscar pierde con juego perfecto. El programa de fuerza bruta valida los casos pequeños, mientras que la solución principal explota una estructura muy rígida por capas en base \(4\) y trabaja módulo \(10^9+7\).
La solución rápida no nace de probar todos los movimientos hasta \(2^n\), sino de describir exactamente la forma de las posiciones perdedoras.
Para un resto \(r\), la derivación sigue dos datos: de quién es el turno y un bit \(q\in\{0,1\}\) que guarda la paridad acumulada relevante para el resultado final. Definimos
$$O_q(r)\in\{0,1\}$$
como “Oscar gana desde resto \(r\) si juega Oscar y la bandera vale \(q\)”, y
$$E_q(r)\in\{0,1\}$$
como el estado análogo cuando juega Eric.
En \(r=0\) ya no hay movimientos, así que el resultado depende solo de la bandera:
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
Para \(r>0\), cada jugada elige un \(x\in[1,r]\), cambia la bandera en \(t(x)\) y deja resto \(r-x\). Oscar busca una jugada ganadora; Eric intenta impedirla. Por tanto,
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
La posición inicial asociada a un número \(r\) es \(O_{t(r)}(r)\). Así, \(r\) aporta a la suma buscada exactamente cuando \(O_{t(r)}(r)=0\).
El sistema de cuatro estados se simplifica enseguida. A partir de la recurrencia anterior se obtiene
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$$
Por eso basta estudiar los dos conjuntos perdedores con Oscar al turno:
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
El conjunto que realmente interesa es
$$L=\{r\ge 1: r\in L_{t(r)}\}.$$
Esto coincide con las tablas de fuerza bruta: la implementación lleva cuatro estados booleanos, pero las posiciones perdedoras finales dependen solo de cuál de los dos estados de Oscar falla.
La sucesión \(t(x)\) es la sucesión de Thue-Morse. Las potencias de \(4\) son la escala natural porque
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
Los dígitos \(1\) y \(2\) en base \(4\) aportan paridad impar de popcount; \(0\) y \(3\), paridad par. Por eso el patrón se repite por bloques.
Partimos los enteros positivos en capas alternas:
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
El patrón exacto que muestran las tablas y explota la solución rápida es:
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
y para las capas pares existe un conjunto de desplazamientos \(E_k\subseteq[0,4^k-1]\) tal que
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
Los primeros conjuntos son
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
Al pasar de la capa par a escala \(4^k\) a la siguiente capa par a escala \(4^{k+1}\), los desplazamientos perdedores siguen la regla exacta
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
En palabras: una copia de los desplazamientos anteriores permanece intacta, otra aparece desplazada en \(4^k\), y el antiguo extremo \(4^k-1\) es reemplazado por el nuevo extremo impar \(4^{k+1}-1\).
Definimos entonces
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$$
Con \(N_0=1\) y \(T_0=0\), la recurrencia de conjuntos da
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$$
En consecuencia,
$$N_k=2^k,$$
que es exactamente la duplicación usada por el solucionador lineal.
La contribución total de la capa par \(I_k^{\mathrm{even}}\) es
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$$
La contribución de la capa impar \(I_k^{\mathrm{odd}}\) es simplemente
$$4^{k+1}-1.$$
Por tanto, la respuesta se obtiene recorriendo las capas de izquierda a derecha. Si \(n\) es par, el extremo \(2^n=4^{n/2}\) pertenece ya a la siguiente capa par y hay que añadirlo aparte. Por eso la implementación suma un término final \(2^n\) exactamente cuando \(n\) es par.
Aquí necesitamos todas las posiciones perdedoras en \([1,64]\).
Las capas impares aportan solo sus extremos:
$$3,\qquad 15,\qquad 63.$$
Las capas pares se construyen con los desplazamientos:
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
Como \(n=6\) es par, añadimos también
$$2^6=64.$$
Así, las posiciones perdedoras son
$$1,3,4,7,15,16,19,20,31,63,64,$$
y su suma vale
$$1+3+4+7+15+16+19+20+31+63+64=243.$$
Este valor coincide con el DP de fuerza bruta.
Las implementaciones en C++, Python y Java usan exactamente la misma recurrencia por capas. Recorren una sola vez el índice de capa, mantienen el número actual de desplazamientos de capa par, la suma de esos desplazamientos y la potencia \(4^k\), y añaden o bien
$$N_k4^k+T_k$$
para una capa par, o bien
$$4^{k+1}-1$$
para una capa impar. Después de cada capa par, actualizan las estadísticas con
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k.$$
Al final, si \(n\) es par, la implementación añade \(2^n\) mediante exponenciación modular. La versión en C++ también incluye un verificador de fuerza bruta para exponentes pequeños y comprueba la recurrencia con puntos de control como \(n=4\mapsto 46\) y \(n=12\mapsto 54532\).
El verificador de fuerza bruta rellena estados para cada \(r\le 2^n\) y examina todos los movimientos legales \(x\le r\), por lo que tarda \(O(4^n)\) y usa \(O(2^n)\) memoria. El solucionador optimizado nunca expande el grafo completo de posiciones. Hace una actualización de tiempo constante por capa, así que corre en \(O(n)\) tiempo y \(O(1)\) memoria.
对每个起始值 \(r\)，合法操作按照被减去的数 \(x\) 的二进制中 \(1\) 的个数奇偶性分成两类：
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
题目要求把区间 \([1,2^n]\) 中所有会让 Oscar 在最优对弈下失败的 \(r\) 全部加起来。实现中的暴力动态规划负责验证小规模情形，而真正用于大规模 \(n\) 的方法，是利用一种严格的四进制分层结构，在模 \(10^9+7\) 下线性推进。
快速算法的关键不是枚举到 \(2^n\) 的所有局面，而是先刻画失败位置究竟长成什么样。
对于剩余值 \(r\)，推导里需要跟踪两件事：当前轮到谁行动，以及一个二值标记 \(q\in\{0,1\}\)，它记录与最终胜负相关的累计奇偶信息。定义
$$O_q(r)\in\{0,1\}$$
表示“当剩余值为 \(r\)、轮到 Oscar、且标记为 \(q\) 时，Oscar 是否必胜”；再定义
$$E_q(r)\in\{0,1\}$$
表示同样的状态，只是轮到 Eric 行动。
当 \(r=0\) 时已经没有合法操作，所以终局只由标记决定：
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
当 \(r>0\) 时，一步操作就是选择某个 \(x\in[1,r]\)，把标记按 \(t(x)\) 翻转，并把剩余值变成 \(r-x\)。Oscar 追求存在一个赢法，Eric 则要求所有后续都对 Oscar 有利，因此递推写成
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
对给定起点 \(r\)，真正的起始状态是 \(O_{t(r)}(r)\)。因此，当且仅当 \(O_{t(r)}(r)=0\) 时，这个 \(r\) 会被计入答案。
上面的四状态递推其实可以大幅简化。由定义直接推出
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$$
也就是说，只需要研究 Oscar 先手时的两个失败集合：
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
最终真正要加总的集合就是
$$L=\{r\ge 1: r\in L_{t(r)}\}.$$
这和暴力程序的行为完全一致。实现虽然维护了四个布尔状态表，但真正决定一个数是否为失败位置的，只是 Oscar 在哪一个奇偶标记下无法取胜。
序列 \(t(x)\) 正是 Thue-Morse 序列。之所以自然地出现 \(4\) 的幂，是因为对任意 \(0\le y<4^k\) 都有
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
原因是四进制前导数字 \(1\) 和 \(2\) 会贡献奇数个二进制 \(1\)，而 \(0\) 和 \(3\) 会贡献偶数个二进制 \(1\)。因此，失败位置会在长度为 \(4^k\) 的块中呈现自相似结构。
把正整数按下面的两类交替区间划分：
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
暴力表格揭示、快速算法也正是利用了以下精确模式：
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
而在偶层中，存在一个偏移集合 \(E_k\subseteq[0,4^k-1]\)，使得
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
前几层的偏移集合具体是
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
这说明偶层不是胡乱分布的，而是由较小尺度的结构递归生成出来的。
从尺度 \(4^k\) 的偶层走到尺度 \(4^{k+1}\) 的下一偶层时，失败偏移满足严格的递推规则：
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
直观地说，旧偏移会保留一份原样副本；再复制出一份并整体右移 \(4^k\)；但是旧的最右端点 \(4^k-1\) 不再以平移方式出现，而是“抬升”为新奇层中的唯一端点 \(4^{k+1}-1\)。
为了让实现只做常数次更新，引入两个统计量：
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$$
由初值 \(N_0=1\)、\(T_0=0\) 以及上面的集合递推，可以直接得到
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$$
于是
$$N_k=2^k,$$
也就是每升一级偶层，偏移个数恰好翻倍。这正是线性算法中的核心递推。
偶层 \(I_k^{\mathrm{even}}\) 的总贡献为
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$$
奇层 \(I_k^{\mathrm{odd}}\) 只有一个失败位置，因此它的贡献就是
$$4^{k+1}-1.$$
这样一来，答案只需沿着这些层从左到右累加即可。如果 \(n\) 是偶数，那么终点
$$2^n=4^{n/2}$$
恰好落在下一层偶层的起点，它本身也是失败位置，所以必须在最后单独补上。这也解释了实现中为什么只在偶数 \(n\) 时再加一个 \(2^n\) 修正项。
现在要找出区间 \([1,64]\) 中所有失败位置。
奇层的贡献很简单，只是它们的右端点：
$$3,\qquad 15,\qquad 63.$$
偶层则由偏移集合给出：
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
因为 \(n=6\) 是偶数，还要额外加入终点
$$2^6=64.$$
所以全部失败位置为
$$1,3,4,7,15,16,19,20,31,63,64,$$
它们的和是
$$1+3+4+7+15+16+19+20+31+63+64=243.$$
这个结果与暴力动态规划完全一致。
C++、Python 和 Java 三份实现都采用同一套快速分层递推。它们不会枚举每个 \(r\)，而是顺次扫描层编号，只维护当前偶层的偏移个数、偏移和以及当前的 \(4^k\)。遇到偶层时加上
$$N_k4^k+T_k,$$
遇到奇层时加上
$$4^{k+1}-1.$$
每处理完一个偶层，就用
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k$$
更新统计量。循环结束后，若 \(n\) 为偶数，再用模幂运算补上 \(2^n\)。其中 C++ 版本还保留了一个小规模暴力验证器，并用 \(n=4\mapsto 46\)、\(n=12\mapsto 54532\) 这类校验值来确认递推正确。
暴力验证器需要对每个 \(r\le 2^n\) 枚举所有合法减法 \(x\le r\)，因此时间复杂度是 \(O(4^n)\)，空间复杂度是 \(O(2^n)\)。优化后的主算法完全不展开整个博弈图，只对每一层做常数次更新，所以总时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)。
Для каждого стартового значения \(r\) разрешённые ходы делятся по чётности веса Хэмминга вычитаемого числа:
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
Нужно просуммировать все \(r\in[1,2^n]\), в которых Oscar проигрывает при оптимальной игре. Полный динамический перебор в реализации служит только для проверки малых случаев; основное решение использует жёсткую послойную структуру по степеням \(4\) и считает ответ по модулю \(10^9+7\).
Быстрое решение получается не из перебора всех ходов до \(2^n\), а из точного описания проигрышных позиций.
Для остатка \(r\) нужно хранить две вещи: чей сейчас ход и двоичный флаг \(q\in\{0,1\}\), отражающий накопленную чётность, важную для финального исхода. Обозначим через
$$O_q(r)\in\{0,1\}$$
утверждение «Oscar выигрывает из остатка \(r\), если сейчас ход Oscar и флаг равен \(q\)», а через
$$E_q(r)\in\{0,1\}$$
аналогичное состояние, когда ходит Eric.
При \(r=0\) хода уже нет, поэтому результат зависит только от флага:
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
Если \(r>0\), ход выбирает число \(x\in[1,r]\), меняет флаг на \(t(x)\) и оставляет остаток \(r-x\). Oscar ищет хотя бы один выигрышный переход, Eric требует, чтобы все переходы были хороши для Oscar. Поэтому
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
Стартовое состояние для числа \(r\) равно \(O_{t(r)}(r)\). Значит, число \(r\) входит в ответ тогда и только тогда, когда \(O_{t(r)}(r)=0\).
Система из четырёх состояний упрощается очень сильно. Из рекуррентных формул следует
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$$
Следовательно, достаточно изучать только два проигрышных множества для состояний «ходит Oscar»:
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
Итоговое множество чисел, которые нужно суммировать, равно
$$L=\{r\ge 1: r\in L_{t(r)}\}.$$
Это полностью согласуется с таблицами полного DP: реализация действительно хранит четыре булевых состояния, но для ответа важно только, в каком из двух состояний Oscar не может обеспечить победу.
Последовательность \(t(x)\) есть последовательность Туэ-Морса. Степени \(4\) возникают естественно, потому что
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
Цифры \(1\) и \(2\) в записи по основанию \(4\) дают нечётную popcount-парность, а \(0\) и \(3\) дают чётную. Поэтому рисунок проигрышных позиций повторяется блоками.
Разобьём положительные числа на чередующиеся слои:
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
Точная структура, которую показывают таблицы и использует быстрый алгоритм, такова:
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
а для чётных слоёв существует множество сдвигов \(E_k\subseteq[0,4^k-1]\), для которого
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
Первые значения таковы:
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
При переходе от чётного слоя масштаба \(4^k\) к следующему чётному слою масштаба \(4^{k+1}\) проигрышные сдвиги подчиняются точной рекурсии
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
То есть одна копия старого множества остаётся на месте, вторая копия сдвигается на \(4^k\), а прежняя крайняя точка \(4^k-1\) заменяется новой одиночной точкой \(4^{k+1}-1\) из нечётного слоя.
Введём агрегаты
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$$
Тогда \(N_0=1\), \(T_0=0\), и из рекурсии множеств получаем
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$$
Следовательно,
$$N_k=2^k,$$
что и даёт линейный рост числа параметров в быстром решении.
Полный вклад чётного слоя \(I_k^{\mathrm{even}}\) равен
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$$
Вклад нечётного слоя \(I_k^{\mathrm{odd}}\) равен просто
$$4^{k+1}-1.$$
Значит, ответ получается последовательным суммированием слоёв слева направо. Если \(n\) чётно, то конечная точка
$$2^n=4^{n/2}$$
лежит уже в следующем чётном слое, поэтому её нужно добавить отдельно. Именно отсюда в реализации появляется финальная поправка \(2^n\) только для чётных \(n\).
Нужно найти все проигрышные позиции в \([1,64]\).
Нечётные слои дают только свои правые концы:
$$3,\qquad 15,\qquad 63.$$
Чётные слои строятся из множеств сдвигов:
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
Так как \(n=6\) чётно, отдельно добавляем
$$2^6=64.$$
В итоге проигрышные позиции:
$$1,3,4,7,15,16,19,20,31,63,64,$$
а их сумма равна
$$1+3+4+7+15+16+19+20+31+63+64=243.$$
Это полностью совпадает с полным динамическим перебором.
Реализации на C++, Python и Java используют одну и ту же быструю рекурсию по слоям. Они один раз проходят по индексу слоя, хранят текущее число сдвигов в чётном слое, сумму этих сдвигов и текущую степень \(4^k\), а затем прибавляют либо
$$N_k4^k+T_k$$
для чётного слоя, либо
$$4^{k+1}-1$$
для нечётного. После каждого чётного слоя статистики обновляются по формулам
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k.$$
В конце, если \(n\) чётно, добавляется \(2^n\) через быстрое возведение в степень по модулю. В версии на C++ дополнительно есть проверочный полный DP для малых степеней и контрольные значения вроде \(n=4\mapsto 46\) и \(n=12\mapsto 54532\).
Проверочный полный DP заполняет состояния для каждого \(r\le 2^n\) и рассматривает все допустимые ходы \(x\le r\), поэтому работает за \(O(4^n)\) и использует \(O(2^n)\) памяти. Оптимизированный алгоритм никогда не раскрывает весь граф позиций. Он делает только константное число операций на слой, то есть требует \(O(n)\) времени и \(O(1)\) памяти.
لكل قيمة ابتدائية \(r\)، تُقسَّم النقلات بحسب زوجية عدد الواحدات في التمثيل الثنائي للعدد المطروح:
$$t(x)=\operatorname{popcount}(x)\bmod 2.$$
المطلوب هو جمع كل القيم \(r\in[1,2^n]\) التي يخسر فيها Oscar عند اللعب الأمثل. البرمجة الديناميكية الكاملة تُستخدم فقط للتحقق من الحالات الصغيرة، أما الحل الفعلي فيعتمد على بنية طبقية صارمة مرتبطة بقوى العدد \(4\)، ويحسب الناتج modulo \(10^9+7\).
الحل السريع لا يأتي من تعداد جميع النقلات حتى \(2^n\)، بل من فهم الشكل الدقيق لمواضع الخسارة.
عند قيمة متبقية \(r\)، نحتاج إلى تتبع معلومتين: من صاحب الدور، وراية ثنائية \(q\in\{0,1\}\) تسجل الزوجية التراكمية المؤثرة في النتيجة النهائية. نعرّف
$$O_q(r)\in\{0,1\}$$
بمعنى: “هل يستطيع Oscar الفوز من الباقي \(r\) إذا كان الدور له والراية تساوي \(q\)؟”، ونعرّف كذلك
$$E_q(r)\in\{0,1\}$$
للحالة المناظرة عندما يكون الدور لـ Eric.
عند \(r=0\) لا تبقى أي نقلة قانونية، لذا تعتمد النتيجة فقط على الراية:
$$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$$
إذا كان \(r>0\)، فإن كل نقلة تختار عددًا \(x\in[1,r]\)، وتغيّر الراية بمقدار \(t(x)\)، وتترك الباقي \(r-x\). Oscar يبحث عن نقلة رابحة، بينما Eric يفرض أن تكون كل النهايات اللاحقة مناسبة له، ولذلك نحصل على
$$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$$
حالة البداية للعدد \(r\) هي \(O_{t(r)}(r)\). لذلك فإن \(r\) يساهم في الجواب إذا وفقط إذا كان \(O_{t(r)}(r)=0\).
هذه المنظومة ذات الحالات الأربع تختزل بشكل أنيق. من العلاقة السابقة ينتج
$$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$$
إذًا يكفي أن ندرس مجموعتي الخسارة عندما يكون الدور على Oscar:
$$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$$
أما المجموعة التي تدخل فعلًا في المجموع النهائي فهي
$$L=\{r\ge 1: r\in L_{t(r)}\}.$$
وهذا يطابق تمامًا ما يظهر في الجداول الناتجة عن الحل الكامل: فالبرنامج يتابع أربع حالات منطقية، لكن موضع الخسارة النهائي يتحدد فقط بحسب أيٍّ من حالتي Oscar ذواتي الفهرسة بالزوجية يفشل.
المتتالية \(t(x)\) هي متتالية Thue-Morse. وتظهر قوى \(4\) طبيعيًا لأن
$$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$$
فالرقمان \(1\) و\(2\) في الكتابة بالأساس \(4\) يضيفان زوجية فردية لعدد الواحدات، بينما الرقمان \(0\) و\(3\) يضيفان زوجية زوجية. لهذا السبب يتكرر النمط على مستوى الكتل.
نقسّم الأعداد الموجبة إلى طبقات متعاقبة كما يلي:
$$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$$
النمط الدقيق الذي يكشفه الحل الكامل ويستغله الحل السريع هو:
$$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$$
أما الطبقات الزوجية فهناك مجموعة إزاحات \(E_k\subseteq[0,4^k-1]\) تحقق
$$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$$
وأول المجموعات هي
$$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$$
عند الانتقال من الطبقة الزوجية ذات المقياس \(4^k\) إلى الطبقة الزوجية التالية ذات المقياس \(4^{k+1}\)، تتبع إزاحات الخسارة العلاقة الدقيقة
$$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$$
بصورة حدسية: تبقى نسخة من الإزاحات القديمة كما هي، وتظهر نسخة ثانية بعد إزاحة مقدارها \(4^k\)، لكن النقطة القصوى القديمة \(4^k-1\) لا تنتقل كما هي، بل تُستبدل بالنقطة الطرفية الجديدة \(4^{k+1}-1\) في الطبقة الفردية.
لنحوّل هذا الوصف إلى تحديثات عددية، نعرّف
$$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$$
مع \(N_0=1\) و\(T_0=0\)، تعطي علاقة المجموعات
$$N_{k+1}=2N_k,$$
$$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$$
ومن ثم
$$N_k=2^k,$$
أي إن عدد الإزاحات يتضاعف في كل انتقال، وهذه هي البنية التي يستخدمها الحل الخطي مباشرة.
مساهمة الطبقة الزوجية \(I_k^{\mathrm{even}}\) تساوي
$$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$$
أما الطبقة الفردية \(I_k^{\mathrm{odd}}\) ففيها موضع خسارة واحد فقط، لذا مساهمتها هي
$$4^{k+1}-1.$$
إذًا يكفي المرور على الطبقات من اليسار إلى اليمين وجمع مساهماتها. وإذا كان \(n\) زوجيًا، فإن الطرف النهائي
$$2^n=4^{n/2}$$
يقع في بداية الطبقة الزوجية التالية، ولذلك يجب إضافته منفصلًا. ولهذا السبب بالضبط تضيف التطبيقات حدًا أخيرًا \(2^n\) فقط عندما يكون \(n\) زوجيًا.
نريد جميع مواضع الخسارة داخل \([1,64]\).
الطبقات الفردية تعطي فقط أطرافها اليمنى:
$$3,\qquad 15,\qquad 63.$$
والطبقات الزوجية تُبنى من مجموعات الإزاحة:
$$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$$
وبما أن \(n=6\) زوجي، نضيف أيضًا
$$2^6=64.$$
إذن مواضع الخسارة هي
$$1,3,4,7,15,16,19,20,31,63,64,$$
ومجموعها يساوي
$$1+3+4+7+15+16+19+20+31+63+64=243.$$
وهذا يطابق تمامًا ما ينتجه الحل الكامل بالبرمجة الديناميكية.
تستخدم تطبيقات C++ وPython وJava جميعها علاقة الطبقات نفسها. فهي لا تعدّد كل قيمة \(r\)، بل تمر مرة واحدة على فهرس الطبقة، وتحفظ عدد إزاحات الطبقة الزوجية الحالية، ومجموع تلك الإزاحات، وقيمة \(4^k\) الحالية، ثم تضيف إما
$$N_k4^k+T_k$$
للطبقة الزوجية، أو
$$4^{k+1}-1$$
للطبقة الفردية. وبعد كل طبقة زوجية، تُحدَّث الإحصاءات بواسطة
$$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k.$$
وفي النهاية، إذا كان \(n\) زوجيًا، تضيف الشيفرة \(2^n\) باستعمال الأس المعياري السريع. كما تحتوي نسخة C++ على متحقق brute-force للأسس الصغيرة وتطابق العلاقة مع نقاط فحص مثل \(n=4\mapsto 46\) و\(n=12\mapsto 54532\).
المتحقق الكامل يملأ الحالات لكل \(r\le 2^n\) ويفحص كل نقلة قانونية \(x\le r\)، لذلك زمنه \(O(4^n)\) وذاكرته \(O(2^n)\). أما الخوارزمية المحسنة فلا تبني مخطط الحالات كاملًا أبدًا، بل تنفذ تحديثًا ثابت الكلفة لكل طبقة، ولهذا تعمل في زمن \(O(n)\) وذاكرة \(O(1)\).