Problem 950 asks for the quantity \(T(N,C,D)\) at an extreme scale. The implementations evaluate
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}, \]
so even one parameter set is far beyond direct simulation. What the code actually sums is a sequence \((c_n)_{n\ge 1}\) with
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C. \]
The hard part is that the next exceptional value does not depend only on the current term; it depends on a whole multiset of carried values. The successful strategy is to keep that multiset in compressed form, jump directly to the next index where a nontrivial update occurs, and sum the long linear stretches in between with a closed formula.
At a landing position \(s\), the algorithm maintains two pieces of information: the current sequence value \(c_s\), and a multiset \(\mathcal{M}_s\) of size \(s\) that controls every future transition. Only positive entries are stored explicitly. Zeros are tracked by a counter \(z_s\).
Write the multiset as
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r. \]
Here the exponent means multiplicity: \(v_i^{m_i}\) means that the value \(v_i\) occurs \(m_i\) times. The invariant is
\[ z_s+\sum_{i=1}^{r} m_i=s. \]
The key summary statistic derived from this state is
\[ P_s(b)=\text{the sum of the } b \text{ smallest elements of }\mathcal{M}_s. \]
Because zeros come first and the positive values are stored in increasing groups, \(P_s(b)\) can be read off by a short scan of the grouped state instead of by expanding all \(s\) entries.
From a landing at index \(s\), the next nontrivial landing is searched in the form \(s+d\) with \(1\le d\le s\). For each candidate distance \(d\), the implementations define
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil. \]
The quantity \(b\) tells us how many of the smallest carried values must be consumed, while \(g\) is the common surcharge attached to a jump of length \(d\). The total cost of using that jump is
\[ \operatorname{cost}(d)=P_s(b)+b\,g. \]
The jump is feasible exactly when
\[ \operatorname{cost}(d)\le C. \]
The first feasible \(d\) is chosen. This is the decisive observation in the code: once the earliest feasible landing is known, every index before it follows the trivial linear rule and does not need to be processed one by one.
The scan does not start from \(d=1\) blindly. Since \(g\ge 1\) and \(P_s(b)\ge 0\), any feasible jump must satisfy \(b\le C\). Using
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \]
this implies
\[ d\ge s-2C. \]
So the candidate range can be shortened to
\[ d\in[\max(1,s-2C),\,s]. \]
There is also a guaranteed fallback. When \(d=s\), we get
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0, \]
hence \(\operatorname{cost}(s)=0\), which is always feasible. Therefore every state has a next landing. This special case produces a full reset: the next landing is at \(2s\), the new sequence value becomes \(C\), and the positive part of the state collapses to a single copy of \(C\).
Assume the chosen jump has \(b>0\). Let \(z_{\mathrm{sel}}=\min(b,z_s)\); these are the selected zeros among the \(b\) smallest elements. The remaining \(b-z_{\mathrm{sel}}\) selected elements are the smallest positive values of \(\mathcal{M}_s\), say
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}}. \]
The landing value is then
\[ c_{s+d}=C-\operatorname{cost}(d). \]
The new positive entries are built as follows:
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}\text{ copies}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
If \(c_{s+d}>0\), one further copy of \(c_{s+d}\) is inserted. Everything else is zero, so the new zero count is simply whatever is needed to make the total size equal to \(s+d\). Finally, equal positive values are merged back into grouped multiplicities. That normalization step is what keeps the state compact.
If the first feasible jump length is \(d\), then there is no special landing at any of the intermediate indices \(s+1,s+2,\dots,s+d-1\). Their values follow the linear pattern
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d). \]
So the skipped contribution is a simple arithmetic progression:
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
This is the reason the algorithm can jump over huge stretches of indices. Once the next landing is known, the entire block before it is summed in \(O(1)\) time.
The checkpoint case \(T(30,3,3)=190\) already shows the two essential behaviors. After a few updates the state at \(s=4\) is
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\}. \]
Try \(d=1\). Then
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0, \]
because the two smallest multiset elements are both zero. Hence
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1. \]
The two selected zeros become two copies of \(1\), and the landing value contributes one more \(1\). So the next grouped state is
\[ \mathcal{M}_5=\{0,0,1,1,1\}. \]
Later, at \(s=8\), every \(d<8\) fails the budget test, so the fallback \(d=8\) is used. That means indices \(9\) through \(15\) are just the arithmetic run \(1,2,3,4,5,6,7\) above \(c_8=0\), and index \(16\) resets to \(c_{16}=3\). This single trace explains why the code alternates between exact landing updates and long linear blocks.
The C++ and Python implementations maintain the landing index \(s\), the current value \(c_s\), the zero count, and the sorted positive groups. For each landing they scan candidate distances \(d\) from \(\max(1,s-2C)\) upward. To compute \(g=\lceil d/\sqrt D\rceil\) safely, they start from a numerical estimate and then correct it with the exact integer inequality \(g^2D\ge d^2\). Since \(g\) is monotone in \(d\), it can then be updated incrementally.
For each candidate, the implementation evaluates \(P_s(b)\) by consuming zeros first and then walking through the positive groups from smallest to largest. The scan stops early as soon as the partial sum exceeds \(C\), because such a candidate can never be feasible. Once the first feasible \(d\) is found, the code either performs the reset case \(d=s\) or constructs the next grouped multiset from the selected smallest elements, then sorts and merges equal positive values again.
The outer accumulation loop never expands all \(N\) indices. It adds the skipped arithmetic block in closed form, adds the landing value \(c_{s+d}\), and repeats from the new state. The Python version is a direct compact transcription of the same logic. The Java version serves as a thin launcher around the same computation, compiling and invoking the C++ implementation so that all three languages produce the same numerical result.
Let \(J\) be the number of landing states actually visited. At landing \(j\), let \(R_j\) be the number of candidate distances examined before the first feasible one is found, and let \(G_j\) be the number of distinct positive groups in the compressed state. Both the prefix-sum test and the landing update inspect at most \(G_j\) groups, so a safe worst-case bound is
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right). \]
The memory usage is \(O(\max_j G_j)\), because zeros are implicit and equal positive values are merged. That is the decisive compression: a state with enormous index \(s\) may still be represented by only a few grouped values. The final program repeats this computation for six parameter pairs, which is only a constant-factor multiplier.
The crucial point is qualitative rather than asymptotic. A naive method would need \(10^{16}\) sequence updates per parameter set, while this method processes only the landing states and treats the vast linear stretches analytically.
Problem 950 verlangt die Größe \(T(N,C,D)\) in einer extremen Größenordnung. Die Implementierungen berechnen
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}, \]
also ist schon ein einziger Parametersatz viel zu groß für eine direkte Simulation. Tatsächlich summiert der Code eine Folge \((c_n)_{n\ge 1}\) mit
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C. \]
Die Schwierigkeit liegt darin, dass der nächste nichttriviale Wert nicht nur vom aktuellen Folgenglied abhängt, sondern von einer ganzen Multimenge mitgetragenen Werten. Die erfolgreiche Strategie besteht darin, diese Multimenge komprimiert zu halten, direkt zum nächsten nichttrivialen Index zu springen und die langen linearen Abschnitte dazwischen per geschlossener Formel zu summieren.
An einer Landeposition \(s\) speichert der Algorithmus zwei Dinge: den aktuellen Folgenwert \(c_s\) und eine Multimenge \(\mathcal{M}_s\) der Größe \(s\), die alle zukünftigen Übergänge steuert. Nur positive Einträge werden explizit gespeichert. Nullen werden durch einen Zähler \(z_s\) erfasst.
Wir schreiben die Multimenge als
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r. \]
Der Exponent bezeichnet hier die Vielfachheit: \(v_i^{m_i}\) bedeutet, dass der Wert \(v_i\) genau \(m_i\)-mal vorkommt. Die Invariante lautet
\[ z_s+\sum_{i=1}^{r} m_i=s. \]
Die wichtigste aus diesem Zustand abgeleitete Größe ist
\[ P_s(b)=\text{die Summe der } b \text{ kleinsten Elemente von }\mathcal{M}_s. \]
Da die Nullen zuerst kommen und die positiven Werte als aufsteigend sortierte Gruppen vorliegen, kann \(P_s(b)\) durch einen kurzen Gruppenscan bestimmt werden, ohne alle \(s\) Elemente auszuschreiben.
Von einer Landeposition \(s\) aus wird die nächste nichttriviale Landung in der Form \(s+d\) mit \(1\le d\le s\) gesucht. Für jede Kandidatenlänge \(d\) definieren die Implementierungen
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil. \]
Die Größe \(b\) sagt, wie viele der kleinsten mitgetragenen Werte verbraucht werden müssen, während \(g\) den gemeinsamen Zuschlag für einen Sprung der Länge \(d\) beschreibt. Die Gesamtkosten dieses Sprungs sind
\[ \operatorname{cost}(d)=P_s(b)+b\,g. \]
Der Sprung ist genau dann zulässig, wenn
\[ \operatorname{cost}(d)\le C. \]
Gewählt wird das erste zulässige \(d\). Genau darin steckt die Schluesselidee des Programms: Sobald die frueheste moegliche Landung bekannt ist, folgen alle Indizes davor nur noch der trivialen linearen Regel und muessen nicht einzeln ausgewertet werden.
Die Suche startet nicht blind bei \(d=1\). Weil \(g\ge 1\) und \(P_s(b)\ge 0\) gilt, muss fuer jeden zulaessigen Sprung auch \(b\le C\) gelten. Mit
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor \]
folgt daraus
\[ d\ge s-2C. \]
Deshalb kann die Kandidatenmenge auf
\[ d\in[\max(1,s-2C),\,s] \]
verkuerzt werden. Ausserdem gibt es immer einen Rueckfallfall. Fuer \(d=s\) erhaelt man
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0, \]
also \(\operatorname{cost}(s)=0\), und dieser Fall ist immer zulaessig. Jeder Zustand besitzt daher eine naechste Landung. Im Spezialfall \(d=s\) entsteht ein kompletter Reset: Die naechste Landung liegt bei \(2s\), der neue Folgenwert ist wieder \(C\), und der positive Teil des Zustands schrumpft auf genau eine Kopie von \(C\).
Nehmen wir an, der gewaehlte Sprung hat \(b>0\). Setze \(z_{\mathrm{sel}}=\min(b,z_s)\); das ist die Zahl der ausgewaehlten Nullen unter den \(b\) kleinsten Elementen. Die restlichen \(b-z_{\mathrm{sel}}\) ausgewaehlten Elemente sind die kleinsten positiven Werte aus \(\mathcal{M}_s\), also
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}}. \]
Der neue Landewert ist dann
\[ c_{s+d}=C-\operatorname{cost}(d). \]
Die neuen positiven Eintraege entstehen durch
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}\text{ Kopien}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
Falls \(c_{s+d}>0\) ist, kommt noch eine weitere Kopie von \(c_{s+d}\) hinzu. Alles andere ist Null, also ergibt sich die neue Nullenzahl einfach aus der Bedingung, dass die Gesamtgroesse \(s+d\) sein muss. Danach werden gleiche positive Werte wieder zu Gruppen zusammengefasst. Genau diese Normalisierung haelt den Zustand klein.
Ist \(d\) die erste zulaessige Sprunglaenge, dann gibt es an den Zwischenpositionen \(s+1,s+2,\dots,s+d-1\) keine spezielle Landung. Dort gilt schlicht
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d). \]
Der uebersprungene Beitrag ist also eine arithmetische Reihe:
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
Genau deshalb kann der Algorithmus riesige Indexbereiche in einem Schritt ueberspringen. Sobald die naechste Landung bekannt ist, laesst sich der ganze Block davor in \(O(1)\) aufsummieren.
Schon der Kontrollfall \(T(30,3,3)=190\) zeigt die beiden wesentlichen Mechanismen. Nach einigen Aktualisierungen lautet der Zustand bei \(s=4\)
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\}. \]
Teste \(d=1\). Dann gilt
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0, \]
weil die beiden kleinsten Elemente der Multimenge Null sind. Also folgt
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1. \]
Die beiden ausgewaehlten Nullen werden zu zwei Kopien von \(1\), und der Landewert liefert eine dritte Kopie von \(1\). Damit erhaelt man
\[ \mathcal{M}_5=\{0,0,1,1,1\}. \]
Später, bei \(s=8\), scheitert jedes \(d<8\) am Budgettest, also wird der Rueckfall \(d=8\) verwendet. Das bedeutet: Die Indizes \(9\) bis \(15\) bilden einfach den linearen Lauf \(1,2,3,4,5,6,7\) ueber \(c_8=0\), und bei Index \(16\) erfolgt der Reset zu \(c_{16}=3\). Diese eine Spur zeigt bereits, warum der Code zwischen exakten Landungsupdates und langen linearen Bloecken wechselt.
Die C++- und Python-Implementierungen halten den Landeindex \(s\), den aktuellen Wert \(c_s\), die Zahl der Nullen und die sortierten positiven Gruppen. Fuer jede Landung pruefen sie Kandidaten \(d\) aufsteigend ab \(\max(1,s-2C)\). Um \(g=\lceil d/\sqrt D\rceil\) robust zu bestimmen, beginnen sie mit einer numerischen Naeherung und korrigieren diese dann mit der exakten ganzzahligen Bedingung \(g^2D\ge d^2\). Da \(g\) mit wachsendem \(d\) monoton ist, kann es danach inkrementell weitergefuehrt werden.
Fuer jeden Kandidaten wird \(P_s(b)\) berechnet, indem zuerst Nullen und dann positive Gruppen von klein nach gross verbraucht werden. Sobald die partielle Summe groesser als \(C\) wird, bricht die Pruefung sofort ab, denn ein solcher Kandidat kann nie zulaessig sein. Ist das erste zulaessige \(d\) gefunden, fuehrt der Code entweder den Resetfall \(d=s\) aus oder baut aus den ausgewaehlten kleinsten Elementen die naechste gruppierte Multimenge auf und normalisiert sie erneut.
Die aeussere Akkumulationsschleife expandiert nie alle \(N\) Indizes. Sie addiert den uebersprungenen arithmetischen Block per geschlossener Formel, addiert den Landewert \(c_{s+d}\) und setzt die Rechnung vom neuen Zustand aus fort. Die Python-Version ist eine kompakte direkte Umsetzung derselben Logik. Die Java-Version ist ein schlanker Starter um dieselbe Rechnung herum und kompiliert beziehungsweise startet die C++-Implementierung, sodass alle drei Sprachen denselben numerischen Weg benutzen.
Sei \(J\) die Zahl der tatsaechlich besuchten Landungszustaende. Fuer die \(j\)-te Landung bezeichne \(R_j\) die Zahl der getesteten Kandidatenabstaende bis zum ersten zulaessigen Wert und \(G_j\) die Zahl der verschiedenen positiven Gruppen im komprimierten Zustand. Sowohl der Praefixsummen-Test als auch das Update der Landung betrachten hoechstens \(G_j\) Gruppen, also ist eine sichere obere Schranke
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right). \]
Der Speicherverbrauch ist \(O(\max_j G_j)\), weil Nullen implizit bleiben und gleiche positive Werte zusammengelegt werden. Genau darin liegt die entscheidende Kompression: Ein Zustand mit riesigem Index \(s\) kann trotzdem nur aus wenigen Gruppen bestehen. Das Gesamtprogramm wiederholt diese Rechnung fuer sechs Parametersaetze, was nur ein konstanter Faktor ist.
Wichtiger als die asymptotische Formel ist der qualitative Gewinn. Ein naiver Ansatz braeuchte pro Parametersatz \(10^{16}\) Folgenschritte, waehrend diese Methode nur die echten Landungszustaende verarbeitet und die grossen linearen Strecken analytisch behandelt.
Problem 950, \(T(N,C,D)\) büyüklüğünü son derece büyük parametrelerde hesaplamayı ister. Uygulamalar şu toplamı hesaplar:
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}. \]
Dolayısıyla tek bir parametre çifti bile doğrudan simülasyon için fazla büyüktür. Kodun gerçekte topladığı şey,
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C \]
eşitliğiyle tanımlanan \((c_n)_{n\ge 1}\) dizisidir. Zorluk şuradadır: bir sonraki özel değer yalnızca son terime bağlı değildir; taşınan değerlerden oluşan bütün bir çoklu-kümeye bağlıdır. Bu yüzden doğru yaklaşım, bu çoklu-kümeyi sıkıştırılmış halde tutmak, bir sonraki anlamlı güncellemeye doğrudan sıçramak ve aradaki uzun doğrusal aralıkları kapalı formülle toplamaktır.
Dizi içinde bir iniş konumu \(s\) seçildiğinde algoritma iki bilgiyi taşır: mevcut dizi değeri \(c_s\) ve gelecekteki bütün geçişleri belirleyen, boyutu \(s\) olan bir çoklu-küme \(\mathcal{M}_s\). Yalnızca pozitif elemanlar açıkça saklanır. Sıfırlar ise \(z_s\) sayacıyla tutulur.
Bu çoklu-kümeyi
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r \]
şeklinde yazalım. Buradaki üs, tekrar sayısını gösterir: \(v_i^{m_i}\), \(v_i\) değerinin \(m_i\) kez bulunduğu anlamına gelir. Temel değişmez
\[ z_s+\sum_{i=1}^{r} m_i=s \]
eşitliğidir. Bu durumdan türetilen en önemli özet büyüklük ise
\[ P_s(b)=\mathcal{M}_s \text{ içindeki en küçük } b \text{ elemanın toplamı} \]
olur. Sıfırlar önce geldiği ve pozitif değerler artan gruplar halinde tutulduğu için \(P_s(b)\), bütün \(s\) elemanı açmadan kısa bir grup taramasıyla hesaplanabilir.
Bir iniş noktası \(s\)'den sonra gelen bir sonraki özel iniş, \(1\le d\le s\) olmak üzere \(s+d\) biçiminde aranır. Her aday uzaklık için uygulamalar
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil \]
tanımlarını kullanır. Burada \(b\), en küçük taşınan değerlerden kaç tanesinin tüketileceğini; \(g\) ise uzunluğu \(d\) olan sıçramanın ortak ek maliyetini ifade eder. Toplam maliyet
\[ \operatorname{cost}(d)=P_s(b)+b\,g \]
şeklindedir. Sıçrama tam olarak
\[ \operatorname{cost}(d)\le C \]
olduğunda uygundur. Algoritma ilk uygun \(d\)'yi seçer. Kodun belirleyici fikri budur: en erken uygun iniş bulunduğu anda, ondan önceki bütün indekslerin yalnızca doğrusal kuralı izlediği bilinir ve tek tek işlenmeleri gerekmez.
Tarama körlemesine \(d=1\)'den başlamaz. Çünkü \(g\ge 1\) ve \(P_s(b)\ge 0\) olduğundan, uygun her sıçrama için mutlaka \(b\le C\) olmalıdır. Şimdi
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor \]
eşitliğini kullanırsak
\[ d\ge s-2C \]
elde edilir. Bu yüzden aday aralığı
\[ d\in[\max(1,s-2C),\,s] \]
şeklinde daraltılır. Ayrıca her zaman garantili bir geri dönüş durumu vardır. \(d=s\) olduğunda
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0 \]
olur; dolayısıyla \(\operatorname{cost}(s)=0\) ve bu durum her zaman uygundur. Demek ki her durumun mutlaka bir sonraki inişi vardır. Bu özel durumda tam bir sıfırlama oluşur: sonraki iniş \(2s\) konumunda olur, yeni dizi değeri yine \(C\)'dir ve durumun pozitif kısmı tek bir \(C\) kopyasına iner.
Seçilen sıçramanın \(b>0\) olduğunu varsayalım. \(z_{\mathrm{sel}}=\min(b,z_s)\) olsun; bu, en küçük \(b\) eleman içindeki seçilmiş sıfır sayısıdır. Geriye kalan \(b-z_{\mathrm{sel}}\) seçili elemanlar, \(\mathcal{M}_s\)'nin en küçük pozitif değerleridir; bunları
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}} \]
diye yazalım. Yeni iniş değeri
\[ c_{s+d}=C-\operatorname{cost}(d) \]
olur. Yeni pozitif girişler şu şekilde kurulur:
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}\text{ kopya}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
Eğer \(c_{s+d}>0\) ise buna bir kopya daha eklenir. Geriye kalan her şey sıfırdır; dolayısıyla yeni sıfır sayısı, toplam boyutun \(s+d\) olması şartından otomatik çıkar. Son adımda eşit pozitif değerler yeniden birleştirilir. Durumun küçük kalmasını sağlayan şey bu normalizasyon adımıdır.
İlk uygun sıçrama uzunluğu \(d\) ise, \(s+1,s+2,\dots,s+d-1\) ara indekslerinde özel bir iniş yoktur. Bu değerler yalnızca
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d) \]
doğrusal desenini izler. Dolayısıyla atlanan katkı basit bir aritmetik dizi toplamıdır:
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
Algoritmanın çok uzun indeks aralıklarını tek hamlede geçebilmesinin nedeni budur. Bir sonraki iniş bilindiğinde, ondan önceki blok \(O(1)\) zamanda toplanır.
Doğrulama noktası olan \(T(30,3,3)=190\) bile iki temel davranışı açıkça gösterir. Birkaç güncellemeden sonra \(s=4\) anındaki durum
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\} \]
olur. Şimdi \(d=1\) deneyelim. O zaman
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0 \]
elde edilir; çünkü çoklu-kümenin en küçük iki elemanı sıfırdır. Buna göre
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1 \]
olur. Seçilen iki sıfır iki adet \(1\)'e dönüşür ve iniş değeri de bir tane daha \(1\) ekler. Sonraki grup durumu
\[ \mathcal{M}_5=\{0,0,1,1,1\} \]
şeklindedir. Daha sonra \(s=8\) olduğunda, her \(d<8\) bütçe testinde başarısız olur; bu yüzden geri dönüş durumu \(d=8\) kullanılır. Böylece \(9\) ile \(15\) arasındaki indeksler, \(c_8=0\) üstünde yalnızca \(1,2,3,4,5,6,7\) doğrusal koşusunu verir ve \(16\). indekste değer yeniden \(3\)'e sıçrar. Bu tek iz bile kodun neden bazen tam güncelleme, bazen uzun doğrusal blok kullandığını açıklar.
C++ ve Python uygulamaları iniş indeksi \(s\)'yi, mevcut değeri \(c_s\)'yi, sıfır sayısını ve sıralı pozitif grupları birlikte tutar. Her inişte aday \(d\) değerleri \(\max(1,s-2C)\)'den başlayarak yukarı doğru taranır. \(g=\lceil d/\sqrt D\rceil\) değerini güvenli biçimde elde etmek için önce sayısal bir yaklaşık alınır, ardından bu değer \(g^2D\ge d^2\) tamsayı eşitsizliğiyle düzeltilir. \(g\), \(d\) arttıkça tekdüze büyüdüğünden bundan sonra artımlı güncellenebilir.
Her aday için uygulama önce sıfırları, sonra da en küçükten büyüğe doğru pozitif grupları tüketerek \(P_s(b)\) değerini hesaplar. Kısmi toplam \(C\)'yi geçtiği anda tarama durur; çünkü böyle bir adayın uygun olma şansı yoktur. İlk uygun \(d\) bulunduğunda kod ya sıfırlama durumu \(d=s\)'yi uygular ya da seçilen en küçük elemanlardan yeni gruplanmış çoklu-kümeyi kurup eşit pozitifleri tekrar birleştirir.
Dıştaki toplama döngüsü bütün \(N\) indeksini asla açmaz. Atlanan aritmetik bloğu kapalı formülle ekler, ardından iniş değeri \(c_{s+d}\)'yi ekler ve yeni durumla devam eder. Python sürümü aynı mantığın doğrudan ve kısa bir uyarlamasıdır. Java sürümü ise aynı hesabın ince bir başlatıcısıdır; gerektiğinde C++ uygulamasını derleyip çalıştırır, böylece üç dil de aynı sayısal sonucu üretir.
Gerçekte ziyaret edilen iniş durumu sayısı \(J\) olsun. \(j\). inişte, ilk uygun aday bulunana kadar denenen uzaklık sayısını \(R_j\), sıkıştırılmış durumda bulunan farklı pozitif grup sayısını da \(G_j\) ile gösterelim. Hem önek-toplam testi hem de iniş güncellemesi en fazla \(G_j\) grup inceler; dolayısıyla güvenli bir üst sınır
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right) \]
olur. Bellek kullanımı \(O(\max_j G_j)\) düzeyindedir; çünkü sıfırlar örtük tutulur ve eşit pozitif değerler birleştirilir. Asıl sıkıştırma burada kazanılır: indeks \(s\) devasa olsa bile durum yalnızca birkaç gruplanmış değerden oluşabilir. Nihai program aynı hesabı altı parametre çifti için tekrarlar; bu da yalnızca sabit bir çarpandır.
Buradaki asıl kazanç yalnızca asimptotik gösterim değildir. Saf bir yöntem her parametre çifti için \(10^{16}\) güncelleme yapmak zorunda kalırken, bu yaklaşım yalnızca gerçek iniş durumlarını işler ve aradaki çok uzun doğrusal parçaları analitik olarak toplar.
El problema 950 pide la magnitud \(T(N,C,D)\) en una escala extrema. Las implementaciones evalúan
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}, \]
de modo que incluso un solo conjunto de parámetros está muy fuera del alcance de una simulación directa. Lo que el código suma de verdad es una sucesión \((c_n)_{n\ge 1}\) tal que
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C. \]
La dificultad es que el siguiente valor excepcional no depende solo del término actual, sino de un multiconjunto completo de valores arrastrados. Por eso la estrategia correcta es mantener ese multiconjunto en forma comprimida, saltar directamente al siguiente índice donde ocurre una actualización no trivial y sumar con fórmula cerrada los largos tramos lineales intermedios.
En una posición de aterrizaje \(s\), el algoritmo mantiene dos objetos: el valor actual de la sucesión \(c_s\) y un multiconjunto \(\mathcal{M}_s\) de tamaño \(s\) que controla todas las transiciones futuras. Solo se almacenan de forma explícita las entradas positivas. Los ceros se contabilizan con un contador \(z_s\).
Escribimos el multiconjunto como
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r. \]
Aquí el exponente indica multiplicidad: \(v_i^{m_i}\) significa que el valor \(v_i\) aparece \(m_i\) veces. El invariante básico es
\[ z_s+\sum_{i=1}^{r} m_i=s. \]
La cantidad resumida más importante derivada de este estado es
\[ P_s(b)=\text{la suma de los } b \text{ elementos más pequeños de }\mathcal{M}_s. \]
Como los ceros van primero y los valores positivos están guardados en grupos crecientes, \(P_s(b)\) puede obtenerse con un recorrido corto sobre el estado agrupado, sin expandir los \(s\) elementos.
Desde una posición de aterrizaje \(s\), el siguiente aterrizaje no trivial se busca en la forma \(s+d\), con \(1\le d\le s\). Para cada distancia candidata \(d\), las implementaciones definen
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil. \]
La cantidad \(b\) indica cuántos de los valores arrastrados más pequeños deben consumirse, mientras que \(g\) es el recargo común asociado a un salto de longitud \(d\). El coste total de ese salto es
\[ \operatorname{cost}(d)=P_s(b)+b\,g. \]
El salto es factible exactamente cuando
\[ \operatorname{cost}(d)\le C. \]
Se elige el primer \(d\) factible. Esa es la observación clave del código: una vez conocido el primer aterrizaje posible, todos los índices anteriores siguen una regla lineal trivial y no hace falta procesarlos uno por uno.
La exploración no empieza ciegamente en \(d=1\). Como \(g\ge 1\) y \(P_s(b)\ge 0\), cualquier salto factible debe cumplir \(b\le C\). A partir de
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor \]
se obtiene
\[ d\ge s-2C. \]
Por tanto, el rango candidato puede reducirse a
\[ d\in[\max(1,s-2C),\,s]. \]
Además existe un caso de respaldo garantizado. Cuando \(d=s\), tenemos
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0, \]
de modo que \(\operatorname{cost}(s)=0\), siempre factible. Por eso cada estado tiene necesariamente un siguiente aterrizaje. Ese caso especial provoca un reinicio completo: el siguiente aterrizaje está en \(2s\), el nuevo valor de la sucesión vuelve a ser \(C\) y la parte positiva del estado se reduce a una sola copia de \(C\).
Supongamos que el salto elegido tiene \(b>0\). Definimos \(z_{\mathrm{sel}}=\min(b,z_s)\); ese es el número de ceros seleccionados entre los \(b\) menores elementos. Los otros \(b-z_{\mathrm{sel}}\) elementos seleccionados son los menores valores positivos de \(\mathcal{M}_s\), que escribimos como
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}}. \]
El valor en el aterrizaje es entonces
\[ c_{s+d}=C-\operatorname{cost}(d). \]
Las nuevas entradas positivas se construyen mediante
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}\text{ copias}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
Si \(c_{s+d}>0\), se añade además una copia de \(c_{s+d}\). Todo lo demás es cero, así que el nuevo número de ceros es simplemente el necesario para que el tamaño total sea \(s+d\). Finalmente, los valores positivos iguales se vuelven a fusionar en grupos. Esa normalización es la que mantiene pequeño el estado.
Si la primera longitud factible es \(d\), entonces no existe ningún aterrizaje especial en los índices intermedios \(s+1,s+2,\dots,s+d-1\). Esos valores siguen la pauta lineal
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d). \]
Por lo tanto, la contribución omitida es una progresión aritmética simple:
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
Esa es la razón por la que el algoritmo puede saltar intervalos enormes. Una vez conocida la siguiente llegada, todo el bloque anterior se suma en \(O(1)\).
El caso de control \(T(30,3,3)=190\) ya muestra los dos comportamientos esenciales. Tras unas cuantas actualizaciones, el estado en \(s=4\) es
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\}. \]
Probemos \(d=1\). Entonces
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0, \]
porque los dos elementos más pequeños del multiconjunto son ceros. En consecuencia,
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1. \]
Los dos ceros seleccionados se convierten en dos copias de \(1\), y el valor de aterrizaje aporta una tercera copia de \(1\). Por tanto, el siguiente estado agrupado es
\[ \mathcal{M}_5=\{0,0,1,1,1\}. \]
Más adelante, en \(s=8\), cualquier \(d<8\) falla la prueba de presupuesto, así que se usa el caso de respaldo \(d=8\). Eso significa que los índices \(9\) a \(15\) forman simplemente la carrera aritmética \(1,2,3,4,5,6,7\) por encima de \(c_8=0\), y el índice \(16\) se reinicia a \(c_{16}=3\). Este pequeño rastro ya explica por qué el código alterna entre actualizaciones exactas de aterrizaje y bloques lineales largos.
Las implementaciones en C++ y Python mantienen el índice de aterrizaje \(s\), el valor actual \(c_s\), el número de ceros y los grupos positivos ordenados. En cada aterrizaje examinan las distancias candidatas \(d\) a partir de \(\max(1,s-2C)\). Para calcular con seguridad \(g=\lceil d/\sqrt D\rceil\), parten de una estimación numérica y luego la corrigen con la desigualdad entera exacta \(g^2D\ge d^2\). Como \(g\) es monótono en \(d\), después puede actualizarse de forma incremental.
Para cada candidato, la implementación evalúa \(P_s(b)\) consumiendo primero ceros y luego recorriendo los grupos positivos desde el menor al mayor. En cuanto la suma parcial supera \(C\), la exploración se corta, porque ese candidato ya no puede ser factible. Una vez encontrado el primer \(d\) factible, el código ejecuta el caso de reinicio \(d=s\) o bien construye el siguiente multiconjunto agrupado a partir de los elementos más pequeños seleccionados y vuelve a fusionar los valores positivos iguales.
El bucle externo de acumulación nunca expande los \(N\) índices. Añade el bloque aritmético omitido mediante fórmula cerrada, suma el valor de aterrizaje \(c_{s+d}\) y continúa desde el nuevo estado. La versión en Python es una transcripción compacta de la misma lógica. La versión en Java actúa como un lanzador ligero de ese mismo cálculo: compila e invoca la implementación en C++, de modo que los tres lenguajes terminan produciendo el mismo resultado numérico.
Sea \(J\) el número de estados de aterrizaje que realmente se visitan. En el aterrizaje \(j\), sea \(R_j\) el número de distancias candidatas probadas hasta encontrar la primera factible y \(G_j\) el número de grupos positivos distintos en el estado comprimido. Tanto la prueba de suma prefijo como la actualización del aterrizaje inspeccionan a lo sumo \(G_j\) grupos, así que una cota superior segura es
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right). \]
La memoria utilizada es \(O(\max_j G_j)\), porque los ceros son implícitos y los valores positivos iguales se fusionan. Esa es la compresión decisiva: un estado con índice \(s\) enorme puede seguir representándose con solo unos pocos grupos. El programa final repite este cálculo para seis pares de parámetros, lo cual solo introduce un factor constante.
El punto clave es cualitativo más que asintótico. Un método ingenuo necesitaría \(10^{16}\) actualizaciones de la sucesión por cada conjunto de parámetros, mientras que este procedimiento procesa únicamente los estados de aterrizaje y trata analíticamente los larguísimos tramos lineales.
第 950 题要求在极大规模下计算 \(T(N,C,D)\)。实现中实际求的是
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}, \]
所以哪怕只看一个参数组，也完全不可能按下标逐项模拟。代码真正累加的是一个序列 \((c_n)_{n\ge 1}\)，满足
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C. \]
困难之处在于，下一个“特殊”值并不只由当前项决定，而是取决于一整个被继续携带的多重集合。有效做法不是把所有历史都展开，而是把这个多重集合压缩表示，直接跳到下一个发生非平凡更新的位置，并把中间那一大段纯线性区间用闭式公式一次性求和。
在一个落点位置 \(s\)，算法维护两类信息：当前序列值 \(c_s\)，以及一个大小为 \(s\) 的多重集合 \(\mathcal{M}_s\)。未来的每一次转移都由这个状态决定。只有正值会被显式存储；值为 \(0\) 的项只通过计数器 \(z_s\) 记录。
把这个多重集合写成
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r. \]
这里的指数表示重数，也就是 \(v_i^{m_i}\) 表示数值 \(v_i\) 出现了 \(m_i\) 次。状态满足基本不变量
\[ z_s+\sum_{i=1}^{r} m_i=s. \]
从这个状态里抽取出来的核心统计量是
\[ P_s(b)=\mathcal{M}_s \text{ 中最小的 } b \text{ 个元素之和}. \]
由于零一定排在最前面，而正值又按大小分组存放，所以计算 \(P_s(b)\) 时不必把全部 \(s\) 个元素展开，只需从小到大扫过这些分组即可。
从落点 \(s\) 出发，下一个非平凡落点写成 \(s+d\)，其中 \(1\le d\le s\)。对每个候选距离 \(d\)，实现都定义
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil. \]
其中 \(b\) 表示必须消耗掉当前状态里最小的多少个“被携带值”，而 \(g\) 是长度为 \(d\) 的跳跃统一附带的增量代价。这个跳跃的总代价为
\[ \operatorname{cost}(d)=P_s(b)+b\,g. \]
当且仅当
\[ \operatorname{cost}(d)\le C \]
时，这个跳跃才可行。算法总是选择第一个可行的 \(d\)。这正是程序的关键观察：一旦知道最早可行的落点，前面所有位置都只服从简单的线性规律，不需要逐个下标去算。
候选搜索并不是机械地从 \(d=1\) 开始。因为 \(g\ge 1\) 且 \(P_s(b)\ge 0\)，任何可行跳跃都必须满足 \(b\le C\)。再利用
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor \]
就得到
\[ d\ge s-2C. \]
于是候选区间可以直接缩短为
\[ d\in[\max(1,s-2C),\,s]. \]
另外还有一个保证存在的兜底情形。当 \(d=s\) 时，
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0, \]
因此 \(\operatorname{cost}(s)=0\)，必然可行。所以每个状态都一定存在下一个落点。这个特殊分支对应一次完全重置：下一个落点在 \(2s\)，新的序列值重新变成 \(C\)，状态中的正值部分也缩成单独一个 \(C\)。
假设选中的跳跃满足 \(b>0\)。记 \(z_{\mathrm{sel}}=\min(b,z_s)\)，它表示在最小的 \(b\) 个元素里被选中的零的个数。其余 \(b-z_{\mathrm{sel}}\) 个被选元素就是 \(\mathcal{M}_s\) 中最小的正值，记为
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}}. \]
落点上的新值为
\[ c_{s+d}=C-\operatorname{cost}(d). \]
新的正值部分由下面几类元素组成：
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}\text{ 个}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
如果 \(c_{s+d}>0\)，还要再加入一个 \(c_{s+d}\)。除此之外的所有位置都视为零，因此新的零计数只需要由总大小等于 \(s+d\) 这个条件补齐即可。最后再把相等的正值合并回分组表示。也正是这个归并步骤保证了状态不会失控膨胀。
若第一个可行跳跃长度是 \(d\)，那么在中间的 \(s+1,s+2,\dots,s+d-1\) 这些位置上不会发生特殊落点。它们的值只满足简单的线性规律
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d). \]
因此被跳过的贡献就是一个普通的等差数列求和：
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
算法之所以能一口气跨过巨大的区间，原因就在这里。只要下一个落点确定下来，前面的整段区间就能用 \(O(1)\) 时间直接求和。
验证点 \(T(30,3,3)=190\) 已经足以展示两种关键行为。经过若干次更新后，在 \(s=4\) 时状态为
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\}. \]
现在尝试 \(d=1\)。于是
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0, \]
因为多重集合里最小的两个元素都是零。所以
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1. \]
这两个被选中的零会变成两个 \(1\)，而落点值又再贡献一个 \(1\)，因此新的分组状态变成
\[ \mathcal{M}_5=\{0,0,1,1,1\}. \]
再往后到 \(s=8\) 时，所有 \(d<8\) 都无法通过预算判定，于是使用兜底分支 \(d=8\)。这意味着下标 \(9\) 到 \(15\) 只是建立在 \(c_8=0\) 之上的线性序列 \(1,2,3,4,5,6,7\)，而在下标 \(16\) 又重置回 \(c_{16}=3\)。这个小例子已经把代码为何在“精确落点更新”和“长线性区间”之间切换说明白了。
C++ 和 Python 实现都维护同一组核心状态：落点下标 \(s\)、当前值 \(c_s\)、零的数量，以及按大小排序的正值分组。每到一个落点，它们就从 \(\max(1,s-2C)\) 开始向上扫描候选距离 \(d\)。为了稳定地计算 \(g=\lceil d/\sqrt D\rceil\)，实现会先取一个浮点近似，再用精确的整数不等式 \(g^2D\ge d^2\) 修正它。由于 \(g\) 随 \(d\) 单调不减，之后就可以增量更新。
对每个候选值，程序先消耗零，再按从小到大的顺序扫描正值分组，从而得到 \(P_s(b)\)。一旦部分和已经超过 \(C\)，该候选就立刻被放弃，因为它不可能再满足预算。找到第一个可行的 \(d\) 后，代码要么执行 \(d=s\) 的重置分支，要么根据选中的最小元素构造新的分组多重集合，并重新合并相等的正值。
外层累加循环从来不会把全部 \(N\) 个位置展开。它先用闭式公式加入被跳过的等差区间，再加入落点值 \(c_{s+d}\)，然后从新状态继续。Python 版本是这套逻辑的紧凑直译。Java 版本则是同一计算的轻量启动器：它会在需要时编译并调用 C++ 实现，因此三种语言最终走的是同一条数值路径。
设实际访问到的落点状态数为 \(J\)。在第 \(j\) 个落点，记找到第一个可行距离前检查过的候选数为 \(R_j\)，记压缩状态里不同正值分组的数量为 \(G_j\)。前缀和测试与落点更新最多都只会查看 \(G_j\) 个分组，因此一个安全的上界是
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right). \]
空间复杂度为 \(O(\max_j G_j)\)，因为零是隐式表示的，而相同的正值会被合并。真正关键的压缩就体现在这里：即使下标 \(s\) 已经大得惊人，状态本身也可能只需要几个分组就能表示。最终程序把这个计算重复六次，对应六组参数，所以只多了一个常数因子。
真正重要的是质的改进，而不只是渐近符号。朴素做法每组参数都要进行 \(10^{16}\) 次序列更新，而这里的方法只处理那些真正的落点状态，并把中间巨大的线性区间用解析方式统一处理掉。
В задаче 950 требуется вычислить величину \(T(N,C,D)\) при чрезвычайно больших параметрах. Реально программы считают
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}, \]
поэтому даже один набор параметров недоступен для пошаговой симуляции. Фактически код суммирует последовательность \((c_n)_{n\ge 1}\), для которой
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C. \]
Трудность в том, что следующее особое значение определяется не только текущим членом, а целым мультимножеством переносимых значений. Поэтому рабочий подход таков: хранить это мультимножество в сжатом виде, перескакивать сразу к следующему индексу с нетривиальным обновлением и суммировать длинные линейные участки между такими точками по закрытой формуле.
В точке приземления \(s\) алгоритм хранит две вещи: текущее значение последовательности \(c_s\) и мультимножество \(\mathcal{M}_s\) размера \(s\), которое определяет все будущие переходы. Явно сохраняются только положительные элементы. Нули учитываются отдельным счётчиком \(z_s\).
Запишем мультимножество в виде
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r. \]
Здесь показатель означает кратность: \(v_i^{m_i}\) означает, что значение \(v_i\) встречается \(m_i\) раз. Основной инвариант равен
\[ z_s+\sum_{i=1}^{r} m_i=s. \]
Главная сводная характеристика этого состояния имеет вид
\[ P_s(b)=\text{сумма } b \text{ наименьших элементов мультимножества } \mathcal{M}_s. \]
Поскольку нули идут первыми, а положительные значения хранятся в возрастающих группах, \(P_s(b)\) можно получить коротким проходом по группам, не разворачивая все \(s\) элементов.
Из точки приземления \(s\) следующая нетривиальная точка ищется в виде \(s+d\), где \(1\le d\le s\). Для каждого кандидата \(d\) реализации определяют
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil. \]
Число \(b\) показывает, сколько наименьших переносимых значений надо израсходовать, а \(g\) задаёт общий дополнительный взнос для прыжка длины \(d\). Полная стоимость такого прыжка равна
\[ \operatorname{cost}(d)=P_s(b)+b\,g. \]
Прыжок допустим тогда и только тогда, когда
\[ \operatorname{cost}(d)\le C. \]
Выбирается первый допустимый \(d\). Это и есть решающая идея программы: как только найдено самое раннее возможное приземление, все индексы до него подчиняются тривиальному линейному правилу и не требуют поштучной обработки.
Просмотр кандидатов не стартует вслепую с \(d=1\). Так как \(g\ge 1\) и \(P_s(b)\ge 0\), любой допустимый прыжок обязан удовлетворять условию \(b\le C\). Подставляя
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \]
получаем
\[ d\ge s-2C. \]
Значит, диапазон кандидатов можно сразу сократить до
\[ d\in[\max(1,s-2C),\,s]. \]
Кроме того, существует гарантированный запасной вариант. При \(d=s\) имеем
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0, \]
а значит \(\operatorname{cost}(s)=0\), то есть этот вариант всегда допустим. Следовательно, у каждого состояния есть следующая точка приземления. В этом специальном случае происходит полный сброс: следующее приземление находится в \(2s\), новое значение последовательности снова равно \(C\), а положительная часть состояния схлопывается до одной копии \(C\).
Предположим, что выбранный прыжок имеет \(b>0\). Положим \(z_{\mathrm{sel}}=\min(b,z_s)\); это число выбранных нулей среди \(b\) наименьших элементов. Остальные \(b-z_{\mathrm{sel}}\) выбранных элементов - это наименьшие положительные значения из \(\mathcal{M}_s\), обозначим их
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}}. \]
Тогда значение в точке приземления равно
\[ c_{s+d}=C-\operatorname{cost}(d). \]
Новые положительные элементы строятся так:
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}\text{ копий}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
Если \(c_{s+d}>0\), добавляется ещё одна копия \(c_{s+d}\). Всё остальное считается нулём, поэтому новое число нулей просто добирается из условия, что общий размер должен быть равен \(s+d\). После этого одинаковые положительные значения снова сливаются в группы. Именно эта нормализация и удерживает состояние компактным.
Если первая допустимая длина прыжка равна \(d\), то на промежуточных индексах \(s+1,s+2,\dots,s+d-1\) специальных приземлений нет. Их значения подчиняются простой линейной формуле
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d). \]
Следовательно, пропущенный вклад представляет собой обычную арифметическую прогрессию:
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
Именно поэтому алгоритм способен перепрыгивать огромные интервалы. Как только известна следующая точка приземления, весь предыдущий блок суммируется за \(O(1)\).
Проверочный случай \(T(30,3,3)=190\) уже демонстрирует оба ключевых режима. После нескольких обновлений состояние при \(s=4\) имеет вид
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\}. \]
Попробуем \(d=1\). Тогда
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0, \]
потому что два наименьших элемента мультимножества равны нулю. Значит,
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1. \]
Два выбранных нуля превращаются в две копии \(1\), а значение в точке приземления даёт ещё одну копию \(1\). Поэтому следующее сгруппированное состояние равно
\[ \mathcal{M}_5=\{0,0,1,1,1\}. \]
Позже, при \(s=8\), любой \(d<8\) проваливает бюджетную проверку, и используется запасной вариант \(d=8\). Это означает, что индексы от \(9\) до \(15\) дают просто арифметический пробег \(1,2,3,4,5,6,7\) поверх \(c_8=0\), а в точке \(16\) происходит сброс к \(c_{16}=3\). Один этот след уже хорошо показывает, почему программа чередует точные обновления приземления и длинные линейные блоки.
Реализации на C++ и Python поддерживают индекс приземления \(s\), текущее значение \(c_s\), число нулей и отсортированные группы положительных значений. Для каждого приземления они перебирают кандидатные расстояния \(d\), начиная с \(\max(1,s-2C)\). Чтобы безопасно вычислить \(g=\lceil d/\sqrt D\rceil\), они берут численную оценку, а затем исправляют её с помощью точного целочисленного неравенства \(g^2D\ge d^2\). Поскольку \(g\) монотонно растёт вместе с \(d\), дальше его можно обновлять инкрементально.
Для каждого кандидата вычисляется \(P_s(b)\): сначала расходуются нули, затем группы положительных значений просматриваются от меньших к большим. Как только частичная сумма превысила \(C\), проверка мгновенно прерывается, потому что такой кандидат уже не может стать допустимым. После нахождения первого допустимого \(d\) код либо выполняет случай сброса \(d=s\), либо строит следующее сгруппированное мультимножество из выбранных наименьших элементов и снова сливает одинаковые положительные значения.
Внешний цикл накопления никогда не разворачивает все \(N\) индексов. Он добавляет пропущенный арифметический блок по закрытой формуле, прибавляет значение в точке приземления \(c_{s+d}\) и продолжает работу из нового состояния. Версия на Python является компактной прямой записью той же логики. Версия на Java служит тонким запускателем того же вычисления: она компилирует и вызывает реализацию на C++, поэтому все три языка фактически используют одну и ту же численную схему.
Пусть \(J\) обозначает число реально посещённых состояний приземления. Для \(j\)-го приземления через \(R_j\) обозначим число проверенных расстояний до первого допустимого, а через \(G_j\) - число различных положительных групп в сжатом состоянии. И тест префиксной суммы, и обновление приземления просматривают не более \(G_j\) групп, поэтому надёжная верхняя оценка имеет вид
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right). \]
Память расходуется как \(O(\max_j G_j)\), поскольку нули хранятся неявно, а одинаковые положительные значения сливаются. Именно в этом состоит решающее сжатие: состояние с огромным индексом \(s\) всё ещё может описываться всего несколькими группами. Итоговая программа повторяет такой расчёт для шести наборов параметров, что даёт лишь постоянный множитель.
Ключевой выигрыш здесь скорее качественный, чем асимптотический. Наивный метод потребовал бы по \(10^{16}\) обновлений последовательности для каждого набора параметров, тогда как этот подход обрабатывает только реальные состояния приземления и аналитически суммирует гигантские линейные промежутки между ними.
تطلب المسألة 950 حساب الكمية \(T(N,C,D)\) عند أحجام هائلة جدًا. التنفيذات تحسب فعليًا
\[ \sum_{k=1}^{6} T(10^{16},10^k+1,10^k+1) \pmod{10^9}, \]
ولذلك فإن أي محاكاة مباشرة، حتى لحالة معاملات واحدة، غير عملية تمامًا. ما يجمعه الكود في الحقيقة هو متتالية \((c_n)_{n\ge 1}\) تحقق
\[ T(N,C,D)=\sum_{n=1}^{N} c_n, \qquad c_1=C. \]
الصعوبة الأساسية أن القيمة الخاصة التالية لا تعتمد على الحد الحالي وحده، بل على متعدد مجموعات كامل من القيم المحمولة إلى الأمام. لذلك فالفكرة الناجحة هي حفظ هذا المتعدد بشكل مضغوط، ثم القفز مباشرة إلى الموضع التالي الذي يحدث فيه تحديث غير بسيط، ثم جمع المقاطع الخطية الطويلة الواقعة بين هذه المواضع بواسطة صيغة مغلقة.
عند موضع هبوط \(s\)، تحتفظ الخوارزمية بمعلومتين: قيمة المتتالية الحالية \(c_s\)، ومتعدد مجموعات \(\mathcal{M}_s\) حجمه \(s\) ويتحكم في جميع الانتقالات اللاحقة. القيم الموجبة فقط هي التي تُخزَّن صراحةً، أما الأصفار فيمثلها العداد \(z_s\).
نكتب متعدد المجموعات على الصورة
\[ \mathcal{M}_s=\{0^{z_s}\}\cup \{v_1^{m_1},v_2^{m_2},\dots,v_r^{m_r}\}, \qquad 0 \lt v_1 \lt \cdots \lt v_r. \]
الأس هنا يعني التكرار: فـ \(v_i^{m_i}\) تعني أن القيمة \(v_i\) تظهر \(m_i\) مرة. والثابت الأساسي للحالة هو
\[ z_s+\sum_{i=1}^{r} m_i=s. \]
وأهم كمية مشتقة من هذه الحالة هي \(P_s(b)\)، أي مجموع أصغر \(b\) عناصر في \(\mathcal{M}_s\). وبما أن الأصفار تأتي أولًا، والقيم الموجبة محفوظة في مجموعات مرتبة تصاعديًا، فإن حساب \(P_s(b)\) لا يحتاج إلى توسيع جميع العناصر، بل يكفيه مرور قصير على المجموعات المضغوطة.
انطلاقًا من موضع هبوط \(s\)، يُبحث عن موضع الهبوط غير البسيط التالي على صورة \(s+d\) حيث \(1\le d\le s\). ولكل مسافة مرشحة \(d\)، تُعرِّف التنفيذات
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor, \qquad g=\left\lceil\frac{d}{\sqrt D}\right\rceil. \]
الكمية \(b\) تحدد عدد أصغر القيم المحمولة التي يجب استهلاكها، بينما تمثل \(g\) الزيادة المشتركة المصاحبة لقفزة طولها \(d\). وعندئذ تكون الكلفة الكلية لهذه القفزة
\[ \operatorname{cost}(d)=P_s(b)+b\,g. \]
وتكون القفزة ممكنة بالضبط عندما
\[ \operatorname{cost}(d)\le C. \]
وتختار الخوارزمية أول قيمة \(d\) تحقق هذا الشرط. وهذه هي الفكرة الحاسمة في الحل: ما إن نعرف أول موضع هبوط ممكن، يصبح كل ما قبله مجرد امتداد خطي بسيط لا حاجة لحسابه عنصرًا عنصرًا.
لا يبدأ الفحص من \(d=1\) بصورة عمياء. بما أن \(g\ge 1\) و \(P_s(b)\ge 0\)، فإن أي قفزة ممكنة لا بد أن تحقق \(b\le C\). ومن العلاقة
\[ b=\left\lfloor\frac{s-d+1}{2}\right\rfloor \]
نستنتج
\[ d\ge s-2C. \]
إذن يمكن تقليص مجال البحث إلى
\[ d\in[\max(1,s-2C),\,s]. \]
وهناك أيضًا حالة احتياطية مضمونة. عندما \(d=s\)، نحصل على
\[ b=\left\lfloor\frac{s-s+1}{2}\right\rfloor=0, \]
ومن ثم \(\operatorname{cost}(s)=0\)، وهي ممكنة دائمًا. لذلك فلكل حالة موضع هبوط تالٍ لا محالة. وهذا الفرع الخاص يعطي إعادة ضبط كاملة: يكون الهبوط التالي عند \(2s\)، وتعود قيمة المتتالية إلى \(C\)، كما ينكمش الجزء الموجب من الحالة إلى نسخة واحدة فقط من \(C\).
افترض أن القفزة المختارة تحقق \(b>0\). ولْيكن \(z_{\mathrm{sel}}=\min(b,z_s)\)، وهو عدد الأصفار المختارة ضمن أصغر \(b\) عناصر. أما العناصر المختارة الأخرى وعددها \(b-z_{\mathrm{sel}}\) فهي أصغر القيم الموجبة في \(\mathcal{M}_s\)، ولنكتبها على الصورة
\[ x_1,\dots,x_{b-z_{\mathrm{sel}}}. \]
عند موضع الهبوط تصبح القيمة الجديدة
\[ c_{s+d}=C-\operatorname{cost}(d). \]
أما القيم الموجبة الجديدة فتُبنى بالشكل
\[ \underbrace{\{g,\dots,g\}}_{z_{\mathrm{sel}}} \cup \{x_1+g,\dots,x_{b-z_{\mathrm{sel}}}+g\}. \]
والحد الأول يعني \(z_{\mathrm{sel}}\) نسخة من \(g\). وإذا كان \(c_{s+d}>0\) فإننا نضيف نسخة أخرى منه. وما عدا ذلك يُعد صفراً، ولهذا فإن عدد الأصفار الجديد يُستنتج مباشرة من شرط أن يصبح الحجم الكلي مساويًا لـ \(s+d\). وفي النهاية تُدمج القيم الموجبة المتساوية من جديد داخل مجموعات. وهذه خطوة التطبيع هي التي تُبقي الحالة مضغوطة.
إذا كانت أول قفزة ممكنة طولها \(d\)، فهذا يعني أنه لا يوجد هبوط خاص عند المواقع الوسيطة \(s+1,s+2,\dots,s+d-1\). قيم هذه المواقع تتبع القاعدة الخطية
\[ c_{s+t}=c_s+t \qquad (1\le t \lt d). \]
إذن المساهمة التي يتم تجاوزها هي مجرد متتالية حسابية بسيطة:
\[ \sum_{t=1}^{d-1}(c_s+t) = (d-1)c_s+\frac{(d-1)d}{2}. \]
وهذا هو السبب الذي يسمح للخوارزمية بالقفز فوق فترات هائلة. فبمجرد معرفة موضع الهبوط التالي، يمكن جمع الكتلة التي تسبقه كلها في \(O(1)\).
حتى حالة التحقق \(T(30,3,3)=190\) تكشف السلوكين الأساسيين. بعد عدة تحديثات تصبح الحالة عند \(s=4\)
\[ c_4=2, \qquad \mathcal{M}_4=\{0,0,1,2\}. \]
لنجرّب \(d=1\). عندئذ
\[ b=\left\lfloor\frac{4-1+1}{2}\right\rfloor=2, \qquad g=\left\lceil\frac{1}{\sqrt 3}\right\rceil=1, \qquad P_4(2)=0, \]
لأن أصغر عنصرين في متعدد المجموعات كلاهما صفر. وبالتالي
\[ \operatorname{cost}(1)=2, \qquad c_5=3-2=1. \]
الصفران المختاران يتحولان إلى نسختين من \(1\)، وقيمة الهبوط تضيف نسخة ثالثة من \(1\). لذلك تصبح الحالة المجمعة التالية
\[ \mathcal{M}_5=\{0,0,1,1,1\}. \]
وفي وقت لاحق، عندما \(s=8\)، تفشل كل القيم \(d<8\) في اختبار الميزانية، فيُستخدم فرع الاحتياط \(d=8\). وهذا يعني أن المواقع من \(9\) إلى \(15\) ليست إلا الجري الحسابي \(1,2,3,4,5,6,7\) فوق \(c_8=0\)، ثم تعود القيمة عند الموقع \(16\) إلى \(c_{16}=3\). هذا الأثر الصغير وحده يوضح لماذا يتناوب الكود بين تحديثات هبوط دقيقة وكتل خطية طويلة.
يحافظ تنفيذا C++ و Python على فهرس الهبوط \(s\)، والقيمة الحالية \(c_s\)، وعدد الأصفار، والمجموعات الموجبة المرتبة. وعند كل هبوط يفحصان المسافات المرشحة \(d\) ابتداءً من \(\max(1,s-2C)\). ولحساب \(g=\lceil d/\sqrt D\rceil\) بطريقة آمنة، يبدآن بتقدير عددي ثم يصححانه باستخدام المتباينة الصحيحة الدقيقة \(g^2D\ge d^2\). وبما أن \(g\) رتيبة مع \(d\)، يمكن بعد ذلك تحديثها تدريجيًا.
لكل مرشح، يحسب التنفيذ \(P_s(b)\) عبر استهلاك الأصفار أولًا، ثم المرور على المجموعات الموجبة من الأصغر إلى الأكبر. وما إن يتجاوز المجموع الجزئي القيمة \(C\)، يتوقف الفحص فورًا لأن هذا المرشح لم يعد ممكنًا. وبعد إيجاد أول قيمة \(d\) ممكنة، ينفذ الكود إما حالة إعادة الضبط \(d=s\)، أو يبني متعدد المجموعات التالي من أصغر العناصر المختارة ثم يعيد دمج القيم الموجبة المتساوية.
حلقة التجميع الخارجية لا توسّع جميع المؤشرات حتى \(N\) أبدًا. فهي تضيف المقطع الحسابي المتجاوز بصيغة مغلقة، ثم تضيف قيمة الهبوط \(c_{s+d}\)، ثم تتابع من الحالة الجديدة. إصدار Python هو ترجمة مدمجة مباشرة للمنطق نفسه. أما إصدار Java فهو مجرد مشغّل خفيف للحساب نفسه؛ إذ يقوم عند الحاجة بترجمة تنفيذ C++ واستدعائه، ولذلك تنتهي اللغات الثلاث إلى النتيجة العددية ذاتها.
لنفرض أن \(J\) هو عدد حالات الهبوط التي تُزار فعليًا. وعند الهبوط رقم \(j\)، لْيكن \(R_j\) عدد المسافات المرشحة التي فُحصت قبل العثور على أول مسافة ممكنة، و\(G_j\) عدد المجموعات الموجبة المختلفة داخل الحالة المضغوطة. كل من اختبار المجموع الجزئي وتحديث الهبوط يفحص في أسوأ الأحوال \(G_j\) مجموعة، ولذلك يمكن كتابة حد علوي آمن على الصورة
\[ O\!\left(\sum_{j=1}^{J} R_j G_j\right). \]
أما الذاكرة فهي \(O(\max_j G_j)\)، لأن الأصفار تمثل ضمنيًا ولأن القيم الموجبة المتساوية تُدمج. وهنا تظهر فائدة الضغط الحقيقية: فقد يكون الفهرس \(s\) هائلًا جدًا، ومع ذلك تظل الحالة ممثلة بعدد صغير من المجموعات فقط. والبرنامج النهائي يكرر هذا الحساب لستة أزواج من المعاملات، وهو مجرد عامل ثابت إضافي.
النقطة الحاسمة هنا نوعية أكثر منها شكلية. فالطريقة الساذجة كانت ستحتاج إلى \(10^{16}\) تحديثًا للمتتالية لكل زوج معاملات، بينما هذه الطريقة تعالج فقط حالات الهبوط الفعلية وتتعامل تحليليًا مع المقاطع الخطية الطويلة الواقعة بينها.