Start with the ordered list \(1,2,\dots,n\). In the first sweep, moving from left to right, remove every other surviving entry, so the first, third, fifth, and so on disappear. In the next sweep, move from right to left on the remaining list and again remove every other entry. Keep alternating directions until only one number remains; call that survivor \(P(n)\).
The problem asks for the prefix sum
$$S(n)=\sum_{i=1}^{n}P(i)$$
at
$$n=10^{18},$$
with the final result taken modulo
$$M=987654321.$$
The decisive observation is that one left-to-right sweep immediately shrinks the list to roughly half its size. The only extra complication is that the next sweep starts from the opposite end, and that change can be handled by a simple mirror argument.
Let
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
After the first left-to-right elimination, the surviving values are exactly
$$2,4,6,\dots,2m.$$
Dividing all surviving entries by \(2\) produces the reduced list
$$1,2,3,\dots,m.$$
So the original problem on size \(n\) becomes a smaller problem on size \(m\), except that the next elimination pass now starts from the right rather than the left.
Because both \(2m\) and \(2m+1\) leave the same even survivors after the first sweep, we already know that
$$P(2m)=P(2m+1).$$
Consider the reduced list \(1,2,\dots,m\). A game that starts from the right is the mirror image of a game that starts from the left. Under the reflection
$$j\longmapsto m+1-j,$$
the survivor position of the right-start process is the complement of the survivor position of the left-start process.
Therefore the survivor index on \(1,\dots,m\) when the next sweep begins on the right is
$$m+1-P(m).$$
Undoing the earlier factor of \(2\) gives the survivor in the original list:
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
Together with the base case
$$P(1)=1,$$
this determines the survivor for every \(n\).
Since \(2m\) and \(2m+1\) share the same value of \(\lfloor n/2\rfloor\), the recurrence shows that they also share the same survivor:
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
This pairing is the main simplification for the sum. Instead of treating every term separately, we can combine the contribution of each pair \((2m,2m+1)\) into one formula.
Define
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$$
For an odd upper bound \(n=2m+1\), group the equal pairs:
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
Since
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m,$$
we obtain
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
For an even upper bound, subtract the last term of the odd case:
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
Simplifying gives
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
Both recurrences replace \(n\) by \(\lfloor n/2\rfloor\). Starting from \(10^{18}\), repeated halving reaches \(1\) after only about sixty recursive levels.
So the algorithm only needs arguments along the short chain
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
Once these states are memoized, the full problem size becomes easy to handle.
The elimination process is visible directly:
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
Hence
$$P(9)=6.$$
The recurrence gives the same answer. Since \(m=\lfloor 9/2\rfloor=4\),
$$P(9)=2\left(5-P(4)\right).$$
Now \(P(4)=2\), so \(P(9)=2(5-2)=6\).
The first nine survivor values are
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$$
therefore
$$S(9)=29.$$
The odd recurrence confirms this:
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
The C++, Python, and Java implementations keep two memo tables: one for the survivor value and one for the prefix sum. Every recursive call first handles the tiny base cases, then checks whether the current argument has already been computed, and otherwise evaluates the halved subproblem.
The implementation uses the closed odd and even recurrences above instead of simulating the elimination list. Because each new state only depends on \(\lfloor n/2\rfloor\), the cache remains very small even for \(n=10^{18}\).
All final arithmetic is reduced modulo \(987654321\). The arithmetic logic is written so that subtraction stays non-negative modulo \(M\) and multiplication remains safe in each language's numeric model.
Let \(L(n)\) be the number of distinct arguments reached by repeated halving. Then \(L(n)=O(\log n)\). With memoization, each distinct argument is solved once for the survivor value and once for the prefix sum, and each solve performs only constant-time arithmetic. The total runtime is therefore \(O(\log n)\), and the extra memory usage is also \(O(\log n)\).
Man startet mit der geordneten Liste \(1,2,\dots,n\). Im ersten Durchgang werden von links nach rechts jede zweite noch vorhandene Zahl entfernt, also die Positionen \(1,3,5,\dots\). Im nächsten Durchgang läuft man auf der Restliste von rechts nach links und entfernt erneut jede zweite Position. Die Richtung wechselt so lange, bis nur noch eine Zahl übrig bleibt; dieser Überlebende sei \(P(n)\).
Gesucht ist die Präfixsumme
$$S(n)=\sum_{i=1}^{n}P(i)$$
für
$$n=10^{18},$$
wobei das Endergebnis modulo
$$M=987654321$$
auszugeben ist.
Die entscheidende Beobachtung ist, dass ein einziger Links-nach-rechts-Durchgang die Liste sofort auf ungefähr die Hälfte schrumpfen lässt. Die anschließende Richtungsumkehr kann dann mit einem Spiegelungsargument in eine einfache Rekurrenz übersetzt werden.
Setze
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
Nach dem ersten Eliminationsdurchgang von links nach rechts bleiben genau die geraden Werte
$$2,4,6,\dots,2m$$
übrig. Teilt man alle Überlebenden durch \(2\), so entsteht die reduzierte Liste
$$1,2,3,\dots,m.$$
Damit wird das Problem der Größe \(n\) auf ein kleineres Problem der Größe \(m\) zurückgeführt, nur dass der nächste Durchgang nun auf der rechten Seite beginnt.
Weil sowohl \(2m\) als auch \(2m+1\) nach dem ersten Durchgang dieselbe Restliste erzeugen, gilt bereits
$$P(2m)=P(2m+1).$$
Betrachte die reduzierte Liste \(1,2,\dots,m\). Ein Prozess, der rechts beginnt, ist das Spiegelbild des ursprünglichen Prozesses, der links beginnt. Unter der Abbildung
$$j\longmapsto m+1-j$$
wird die Überlebensposition des rechts startenden Prozesses zum Komplement der links startenden Überlebensposition.
Daher ist der Überlebensindex auf \(1,\dots,m\), wenn der nächste Durchgang rechts beginnt, gleich
$$m+1-P(m).$$
Hebt man die frühere Division durch \(2\) wieder auf, erhält man den Überlebenden in der ursprünglichen Liste:
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
Zusammen mit der Basis
$$P(1)=1$$
bestimmt diese Rekurrenz alle Werte.
Da \(2m\) und \(2m+1\) denselben Wert von \(\lfloor n/2\rfloor\) besitzen, liefern sie auch denselben Überlebenden:
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
Genau diese Paarstruktur macht die Summenbildung beherrschbar. Statt alle Terme einzeln zu behandeln, kann man jedes Paar \((2m,2m+1)\) in einem einzigen Ausdruck zusammenfassen.
Definiere
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$$
Für eine ungerade Obergrenze \(n=2m+1\) gruppieren wir die gleichen Paare:
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
Mit
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m$$
folgt
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
Für eine gerade Obergrenze zieht man den letzten Term wieder ab:
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
Nach dem Vereinfachen ergibt sich
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
Beide Rekurrenzen ersetzen \(n\) durch \(\lfloor n/2\rfloor\). Von \(10^{18}\) aus erreicht wiederholtes Halbieren die \(1\) schon nach ungefähr sechzig Ebenen.
Man benötigt also nur die kurze Kette
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
Werden diese Zustände memoisiert, ist selbst die volle Eingabegröße problemlos beherrschbar.
Direkt sieht der Prozess so aus:
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
Also gilt
$$P(9)=6.$$
Die Rekurrenz bestätigt das. Wegen \(m=\lfloor 9/2\rfloor=4\) ist
$$P(9)=2\left(5-P(4)\right).$$
Mit \(P(4)=2\) erhält man \(P(9)=2(5-2)=6\).
Die ersten neun Überlebenswerte lauten
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$$
somit
$$S(9)=29.$$
Auch die ungerade Summenrekurrenz liefert
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
Die C++-, Python- und Java-Implementierungen halten zwei Memo-Tabellen bereit: eine für den Überlebenden und eine für die Präfixsumme. Jeder rekursive Aufruf behandelt zuerst die kleinen Basisfälle, prüft dann den Cache und berechnet nur bei Bedarf das halbierte Teilproblem.
Statt die Eliminationsliste direkt zu simulieren, verwendet die Implementierung ausschließlich die geschlossenen Rekurrenzen für gerade und ungerade Argumente. Da jeder neue Zustand nur von \(\lfloor n/2\rfloor\) abhängt, bleibt der Cache selbst für \(n=10^{18}\) sehr klein.
Alle Endrechnungen werden modulo \(987654321\) durchgeführt. Die Arithmetik ist so formuliert, dass Subtraktionen im Modulo-System korrekt bleiben und Produkte in jedem der drei Sprachen sicher behandelt werden.
Sei \(L(n)\) die Zahl der verschiedenen Argumente, die durch wiederholtes Halbieren entstehen. Dann gilt \(L(n)=O(\log n)\). Mit Memoisierung wird jedes Argument genau einmal für den Überlebenden und genau einmal für die Präfixsumme ausgewertet, und jede Auswertung benötigt nur konstante viele arithmetische Operationen. Daher beträgt die Laufzeit \(O(\log n)\), und der zusätzliche Speicherverbrauch ist ebenfalls \(O(\log n)\).
Sıralı \(1,2,\dots,n\) listesiyle başlanır. İlk turda soldan sağa gidilerek hayatta kalan elemanların her ikincisi silinir; yani ilk, üçüncü, beşinci ve benzeri konumlar yok olur. Sonraki turda kalan liste üzerinde sağdan sola gidilir ve yine her ikinci eleman elenir. Yön her turda değişir ve sonunda tek bir sayı kalır; buna \(P(n)\) diyelim.
İstenen büyüklük
$$S(n)=\sum_{i=1}^{n}P(i)$$
önek toplamının
$$n=10^{18}$$
için değeri ve sonucun
$$M=987654321$$
modunda verilmesidir.
Kritik nokta şudur: soldan sağa yapılan ilk tarama listeyi hemen yaklaşık yarıya indirir. Sonraki turun sağdan başlaması ise basit bir ayna simetrisiyle aynı tipte bir reküransa dönüştürülebilir.
Şunu tanımlayalım:
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
İlk soldan-sağa elemeden sonra geriye tam olarak
$$2,4,6,\dots,2m$$
kalır. Bu kalanların hepsini \(2\)'ye bölersek küçültülmüş liste
$$1,2,3,\dots,m$$
olur. Demek ki boyutu \(n\) olan orijinal problem, boyutu \(m\) olan daha küçük bir probleme iner; tek fark, sonraki turun artık sağdan başlamasıdır.
Ayrıca hem \(2m\) hem de \(2m+1\) için ilk turun sonunda aynı çift sayılar kaldığından
$$P(2m)=P(2m+1)$$
hemen elde edilir.
Küçültülmüş \(1,2,\dots,m\) listesine bakalım. Sağdan başlayan süreç, soldan başlayan sürecin aynadaki görüntüsüdür. Şu yansıma altında
$$j\longmapsto m+1-j,$$
sağdan başlayan oyunun kazanan konumu, soldan başlayan oyunun kazanan konumunun tamamlayıcısı olur.
Bu yüzden \(1,\dots,m\) üzerinde sonraki tur sağdan başladığında hayatta kalan indeks
$$m+1-P(m)$$
olur. Başta yaptığımız \(2\)'ye bölmeyi geri alırsak orijinal listedeki sağ kalan değer
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
şeklindedir. Taban durum
$$P(1)=1$$
ile birlikte bu bağıntı tüm değerleri belirler.
\(2m\) ve \(2m+1\) aynı \(\lfloor n/2\rfloor\) değerini kullandığı için aynı kazanana sahiptir:
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
Toplamı hızlandıran fikir tam olarak bu eşleşmedir. Böylece her terimi tek tek işlemek yerine \((2m,2m+1)\) çiftlerini birlikte toplarız.
Şimdi
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1$$
olsun. Tek üst sınır \(n=2m+1\) için eş çiftleri gruplayalım:
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
Burada
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m$$
olduğundan
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
Çift üst sınır için tek durumdan son terimi çıkarırız:
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
Buradan sadeleştirince
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
Her iki rekürans da \(n\)'yi \(\lfloor n/2\rfloor\)'ye indirir. \(10^{18}\) değerinden başlanınca art arda ikiye bölme yaklaşık altmış seviyede \(1\)'e ulaşır.
Dolayısıyla gereken durumlar yalnızca şu kısa zincirde yer alır:
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
Bu durumlar belleğe alındığında tam girdi boyutu rahatlıkla yönetilebilir.
Süreci doğrudan izleyelim:
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
Bu yüzden
$$P(9)=6.$$
Rekürans da aynı sonucu verir. \(m=\lfloor 9/2\rfloor=4\) olduğundan
$$P(9)=2\left(5-P(4)\right).$$
\(P(4)=2\) ile \(P(9)=2(5-2)=6\) elde edilir.
İlk dokuz kazanan değeri
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6$$
olduğu için
$$S(9)=29$$
çıkar. Tek durum formülü de bunu doğrular:
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
C++, Python ve Java implementasyonları iki ayrı önbellek tutar: biri kazanan değeri, diğeri önek toplamı içindir. Her özyinelemeli çağrı önce küçük taban durumlarını çözer, sonra ilgili değerin daha önce hesaplanıp hesaplanmadığını kontrol eder ve yalnızca gerekirse yarıya inmiş alt problemi hesaplar.
Implementasyon, eleme listesini gerçekten simüle etmek yerine yukarıdaki kapalı tek/çift reküranslarını kullanır. Her yeni durum sadece \(\lfloor n/2\rfloor\)'ye bağlı olduğundan, \(n=10^{18}\) için bile önbellek çok küçük kalır.
Tüm son işlemler \(987654321\) modunda yapılır. Aritmetik düzeni, çıkarma işlemlerinin mod altında doğru kalmasını ve çarpımların her dilin sayı modelinde güvenle hesaplanmasını sağlar.
Tekrarlı yarıya indirme ile ulaşılan farklı argüman sayısına \(L(n)\) diyelim. O halde \(L(n)=O(\log n)\) olur. Memoization sayesinde her farklı argüman kazanan için bir kez, önek toplam için bir kez çözülür ve her çözüm sabit sayıda aritmetik işlem içerir. Bu nedenle toplam süre \(O(\log n)\), ek bellek kullanımı da \(O(\log n)\) olur.
Se empieza con la lista ordenada \(1,2,\dots,n\). En la primera pasada, avanzando de izquierda a derecha, se elimina una de cada dos entradas supervivientes, así que desaparecen las posiciones primera, tercera, quinta, etcétera. En la siguiente pasada se recorre la lista restante de derecha a izquierda y se vuelve a eliminar una de cada dos entradas. La dirección se alterna hasta que solo queda un número; a ese superviviente lo llamamos \(P(n)\).
La cantidad pedida es la suma prefijo
$$S(n)=\sum_{i=1}^{n}P(i)$$
para
$$n=10^{18},$$
tomando el resultado final módulo
$$M=987654321.$$
La observación central es que una sola pasada de izquierda a derecha reduce la lista a aproximadamente la mitad. El cambio de dirección en la siguiente pasada no obliga a redefinir todo el problema: se resuelve con un argumento de espejo muy simple.
Sea
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
Después de la primera eliminación de izquierda a derecha sobreviven exactamente
$$2,4,6,\dots,2m.$$
Si dividimos todos esos supervivientes entre \(2\), la lista se reduce a
$$1,2,3,\dots,m.$$
Por tanto, el problema original de tamaño \(n\) se convierte enseguida en un problema menor de tamaño \(m\), salvo que la siguiente pasada comienza por la derecha.
Además, tanto \(2m\) como \(2m+1\) dejan la misma lista de pares tras esa primera pasada, así que
$$P(2m)=P(2m+1).$$
Consideremos la lista reducida \(1,2,\dots,m\). Un juego que empieza por la derecha es la imagen especular de uno que empieza por la izquierda. Bajo la reflexión
$$j\longmapsto m+1-j,$$
la posición ganadora del proceso que empieza por la derecha es el complemento de la posición ganadora del proceso que empieza por la izquierda.
Así, el índice superviviente en \(1,\dots,m\) cuando la siguiente pasada empieza por la derecha es
$$m+1-P(m).$$
Deshaciendo la división previa entre \(2\), el valor superviviente en la lista original resulta ser
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
Con la condición inicial
$$P(1)=1,$$
esta recurrencia determina todos los valores.
Como \(2m\) y \(2m+1\) comparten el mismo \(\lfloor n/2\rfloor\), también comparten el mismo superviviente:
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
Ese emparejamiento es la simplificación clave para la suma. En vez de tratar cada término por separado, agrupamos la contribución de cada pareja \((2m,2m+1)\).
Definimos
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$$
Para un límite impar \(n=2m+1\), agrupamos las parejas iguales:
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
Como
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m,$$
obtenemos
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
Para un límite par, restamos el último término del caso impar:
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
Al simplificar, queda
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
Ambas recurrencias sustituyen \(n\) por \(\lfloor n/2\rfloor\). Empezando en \(10^{18}\), unas sesenta divisiones sucesivas por \(2\) bastan para llegar a \(1\).
Por eso el algoritmo solo necesita la cadena corta
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
Una vez memorizados esos estados, el tamaño real de la entrada deja de ser un obstáculo.
El proceso de eliminación se ve directamente:
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
Así que
$$P(9)=6.$$
La recurrencia da lo mismo. Como \(m=\lfloor 9/2\rfloor=4\),
$$P(9)=2\left(5-P(4)\right).$$
Y como \(P(4)=2\), obtenemos \(P(9)=2(5-2)=6\).
Los nueve primeros valores son
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$$
por lo que
$$S(9)=29.$$
La recurrencia impar también lo confirma:
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
Las implementaciones en C++, Python y Java mantienen dos tablas de memoización: una para el valor superviviente y otra para la suma prefijo. Cada llamada recursiva resuelve primero los casos base pequeños, luego consulta la caché y solo calcula el subproblema reducido cuando aún no existe el resultado.
La implementación no simula la lista de eliminación. En su lugar evalúa directamente las recurrencias cerradas para los casos par e impar. Como cada estado nuevo solo depende de \(\lfloor n/2\rfloor\), la caché sigue siendo muy pequeña incluso cuando \(n=10^{18}\).
Toda la aritmética final se reduce módulo \(987654321\). La lógica aritmética está escrita para que las restas permanezcan correctas dentro del módulo y para que las multiplicaciones sean seguras en el modelo numérico de cada lenguaje.
Sea \(L(n)\) el número de argumentos distintos que aparecen al ir dividiendo entre \(2\). Entonces \(L(n)=O(\log n)\). Con memoización, cada argumento distinto se calcula una vez para el superviviente y una vez para la suma prefijo, y cada cálculo usa solo aritmética de tiempo constante. En consecuencia, el tiempo total es \(O(\log n)\) y la memoria adicional también es \(O(\log n)\).
从有序列表 \(1,2,\dots,n\) 开始。第一轮从左到右扫描，每隔一个当前仍然存活的元素删掉一个，所以第 \(1,3,5,\dots\) 个位置会被删除。下一轮改为从右到左，再次每隔一个删掉一个。方向不断交替，直到只剩下一个数；把这个最后留下来的数记作 \(P(n)\)。
题目要求计算前缀和
$$S(n)=\sum_{i=1}^{n}P(i)$$
在
$$n=10^{18}$$
时的值，并对
$$M=987654321$$
取模。
关键观察是：只要做完第一轮从左到右的删除，问题规模就立刻缩小到大约一半。剩下唯一需要处理的是下一轮从右端开始，而这可以用一个简单的镜像对称论证转化回同一种递推。
设
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
第一轮从左到右删除之后，留下来的恰好是所有偶数：
$$2,4,6,\dots,2m.$$
把这些存活元素全部除以 \(2\)，就得到缩小后的列表
$$1,2,3,\dots,m.$$
所以原来大小为 \(n\) 的问题，立刻变成了大小为 \(m\) 的同类问题；唯一差别只是下一轮不再从左边开始，而是从右边开始。
另外，\(2m\) 和 \(2m+1\) 在第一轮之后留下的偶数列表完全相同，因此立刻有
$$P(2m)=P(2m+1).$$
考虑缩小后的列表 \(1,2,\dots,m\)。如果下一轮从右边开始，那么这个过程就是“从左边开始”的镜像版本。在反射映射
$$j\longmapsto m+1-j$$
之下，从右开始时的最终存活位置，正好等于从左开始时存活位置的补位置。
因此，当下一轮从右边开始时，\(1,\dots,m\) 中的存活下标是
$$m+1-P(m).$$
再把前面除掉的那个 \(2\) 乘回来，就得到原列表中的最终存活值：
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
配合初值
$$P(1)=1,$$
就能递推出所有 \(P(n)\)。
因为 \(2m\) 和 \(2m+1\) 对应的 \(\lfloor n/2\rfloor\) 相同，所以它们的幸存者也相同：
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
这就是前缀和能够大幅压缩的原因。我们不用逐项处理 \(P(1),P(2),\dots\)，而是可以把每一对 \((2m,2m+1)\) 合并成一项来计算。
定义
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$$
当上界是奇数 \(n=2m+1\) 时，把相等的成对项合并：
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
又因为
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m,$$
所以得到
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
如果上界是偶数，那么从奇数情形里减去最后一个相等项即可：
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
化简后得到
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
无论是 \(P(n)\) 还是 \(S(n)\)，递推都会把参数缩成 \(\lfloor n/2\rfloor\)。从 \(10^{18}\) 开始，不断折半大约只需要六十层就会到达 \(1\)。
也就是说，真正需要访问的状态只在这条很短的链上：
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
把这些状态记忆化以后，完整输入规模也就变得完全可处理了。
直接模拟删除过程：
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
因此
$$P(9)=6.$$
递推式也会得到同样的答案。因为 \(m=\lfloor 9/2\rfloor=4\)，
$$P(9)=2\left(5-P(4)\right).$$
而 \(P(4)=2\)，所以 \(P(9)=2(5-2)=6\)。
前九项幸存者依次为
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$$
于是
$$S(9)=29.$$
用奇数前缀和公式验证：
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
C++、Python 和 Java 实现都维护了两个记忆化表：一个缓存幸存者值，一个缓存前缀和。每次递归调用先处理很小的边界情形，然后查看该参数是否已经算过；只有缓存里还没有时，才继续求解折半后的子问题。
实现并不会真的构造或模拟整条消除链表，而是直接计算上面的奇偶闭式递推。由于每个新状态只依赖 \(\lfloor n/2\rfloor\)，即使 \(n=10^{18}\)，缓存规模也仍然很小。
所有最终运算都在模 \(987654321\) 下进行。算术处理专门保证了模减法不会出错，同时乘法在各语言的数值模型里也保持安全。
设不断折半后会访问到的不同参数个数为 \(L(n)\)，那么 \(L(n)=O(\log n)\)。在记忆化之后，每个参数至多被计算一次幸存者值、一次前缀和值，而且每次计算只做常数次算术操作。因此总时间复杂度是 \(O(\log n)\)，额外空间复杂度也是 \(O(\log n)\)。
Начинаем с упорядоченного списка \(1,2,\dots,n\). В первом проходе, двигаясь слева направо, удаляем каждый второй из еще оставшихся элементов, то есть исчезают позиции \(1,3,5,\dots\). В следующем проходе идем по оставшемуся списку справа налево и снова удаляем каждый второй элемент. Направление чередуется, пока не останется одно число; обозначим этого последнего выжившего через \(P(n)\).
Нужно вычислить префиксную сумму
$$S(n)=\sum_{i=1}^{n}P(i)$$
при
$$n=10^{18}$$
и взять результат по модулю
$$M=987654321.$$
Ключевое наблюдение состоит в том, что уже один проход слева направо уменьшает задачу примерно вдвое. Остается только учесть, что следующий проход начинается с противоположной стороны, а это аккуратно сводится к простому зеркальному соображению.
Положим
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
После первого удаления слева направо остаются ровно числа
$$2,4,6,\dots,2m.$$
Если разделить всех выживших на \(2\), получится уменьшенный список
$$1,2,3,\dots,m.$$
Значит, задача размера \(n\) сразу переходит в задачу размера \(m\), только следующий проход начинается уже справа.
Кроме того, числа \(2m\) и \(2m+1\) после первого прохода дают один и тот же список четных, поэтому
$$P(2m)=P(2m+1).$$
Рассмотрим уменьшенный список \(1,2,\dots,m\). Процесс, который стартует справа, является зеркальным отражением процесса, стартующего слева. При отображении
$$j\longmapsto m+1-j$$
позиция выжившего в правостороннем процессе становится дополнением позиции выжившего в левостороннем процессе.
Следовательно, если следующий проход начинается справа, то индекс выжившего на \(1,\dots,m\) равен
$$m+1-P(m).$$
Возвращая ранее вынесенный множитель \(2\), получаем выжившее значение в исходном списке:
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
Совместно с базовым условием
$$P(1)=1$$
эта рекурсия задает все значения.
Так как \(2m\) и \(2m+1\) имеют один и тот же \(\lfloor n/2\rfloor\), их выжившие совпадают:
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
Именно это совпадение по парам делает сумму удобной. Вместо поэлементного суммирования можно сразу складывать вклад каждой пары \((2m,2m+1)\).
Определим
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$$
Для нечетной верхней границы \(n=2m+1\) группируем равные пары:
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
Так как
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m,$$
получаем
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
Для четной верхней границы вычтем последний член из нечетного случая:
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
После упрощения остается
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
Обе формулы заменяют \(n\) на \(\lfloor n/2\rfloor\). Начиная с \(10^{18}\), примерно через шестьдесят делений пополам мы приходим к \(1\).
То есть реально нужны только состояния из короткой цепочки
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
Если запоминать уже найденные значения, то полный размер входа не создает проблем.
Сам процесс выглядит так:
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
Следовательно,
$$P(9)=6.$$
Рекурсия дает тот же ответ. При \(m=\lfloor 9/2\rfloor=4\) имеем
$$P(9)=2\left(5-P(4)\right).$$
Так как \(P(4)=2\), получаем \(P(9)=2(5-2)=6\).
Первые девять значений выжившего таковы:
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$$
поэтому
$$S(9)=29.$$
Рекурсия для нечетного случая подтверждает это:
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
Реализации на C++, Python и Java поддерживают две таблицы мемоизации: одну для значения выжившего и одну для префиксной суммы. Каждый рекурсивный вызов сначала обрабатывает маленькие базовые случаи, затем проверяет кэш и только при отсутствии ответа вычисляет подзадачу с аргументом, уменьшенным вдвое.
Сама реализация не моделирует список удаления напрямую. Вместо этого она использует выведенные выше закрытые формулы для четных и нечетных аргументов. Поскольку каждый новый случай зависит только от \(\lfloor n/2\rfloor\), кэш остается очень маленьким даже для \(n=10^{18}\).
Все окончательные вычисления ведутся по модулю \(987654321\). Арифметика организована так, чтобы вычитание корректно работало по модулю, а умножение оставалось безопасным в числовой модели каждого языка.
Пусть \(L(n)\) обозначает число различных аргументов, возникающих при последовательном делении пополам. Тогда \(L(n)=O(\log n)\). При мемоизации каждый такой аргумент вычисляется один раз для значения выжившего и один раз для префиксной суммы, а каждая операция занимает константное время. Следовательно, суммарное время равно \(O(\log n)\), и дополнительная память тоже имеет порядок \(O(\log n)\).
نبدأ بالقائمة المرتبة \(1,2,\dots,n\). في الجولة الأولى، وأثناء التحرك من اليسار إلى اليمين، نحذف عنصرًا من كل عنصرين ما زالا موجودين، فتختفي المواقع الأولى والثالثة والخامسة وهكذا. في الجولة التالية نتحرك من اليمين إلى اليسار على القائمة المتبقية ونكرر حذف عنصر من كل عنصرين. نستمر في تبديل الاتجاه حتى يبقى عدد واحد فقط؛ ولنسم هذا الناجي \(P(n)\).
المطلوب هو حساب المجموع التراكمي
$$S(n)=\sum_{i=1}^{n}P(i)$$
عندما
$$n=10^{18}$$
ثم أخذ النتيجة بترديد
$$M=987654321.$$
الفكرة الحاسمة هي أن المرور الأول من اليسار إلى اليمين يقلص القائمة مباشرة إلى نحو نصف حجمها. أما كون المرور التالي يبدأ من الجهة المقابلة فيمكن التعامل معه بحجة تناظر انعكاسي بسيطة جدًا.
لنضع
$$m=\left\lfloor\frac{n}{2}\right\rfloor.$$
بعد أول حذف من اليسار إلى اليمين تبقى بالضبط القيم
$$2,4,6,\dots,2m.$$
وإذا قسمنا جميع العناصر الباقية على \(2\) نحصل على القائمة المختزلة
$$1,2,3,\dots,m.$$
إذًا تتحول المسألة الأصلية ذات الحجم \(n\) فورًا إلى مسألة أصغر ذات حجم \(m\)، مع الفرق الوحيد أن الجولة التالية تبدأ من اليمين لا من اليسار.
ولأن \(2m\) و\(2m+1\) يتركان القائمة الزوجية نفسها بعد الجولة الأولى، فإننا نحصل مباشرة على
$$P(2m)=P(2m+1).$$
انظر إلى القائمة المختزلة \(1,2,\dots,m\). العملية التي تبدأ من اليمين هي الصورة المرآوية للعملية التي تبدأ من اليسار. تحت التحويل
$$j\longmapsto m+1-j,$$
تصبح رتبة الناجي في العملية التي تبدأ من اليمين هي المتممة لرتبة الناجي في العملية التي تبدأ من اليسار.
وعليه فإن رتبة الناجي على \(1,\dots,m\) عندما تبدأ الجولة التالية من اليمين تساوي
$$m+1-P(m).$$
وبإرجاع عامل \(2\) الذي قسمنا به سابقًا نحصل على قيمة الناجي في القائمة الأصلية:
$$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$$
ومع الحالة الأساسية
$$P(1)=1$$
تصبح جميع القيم محددة بالكامل.
بما أن \(2m\) و\(2m+1\) يشتركان في القيمة نفسها لـ \(\lfloor n/2\rfloor\)، فإنهما يشتركان أيضًا في الناجي نفسه:
$$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$$
وهذه البنية الزوجية هي ما يجعل مجموع البوادئ سهلًا. فبدل جمع كل قيمة على حدة، نجمع مساهمة كل زوج \((2m,2m+1)\) دفعة واحدة.
نعرف
$$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$$
عندما يكون الحد الأعلى فرديًا \(n=2m+1\)، نجمع الأزواج المتساوية:
$$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$$
وبما أن
$$\sum_{k=1}^{m}(k+1)=\frac{m(m+1)}{2}+m,$$
فإننا نحصل على
$$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$$
أما عندما يكون الحد الأعلى زوجيًا فنطرح الحد الأخير من حالة الفردي:
$$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$$
وبعد التبسيط نحصل على
$$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$$
كلتا العلاقتين تستبدلان \(n\) بـ \(\lfloor n/2\rfloor\). فإذا بدأنا من \(10^{18}\)، فإن التكرار عبر القسمة على \(2\) يصل إلى \(1\) بعد نحو ستين مستوى فقط.
ولهذا لا تحتاج الخوارزمية إلا إلى السلسلة القصيرة
$$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$$
ومتى خزنت هذه الحالات بالاستذكار، يصبح التعامل مع حجم الإدخال الكامل أمرًا مباشرًا.
يمكن رؤية عملية الحذف مباشرة:
$$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$$
إذن
$$P(9)=6.$$
والعلاقة التراجعية تعطي النتيجة نفسها. فبما أن \(m=\lfloor 9/2\rfloor=4\)، فإن
$$P(9)=2\left(5-P(4)\right).$$
ومع \(P(4)=2\) نحصل على \(P(9)=2(5-2)=6\).
أما القيم التسع الأولى فهي
$$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$$
ومن ثم
$$S(9)=29.$$
وتؤكد علاقة الفردي ذلك أيضًا:
$$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$$
تحتفظ تطبيقات C++ وPython وJava بجدولي استذكار: أحدهما لقيمة الناجي والآخر لمجموع البادئة. يبدأ كل استدعاء تراجعي بمعالجة الحالات الأساسية الصغيرة، ثم يفحص ما إذا كانت القيمة المطلوبة محفوظة سابقًا، ولا يحسب المسألة الأصغر إلا إذا لم تكن النتيجة موجودة في الجدول.
لا تقوم الشيفرة بمحاكاة قائمة الحذف فعليًا، بل تعتمد مباشرة على العلاقات المغلقة للحالتين الزوجية والفردية. وبما أن كل حالة جديدة تعتمد فقط على \(\lfloor n/2\rfloor\)، فإن حجم التخزين المؤقت يبقى صغيرًا جدًا حتى عند \(n=10^{18}\).
تُجرى كل الحسابات النهائية بترديد \(987654321\). وصيغ العمليات الحسابية مكتوبة بحيث يبقى الطرح صحيحًا ضمن الترديد وتظل عمليات الضرب آمنة داخل النموذج العددي لكل لغة.
إذا رمزنا بعدد الوسائط المختلفة الناتجة عن التكرار بالقسمة على \(2\) بالرمز \(L(n)\)، فإن \(L(n)=O(\log n)\). ومع الاستذكار، يُحسب كل وسيط مختلف مرة واحدة لقيمة الناجي ومرة واحدة لمجموع البادئة، وكل حساب يتطلب عددًا ثابتًا من العمليات الحسابية. لذلك يكون الزمن الكلي \(O(\log n)\)، كما تكون الذاكرة الإضافية \(O(\log n)\) أيضًا.