The three solutions show that Random Dealings is organized around a single arithmetic quantity \(X(n)\), and the required task is to evaluate \(X(10000)\) modulo \(10^9+7\). The key point is that the answer is not obtained by simulating individual dealings. Instead, the full result splits into independent dyadic scales \(2^k\), together with one extra correction that appears only when \(n\) is odd.
Write \(M=10^9+7\), and let \(\varepsilon(n)=1\) when \(n\) is odd and \(\varepsilon(n)=0\) when \(n\) is even. The common structure extracted from the implementations is
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
So the real mathematics lies in the scale-dependent sequence \(A_k(n)\). For the scale \(s=2^k\), the contribution is zero before \(n=s\), it has an explicit closed form on the first band \(s \le n \lt 2s\), and after that it follows a longer linear recurrence with a fixed-width rolling sum. Those are the problem-specific objects that drive all three programs.
The solutions encode a clean scale-by-scale description. Once a power-of-two scale \(s=2^k\) is fixed, everything can be expressed in terms of a single sequence \(A_k(n)\) and one auxiliary interval sum.
For every \(k \ge 1\), let \(s=2^k\). The scale \(s\) contributes only when \(n \ge s\), so it is convenient to extend the sequence by \(A_k(n)=0\) for \(n \lt s\). The global answer is then the sum of all active scales, plus the odd-\(n\) correction \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\).
This decomposition is the first important invariant: there is no interaction term mixing different \(k\)-values. Each scale can be solved independently and only combined at the very end with the weight \(2^k\).
The first nonzero values are not produced by the long recurrence. They are given explicitly by
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
So inside the first dyadic band, \(A_k(i)\) is a linear factor times a power of two. This start-up band provides the initial conditions for the rest of the computation. It is treated separately because, before \(i\) reaches \(2s\), the lagged terms at distances \(s\) and \(s+1\) have not both become part of the active history yet.
Once \(i \ge 2s\), the implementations switch to a recurrence. Define the rolling window
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j),$$
where the empty sum is interpreted as \(0\). In particular, when \(s=2\), this window has length \(0\) and vanishes identically.
For every \(i \ge 2s\), the sequence satisfies
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
This shows exactly which history matters: the previous value, two lagged values spaced by the scale \(s\), and the sum of the \(s-2\) values in between. The rolling sum itself obeys
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
That update is crucial. A naive evaluation of \(W_k(i)\) would cost \(O(s)\) per step, but this invariant turns it into \(O(1)\) time per step.
Take \(n=4\). Two scales are active: \(k=1\) with \(s=2\), and \(k=2\) with \(s=4\).
For \(k=1\), the start-up values are \(A_1(2)=1\) and \(A_1(3)=3\). Because \(s=2\), the window term is empty, so the first recurrence step is
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
For \(k=2\), we are exactly at the boundary \(n=s\), so \(A_2(4)=1\). Therefore
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
which matches the built-in checkpoint.
To see a genuine nonempty window, stay with \(k=2\), so \(s=4\). The start-up values are
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
At \(i=8\), the rolling sum is
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
and the recurrence gives
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
This is exactly the pattern used for all larger \(n\): a closed-form start-up region followed by a windowed linear recurrence.
After every active scale has supplied its value \(A_k(n)\), the final answer is assembled as
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Because the scales are independent, this reconstruction is simple: compute each \(A_k(n)\), weight it by \(2^k\), add the odd correction when needed, and reduce modulo \(M\).
The C++, Python, and Java implementations all follow the same mathematical pipeline. They differ only in language-specific orchestration, not in the underlying recurrence.
For a fixed \(k\), the implementation sets \(s=2^k\). If \(n \lt s\), the scale contributes \(0\). If \(s \le n \lt 2s\), it returns the explicit start-up formula immediately. Otherwise it allocates a linear array for the values \(A_k(i)\), seeds the interval \(s \le i \lt 2s\) with the closed form, and initializes the first rolling sum
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j).$$
From there, it advances from \(i=2s\) up to \(i=n\), updating \(A_k(i)\) with the recurrence and then shifting the rolling sum by one step. Powers of two are always taken modulo \(M\) with modular exponentiation.
Once the scale solver is available, the global routine launches one independent task for each \(k\) with \(2^k \le n\). When a task returns \(A_k(n)\), the result is multiplied by \(2^k\) and added into the total. If \(n\) is odd, the extra term \(2^{n-1}-1\) is inserted before the scale sum is accumulated.
All three implementations also verify the same small checkpoints before producing the final answer: \(X(2)=2\), \(X(4)=14\), and \(X(10)=1418\). Those checks are a strong sanity test for both the closed-form start-up band and the long recurrence.
There are \(\lfloor \log_2 n \rfloor\) active scales. For each scale, the implementation performs only constant work per index once the rolling window invariant is in place, so one scale costs \(O(n)\) time. Summed over all scales, the arithmetic work is \(O(n\log n)\).
Memory usage is \(O(n)\) for one active scale because it stores a linear table of values up to \(n\). Since the implementations evaluate different scales independently and can run them in parallel, the peak live memory can be larger in practice, but the mathematical core of each scale remains linear-space.
Die drei Lösungen zeigen, dass Random Dealings um eine einzige arithmetische Größe \(X(n)\) organisiert ist und dass letztlich \(X(10000)\) modulo \(10^9+7\) berechnet werden muss. Entscheidend ist, dass man die einzelnen Dealings nicht direkt simuliert. Stattdessen zerfällt das Ergebnis in unabhängige dyadische Skalen \(2^k\) sowie einen zusätzlichen Korrekturterm, der nur bei ungeradem \(n\) auftritt.
Setze \(M=10^9+7\) und \(\varepsilon(n)=1\) für ungerades \(n\), sonst \(\varepsilon(n)=0\). Die gemeinsame Struktur aus den Implementierungen lautet
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Damit liegt die eigentliche Mathematik in der skalenabhängigen Folge \(A_k(n)\). Für die Skala \(s=2^k\) ist der Beitrag vor \(n=s\) null, auf dem ersten Band \(s \le n \lt 2s\) gilt eine explizite Formel, und danach übernimmt eine lineare Rekursion mit gleitender Fenstersumme. Genau diese Objekte sind problemspezifisch und treiben alle drei Programme.
Die Lösungen kodieren eine saubere Beschreibung Skala für Skala. Sobald eine Zweierpotenz \(s=2^k\) feststeht, lässt sich alles mit einer einzigen Folge \(A_k(n)\) und einer Hilfssumme über ein Intervall formulieren.
Für jedes \(k \ge 1\) sei \(s=2^k\). Die Skala \(s\) trägt nur bei, wenn \(n \ge s\). Deshalb ist es praktisch, die Folge durch \(A_k(n)=0\) für \(n \lt s\) zu erweitern. Die Gesamtantwort ist dann die Summe aller aktiven Skalen plus der ungerade Zusatzterm \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\).
Das ist die erste wichtige Invariante: Es gibt keinen Mischterm zwischen verschiedenen \(k\)-Werten. Jede Skala wird unabhängig gelöst und erst ganz am Ende mit dem Gewicht \(2^k\) zusammengesetzt.
Die ersten von null verschiedenen Werte entstehen noch nicht durch die lange Rekursion. Sie sind direkt gegeben durch
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
Innerhalb dieses ersten dyadischen Bandes ist \(A_k(i)\) also ein linearer Faktor mal einer Zweierpotenz. Dieses Startband liefert die Anfangswerte für den restlichen Ablauf. Es wird getrennt behandelt, weil vor \(i=2s\) die verzögerten Terme im Abstand \(s\) und \(s+1\) noch nicht beide vollständig in der aktiven Historie liegen.
Sobald \(i \ge 2s\) gilt, wechseln die Implementierungen zu einer Rekursion. Definiere die gleitende Fenstersumme
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j),$$
wobei die leere Summe als \(0\) verstanden wird. Insbesondere hat dieses Fenster für \(s=2\) Länge \(0\) und verschwindet vollständig.
Für jedes \(i \ge 2s\) gilt dann
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
Damit ist exakt sichtbar, welche Vergangenheit relevant ist: der unmittelbare Vorgänger, zwei um die Skala \(s\) versetzte Werte und die Summe der \(s-2\) Zwischenwerte. Die Fenstersumme selbst erfüllt
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
Gerade dieses Update ist entscheidend. Eine naive Auswertung von \(W_k(i)\) würde \(O(s)\) pro Schritt kosten; durch diese Invariante wird daraus \(O(1)\) Zeit pro Schritt.
Betrachte \(n=4\). Aktiv sind zwei Skalen: \(k=1\) mit \(s=2\) und \(k=2\) mit \(s=4\).
Für \(k=1\) lauten die Startwerte \(A_1(2)=1\) und \(A_1(3)=3\). Weil bei \(s=2\) das Fenster leer ist, ergibt der erste Rekursionsschritt
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
Für \(k=2\) sind wir genau am Rand \(n=s\), also ist \(A_2(4)=1\). Daher
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
und genau das ist der eingebaute Prüfwert.
Für ein nichtleeres Fenster bleibe bei \(k=2\), also \(s=4\). Die Startwerte sind
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
Bei \(i=8\) ist die Fenstersumme
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
und die Rekursion liefert
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
Genau dieses Muster wird für alle größeren \(n\) verwendet: erst eine explizite Startzone, danach eine fensterbasierte lineare Rekursion.
Sobald jede aktive Skala ihren Wert \(A_k(n)\) geliefert hat, wird die Endantwort als
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}$$
zusammengesetzt. Weil die Skalen unabhängig sind, ist dieser letzte Schritt direkt: jedes \(A_k(n)\) berechnen, mit \(2^k\) gewichten, gegebenenfalls den ungeraden Zusatzterm hinzufügen und alles modulo \(M\) reduzieren.
Die C++-, Python- und Java-Implementierungen folgen alle demselben mathematischen Ablauf. Unterschiede gibt es nur in der sprachspezifischen Organisation, nicht in der Rekursion selbst.
Für ein festes \(k\) setzt die Implementierung \(s=2^k\). Falls \(n \lt s\), liefert die Skala \(0\). Falls \(s \le n \lt 2s\), wird die explizite Startformel sofort verwendet. Andernfalls wird ein lineares Array für die Werte \(A_k(i)\) angelegt, das Intervall \(s \le i \lt 2s\) mit der geschlossenen Formel initialisiert und die erste Fenstersumme
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j)$$
vorbereitet. Von dort aus läuft die Berechnung von \(i=2s\) bis \(i=n\), wobei nach jedem Rekursionsschritt auch das Fenster um genau eine Position weitergeschoben wird. Zweierpotenzen werden stets per modularer Exponentiation unter \(M\) ausgewertet.
Sobald der Solver für eine einzelne Skala feststeht, startet die Gesamtroutine für jedes \(k\) mit \(2^k \le n\) eine unabhängige Aufgabe. Wenn eine Aufgabe \(A_k(n)\) zurückliefert, wird das Ergebnis mit \(2^k\) multipliziert und zur Summe addiert. Ist \(n\) ungerade, kommt vorher noch der Zusatzterm \(2^{n-1}-1\) dazu.
Alle drei Implementierungen prüfen außerdem dieselben kleinen Kontrollwerte, bevor die endgültige Ausgabe erzeugt wird: \(X(2)=2\), \(X(4)=14\) und \(X(10)=1418\). Diese Tests sichern sowohl das Startband als auch die lange Rekursion ab.
Es gibt \(\lfloor \log_2 n \rfloor\) aktive Skalen. Für jede Skala kostet die Berechnung dank der Fensterinvariante nur konstante Arbeit pro Index, also insgesamt \(O(n)\) Zeit pro Skala. Über alle Skalen hinweg ergibt sich damit \(O(n\log n)\) Rechenaufwand.
Der Speicherbedarf beträgt \(O(n)\) für eine einzelne aktive Skala, weil eine lineare Tabelle bis \(n\) gespeichert wird. Da die Implementierungen verschiedene Skalen unabhängig voneinander und parallel auswerten können, kann der praktische Spitzenspeicher größer sein; der mathematische Kern pro Skala bleibt aber linear.
Üç çözüm de Random Dealings probleminin tek bir aritmetik büyüklük \(X(n)\) etrafında kurulduğunu ve istenen şeyin \(X(10000)\) değerini \(10^9+7\) modunda hesaplamak olduğunu gösteriyor. Kritik nokta, tek tek dealing durumlarını simüle etmemek. Bunun yerine toplam sonuç, birbirinden bağımsız ikili ölçeklere \(2^k\) ayrılıyor ve yalnızca \(n\) tek olduğunda görünen ek bir düzeltme terimi ekleniyor.
\(M=10^9+7\) olsun; \(n\) tekse \(\varepsilon(n)=1\), çiftse \(\varepsilon(n)=0\) diyelim. Uygulamalardan çıkarılan ortak yapı şudur:
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Dolayısıyla asıl matematik, ölçeğe bağlı \(A_k(n)\) dizisindedir. \(s=2^k\) ölçeği için katkı \(n=s\) olmadan önce sıfırdır; ilk bant olan \(s \le n \lt 2s\) aralığında kapalı bir form vardır; daha sonra ise sabit genişlikli kayan toplam kullanan daha uzun bir lineer rekürans devreye girer. Üç programı da yöneten problem-özgü nesneler tam olarak bunlardır.
Çözüm dosyaları ölçek ölçek çok temiz bir tanım veriyor. Bir kere \(s=2^k\) sabitlenince, her şey tek bir \(A_k(n)\) dizisi ve ona eşlik eden bir aralık toplamı ile ifade edilebiliyor.
Her \(k \ge 1\) için \(s=2^k\) yazalım. \(s\) ölçeği yalnızca \(n \ge s\) olduğunda katkı verdiği için, \(n \lt s\) için \(A_k(n)=0\) kabul etmek kullanışlıdır. Böylece toplam cevap, aktif olan bütün ölçeklerin toplamı ve tek \(n\) için gelen \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\) düzeltmesinden oluşur.
Bu ilk önemli invariandır: farklı \(k\) değerlerini birbirine karıştıran bir çapraz terim yoktur. Her ölçek bağımsız çözülür ve yalnızca en sonda \(2^k\) ağırlığıyla toplama katılır.
Sıfırdan farklı ilk değerler uzun reküranstan gelmez. Doğrudan
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s)$$
formülüyle verilir. Yani ilk ikili bant içinde \(A_k(i)\), doğrusal bir çarpan ile bir 2 kuvvetinin çarpımıdır. Bu başlangıç bandı geri kalan hesaplamanın başlangıç koşullarını sağlar. Ayrı ele alınmasının nedeni, \(i\) henüz \(2s\) değerine ulaşmadan \(s\) ve \(s+1\) uzaklığındaki gecikmeli terimlerin ikisinin birden aktif geçmişe tam olarak girmemiş olmasıdır.
\(i \ge 2s\) olduğunda uygulamalar bir reküransa geçer. Kayan pencere toplamını
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j)$$
diye tanımlayalım. Boş toplam \(0\) kabul edilir. Özellikle \(s=2\) için bu pencerenin uzunluğu \(0\) olur ve tamamen kaybolur.
Her \(i \ge 2s\) için
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}$$
eşitliği geçerlidir. Böylece geçmişten tam olarak hangi bilgilerin gerektiği açıkça ortaya çıkar: bir önceki değer, ölçek kadar gerideki iki değer ve aradaki \(s-2\) terimin toplamı. Pencerenin kendisi de
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1)$$
şeklinde güncellenir. Kritik fikir budur; aksi halde \(W_k(i)\) her adımda \(O(s)\) zamanda yeniden hesaplanmak zorunda kalırdı. Bu güncelleme ile her adım \(O(1)\) maliyete düşer.
\(n=4\) alalım. İki ölçek aktiftir: \(k=1\) için \(s=2\), \(k=2\) için \(s=4\).
\(k=1\) için başlangıç değerleri \(A_1(2)=1\) ve \(A_1(3)=3\) olur. \(s=2\) olduğundan pencere boştur; dolayısıyla ilk rekürans adımı
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5$$
şeklindedir. \(k=2\) için ise tam sınırdayız; dolayısıyla \(A_2(4)=1\). Böylece
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14$$
elde edilir ve bu da gömülü kontrol değeriyle aynıdır.
Boş olmayan gerçek bir pencere görmek için \(k=2\), yani \(s=4\) üzerinde kalalım. Başlangıç değerleri
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20$$
olur. \(i=8\) anındaki pencere toplamı
$$W_2(8)=A_2(5)+A_2(6)=3+8=11$$
ve rekürans sonucu
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45$$
çıkar. Büyük \(n\) değerlerinin tamamı da aynı şablonu izler: önce kapalı formdaki başlangıç bölgesi, sonra pencere destekli lineer rekürans.
Aktif olan her ölçek \(A_k(n)\) değerini ürettikten sonra son cevap
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}$$
olarak toplanır. Ölçekler bağımsız olduğu için son aşama düzdür: her \(A_k(n)\) hesaplanır, \(2^k\) ile ağırlıklandırılır, gerekiyorsa tek-\(n\) düzeltmesi eklenir ve her şey \(M\) modunda tutulur.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Farklar yalnızca dil düzeyindeki düzenleme biçimindedir; kullanılan rekürans aynıdır.
Sabit bir \(k\) için uygulama önce \(s=2^k\) alır. Eğer \(n \lt s\) ise bu ölçek \(0\) katkı verir. Eğer \(s \le n \lt 2s\) ise doğrudan kapalı form döndürülür. Aksi halde \(A_k(i)\) değerleri için doğrusal bir dizi ayrılır, \(s \le i \lt 2s\) aralığı kapalı form ile doldurulur ve ilk pencere toplamı
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j)$$
başlatılır. Bundan sonra \(i=2s\) ile \(i=n\) arasında ilerlenir; her adımda önce rekürans uygulanır, ardından pencere bir konum kaydırılır. İkili kuvvetler her zaman modüler üs alma ile hesaplanır.
Tek ölçeği çözen yordam hazır olduktan sonra, toplam yordam \(2^k \le n\) olan her \(k\) için bağımsız bir görev başlatır. Bir görev \(A_k(n)\) döndürdüğünde sonuç \(2^k\) ile çarpılır ve toplama eklenir. \(n\) tek ise, ölçek toplamından önce \(2^{n-1}-1\) düzeltmesi eklenir.
Üç uygulamanın hepsi de nihai sonucu üretmeden önce aynı küçük kontrol değerlerini sınar: \(X(2)=2\), \(X(4)=14\) ve \(X(10)=1418\). Bu doğrulamalar hem başlangıç bandını hem de uzun reküransı aynı anda test eder.
Aktif ölçek sayısı \(\lfloor \log_2 n \rfloor\) kadardır. Pencere invarianti sayesinde her ölçek için her indis başına sabit iş yapılır; bu yüzden tek ölçeğin maliyeti \(O(n)\) zamandır. Tüm ölçekler toplandığında aritmetik iş yükü \(O(n\log n)\) olur.
Tek bir aktif ölçeğin bellek kullanımı \(O(n)\) düzeyindedir; çünkü \(n\)'e kadar giden doğrusal bir tablo tutulur. Uygulamalar farklı ölçekleri bağımsız ve paralel biçimde çalıştırabildiği için pratikte tepe bellek daha yüksek olabilir; fakat matematiksel çekirdek ölçek başına yine lineer uzay kullanır.
Las tres soluciones muestran que Random Dealings gira alrededor de una sola cantidad aritmética \(X(n)\), y la tarea final consiste en calcular \(X(10000)\) módulo \(10^9+7\). El punto clave es que no se enumeran directamente las distribuciones o dealings individuales. En su lugar, el resultado total se descompone en escalas diádicas independientes \(2^k\), junto con una corrección adicional que aparece solo cuando \(n\) es impar.
Sea \(M=10^9+7\), y defínase \(\varepsilon(n)=1\) si \(n\) es impar y \(\varepsilon(n)=0\) si \(n\) es par. La estructura común extraída de las implementaciones es
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Por tanto, la parte realmente matemática está en la sucesión dependiente de la escala \(A_k(n)\). Para la escala \(s=2^k\), la contribución es cero antes de \(n=s\), tiene una forma cerrada explícita en la primera banda \(s \le n \lt 2s\), y después sigue una recurrencia lineal de mayor alcance con una suma móvil de anchura fija. Esos son los objetos específicos del problema que utilizan los tres programas.
Los archivos de solución codifican una descripción muy limpia, escala por escala. Una vez fijada una potencia de dos \(s=2^k\), todo puede expresarse mediante una sola sucesión \(A_k(n)\) y una suma auxiliar sobre un intervalo.
Para cada \(k \ge 1\), tomemos \(s=2^k\). La escala \(s\) solo aporta cuando \(n \ge s\), así que conviene prolongar la sucesión definiendo \(A_k(n)=0\) para \(n \lt s\). Entonces la respuesta global es la suma de todas las escalas activas más la corrección impar \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\).
Esta es la primera invariante importante: no hay términos de interacción entre distintos valores de \(k\). Cada escala se resuelve de manera independiente y solo al final se incorpora con el peso \(2^k\).
Los primeros valores no nulos no salen todavía de la recurrencia larga. Están dados explícitamente por
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
Dentro de esta primera banda diádica, \(A_k(i)\) es por tanto un factor lineal multiplicado por una potencia de dos. Esta zona inicial suministra las condiciones iniciales del resto del cálculo. Se trata aparte porque, antes de llegar a \(i=2s\), los términos retrasados a distancias \(s\) y \(s+1\) todavía no han entrado ambos por completo en la historia activa.
Cuando \(i \ge 2s\), las implementaciones cambian a una recurrencia. Definimos la suma móvil
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j),$$
donde la suma vacía se interpreta como \(0\). En particular, si \(s=2\), esa ventana tiene longitud \(0\) y desaparece por completo.
Para todo \(i \ge 2s\), se cumple
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
La fórmula deja claro qué parte del pasado importa realmente: el valor anterior, dos valores retrasados separados por la escala \(s\) y la suma de los \(s-2\) valores intermedios. La propia ventana satisface
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
Esa actualización es esencial. Si se recalculara \(W_k(i)\) desde cero en cada paso, el coste sería \(O(s)\) por índice; con esta invariante, cada transición cuesta solo \(O(1)\).
Tomemos \(n=4\). Hay dos escalas activas: \(k=1\) con \(s=2\), y \(k=2\) con \(s=4\).
Para \(k=1\), los valores iniciales son \(A_1(2)=1\) y \(A_1(3)=3\). Como \(s=2\), el término de ventana es vacío, así que el primer paso recursivo da
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
Para \(k=2\), estamos exactamente en la frontera \(n=s\), por lo que \(A_2(4)=1\). Entonces
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
que coincide con el valor de comprobación incorporado.
Para ver una ventana no vacía de verdad, mantengamos \(k=2\), es decir, \(s=4\). Los valores iniciales son
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
En \(i=8\), la suma móvil vale
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
y la recurrencia produce
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
Ese es exactamente el patrón que se usa para todos los \(n\) mayores: una región inicial con fórmula cerrada y, después, una recurrencia lineal apoyada por una ventana deslizante.
Una vez que cada escala activa ha aportado su valor \(A_k(n)\), la respuesta final se recompone como
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Como las escalas son independientes, esta fase final es directa: se calcula cada \(A_k(n)\), se multiplica por \(2^k\), se añade la corrección impar si hace falta y se reduce todo módulo \(M\).
Las implementaciones en C++, Python y Java siguen exactamente la misma tubería matemática. Solo cambian los detalles de orquestación propios de cada lenguaje, no la recurrencia utilizada.
Para un \(k\) fijo, la implementación toma \(s=2^k\). Si \(n \lt s\), la escala aporta \(0\). Si \(s \le n \lt 2s\), devuelve directamente la fórmula cerrada de la banda inicial. En caso contrario, reserva un arreglo lineal para los valores \(A_k(i)\), inicializa el tramo \(s \le i \lt 2s\) con la fórmula explícita y prepara la primera suma móvil
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j).$$
A partir de ahí avanza desde \(i=2s\) hasta \(i=n\), actualizando \(A_k(i)\) con la recurrencia y desplazando la ventana una posición en cada paso. Las potencias de dos se evalúan siempre módulo \(M\) mediante exponenciación modular.
Una vez disponible el solver de una sola escala, la rutina global lanza una tarea independiente por cada \(k\) con \(2^k \le n\). Cuando una tarea devuelve \(A_k(n)\), ese valor se multiplica por \(2^k\) y se añade al total. Si \(n\) es impar, antes de acumular las escalas se incorpora también el término adicional \(2^{n-1}-1\).
Las tres implementaciones validan además los mismos puntos pequeños antes de producir la salida final: \(X(2)=2\), \(X(4)=14\) y \(X(10)=1418\). Esas comprobaciones verifican al mismo tiempo la zona inicial y la recurrencia larga.
Hay \(\lfloor \log_2 n \rfloor\) escalas activas. Para cada una, gracias a la invariante de la ventana, se hace trabajo constante por índice, de modo que una sola escala cuesta \(O(n)\) tiempo. Sumando todas las escalas, el trabajo aritmético total es \(O(n\log n)\).
El uso de memoria es \(O(n)\) para una escala activa, porque se almacena una tabla lineal hasta \(n\). Como las implementaciones evalúan escalas distintas de forma independiente y pueden hacerlo en paralelo, el pico práctico de memoria puede ser mayor; aun así, el núcleo matemático de cada escala sigue siendo lineal en espacio.
这三份解法表明，Random Dealings 的核心并不是去逐个模拟具体的 dealing 过程，而是围绕一个统一的算术量 \(X(n)\) 来组织计算，最终要求的是 \(X(10000)\bmod (10^9+7)\)。真正重要的结构是：总答案可以拆成若干个彼此独立的二进制尺度 \(2^k\) 的贡献，再加上一个只在 \(n\) 为奇数时出现的额外修正项。
记 \(M=10^9+7\)，并定义 \(\varepsilon(n)=1\) 当 \(n\) 为奇数，\(\varepsilon(n)=0\) 当 \(n\) 为偶数。三份实现共同使用的总公式是
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
因此，真正需要研究的是按尺度划分的序列 \(A_k(n)\)。对固定尺度 \(s=2^k\) 而言，在 \(n=s\) 之前贡献恒为零；在第一段区间 \(s \le n \lt 2s\) 上存在显式闭式；而一旦越过 \(2s\)，就进入一个带有固定宽度滚动区间和的线性递推。这些对象正是本题在解法层面上最关键、也最具体的数学成分。
从解法代码中可以提炼出一个非常清晰的分尺度框架。只要固定某个二的幂尺度 \(s=2^k\)，整件事就可以用一个序列 \(A_k(n)\) 和一个辅助区间和来描述。
对每个 \(k \ge 1\)，令 \(s=2^k\)。这个尺度只有在 \(n \ge s\) 时才会产生贡献，因此把序列延拓为 \(A_k(n)=0\)（当 \(n \lt s\)）会非常方便。这样一来，总答案就是所有活跃尺度的贡献之和，再加上奇数长度时出现的修正项 \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\)。
这里最重要的第一个不变量是：不同的 \(k\) 之间没有交叉耦合项。也就是说，每个尺度都可以单独求解，最后再乘上权重 \(2^k\) 加回总式中。这也是三份实现都可以按尺度并行计算的根本原因。
序列第一次变成非零时，并不是直接由长递推产生的，而是由显式公式给出：
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
因此，在第一个二进制区间内，\(A_k(i)\) 的形状是“一个线性因子乘上一个二的幂”。这段起始区间提供了后续递推所需的全部初值。之所以要单独处理，是因为在 \(i\) 还没有达到 \(2s\) 之前，递推中所需要的两个长跨度滞后项 \(A_k(i-s)\) 和 \(A_k(i-s-1)\) 还没有同时完整进入有效历史范围。
当 \(i \ge 2s\) 时，程序切换到递推关系。定义滚动窗口和
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j).$$
空和按 \(0\) 处理。特别地，当 \(s=2\) 时，这个窗口长度就是 \(0\)，于是窗口项完全消失。
对每个 \(i \ge 2s\)，都有
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
这个式子把真正有用的历史信息刻画得非常明确：只需要前一项、相距 \(s\) 与 \(s+1\) 的两个滞后项，以及中间那 \(s-2\) 个值的总和即可。窗口和本身还满足
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
这一步更新是整套算法能高效运行的关键。如果每次都重新计算 \(W_k(i)\)，那么单步代价会是 \(O(s)\)；而使用这个不变量之后，每前进一步只需要 \(O(1)\) 时间。
先看 \(n=4\)。此时有两个活跃尺度：\(k=1\) 时 \(s=2\)，\(k=2\) 时 \(s=4\)。
对 \(k=1\)，起始值是 \(A_1(2)=1\) 与 \(A_1(3)=3\)。因为 \(s=2\) 时窗口为空，所以第一次递推直接变成
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
对 \(k=2\)，我们正好处在边界 \(n=s\)，因此 \(A_2(4)=1\)。于是
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
这与程序中的内置校验值完全一致。
如果想看一个真正非空的窗口，就继续看 \(k=2\)，即 \(s=4\)。起始区间上的值为
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
当 \(i=8\) 时，窗口和为
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
于是递推给出
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
大规模计算时做的事情完全相同：先用显式公式铺好起始带，再用带窗口和的递推一路推进到目标 \(n\)。
当所有活跃尺度都已经算出 \(A_k(n)\) 之后，最终答案按照
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}$$
进行重组。由于各个尺度之间彼此独立，这一步没有额外难度：算出每个 \(A_k(n)\)，乘上对应的 \(2^k\)，如果 \(n\) 是奇数再加上修正项，最后统一对 \(M\) 取模即可。
C++、Python 和 Java 三份实现遵循的是同一条数学流程线。它们之间的差别只体现在语言层面的调度方式，而不在于核心递推本身。
对固定的 \(k\)，实现先设 \(s=2^k\)。如果 \(n \lt s\)，该尺度直接返回 \(0\)。如果 \(s \le n \lt 2s\)，就直接使用起始带上的闭式公式。否则，程序会分配一个到 \(n\) 为止的线性数组来存储 \(A_k(i)\)，先用闭式填好区间 \(s \le i \lt 2s\)，再初始化第一个窗口和
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j).$$
随后从 \(i=2s\) 一直推进到 \(i=n\)：每一步先用递推式求出新的 \(A_k(i)\)，再把窗口整体右移一格。所有出现的二次幂都通过模 \(M\) 下的快速幂来计算。
有了单尺度求解器以后，总过程会对每个满足 \(2^k \le n\) 的 \(k\) 启动一个独立任务。某个任务返回 \(A_k(n)\) 后，就把它乘上 \(2^k\) 加入总和。如果 \(n\) 为奇数，则在累加尺度贡献之前还要先加入额外项 \(2^{n-1}-1\)。
三份实现还都会在输出最终结果前检查相同的几个小规模值：\(X(2)=2\)、\(X(4)=14\)、\(X(10)=1418\)。这些检查同时覆盖了起始带公式与长递推公式，是非常有力的正确性信号。
活跃尺度的个数是 \(\lfloor \log_2 n \rfloor\)。由于窗口和可以 \(O(1)\) 更新，所以对每个尺度而言，每个下标只做常数次运算，因此单个尺度耗时 \(O(n)\)。把所有尺度加起来，总时间复杂度就是 \(O(n\log n)\)。
单个尺度需要 \(O(n)\) 空间来保存到 \(n\) 为止的线性表。由于程序可以把不同尺度并行执行，实际运行时的峰值内存可能更高；不过从数学算法本身来看，每个尺度仍然只是线性空间。
Все три решения показывают, что в основе Random Dealings лежит одна арифметическая величина \(X(n)\), и в итоге требуется вычислить \(X(10000)\) по модулю \(10^9+7\). Важнейшая идея состоит в том, что отдельные dealing-сценарии не перебираются напрямую. Вместо этого ответ раскладывается на независимые двоичные масштабы \(2^k\), а также на дополнительный поправочный член, который появляется только при нечётном \(n\).
Обозначим \(M=10^9+7\), а \(\varepsilon(n)=1\) для нечётного \(n\) и \(\varepsilon(n)=0\) для чётного. Тогда общая формула, извлекаемая из реализаций, имеет вид
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Следовательно, вся содержательная математика сосредоточена в зависящей от масштаба последовательности \(A_k(n)\). Для масштаба \(s=2^k\) вклад равен нулю до порога \(n=s\), на первом диапазоне \(s \le n \lt 2s\) задаётся явной формулой, а после этого подчиняется линейной рекурсии с окном фиксированной ширины. Именно эти объекты и являются специфическими для данной задачи.
Из кода решений можно извлечь очень чистую послойную схему. Если зафиксирован масштаб \(s=2^k\), то вся динамика описывается одной последовательностью \(A_k(n)\) и одной вспомогательной суммой по интервалу.
Для каждого \(k \ge 1\) положим \(s=2^k\). Масштаб \(s\) вносит вклад только при \(n \ge s\), поэтому удобно продолжить последовательность правилом \(A_k(n)=0\) для \(n \lt s\). Тогда итоговый ответ состоит из суммы всех активных масштабов и нечётной поправки \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\).
Это и есть первый ключевой инвариант: между различными значениями \(k\) нет смешанных членов. Каждый масштаб решается полностью независимо, а затем только в самом конце добавляется в общую сумму с весом \(2^k\).
Первые ненулевые значения ещё не создаются длинной рекурсией. Они задаются явно:
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
Значит, внутри первой двоичной полосы \(A_k(i)\) имеет вид линейного множителя, умноженного на степень двойки. Этот стартовый диапазон даёт начальные условия для остального вычисления. Его приходится обрабатывать отдельно, потому что до момента \(i=2s\) оба дальних лага на расстояниях \(s\) и \(s+1\) ещё не вошли полностью в активную историю.
Когда \(i \ge 2s\), реализации переходят к рекурсии. Введём скользящую сумму
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j),$$
где пустая сумма понимается как \(0\). В частности, при \(s=2\) длина окна равна нулю, и этот член полностью исчезает.
Для каждого \(i \ge 2s\) выполняется соотношение
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
Эта формула точно показывает, какая история действительно нужна: предыдущее значение, два отстоящих на масштаб \(s\) запаздывающих значения и сумма промежуточных \(s-2\) членов. Само окно обновляется по правилу
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
Именно здесь скрыта эффективность метода. Если бы \(W_k(i)\) пересчитывалось с нуля на каждом шаге, цена одного перехода была бы \(O(s)\). Благодаря этому инварианту каждый шаг стоит лишь \(O(1)\).
Возьмём \(n=4\). Активны два масштаба: \(k=1\) с \(s=2\) и \(k=2\) с \(s=4\).
Для \(k=1\) стартовые значения равны \(A_1(2)=1\) и \(A_1(3)=3\). Так как при \(s=2\) окно пусто, первый рекурсивный шаг даёт
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
Для \(k=2\) мы находимся ровно на границе \(n=s\), поэтому \(A_2(4)=1\). Следовательно,
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
что совпадает со встроенной проверкой.
Чтобы увидеть действительно непустое окно, останемся при \(k=2\), то есть \(s=4\). Стартовые значения равны
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
Тогда при \(i=8\)
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
и рекурсия даёт
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
Именно по этой схеме выполняется всё большое вычисление: сначала явная стартовая зона, потом линейная рекурсия с поддерживаемой суммой по окну.
После того как каждая активная шкала дала своё значение \(A_k(n)\), окончательный ответ собирается по формуле
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
Так как масштабы независимы, этот последний шаг прост: вычислить каждое \(A_k(n)\), умножить на \(2^k\), при необходимости добавить нечётную поправку и взять остаток по модулю \(M\).
Реализации на C++, Python и Java следуют одному и тому же математическому конвейеру. Отличается только язык и способ запуска независимых частей, но не сама рекурсия.
Для фиксированного \(k\) программа сначала берёт \(s=2^k\). Если \(n \lt s\), вклад масштаба равен \(0\). Если \(s \le n \lt 2s\), сразу используется явная формула стартовой полосы. Иначе создаётся линейный массив для значений \(A_k(i)\), отрезок \(s \le i \lt 2s\) заполняется по закрытой формуле, а первая скользящая сумма инициализируется как
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j).$$
Дальше цикл идёт от \(i=2s\) до \(i=n\): на каждом шаге новое значение получается по рекурсии, после чего окно сдвигается на одну позицию вправо. Все степени двойки вычисляются по модулю \(M\) с помощью быстрого возведения в степень.
Когда решатель для одной шкалы готов, глобальная процедура запускает независимую задачу для каждого \(k\), удовлетворяющего \(2^k \le n\). После возврата значения \(A_k(n)\) оно умножается на \(2^k\) и добавляется к общей сумме. Если \(n\) нечётно, перед суммированием шкал добавляется ещё и дополнительный член \(2^{n-1}-1\).
Во всех трёх реализациях перед финальным выводом проверяются одни и те же малые контрольные значения: \(X(2)=2\), \(X(4)=14\) и \(X(10)=1418\). Эти проверки одновременно подтверждают корректность стартовой зоны и длинной рекурсии.
Активных масштабов ровно \(\lfloor \log_2 n \rfloor\). Благодаря инварианту для окна на каждый индекс в пределах одной шкалы приходится только константная работа, поэтому одна шкала стоит \(O(n)\) времени. Суммарно по всем шкалам получаем \(O(n\log n)\).
Память для одной активной шкалы равна \(O(n)\), так как хранится линейная таблица значений до \(n\). Поскольку разные шкалы могут вычисляться независимо и параллельно, практический пиковый расход памяти может быть выше, но математическое ядро каждой шкалы остаётся линейным по памяти.
تُظهر الحلول الثلاثة أن مسألة Random Dealings تُصاغ حول كمية حسابية واحدة هي \(X(n)\)، وأن المطلوب في النهاية هو حساب \(X(10000)\) بترديد \(10^9+7\). الفكرة الجوهرية هي أننا لا نحاكي التعاملات الفردية مباشرة. بدلاً من ذلك يُفكَّك الجواب إلى مساهمات مستقلة مرتبطة بمقاييس ثنائية من الشكل \(2^k\)، مع حد تصحيحي إضافي لا يظهر إلا عندما يكون \(n\) فرديًا.
لنكتب \(M=10^9+7\)، ولتكن \(\varepsilon(n)=1\) إذا كان \(n\) فرديًا و\(\varepsilon(n)=0\) إذا كان زوجيًا. الصيغة المشتركة المستخرجة من التطبيقات هي
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
لذلك فجوهر الرياضيات يوجد في المتتالية التابعة للمقياس \(A_k(n)\). عند المقياس \(s=2^k\) تكون المساهمة صفرًا قبل \(n=s\)، ثم تظهر صيغة مغلقة صريحة على الشريط الأول \(s \le n \lt 2s\)، وبعد ذلك تبدأ علاقة رجوعية خطية أطول تعتمد على مجموع نافذة منزلق بعرض ثابت. هذه هي العناصر الخاصة بالمسألة والتي تعتمد عليها الحلول الثلاثة فعلًا.
يمكن استخراج وصف واضح جدًا من ملفات الحلول إذا نظرنا إلى المسألة مقياسًا بعد مقياس. ما إن نثبّت قوة اثنين واحدة \(s=2^k\)، حتى يمكن وصف كل شيء بمتتالية واحدة \(A_k(n)\) ومجموع مساعد على فترة محددة.
لكل \(k \ge 1\) نضع \(s=2^k\). هذا المقياس لا يساهم إلا عندما يكون \(n \ge s\)، لذا فمن المفيد تمديد المتتالية بوضع \(A_k(n)=0\) عندما \(n \lt s\). عندئذ يصبح الجواب الكلي مجموع جميع المقاييس النشطة، مضافًا إليه التصحيح الخاص بالحالة الفردية \(\varepsilon(n)\bigl(2^{n-1}-1\bigr)\).
هذه أول ثابتة بنيوية مهمة: لا توجد حدود مزج بين قيم مختلفة لـ \(k\). كل مقياس يُحل مستقلًا عن غيره، ثم يُضاف فقط في النهاية بعد ضربه في الوزن \(2^k\).
أول القيم غير الصفرية لا تنتج بعدُ من العلاقة الرجوعية الطويلة، بل تُعطى مباشرةً بواسطة
$$A_k(s)=1,\qquad A_k(i)=(i-s+2)\,2^{\,i-s-1}\quad (s \lt i \lt 2s).$$
إذن داخل هذا الشريط الثنائي الأول تكون \(A_k(i)\) عبارة عن عامل خطي مضروب في قوة للعدد \(2\). هذا الشريط يزوّدنا بشروط البدء لباقي الحساب. وسبب معالجته بصورة منفصلة هو أنه قبل بلوغ \(i=2s\)، لم يكن الحدّان المتأخران على المسافتين \(s\) و\(s+1\) قد دخلا معًا دخولًا كاملًا في التاريخ الفعّال بعد.
عندما يصبح \(i \ge 2s\)، تنتقل التطبيقات إلى علاقة رجوعية. نعرّف مجموع النافذة المنزلق بالصيغة
$$W_k(i)=\sum_{j=i-s+1}^{i-2} A_k(j).$$
ويُفهم المجموع الفارغ على أنه \(0\). وبصورة خاصة، إذا كان \(s=2\) فإن طول النافذة يساوي صفرًا، وعندئذ يختفي هذا الحد تمامًا.
ولكل \(i \ge 2s\) تتحقق العلاقة
$$A_k(i)=3A_k(i-1)-W_k(i)-4A_k(i-s)+4A_k(i-s-1)\pmod{M}.$$
توضح هذه الصيغة بدقة أي جزء من الماضي يلزمنا: القيمة السابقة مباشرة، وقيمتان متأخرتان تفصل بينهما مسافة المقياس \(s\)، ومجموع \(s-2\) من القيم الواقعة بينهما. كما أن النافذة نفسها تُحدَّث وفق
$$W_k(i+1)=W_k(i)+A_k(i-1)-A_k(i-s+1).$$
وهذه الخطوة هي السر الحقيقي للكفاءة. فلو أُعيد حساب \(W_k(i)\) من الصفر في كل مرة لكانت الكلفة \(O(s)\) لكل انتقال، أما مع هذا الثابت فتصبح كل خطوة \(O(1)\) فقط.
خذ \(n=4\). عندئذ يوجد مقياسان نشطان: \(k=1\) حيث \(s=2\)، و\(k=2\) حيث \(s=4\).
بالنسبة إلى \(k=1\)، قيم البداية هي \(A_1(2)=1\) و\(A_1(3)=3\). وبما أن \(s=2\) يجعل النافذة فارغة، فإن أول خطوة رجوعية تصبح
$$A_1(4)=3A_1(3)-4A_1(2)+4A_1(1)=3\cdot 3-4\cdot 1+4\cdot 0=5.$$
أما عند \(k=2\) فنحن على الحد تمامًا \(n=s\)، ومن ثم \(A_2(4)=1\). لذلك نحصل على
$$X(4)=2^1A_1(4)+2^2A_2(4)=2\cdot 5+4\cdot 1=14,$$
وهذا يطابق قيمة التحقق المدمجة في التطبيقات.
ولرؤية نافذة غير فارغة فعلًا، نبقى عند \(k=2\) أي \(s=4\). قيم البداية هناك هي
$$A_2(4)=1,\qquad A_2(5)=3,\qquad A_2(6)=8,\qquad A_2(7)=20.$$
وعند \(i=8\) يكون مجموع النافذة
$$W_2(8)=A_2(5)+A_2(6)=3+8=11,$$
ومن ثم تعطي العلاقة الرجوعية
$$A_2(8)=3\cdot 20-11-4\cdot 1+4\cdot 0=45.$$
وهذا هو النمط نفسه الذي يُستخدم لكل القيم الأكبر: منطقة بدء بصيغة مغلقة، ثم تقدمٌ لاحق بعلاقة خطية مدعومة بنافذة منزلق.
بعد أن يعطينا كل مقياس نشط القيمة \(A_k(n)\)، يُعاد بناء الجواب النهائي وفق
$$X(n)\equiv \varepsilon(n)\bigl(2^{n-1}-1\bigr)+\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k A_k(n)\pmod{M}.$$
وبما أن المقاييس مستقلة عن بعضها، فإن هذه الخطوة الأخيرة مباشرة: نحسب كل \(A_k(n)\)، نضربه في \(2^k\)، نضيف التصحيح الفردي عند الحاجة، ثم نأخذ الناتج بترديد \(M\).
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه تمامًا. الاختلافات بينها تنظيمية على مستوى اللغة فقط، لا على مستوى الفكرة أو العلاقة الرجوعية.
لـ \(k\) ثابت، يبدأ التنفيذ بوضع \(s=2^k\). إذا كان \(n \lt s\)، فمساهمة هذا المقياس هي \(0\). وإذا كان \(s \le n \lt 2s\)، فتعاد صيغة البداية المغلقة مباشرة. أما إذا كان \(n \ge 2s\)، فيُنشأ جدول خطي لقيم \(A_k(i)\)، ويُملأ الجزء \(s \le i \lt 2s\) من الصيغة الصريحة، ثم يُهيَّأ أول مجموع نافذة
$$W_k(2s)=\sum_{j=s+1}^{2s-2}A_k(j).$$
بعد ذلك تتقدم الحلقة من \(i=2s\) حتى \(i=n\): تُحسب القيمة الجديدة من العلاقة الرجوعية، ثم تُزاح النافذة خطوة واحدة. أما قوى العدد \(2\) فتُحسب دائمًا بتقنية الأسّ المعياري تحت \(M\).
بعد توفر محلل المقياس الواحد، تطلق العملية العامة مهمة مستقلة لكل \(k\) يحقق \(2^k \le n\). وعندما تعيد مهمة ما القيمة \(A_k(n)\)، تُضرب في \(2^k\) وتُضاف إلى المجموع الكلي. وإذا كان \(n\) فرديًا، فيُضاف الحد الإضافي \(2^{n-1}-1\) قبل جمع مساهمات المقاييس.
كما أن الحلول الثلاثة تتحقق من القيم الصغيرة نفسها قبل إخراج النتيجة النهائية: \(X(2)=2\)، و\(X(4)=14\)، و\(X(10)=1418\). هذه الفحوص تؤكد صحة كل من شريط البداية والعلاقة الرجوعية الطويلة.
عدد المقاييس النشطة هو \(\lfloor \log_2 n \rfloor\). وبفضل ثابت النافذة، تكون كلفة كل فهرس داخل المقياس الواحد ثابتة، لذلك فإن حساب مقياس واحد يكلف \(O(n)\) زمنًا. وبجمع جميع المقاييس نحصل على كلفة كلية مقدارها \(O(n\log n)\).
أما الذاكرة فهي \(O(n)\) لمقياس واحد نشط، لأن التنفيذ يحتفظ بجدول خطي حتى \(n\). وبما أن المقاييس المختلفة يمكن أن تُحسب باستقلالية وبصورة متوازية، فقد يرتفع الاستهلاك العملي الأقصى للذاكرة، لكن اللب الرياضي لكل مقياس يبقى خطيًا في المساحة.