Start from a positive integer \(n\). One move removes a single decimal digit, keeps the remaining digits in their original order, and then discards any leading zeros that appear. If every digit has been removed, the next state is \(0\), and the player to move loses. The goal is to count how many starting values below \(10^{18}\) are winning positions for the first player.
The key simplification is that the exact nonzero digits never matter. Only the pattern of zero and nonzero positions matters, so the whole game can be compressed to a short binary mask and then lifted back to decimal numbers by a simple weight.
For an \(\ell\)-digit decimal number \(d_1d_2\cdots d_\ell\) with \(d_1\neq 0\), define a binary mask \(b_1b_2\cdots b_\ell\) by
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$$
Two numbers with the same mask have the same game tree. Deleting the \(i\)-th decimal digit deletes the \(i\)-th bit, and removing leading zeros depends only on where the first remaining \(1\) sits. So every state can be represented by a canonical binary string that is either empty or begins with \(1\).
If a mask contains \(t\) ones, it represents exactly \(9^t\) different decimal numbers, because each active position may hold any digit from \(1\) to \(9\), while the zero positions are forced.
Let \(\mathcal{W}(m)\) denote whether a canonical mask \(m\) is winning. Under normal play,
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
and the empty mask is losing. This is exactly the recurrence evaluated by the implementations.
Writing a nonempty canonical mask as \(1\,0^r\,u\), where \(r\ge 0\) counts the zeros immediately after the leading \(1\) and \(u\) is either empty or begins with \(1\), is the right way to read the recursion: deleting the first bit jumps directly to the suffix \(u\), while deleting any other bit leaves the leading \(1\) in place.
A short induction on the mask length gives two structural facts that explain why the search is so regular.
Every odd-length canonical mask is winning. For even lengths, the situation is much tighter: deleting any non-leading bit keeps the first bit equal to \(1\), so the child has odd length and is therefore winning. That means an even-length mask can only win by deleting its first bit.
Hence an even mask \(1\,0^r\,u\) is winning exactly when deleting the leading digit exposes a losing state, which is equivalent to saying that \(r\) is odd and \(u\) is either empty or itself a losing mask. The parity of the first zero run is the decisive invariant.
The mask \(1100\) is losing. Deleting one of the first two bits produces \(100\), and deleting one of the last two bits produces \(110\). Both children have odd length, so both are winning.
Now consider \(101100\). If the first bit is deleted, the raw result is \(01100\), which canonicalizes to \(1100\), a losing state. Every other deletion leaves a 5-bit state, and every 5-bit state is winning. So \(101100\) is winning. Since it has three ones, it corresponds to \(9^3=729\) actual six-digit numbers.
Let \(A_n\) be the weighted number of winning masks of length \(n\), and \(B_n\) the weighted number of losing masks of length \(n\). Set \(B_0=1\) for the empty mask. The total weight of all \(n\)-digit masks is \(9\cdot 10^{n-1}\).
Because every odd-length mask is winning,
$$A_{2m+1}=9\cdot 10^{2m}.$$
For even length \(2m\), a winning mask must have the form \(1\,0^{2k+1}\,u\), where \(u\) is empty or a losing even-length mask. The prefix contributes only the leading nonzero digit, so
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
Eliminating \(B_{2m}\) gives a one-step recurrence for the even lengths:
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
This solves to
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$$
The required answer is the cumulative total
$$W(10^E)=\sum_{n=1}^{E} A_n.$$
For even exponents, the sum collapses neatly to
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$$
The small checks follow immediately: \(W(10^2)=18\) and \(W(10^4)=1656\).
The C++, Python, and Java implementations solve the game directly on canonical masks of length at most \(18\). For each length \(\ell\), they enumerate every mask whose highest bit is \(1\), so each possible zero/nonzero pattern is considered exactly once.
Each state is evaluated by memoized recursion. The implementation tries every deletion position, builds the next mask with bit operations, shortens the apparent length while leading zeros remain, and stops as soon as it finds one losing child. Once a mask has been classified, that result is reused everywhere else.
After the win/loss table is known, the final accumulation is simple. A winning mask with \(t\) ones represents \(9^t\) decimal numbers, so the implementation adds the corresponding power of \(9\) for every winning mask of every length from \(1\) through \(18\).
There are \(2^{\ell-1}\) canonical masks of length \(\ell\), so the total number of states up to length \(E\) is
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E).$$
Each state tests up to \(\ell\) deletions, and each transition performs a short normalization step to remove leading zeros. A conservative upper bound for the direct recursive implementation is therefore \(O(E^2 2^E)\), with \(O(2^E)\) memory for the memo table.
For the actual target \(E=18\), this is tiny. The regular formulas above explain the structure of the answer, but the brute-force mask recursion is already more than fast enough.
Man startet mit einer positiven ganzen Zahl \(n\). Ein Zug entfernt genau eine Dezimalziffer, lässt die übrigen Ziffern in ihrer Reihenfolge stehen und streicht anschließend eventuell entstandene führende Nullen. Wenn keine Ziffer mehr übrig bleibt, ist der Folgezustand \(0\), und der Spieler am Zug verliert. Gesucht ist die Anzahl der Gewinnstellungen unter allen Startwerten kleiner als \(10^{18}\).
Der entscheidende Punkt ist, dass die konkreten von Null verschiedenen Ziffern keine Rolle spielen. Relevant ist nur das Muster aus Null- und Nichtnullpositionen. Damit lässt sich das Spiel auf kurze Binärmasken reduzieren und danach mit einer einfachen Gewichtung wieder auf Dezimalzahlen zurückheben.
Zu einer \(\ell\)-stelligen Zahl \(d_1d_2\cdots d_\ell\) mit \(d_1\neq 0\) definieren wir die Binärmaske \(b_1b_2\cdots b_\ell\) durch
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$$
Zwei Zahlen mit derselben Maske besitzen denselben Spielgraphen. Löscht man die \(i\)-te Dezimalziffer, so verschwindet genau das \(i\)-te Bit, und das Entfernen führender Nullen hängt nur davon ab, wo die erste verbleibende \(1\) steht. Jeder Zustand kann deshalb als kanonische Binärfolge dargestellt werden, die entweder leer ist oder mit \(1\) beginnt.
Enthält eine Maske \(t\) Einsen, so repräsentiert sie genau \(9^t\) Dezimalzahlen, denn jede aktive Position kann unabhängig eine Ziffer aus \(\{1,\dots,9\}\) tragen.
Sei \(\mathcal{W}(m)\) der Status einer kanonischen Maske \(m\). Unter der normalen Spielregel gilt
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
und die leere Maske ist eine Verluststellung. Genau diese Rekursion werten die Implementierungen aus.
Schreibt man eine nichtleere kanonische Maske in der Form \(1\,0^r\,u\), wobei \(r\ge 0\) die Zahl der Nullen direkt nach der führenden \(1\) bezeichnet und \(u\) entweder leer ist oder wieder mit \(1\) beginnt, dann wird die Struktur der Züge sichtbar: Das Löschen des ersten Bits springt direkt zum Suffix \(u\), während jede andere Löschung die führende \(1\) erhält.
Eine kurze Induktion über die Maskenlänge liefert zwei zentrale Tatsachen.
Jede kanonische Maske ungerader Länge ist eine Gewinnstellung. Bei gerader Länge ist die Lage viel strenger: Löscht man ein nichtführendes Bit, bleibt das erste Bit gleich \(1\), also hat der Nachfolger ungerade Länge und ist damit gewinnend. Eine gerade Maske kann daher nur dadurch gewinnen, dass man das erste Bit löscht.
Folglich ist eine gerade Maske \(1\,0^r\,u\) genau dann gewinnend, wenn das Löschen der führenden Ziffer eine Verluststellung freilegt. Das ist äquivalent dazu, dass \(r\) ungerade ist und \(u\) leer oder selbst eine Verlustmaske ist. Die Parität des ersten Nullblocks ist also die entscheidende Invariante.
Die Maske \(1100\) ist verlierend. Löscht man eines der ersten beiden Bits, erhält man \(100\); löscht man eines der letzten beiden Bits, erhält man \(110\). Beide Nachfolger haben ungerade Länge und sind deshalb gewinnend.
Betrachte nun \(101100\). Wenn das erste Bit gelöscht wird, entsteht zunächst \(01100\), was kanonisch zu \(1100\) wird, also zu einer Verluststellung. Jede andere Löschung führt auf eine 5-Bit-Maske, und jede 5-Bit-Maske ist gewinnend. Also ist \(101100\) gewinnend. Wegen seiner drei Einsen steht diese Maske für \(9^3=729\) echte sechsstellige Zahlen.
Sei \(A_n\) die gewichtete Anzahl gewinnender Masken der Länge \(n\), und \(B_n\) die gewichtete Anzahl verlierender Masken der Länge \(n\). Für die leere Maske setzen wir \(B_0=1\). Das Gesamtgewicht aller \(n\)-stelligen Masken ist \(9\cdot 10^{n-1}\).
Da jede Maske ungerader Länge gewinnt, gilt
$$A_{2m+1}=9\cdot 10^{2m}.$$
Bei gerader Länge \(2m\) muss eine Gewinnmaske die Form \(1\,0^{2k+1}\,u\) haben, wobei \(u\) leer oder eine verlierende Maske gerader Länge ist. Der Präfix liefert nur die führende Nichtnullziffer, also
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
Durch Eliminieren von \(B_{2m}\) erhält man eine einfache Rekursion für gerade Längen:
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
Diese Rekursion besitzt die geschlossene Form
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$$
Die gesuchte Anzahl ist dann die kumulierte Summe
$$W(10^E)=\sum_{n=1}^{E} A_n.$$
Für gerade Exponenten fällt sie zu
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$$
Damit erklären sich auch die kleinen Prüfwerte sofort: \(W(10^2)=18\) und \(W(10^4)=1656\).
Die C++-, Python- und Java-Implementierungen verwenden die geschlossene Form nicht direkt. Stattdessen lösen sie das Spiel exakt auf allen kanonischen Masken bis Länge \(18\). Für jede Länge \(\ell\) werden alle Masken mit führendem Bit \(1\) erzeugt, sodass jedes mögliche Null-/Nichtnullmuster genau einmal betrachtet wird.
Jeder Zustand wird mit Memoisierung rekursiv ausgewertet. Die Implementierung probiert jede Löschposition aus, konstruiert die Folgemaske mit Bitoperationen, reduziert die Länge so lange, wie vorn Nullen stehen, und bricht sofort ab, sobald ein verlierender Nachfolger gefunden wurde. Ein bereits klassifizierter Zustand wird danach überall wiederverwendet.
Ist die Gewinn-Verlust-Tabelle bekannt, ist die Endsumme einfach. Eine Gewinnmaske mit \(t\) Einsen repräsentiert \(9^t\) Dezimalzahlen, also wird für jede gewinnende Maske jeder Länge von \(1\) bis \(18\) genau diese Potenz von \(9\) addiert.
Es gibt \(2^{\ell-1}\) kanonische Masken der Länge \(\ell\), also insgesamt bis Länge \(E\)
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E)$$
Zustände. Jeder Zustand testet bis zu \(\ell\) Löschungen, und jeder Übergang enthält noch eine kurze Normalisierung zum Entfernen führender Nullen. Für die direkte rekursive Implementierung ist \(O(E^2 2^E)\) daher eine konservative obere Schranke, bei \(O(2^E)\) Speicher für die Memo-Tabelle.
Für das eigentliche Ziel \(E=18\) ist das sehr klein. Die Formeln erklären die Regelmäßigkeit der Antwort, aber die maskenbasierte Rekursion ist schon für sich schnell genug.
Pozitif bir \(n\) sayısıyla başlanır. Bir hamlede onluk yazımdaki tek bir basamak silinir, kalan basamaklar aynı sırada bırakılır ve oluşan baştaki sıfırlar atılır. Hiç basamak kalmazsa yeni durum \(0\) olur ve hamle sırası kendisinde olan oyuncu kaybeder. İstenen şey, \(10^{18}\)'den küçük başlangıç sayıları içinde ilk oyuncu için kazanan kaç durum bulunduğunu saymaktır.
Asıl sadeleştirme şudur: sıfır olmayan rakamların hangi değerler olduğu önemli değildir. Yalnızca hangi konumların sıfır, hangilerinin sıfır-dışı olduğu önemlidir. Böylece oyun kısa bir ikili maske üzerinde çözülür; sonra her \(1\) bitine 9 olasılık vererek yeniden onluk sayılara dönülür.
\(d_1d_2\cdots d_\ell\) biçimindeki ve \(d_1\neq 0\) koşulunu sağlayan \(\ell\) basamaklı bir sayı için
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0\end{cases}$$
tanımıyla \(b_1b_2\cdots b_\ell\) ikili maskesini kurarız. Aynı maskeye sahip iki sayının oyun ağacı aynıdır. Çünkü \(i\). basamağı silmek, \(i\). biti silmekle aynı deseni üretir; baştaki sıfırların atılması da yalnızca ilk kalan \(1\)'in nerede olduğuna bağlıdır. Bu yüzden her durum ya boştur ya da \(1\) ile başlayan kanonik bir ikili diziyle temsil edilir.
Maskede \(t\) tane \(1\) varsa, bu maske tam olarak \(9^t\) farklı onluk sayıyı temsil eder. Her aktif konuma \(1\) ile \(9\) arasında herhangi bir rakam bağımsız biçimde yerleştirilebilir.
Kanonik bir maske \(m\) için \(\mathcal{W}(m)\), durumun kazanıp kazanmadığını göstersin. Normal oyun kuralı altında
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
olur; boş maske ise kaybeden durumdur. Uygulamaların değerlendirdiği temel rekürans tam olarak budur.
Boş olmayan bir kanonik maskeyi \(1\,0^r\,u\) biçiminde yazmak yararlıdır. Burada \(r\ge 0\), baştaki \(1\)'den hemen sonraki sıfırların sayısıdır; \(u\) ise ya boştur ya da yeniden \(1\) ile başlar. İlk biti silmek doğrudan \(u\)'ya sıçrar; başka bir biti silmek ise baştaki \(1\)'i yerinde bırakır.
Maske uzunluğu üzerinden yapılan kısa bir indüksiyon iki temel yapısal gerçeği verir.
Tek uzunluklu her kanonik maske kazanan durumdur. Çift uzunlukta ise tablo çok daha dardır: baştaki bit dışındaki bir bit silinirse ilk bit yine \(1\) kalır, dolayısıyla oluşan çocuk durum tek uzunluklu olur ve zaten kazanandır. Demek ki çift uzunluklu bir maske ancak ilk biti silerek kazanabilir.
Buna göre çift uzunluklu \(1\,0^r\,u\) maskesi, ancak ve ancak baştaki bit silindiğinde bir kaybeden durum ortaya çıkıyorsa kazanır. Bu da \(r\)'nin tek olması ve \(u\)'nun boş ya da kaybeden bir maske olması ile eşdeğerdir. Kararı veren değişmez, ilk sıfır bloğunun paritesidir.
\(1100\) maskesi kaybedendir. İlk iki bitten biri silinirse \(100\), son iki bitten biri silinirse \(110\) elde edilir. Her iki çocuk durum da tek uzunluklu olduğu için kazanandır.
Şimdi \(101100\)'e bakalım. İlk bit silinirse ham sonuç \(01100\) olur; kanonikleştirince \(1100\) elde edilir ve bu kaybeden durumdur. Diğer tüm silmeler 5 bitli bir duruma gider; 5 bitli her durum kazanan olduğundan \(101100\) kazanan maskedir. İçinde üç tane \(1\) bulunduğu için bu maske gerçek hayatta \(9^3=729\) altı basamaklı sayıya karşılık gelir.
\(A_n\), uzunluğu \(n\) olan kazanan maskelerin ağırlıklı sayısı; \(B_n\) ise kaybeden maskelerin ağırlıklı sayısı olsun. Boş maske için \(B_0=1\) alırız. Uzunluğu \(n\) olan tüm maskelerin toplam ağırlığı \(9\cdot 10^{n-1}\)'dir.
Tek uzunluklu her maske kazandığı için
$$A_{2m+1}=9\cdot 10^{2m}.$$
Çift uzunluk \(2m\) için kazanan bir maske mutlaka \(1\,0^{2k+1}\,u\) biçimindedir; burada \(u\) boş ya da kaybeden bir çift uzunluklu maskedir. Öndeki parça yalnızca ilk sıfır-dışı basamağı katkıda bulunduğu için
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
\(B_{2m}\)'yi aradan çıkarınca çift uzunluklar için tek adımlı rekürans elde edilir:
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
Bunun kapalı biçimi
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}$$
olur. Sorudaki toplam ise
$$W(10^E)=\sum_{n=1}^{E} A_n$$
şeklindedir. \(E\) çift olduğunda bu toplam çok temiz biçimde
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}$$
haline gelir. Uygulamalarda kullanılan küçük doğrulamalar da buradan çıkar: \(W(10^2)=18\) ve \(W(10^4)=1656\).
C++, Python ve Java uygulamaları kapalı formülü doğrudan kullanmaz. Bunun yerine uzunluğu en fazla \(18\) olan tüm kanonik maskeler üzerinde oyunu doğrudan çözerler. Her \(\ell\) için en yüksek bit \(1\) sabitlenir, kalan \(\ell-1\) bit gezilir ve böylece her sıfır/sıfır-dışı deseni tam bir kez ele alınır.
Her durum memoizasyonlu özyineleme ile değerlendirilir. Uygulama bütün silme konumlarını dener, sonraki maskeyi bit işlemleriyle kurar, başta sıfır kaldığı sürece görünen uzunluğu küçültür ve kaybeden bir çocuk bulduğu anda durur. Bir maske bir kez sınıflandırıldıktan sonra her yerde yeniden kullanılır.
Kazanan-kaybeden tablosu hazır olduktan sonra son toplama basittir. İçinde \(t\) tane \(1\) olan kazanan bir maske \(9^t\) onluk sayıyı temsil ettiği için, uzunluğu \(1\) ile \(18\) arasındaki her kazanan maske için ilgili \(9\) kuvveti sonuca eklenir.
Uzunluğu \(\ell\) olan kanonik maske sayısı \(2^{\ell-1}\)'dir; dolayısıyla \(E\)'ye kadar toplam durum sayısı
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E)$$
olur. Her durumda en fazla \(\ell\) silme denenir ve her geçişte baştaki sıfırları atmak için kısa bir normalleştirme yapılır. Bu yüzden doğrudan özyinelemeli uygulama için muhafazakar üst sınır \(O(E^2 2^E)\), bellek kullanımı ise memo tablosu için \(O(2^E)\)'dir.
Gerçek hedef olan \(E=18\) için bu maliyet çok küçüktür. Yukarıdaki formüller cevabın yapısını açıklar; fakat saf maske reküransı zaten fazlasıyla hızlıdır.
Se parte de un entero positivo \(n\). En cada jugada se elimina una sola cifra decimal, se conservan las demás en el mismo orden y luego se descartan los ceros iniciales que aparezcan. Si ya no queda ninguna cifra, el estado siguiente es \(0\), y el jugador al que le toca mover pierde. La tarea consiste en contar cuántos valores iniciales menores que \(10^{18}\) son posiciones ganadoras para el primer jugador.
La simplificación decisiva es que los dígitos no nulos concretos no importan. Solo importa qué posiciones son cero y cuáles no. Por eso el juego puede resolverse sobre una máscara binaria corta y después convertirse otra vez en un conteo decimal mediante un peso muy simple.
Para un número decimal de \(\ell\) cifras \(d_1d_2\cdots d_\ell\) con \(d_1\neq 0\), definimos la máscara binaria \(b_1b_2\cdots b_\ell\) por
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$$
Dos números con la misma máscara tienen exactamente el mismo grafo de movimientos. Borrar la \(i\)-ésima cifra equivale a borrar el \(i\)-ésimo bit, y la eliminación de ceros a la izquierda depende solo de la posición del primer \(1\) restante. Así, cada estado queda representado por una cadena binaria canónica que o bien está vacía o bien empieza por \(1\).
Si una máscara tiene \(t\) unos, representa exactamente \(9^t\) números decimales, porque cada posición activa puede contener cualquiera de los dígitos de \(1\) a \(9\).
Sea \(\mathcal{W}(m)\) el estado de una máscara canónica \(m\). Bajo la convención normal,
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
y la máscara vacía es perdedora. Esta es exactamente la recurrencia que evalúan las implementaciones.
Es útil escribir una máscara canónica no vacía como \(1\,0^r\,u\), donde \(r\ge 0\) es el número de ceros inmediatamente después del primer \(1\), y \(u\) es vacío o vuelve a empezar por \(1\). Borrar el primer bit salta directamente al sufijo \(u\); borrar cualquier otro bit deja fijo el \(1\) inicial.
Una inducción corta sobre la longitud de la máscara produce dos hechos estructurales.
Toda máscara canónica de longitud impar es ganadora. En longitud par, la situación es mucho más rígida: si se borra un bit que no sea el primero, el primer bit sigue siendo \(1\), así que el hijo tiene longitud impar y por tanto es ganador. Eso significa que una máscara par solo puede ganar borrando su primer bit.
Por lo tanto, una máscara par \(1\,0^r\,u\) es ganadora exactamente cuando borrar la cifra líder deja a la vista un estado perdedor. Eso equivale a que \(r\) sea impar y \(u\) sea vacío o una máscara perdedora. La paridad del primer bloque de ceros es la invariante decisiva.
La máscara \(1100\) es perdedora. Si se borra uno de los dos primeros bits se obtiene \(100\); si se borra uno de los dos últimos, se obtiene \(110\). Ambos hijos tienen longitud impar, luego ambos son ganadores.
Ahora tomemos \(101100\). Si se borra el primer bit, el resultado bruto es \(01100\), que al canonizarse se convierte en \(1100\), un estado perdedor. Cualquier otro borrado deja una máscara de 5 bits, y toda máscara de 5 bits es ganadora. Por eso \(101100\) es ganadora. Como contiene tres unos, representa \(9^3=729\) números reales de seis cifras.
Sea \(A_n\) el número ponderado de máscaras ganadoras de longitud \(n\), y \(B_n\) el de máscaras perdedoras de longitud \(n\). Tomamos \(B_0=1\) para la máscara vacía. El peso total de todas las máscaras de \(n\) cifras es \(9\cdot 10^{n-1}\).
Como toda máscara de longitud impar es ganadora,
$$A_{2m+1}=9\cdot 10^{2m}.$$
Para longitud par \(2m\), una máscara ganadora debe tener la forma \(1\,0^{2k+1}\,u\), donde \(u\) es vacío o una máscara perdedora de longitud par. El prefijo solo aporta la primera cifra no nula, así que
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
Eliminando \(B_{2m}\) se obtiene una recurrencia de un paso para las longitudes pares:
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
Su forma cerrada es
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$$
La cantidad pedida es la suma acumulada
$$W(10^E)=\sum_{n=1}^{E} A_n.$$
Para exponentes pares, esta suma se simplifica a
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$$
De ahí salen enseguida las comprobaciones pequeñas: \(W(10^2)=18\) y \(W(10^4)=1656\).
Las implementaciones en C++, Python y Java no introducen la fórmula cerrada de manera explícita. En su lugar, resuelven el juego directamente sobre todas las máscaras canónicas de longitud como máximo \(18\). Para cada longitud \(\ell\), fijan el bit más alto en \(1\) y recorren todas las posibilidades para los \(\ell-1\) bits restantes.
Cada estado se evalúa con recursión memoizada. La implementación prueba todas las posiciones de borrado, construye la máscara siguiente con operaciones de bits, reduce la longitud aparente mientras queden ceros a la izquierda y se detiene en cuanto encuentra un hijo perdedor. Una vez clasificada una máscara, el resultado se reutiliza en todas las llamadas posteriores.
Después, el conteo final es directo. Si una máscara ganadora tiene \(t\) unos, representa \(9^t\) números decimales, así que el algoritmo añade esa potencia de \(9\) para cada máscara ganadora de cada longitud entre \(1\) y \(18\).
Hay \(2^{\ell-1}\) máscaras canónicas de longitud \(\ell\), así que el número total de estados hasta longitud \(E\) es
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E).$$
Cada estado prueba hasta \(\ell\) borrados, y cada transición realiza una normalización corta para eliminar ceros iniciales. Por eso, una cota conservadora para la implementación recursiva directa es \(O(E^2 2^E)\), con memoria \(O(2^E)\) para la tabla de memoización.
Para el objetivo real \(E=18\), esto es muy pequeño. Las fórmulas anteriores explican la regularidad de la respuesta, pero la recursión sobre máscaras ya es suficientemente rápida por sí sola.
从一个正整数 \(n\) 开始。一次操作删除它十进制表示中的某一位，保留其余数字的相对顺序，然后把新出现的前导零全部去掉。如果所有数字都被删光，下一状态就是 \(0\)，此时轮到行动的一方失败。题目要求统计：小于 \(10^{18}\) 的起始整数中，有多少个是先手必胜态。
真正的简化点在于，具体的非零数字值完全不重要。重要的只有哪些位置是零，哪些位置非零。因此整个游戏可以压缩成一个很短的二进制掩码问题，最后再通过一个简单的权重把掩码计数还原成十进制整数计数。
设 \(d_1d_2\cdots d_\ell\) 是一个 \(\ell\) 位十进制数，且 \(d_1\neq 0\)。定义对应的二进制掩码 \(b_1b_2\cdots b_\ell\)：
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$$
只要两个数的掩码相同，它们的整棵博弈树就完全相同。因为删除第 \(i\) 位十进制数字，正好等价于删除第 \(i\) 个比特；而删除首位后需要继续去掉多少个前导零，也只取决于剩余序列中第一个 \(1\) 在哪里。因此，每个状态都可以用一个规范化的二进制串表示，这个串要么为空，要么首位一定是 \(1\)。
如果一个掩码里有 \(t\) 个 \(1\)，那么它对应的十进制整数个数正好是 \(9^t\)。原因很直接：每个激活位置都可以独立选择 \(1\) 到 \(9\) 中的任意一个数字，而零位置只能放 \(0\)。
记 \(\mathcal{W}(m)\) 为规范掩码 \(m\) 的胜负状态。按照正常对弈规则，
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
空掩码对应的状态是必败态。这正是三份实现共同使用的递推关系。
把任意非空规范掩码写成 \(1\,0^r\,u\) 的形式最有帮助。这里 \(r\ge 0\) 表示首个 \(1\) 之后紧跟着的零的个数，\(u\) 要么为空，要么再次以 \(1\) 开头。删除首位时，状态会直接跳到后缀 \(u\)；删除其他任意一位时，首位的 \(1\) 仍然保留。
对掩码长度做一个简短的归纳，可以得到两个非常关键的结构结论。
第一，所有奇数长度的规范掩码都是必胜态。第二，偶数长度的情况严格得多：如果删除的不是首位，那么首位仍然是 \(1\)，所以子状态的长度是奇数，因此它一定是必胜态。换句话说，偶数长度状态想要获胜，只可能靠删除自己的第一位。
于是，一个偶数长度掩码 \(1\,0^r\,u\) 当且仅当“删除首位后暴露出的状态是必败态”时才是必胜态。这又等价于：\(r\) 是奇数，并且 \(u\) 为空或本身就是一个必败掩码。决定偶数长度状态命运的真正不变量，就是第一个零块的奇偶性。
掩码 \(1100\) 是必败态。删除前两个比特之一会得到 \(100\)，删除后两个比特之一会得到 \(110\)。这两个子状态长度都是 3，而所有 3 位规范掩码都是必胜态，所以 \(1100\) 没有通向必败态的走法。
再看 \(101100\)。如果删掉第一位，原始结果是 \(01100\)，规范化以后得到 \(1100\)，这正是一个必败态。若删除其他任意一位，结果仍然是长度 5 的规范状态，而所有长度 5 的状态都是必胜态。因此 \(101100\) 是必胜掩码。它包含 3 个 \(1\)，所以对应 \(9^3=729\) 个真实的六位十进制整数。
设 \(A_n\) 为长度为 \(n\) 的必胜掩码的加权总数，\(B_n\) 为长度为 \(n\) 的必败掩码的加权总数。对空掩码定义 \(B_0=1\)。所有 \(n\) 位掩码的总权重为 \(9\cdot 10^{n-1}\)。
由于所有奇数长度掩码都是必胜态，立刻得到
$$A_{2m+1}=9\cdot 10^{2m}.$$
对于偶数长度 \(2m\)，一个必胜掩码必须形如 \(1\,0^{2k+1}\,u\)，其中 \(u\) 为空，或者是一个偶数长度的必败掩码。前缀部分只贡献首个非零数字，因此
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
把 \(B_{2m}\) 消去，就得到偶数长度上的一阶递推：
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
这个递推可以解成闭式：
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$$
题目真正要求的是累积总数
$$W(10^E)=\sum_{n=1}^{E} A_n.$$
当指数是偶数时，这个和还能进一步化简为
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$$
实现中使用的小规模校验也就一目了然了：\(W(10^2)=18\)，\(W(10^4)=1656\)。
C++、Python 和 Java 实现并没有把闭式公式硬编码进去，而是直接在长度不超过 \(18\) 的规范掩码上求解整个博弈。对每个长度 \(\ell\)，程序固定最高位为 \(1\)，枚举剩下的 \(\ell-1\) 个比特，于是每一种零/非零模式都恰好被访问一次。
每个状态都通过记忆化递归来判定。实现会尝试删除每一个可能的位置，用位运算构造新的掩码，然后在前导零仍然存在时不断缩短当前长度；一旦发现某个子状态是必败态，就立刻把当前状态标成必胜态。已经算出的状态以后直接复用，不会重复搜索。
当整张胜负表建立好以后，最终统计就很直接了。若某个必胜掩码含有 \(t\) 个 \(1\)，它代表 \(9^t\) 个十进制整数，因此程序只需把所有长度 \(1\) 到 \(18\) 的必胜掩码对应的 \(9\) 的幂累加起来即可。
长度为 \(\ell\) 的规范掩码共有 \(2^{\ell-1}\) 个，所以长度不超过 \(E\) 的总状态数为
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E).$$
每个状态最多尝试 \(\ell\) 次删除，而每次转移还要做一次很短的“去掉前导零”规范化。于是，对这种直接递归实现来说，保守上界可以写成 \(O(E^2 2^E)\)，所需内存则是记忆化表的 \(O(2^E)\)。
对于题目的实际目标 \(E=18\)，这个规模非常小。上面的闭式公式解释了为什么答案具有如此整齐的结构，但即使完全不使用闭式，掩码递归本身也已经足够快。
Берётся положительное целое число \(n\). За ход игрок удаляет одну десятичную цифру, оставляя остальные цифры в прежнем порядке, после чего все появившиеся ведущие нули отбрасываются. Если цифр больше не осталось, получается состояние \(0\), и игрок, которому надо ходить, проигрывает. Нужно посчитать, сколько стартовых чисел меньше \(10^{18}\) являются выигрышными для первого игрока.
Главное упрощение состоит в том, что конкретные ненулевые цифры не важны. Важно только, какие позиции нулевые, а какие ненулевые. Поэтому игра полностью сжимается до короткой двоичной маски, а затем снова переводится в десятичный счёт с помощью простого веса.
Для \(\ell\)-значного десятичного числа \(d_1d_2\cdots d_\ell\) с \(d_1\neq 0\) определим двоичную маску \(b_1b_2\cdots b_\ell\) так:
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$$
Два числа с одной и той же маской имеют одинаковое дерево ходов. Удаление \(i\)-й десятичной цифры эквивалентно удалению \(i\)-го бита, а процесс отбрасывания ведущих нулей зависит только от позиции первого оставшегося \(1\). Значит, каждое состояние можно описывать канонической двоичной строкой, которая либо пуста, либо начинается с \(1\).
Если в маске \(t\) единиц, то она представляет ровно \(9^t\) десятичных чисел: каждая активная позиция может независимо принимать любую цифру от \(1\) до \(9\).
Пусть \(\mathcal{W}(m)\) обозначает статус канонической маски \(m\). При обычном правиле игры
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
а пустая маска проигрышна. Именно эту рекурсию и вычисляют реализации.
Полезно записывать непустую каноническую маску в виде \(1\,0^r\,u\), где \(r\ge 0\) — число нулей сразу после первой единицы, а \(u\) либо пусто, либо тоже начинается с \(1\). Удаление первого бита немедленно переносит нас к суффиксу \(u\); удаление любого другого бита сохраняет ведущую единицу.
Короткая индукция по длине маски даёт два ключевых структурных факта.
Любая каноническая маска нечётной длины выигрышна. Для чётной длины ситуация гораздо жёстче: если удалить не первый бит, то первый бит остаётся равным \(1\), значит, потомок имеет нечётную длину и поэтому выигрышен. Следовательно, чётная маска может выигрывать только удалением первого бита.
Отсюда следует, что чётная маска \(1\,0^r\,u\) выигрышна тогда и только тогда, когда удаление ведущей цифры открывает проигрышное состояние. Эквивалентно: \(r\) должно быть нечётным, а \(u\) должно быть пустым или само проигрышным. То есть судьбу чётного состояния определяет чётность первого блока нулей.
Маска \(1100\) проигрышна. Если удалить один из двух первых битов, получится \(100\); если удалить один из двух последних, получится \(110\). Оба потомка имеют нечётную длину, а значит, оба выигрышны.
Теперь рассмотрим \(101100\). Если удалить первый бит, сначала получится \(01100\), а после канонизации — \(1100\), то есть проигрышное состояние. Любое другое удаление оставляет 5-битную маску, а любая 5-битная маска выигрышна. Следовательно, \(101100\) выигрышна. Так как в ней три единицы, она соответствует \(9^3=729\) реальным шестизначным числам.
Обозначим через \(A_n\) взвешенное число выигрышных масок длины \(n\), а через \(B_n\) — взвешенное число проигрышных масок длины \(n\). Для пустой маски положим \(B_0=1\). Полный вес всех масок длины \(n\) равен \(9\cdot 10^{n-1}\).
Поскольку всякая маска нечётной длины выигрышна, имеем
$$A_{2m+1}=9\cdot 10^{2m}.$$
Для чётной длины \(2m\) выигрышная маска должна иметь вид \(1\,0^{2k+1}\,u\), где \(u\) пусто или является проигрышной маской чётной длины. Префикс даёт только первую ненулевую цифру, поэтому
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
Исключая \(B_{2m}\), получаем одношаговую рекурсию для чётных длин:
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
Её замкнутая форма равна
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$$
Требуемый итог — это накопленная сумма
$$W(10^E)=\sum_{n=1}^{E} A_n.$$
Для чётных показателей она красиво упрощается:
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$$
Из этой формулы сразу следуют малые проверки: \(W(10^2)=18\) и \(W(10^4)=1656\).
Реализации на C++, Python и Java не вшивают замкнутую формулу напрямую. Вместо этого они решают игру в точности на всех канонических масках длины не более \(18\). Для каждой длины \(\ell\) старший бит фиксируется равным \(1\), а остальные \(\ell-1\) битов перебираются полностью.
Каждое состояние вычисляется рекурсией с мемоизацией. Реализация пробует удалить каждую возможную позицию, строит следующую маску побитовыми операциями, уменьшает текущую длину, пока слева остаются нули, и сразу завершает поиск, как только найден проигрышный потомок. Уже классифицированные маски потом используются повторно.
Когда таблица побед и поражений построена, финальный подсчёт становится прямым. Если выигрышная маска содержит \(t\) единиц, она представляет \(9^t\) десятичных чисел, поэтому программа просто добавляет соответствующую степень \(9\) для каждой выигрышной маски каждой длины от \(1\) до \(18\).
Для длины \(\ell\) существует \(2^{\ell-1}\) канонических масок, значит общее число состояний до длины \(E\) равно
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E).$$
Каждое состояние рассматривает до \(\ell\) удалений, а каждый переход включает короткую нормализацию с удалением ведущих нулей. Поэтому консервативная верхняя оценка для прямой рекурсивной реализации — \(O(E^2 2^E)\), при памяти \(O(2^E)\) на таблицу мемоизации.
Для реальной цели \(E=18\) это совсем небольшой объём. Формулы выше объясняют регулярность ответа, но даже без них масочная рекурсия уже работает очень быстро.
نبدأ بعدد صحيح موجب \(n\). في كل نقلة تُحذف خانة عشرية واحدة، وتبقى الخانات الأخرى بالترتيب نفسه، ثم تُزال كل الأصفار البادئة التي تظهر بعد الحذف. إذا لم تبق أي خانة فالحالة التالية هي \(0\)، واللاعب الذي يأتي دوره عندها يخسر. المطلوب هو عدّ عدد القيم الابتدائية الأصغر من \(10^{18}\) التي تكون حالات رابحة للاعب الأول.
التبسيط الحاسم هو أن القيم الفعلية للأرقام غير الصفرية لا تؤثر في اللعبة. المهم فقط هو نمط الخانات الصفرية وغير الصفرية. لذلك يمكن ضغط اللعبة كلها إلى قناع ثنائي قصير، ثم تحويل العد من جديد إلى أعداد عشرية بواسطة وزن بسيط.
لعدد عشري من \(\ell\) خانات على الصورة \(d_1d_2\cdots d_\ell\) مع \(d_1\neq 0\)، نعرّف القناع الثنائي \(b_1b_2\cdots b_\ell\) بالعلاقة
$$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$$
أي عددين لهما القناع نفسه يملكان شجرة حركات متطابقة. حذف الخانة العشرية رقم \(i\) يعني حذف البت رقم \(i\)، وإزالة الأصفار البادئة تعتمد فقط على موضع أول \(1\) متبقٍ. لذلك يمكن تمثيل كل حالة بسلسلة ثنائية قانونية إما أن تكون فارغة، أو تبدأ بالبت \(1\).
إذا احتوى القناع على \(t\) من البتات \(1\)، فإنه يمثل بالضبط \(9^t\) عددًا عشريًا، لأن كل موضع فعّال يمكن أن يأخذ أي رقم من \(1\) إلى \(9\) بصورة مستقلة.
لنرمز بحالة القناع القانوني \(m\) إلى \(\mathcal{W}(m)\). وفق قاعدة اللعب العادية،
$$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$$
أما القناع الفارغ فهو حالة خاسرة. هذه هي العلاقة نفسها التي تحسبها جميع التطبيقات.
من المفيد كتابة أي قناع قانوني غير فارغ بالشكل \(1\,0^r\,u\)، حيث \(r\ge 0\) هو عدد الأصفار مباشرة بعد الـ \(1\) الأولى، و\(u\) إما فارغ أو يبدأ بدوره بـ \(1\). حذف البت الأول ينقلنا مباشرة إلى اللاحقة \(u\)، بينما حذف أي بت آخر يُبقي الـ \(1\) الأولى في مكانها.
استقراء قصير على طول القناع يعطي حقيقتين بنيويتين تفسران انتظام المسألة.
كل قناع قانوني ذي طول فردي هو حالة رابحة. أما في الأطوال الزوجية فالوضع أكثر تقييدًا بكثير: إذا حذفنا بتًا غير أولي، بقي أول بت مساويًا لـ \(1\)، فيكون طول الابن فرديًا، وبالتالي يكون الابن رابحًا. هذا يعني أن القناع الزوجي لا يستطيع أن يربح إلا بحذف البت الأول.
إذن يكون القناع الزوجي \(1\,0^r\,u\) رابحًا إذا وفقط إذا كشف حذف الخانة الأولى عن حالة خاسرة. وهذا يكافئ أن يكون \(r\) فرديًا، وأن يكون \(u\) فارغًا أو خاسرًا هو أيضًا. بعبارة أخرى، الثابت الحاسم هنا هو زوجية أو فردية أول كتلة من الأصفار.
القناع \(1100\) خاسر. حذف أحد البتين الأولين يعطي \(100\)، وحذف أحد البتين الأخيرين يعطي \(110\). وكلا الابنين طوله 3، وكل حالة قانونية ذات طول 3 هي حالة رابحة، لذلك لا توجد نقلة من \(1100\) إلى حالة خاسرة.
الآن انظر إلى \(101100\). إذا حُذف البت الأول كان الناتج الخام \(01100\)، وبعد القانوننة يصبح \(1100\)، وهي حالة خاسرة. أما أي حذف آخر فيترك حالة طولها 5، وكل حالات الطول 5 رابحة. لذلك \(101100\) حالة رابحة. ولأنه يحتوي على ثلاثة بتات \(1\)، فهو يمثل \(9^3=729\) عددًا عشريًا حقيقيًا من ست خانات.
لنعرّف \(A_n\) بأنه العدد الموزون للأقنعة الرابحة ذات الطول \(n\)، و\(B_n\) بأنه العدد الموزون للأقنعة الخاسرة ذات الطول \(n\). ونأخذ \(B_0=1\) للقناع الفارغ. الوزن الكلي لجميع أقنعة الطول \(n\) هو \(9\cdot 10^{n-1}\).
وبما أن كل قناع فردي الطول رابح، فإن
$$A_{2m+1}=9\cdot 10^{2m}.$$
أما في الطول الزوجي \(2m\)، فالقناع الرابح لا بد أن يكون على الصورة \(1\,0^{2k+1}\,u\)، حيث يكون \(u\) فارغًا أو قناعًا خاسرًا ذا طول زوجي. والبادئة لا تضيف إلا الخانة غير الصفرية الأولى، ولذلك
$$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$$
وبحذف \(B_{2m}\) نحصل على علاقة تراجعية من خطوة واحدة للأطوال الزوجية:
$$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$$
وحلها المغلق هو
$$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$$
أما المجموع المطلوب في المسألة فهو
$$W(10^E)=\sum_{n=1}^{E} A_n.$$
وعندما يكون الأس \(E\) زوجيًا، ينهار هذا المجموع إلى الصيغة الأنيقة
$$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$$
ومن هنا تظهر مباشرة الاختبارات الصغيرة المستخدمة في التنفيذ: \(W(10^2)=18\) و\(W(10^4)=1656\).
تنفيذات C++ وPython وJava لا تضع الصيغة المغلقة بشكل مباشر. بدلًا من ذلك، تحل اللعبة حلًا مباشرًا على جميع الأقنعة القانونية ذات الطول حتى \(18\). لكل طول \(\ell\)، يُثبَّت البت الأعلى إلى \(1\)، ثم تُجرَّب كل القيم الممكنة للبتات \(\ell-1\) الباقية، وبذلك يُفحص كل نمط صفري/غير صفري مرة واحدة بالضبط.
كل حالة تُقيَّم باستدعاء عودي مع حفظ النتائج. يجرّب التنفيذ حذف كل موضع ممكن، ثم يبني القناع التالي بعمليات على البتات، ثم يقلّص الطول الظاهر ما دامت هناك أصفار بادئة، ويتوقف فور العثور على ابن خاسر. وبعد تصنيف قناع ما، يُعاد استخدام النتيجة في كل المواضع الأخرى.
بعد اكتمال جدول الربح والخسارة، يصبح العد النهائي مباشرًا. فإذا كان في القناع الرابح \(t\) من البتات \(1\)، فهو يمثل \(9^t\) عددًا عشريًا، ولذلك يضيف التنفيذ هذه القوة من \(9\) لكل قناع رابح من كل طول بين \(1\) و\(18\).
عدد الأقنعة القانونية ذات الطول \(\ell\) هو \(2^{\ell-1}\)، ومن ثم فإن عدد الحالات الكلي حتى الطول \(E\) يساوي
$$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E).$$
كل حالة تجرّب حتى \(\ell\) عمليات حذف، وكل انتقال يتضمن خطوة قصيرة لإزالة الأصفار البادئة. لذلك فإن حدًا علويًا محافظًا للتنفيذ العودي المباشر هو \(O(E^2 2^E)\)، مع ذاكرة \(O(2^E)\) لجدول الحفظ.
وبالنسبة إلى الهدف الفعلي \(E=18\)، فهذا الحجم صغير جدًا. الصيغ السابقة تشرح انتظام الجواب، لكن حتى من دون استغلالها يبقى الحل القائم على الأقنعة سريعًا بما يكفي.