We have \(N\) disks, all initially white. One move chooses two endpoints \(A,B \in \{1,\dots,N\}\) independently and uniformly, then flips every disk in the closed interval between them. If a disk is flipped an odd number of times it ends black; if it is flipped an even number of times it ends white.
The quantity of interest is \(E(N,M)\), the expected number of white disks after \(M\) moves. For the target input \(N=10^{10}\) and \(M=4000\), a direct simulation or a direct \(O(N)\) summation is far too slow, so the solution reduces the whole problem to a one-disk probability formula plus a carefully bounded truncation of the final sum.
Fix a disk position \(i\). In one move, disk \(i\) is not flipped exactly when both chosen endpoints lie strictly to its left or both lie strictly to its right. Because ordered pairs \((A,B)\) are chosen uniformly from \(N^2\) possibilities, the one-turn no-flip probability is
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}.$$
Therefore the one-turn flip probability is
$$p_i=1-q_i.$$
It is convenient to combine these into the signed coefficient
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
This is exactly the quantity raised to the \(M\)-th power by the implementations.
For disk \(i\), introduce a sign variable \(S_t \in \{+1,-1\}\), where \(+1\) means white after \(t\) moves and \(-1\) means black. Initially \(S_0=+1\). Each move multiplies the sign by \(+1\) with probability \(q_i\) and by \(-1\) with probability \(p_i\), so
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
Taking expectations repeatedly gives the simple recurrence
$$\mathbb{E}[S_t]=r_i^t,$$
because \(\mathbb{E}[S_0]=1\). Now the white-indicator of disk \(i\) after \(M\) moves is
$$\mathbf{1}_{i,\text{white}}=\frac{1+S_M}{2},$$
hence
$$\Pr(\text{disk } i \text{ is white after } M \text{ moves})=\frac{1+r_i^M}{2}.$$
This is the core closed form. It converts a random sequence of interval flips into a deterministic per-position contribution.
Expected values add even when the disk colors are not independent. Therefore
$$E(N,M)=\sum_{i=1}^{N}\Pr(\text{disk } i \text{ is white after } M \text{ moves})$$
and the previous formula yields
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
So the entire problem is reduced to evaluating the sum of \(r_i^M\) over all positions.
The coefficients are symmetric:
$$r_i=r_{N+1-i}.$$
This follows directly from the formula, since replacing \(i\) by \(N+1-i\) swaps the two squared terms.
On the left half of the board, the sequence is monotone decreasing. A direct subtraction gives
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}.$$
Hence \(r_{i+1} \lt r_i\) whenever \(i \lt N/2\). The importance of this monotonicity is algorithmic: once a threshold is chosen, the last significant edge position can be found by binary search instead of by scanning all the way from the edge to the center.
For large \(M\), any value with \(\lvert r_i\rvert \lt 1\) becomes tiny after taking the \(M\)-th power. Since the disks in the middle have coefficients much farther from \(1\) than the disks near the edges, almost the entire contribution comes from the two boundaries.
Choose a threshold \(0 \lt \rho \lt 1\), and let \(L\) be the largest index on the left side with \(r_L \gt \rho\). By symmetry, the same number of disks is retained on the right side. The approximation is then
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M,$$
because the factor \(1/2\) in the exact formula is canceled by the two symmetric edge blocks.
The omitted middle block contains \(N-2L\) disks. In the large-\(N\) regime where the accelerated method is used, those terms satisfy \(\lvert r_i\rvert \le \rho\), so the neglected contribution is bounded by
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M.$$
The implementations start from a target tail size \(\varepsilon=10^{-4}\) and choose
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M},$$
so that the theoretical omitted contribution is tiny. They then compute the explicit upper bound above and compare it with \(0.005\), the threshold relevant for safe rounding to two decimal places. If needed, the threshold is tightened slightly and the edge sum is recomputed.
The checkpoint \(E(3,1)=10/9\) follows immediately from the formula. For \(N=3\), the edge disks have
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
while the middle disk has
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}.$$
Therefore
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
Squaring the same coefficients gives
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}.$$
These are exactly the small exact checkpoints used by the implementations before the large-input calculation.
The C++, Python, and Java implementations all follow the same structure. For small inputs they evaluate the exact formula
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M$$
directly, which is useful for validation and checkpoint testing. For very large inputs they switch to the accelerated method: compute the coefficient for a single disk, find the edge cutoff by binary search, sum only the retained edge terms, and use symmetry to reconstruct the total contribution.
The expensive part is the edge summation, so the implementation partitions that retained range across multiple workers and combines the partial sums at the end. The arithmetic itself remains simple: each retained disk contributes one power \(r_i^M\), and the final estimate is protected by the tail bound described above.
The exact method is \(O(N)\) time and \(O(1)\) memory, which is fine for checkpoints but impossible for \(N=10^{10}\). The accelerated method uses \(O(\log N)\) work to find the cutoff and \(O(L)\) work to sum the retained edge terms, where \(L \ll N\). Memory usage stays \(O(1)\) apart from a small number of partial accumulators used for parallel execution.
Es gibt \(N\) Scheiben, anfangs alle weiß. In jedem Zug werden zwei Endpunkte \(A,B \in \{1,\dots,N\}\) unabhängig und gleichverteilt gewählt, danach werden alle Scheiben im abgeschlossenen Intervall zwischen ihnen umgedreht. Eine Scheibe ist nach einer ungeraden Anzahl von Flips schwarz und nach einer geraden Anzahl weiterhin weiß.
Gesucht ist \(E(N,M)\), die erwartete Anzahl weißer Scheiben nach \(M\) Zügen. Für die Zielwerte \(N=10^{10}\) und \(M=4000\) ist weder Simulation noch eine direkte Summe über alle Positionen praktikabel. Der Schlüssel ist deshalb eine geschlossene Formel für eine einzelne Position und anschließend eine kontrollierte Abschneidung der vernachlässigbaren Mittelzone.
Fixiere die Position \(i\). Die Scheibe \(i\) wird in einem Zug genau dann nicht gedreht, wenn beide gewählten Endpunkte strikt links von \(i\) oder beide strikt rechts von \(i\) liegen. Da geordnete Paare \((A,B)\) gleichverteilt aus \(N^2\) Möglichkeiten kommen, ist die Ein-Zug-Wahrscheinlichkeit für „kein Flip“
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}.$$
Damit ist die Flip-Wahrscheinlichkeit
$$p_i=1-q_i.$$
Zweckmäßig ist der signierte Faktor
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
Genau diese Größe wird in den Implementierungen zur \(M\)-ten Potenz erhoben.
Für Scheibe \(i\) führen wir eine Vorzeichenvariable \(S_t \in \{+1,-1\}\) ein: \(+1\) bedeutet weiß nach \(t\) Zügen, \(-1\) bedeutet schwarz. Anfangs gilt \(S_0=+1\). Ein weiterer Zug multipliziert das Vorzeichen mit \(+1\) mit Wahrscheinlichkeit \(q_i\) und mit \(-1\) mit Wahrscheinlichkeit \(p_i\). Also
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
Durch wiederholtes Erwartungsbilden folgt
$$\mathbb{E}[S_t]=r_i^t,$$
denn \(\mathbb{E}[S_0]=1\). Der Indikator dafür, dass Scheibe \(i\) nach \(M\) Zügen weiß ist, lautet
$$\mathbf{1}_{i,\text{weiß}}=\frac{1+S_M}{2},$$
und damit
$$\Pr(\text{Scheibe } i \text{ ist nach } M \text{ Zügen weiß})=\frac{1+r_i^M}{2}.$$
Damit ist der zufällige Prozess auf eine einfache deterministische Formel pro Position reduziert.
Erwartungswerte addieren sich auch ohne Unabhängigkeit der einzelnen Scheibenfarben. Deshalb gilt
$$E(N,M)=\sum_{i=1}^{N}\Pr(\text{Scheibe } i \text{ ist nach } M \text{ Zügen weiß})$$
und somit
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
Das gesamte Problem besteht also darin, diese Potenzsumme effizient auszuwerten.
Die Koeffizienten sind spiegelsymmetrisch:
$$r_i=r_{N+1-i}.$$
Auf der linken Hälfte der Scheiben nehmen sie streng ab. Eine direkte Differenz liefert
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}.$$
Also ist \(r_{i+1} \lt r_i\) für \(i \lt N/2\). Diese Monotonie erlaubt es, den letzten relevanten Randindex per binärer Suche zu bestimmen.
Für großes \(M\) werden alle Werte mit \(\lvert r_i\rvert \lt 1\) nach der Potenzierung extrem klein. Die Beiträge aus der Mitte verschwinden daher fast vollständig; übrig bleiben praktisch nur die beiden Randbereiche.
Wähle eine Schranke \(0 \lt \rho \lt 1\), und sei \(L\) der größte linke Index mit \(r_L \gt \rho\). Wegen der Symmetrie wird rechts dieselbe Anzahl von Scheiben behalten. Dann lautet die Näherung
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M,$$
denn der Faktor \(1/2\) aus der exakten Formel wird durch die beiden symmetrischen Randblöcke kompensiert.
Der ausgelassene Mittelblock enthält \(N-2L\) Scheiben. Im großen-\(N\)-Bereich, in dem die beschleunigte Methode eingesetzt wird, gilt dort \(\lvert r_i\rvert \le \rho\). Daher ist der Fehler durch
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M$$
nach oben beschränkt.
Die Implementierungen starten mit \(\varepsilon=10^{-4}\) und setzen
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M}.$$
Anschließend wird die explizite Schranke oben noch einmal mit \(0{,}005\) verglichen, also genau mit dem Sicherheitsabstand, der für korrektes Runden auf zwei Nachkommastellen relevant ist. Falls nötig, wird \(\rho\) leicht verkleinert und die Randsumme neu berechnet.
Die Kontrollgleichung \(E(3,1)=10/9\) fällt direkt aus der Formel. Für \(N=3\) haben die Randpositionen
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
und die mittlere Scheibe hat
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}.$$
Daher
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
Mit quadrierten Koeffizienten folgt ebenso
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}.$$
Genau diese kleinen exakten Werte werden in den Implementierungen als Prüfsteine verwendet.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Struktur. Für kleine Eingaben wird die exakte Formel
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M$$
direkt summiert. Das ist nützlich für Tests und Kontrollwerte. Für sehr große Eingaben wechseln die Programme auf die beschleunigte Variante: den Einzelscheiben-Koeffizienten ausrechnen, den Randgrenzwert per binärer Suche bestimmen, nur die relevanten Randterme summieren und die Symmetrie ausnutzen.
Der teuerste Teil ist die Summe über die Randterme. Deshalb zerlegen die Implementierungen diesen Bereich in mehrere Teilbereiche und addieren die Teilsummen am Ende zusammen. Mathematisch bleibt es bei derselben Formel; beschleunigt wird nur die Auswertung.
Die exakte Methode benötigt \(O(N)\) Zeit und \(O(1)\) Speicher. Das ist für kleine Kontrollfälle akzeptabel, aber nicht für \(N=10^{10}\). Die beschleunigte Methode braucht \(O(\log N)\) für die Grenzsuche und \(O(L)\) für die Summe über die behaltenen Randterme, wobei \(L \ll N\) ist. Der Speicherbedarf bleibt \(O(1)\), abgesehen von wenigen partiellen Akkumulatoren für die parallele Ausführung.
\(N\) adet diskin hepsi başlangıçta beyazdır. Her turda \(A,B \in \{1,\dots,N\}\) uç noktaları birbirinden bağımsız ve eşit olasılıkla seçilir; sonra bu iki uç arasındaki kapalı aralıktaki bütün diskler çevrilir. Bir disk tek sayıda çevrilirse siyah, çift sayıda çevrilirse beyaz kalır.
Aranan büyüklük \(E(N,M)\), yani \(M\) tur sonunda beklenen beyaz disk sayısıdır. Hedef durumda \(N=10^{10}\) ve \(M=4000\) olduğundan, doğrudan benzetim ya da tüm konumlar üzerinden \(O(N)\) toplam almak mümkün değildir. Çözüm bu yüzden önce tek bir disk için kapalı form çıkarır, sonra da toplamın ortadaki ihmal edilebilir bölümünü güvenli bir hata sınırıyla keser.
\(i\). konumdaki diski sabitleyelim. Bu disk bir turda ancak ve ancak seçilen iki uç nokta da \(i\)'nin tamamen solunda veya tamamen sağında kalırsa çevrilmez. Sıralı \((A,B)\) çiftleri \(N^2\) olasılık arasında eşit dağıldığı için, bir turda çevrilmeme olasılığı
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}$$
olur.
Buna karşılık çevrilme olasılığı
$$p_i=1-q_i$$
şeklindedir. Hesabı sadeleştirmek için şu işaretli katsayıyı tanımlarız:
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
İşlemlerde \(M\). kuvvete yükseltilen temel büyüklük tam olarak budur.
\(i\). disk için \(S_t \in \{+1,-1\}\) işaret değişkenini tanımlayalım: \(+1\) disk \(t\) tur sonra beyazsa, \(-1\) siyahsa. Başlangıçta \(S_0=+1\). Bir sonraki tur, bu işareti olasılık \(q_i\) ile \(+1\) ile, olasılık \(p_i\) ile \(-1\) ile çarpar. Dolayısıyla
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
Bunu art arda uygularsak
$$\mathbb{E}[S_t]=r_i^t$$
elde edilir; çünkü \(\mathbb{E}[S_0]=1\). \(M\) tur sonundaki beyazlık göstergesi
$$\mathbf{1}_{i,\text{white}}=\frac{1+S_M}{2}$$
olduğundan
$$\Pr(\text{disk } i \text{ beyaz})=\frac{1+r_i^M}{2}.$$
Böylece rastgele aralık çevirme süreci, her konum için tek bir kapalı forma dönüşür.
Disklerin renkleri bağımsız olmasa bile beklenen değer doğrusal olarak toplanır. Bu yüzden
$$E(N,M)=\sum_{i=1}^{N}\Pr(\text{disk } i \text{ beyaz})$$
ve dolayısıyla
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
Artık tüm problem, \(r_i^M\) toplamını hızlı hesaplamaya indirgenmiştir.
Katsayılar tam simetriktir:
$$r_i=r_{N+1-i}.$$
Çünkü \(i\) yerine \(N+1-i\) yazmak kare terimleri sadece yer değiştirir. Ayrıca sol yarıda dizi tekdüze azalır. Doğrudan fark alırsak
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}$$
bulunur. Dolayısıyla \(i \lt N/2\) iken \(r_{i+1} \lt r_i\).
Bu özellik algoritmik olarak çok önemlidir: belirli bir eşik seçildiğinde, kenardaki son anlamlı konum tek tek denenerek değil ikili arama ile bulunabilir. Ayrıca \(M\) büyük olduğunda \(\lvert r_i\rvert \lt 1\) olan orta bölge terimleri \(M\). kuvvetten sonra çok hızlı küçülür; toplamın asıl katkısı iki kenardan gelir.
\(0 \lt \rho \lt 1\) olacak bir eşik seçelim ve solda \(r_L \gt \rho\) koşulunu sağlayan en büyük indeksi \(L\) ile gösterelim. Simetriden dolayı sağda da aynı sayıda terim tutulur. Böylece yaklaşım
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M$$
şeklini alır; çünkü tam formüldeki \(1/2\) çarpanı iki simetrik kenar bloğu tarafından dengelenir.
Atlanan orta blokta \(N-2L\) disk vardır. Hızlandırılmış yöntemin kullanıldığı büyük-\(N\) rejiminde bu blok için \(\lvert r_i\rvert \le \rho\) olduğundan, ihmal hatası
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M$$
ile sınırlanır.
Uygulamalar önce \(\varepsilon=10^{-4}\) alıp
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M}$$
değerini seçer. Sonra yukarıdaki açık hata sınırını \(0.005\) ile karşılaştırırlar; bu değer iki ondalık basamağa güvenli yuvarlama için kritik eşiktir. Eğer gerekirse \(\rho\) biraz daha küçültülür ve kenar toplamı tekrar alınır.
\(E(3,1)=10/9\) denetimi kapalı formdan hemen çıkar. \(N=3\) için kenar disklerde
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
ortadaki diskte ise
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}$$
vardır. O halde
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
Aynı katsayıları karesini alarak kullanırsak
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}$$
elde edilir. Uygulamalardaki küçük doğrulama örnekleri tam olarak bunlardır.
C++, Python ve Java uygulamalarının mantığı aynıdır. Küçük girişlerde
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M$$
ifadesi doğrudan hesaplanır; bu yöntem kontrol ve doğrulama için kullanışlıdır. Çok büyük girişlerde ise hızlandırılmış yaklaşım devreye girer: tek disk katsayısı hesaplanır, ikili arama ile kenar kesimi bulunur, sadece anlamlı kenar terimleri toplanır ve simetri kullanılarak toplam yeniden kurulur.
Asıl maliyet kenar toplamındadır. Bu yüzden uygulama, tutulan aralığı birden fazla işçiye bölüp kısmi toplamları en sonda birleştirir. Matematik değişmez; hız kazancı yalnızca gereksiz orta terimlerin atılmasından gelir.
Doğrudan yöntem \(O(N)\) zaman ve \(O(1)\) bellek gerektirir. Bu, küçük denetim örnekleri için uygundur ama \(N=10^{10}\) için imkansızdır. Hızlandırılmış yöntemde sınır araması \(O(\log N)\), tutulan kenar terimlerinin toplamı ise \(O(L)\) zaman alır; burada \(L \ll N\) olur. Bellek kullanımı, paralel çalışmadaki birkaç kısmi toplayıcı dışında yine \(O(1)\) düzeyinde kalır.
Hay \(N\) discos, todos blancos al principio. En cada turno se eligen \(A,B \in \{1,\dots,N\}\) de forma uniforme e independiente, y luego se invierten todos los discos del intervalo cerrado comprendido entre esos dos extremos. Un disco termina blanco si ha sido invertido un número par de veces y negro si ha sido invertido un número impar de veces.
Se pide \(E(N,M)\), el número esperado de discos blancos tras \(M\) turnos. Para el caso objetivo \(N=10^{10}\) y \(M=4000\), ni la simulación ni una suma directa sobre los \(N\) discos son viables. La solución usa una fórmula cerrada para un solo disco y después descarta la zona central con una cota de error controlada.
Fijemos la posición \(i\). El disco \(i\) no se invierte en un turno exactamente cuando ambos extremos elegidos quedan estrictamente a su izquierda o ambos quedan estrictamente a su derecha. Como los pares ordenados \((A,B)\) se eligen uniformemente entre \(N^2\) posibilidades, la probabilidad de no invertirlo es
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}.$$
Por tanto, la probabilidad de invertirlo es
$$p_i=1-q_i.$$
Conviene agrupar ambas cantidades en el coeficiente firmado
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
Ese es exactamente el valor que las implementaciones elevan a la potencia \(M\).
Para el disco \(i\), definimos una variable de signo \(S_t \in \{+1,-1\}\): \(+1\) si el disco está blanco tras \(t\) turnos y \(-1\) si está negro. Al inicio \(S_0=+1\). Un turno adicional multiplica el signo por \(+1\) con probabilidad \(q_i\) y por \(-1\) con probabilidad \(p_i\). Por ello,
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
Repitiendo la expectativa obtenemos
$$\mathbb{E}[S_t]=r_i^t,$$
porque \(\mathbb{E}[S_0]=1\). El indicador de que el disco \(i\) está blanco tras \(M\) turnos es
$$\mathbf{1}_{i,\text{white}}=\frac{1+S_M}{2},$$
de modo que
$$\Pr(\text{el disco } i \text{ está blanco tras } M \text{ turnos})=\frac{1+r_i^M}{2}.$$
Así se transforma un proceso aleatorio de muchas inversiones en una contribución cerrada para cada posición.
Las esperanzas se suman aunque los colores de los discos no sean independientes. Entonces
$$E(N,M)=\sum_{i=1}^{N}\Pr(\text{el disco } i \text{ está blanco tras } M \text{ turnos})$$
y por la fórmula anterior
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
Todo el problema queda reducido a evaluar con eficiencia la suma de \(r_i^M\).
Los coeficientes son simétricos respecto del centro:
$$r_i=r_{N+1-i}.$$
Además, en la mitad izquierda decrecen de manera monótona. Restando términos consecutivos se obtiene
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}.$$
Así, para \(i \lt N/2\) se cumple \(r_{i+1} \lt r_i\). Esta observación es esencial para la implementación rápida, porque permite localizar el último índice relevante del borde mediante búsqueda binaria.
Cuando \(M\) es grande, cualquier valor con \(\lvert r_i\rvert \lt 1\) se hace diminuto al elevarlo a la potencia \(M\). Por eso casi toda la contribución útil procede de las dos franjas cercanas a los extremos.
Elegimos un umbral \(0 \lt \rho \lt 1\) y definimos \(L\) como el mayor índice del lado izquierdo con \(r_L \gt \rho\). Por simetría se conservan también \(L\) términos en el lado derecho. La aproximación pasa a ser
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M,$$
porque el factor \(1/2\) de la fórmula exacta se compensa con los dos bloques simétricos de borde.
La parte omitida contiene \(N-2L\) discos. En el régimen de \(N\) grande donde se usa la aceleración, esos términos satisfacen \(\lvert r_i\rvert \le \rho\), y por tanto el error está acotado por
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M.$$
Las implementaciones parten de \(\varepsilon=10^{-4}\) y eligen
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M}.$$
Luego comparan la cota explícita con \(0.005\), que es el margen crítico para redondear con seguridad a dos decimales. Si hace falta, reducen ligeramente el umbral y recalculan la suma del borde.
La verificación \(E(3,1)=10/9\) sale directamente de la fórmula. Para \(N=3\), los discos de los extremos cumplen
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
mientras que el disco central tiene
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}.$$
Así,
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
Si elevamos esos coeficientes al cuadrado obtenemos también
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}.$$
Esos son precisamente dos de los controles exactos que usan las implementaciones antes del caso grande.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Para entradas pequeñas evalúan directamente la fórmula exacta
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M,$$
lo cual sirve para comprobaciones y casos de validación. Para entradas enormes pasan al método acelerado: calculan el coeficiente de un disco, localizan el corte del borde mediante búsqueda binaria, suman solo los términos retenidos y reconstruyen el total usando la simetría.
La parte costosa es la suma de borde. Por eso la implementación divide ese intervalo entre varios trabajadores y combina las sumas parciales al final. La matemática no cambia; solo cambia la manera eficiente de evaluarla.
El método exacto requiere \(O(N)\) tiempo y \(O(1)\) memoria, razonable para comprobaciones pequeñas pero imposible para \(N=10^{10}\). El método acelerado usa \(O(\log N)\) para hallar el punto de corte y \(O(L)\) para sumar los términos retenidos, con \(L \ll N\). La memoria sigue siendo \(O(1)\), salvo unos pocos acumuladores parciales necesarios para la ejecución en paralelo.
共有 \(N\) 个圆盘，初始时全部是白色。每一步都会独立且均匀地选出两个端点 \(A,B \in \{1,\dots,N\}\)，然后把这两个端点之间的闭区间全部翻转。某个圆盘若被翻转奇数次，最后就是黑色；若被翻转偶数次，最后仍是白色。
目标是求 \(M\) 步之后白色圆盘数量的期望 \(E(N,M)\)。在目标参数 \(N=10^{10}\)、\(M=4000\) 下，直接模拟或直接对全部 \(N\) 个位置求和都不可行。实现采用的思路是：先把问题化成单个位置的概率公式，再利用中间区域快速衰减这一事实，只精确计算两端的重要项，并给出严格误差上界。
固定位置 \(i\)。第 \(i\) 个圆盘在一步中 不会 被翻转，当且仅当两个端点都严格落在它左边，或者都严格落在它右边。因为有序对 \((A,B)\) 在全部 \(N^2\) 个可能中等概率出现，所以单步“不翻转”的概率为
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}.$$
于是单步“翻转”的概率就是
$$p_i=1-q_i.$$
实现中最关键的是下面这个带符号系数：
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
后续真正被提升到 \(M\) 次方的就是这个 \(r_i\)。
对第 \(i\) 个圆盘，引入符号变量 \(S_t \in \{+1,-1\}\)：若经过 \(t\) 步后它是白色，则 \(S_t=+1\)；若是黑色，则 \(S_t=-1\)。初始状态显然满足 \(S_0=+1\)。每走一步，符号以概率 \(q_i\) 乘上 \(+1\)，以概率 \(p_i\) 乘上 \(-1\)。因此有
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
连续取期望后得到
$$\mathbb{E}[S_t]=r_i^t,$$
因为 \(\mathbb{E}[S_0]=1\)。而“第 \(i\) 个圆盘在 \(M\) 步后为白色”的指示量可以写成
$$\mathbf{1}_{i,\text{white}}=\frac{1+S_M}{2}.$$
于是
$$\Pr(\text{第 } i \text{ 个圆盘在 } M \text{ 步后为白})=\frac{1+r_i^M}{2}.$$
这一步把一个随机翻转过程化成了每个位置的闭式贡献。
即使不同圆盘之间并不独立，期望仍然可以直接相加，所以
$$E(N,M)=\sum_{i=1}^{N}\Pr(\text{第 } i \text{ 个圆盘在 } M \text{ 步后为白}).$$
代入前式便有
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
因此整个问题的核心就是高效计算 \(\sum r_i^M\)。
这些系数关于中心完全对称：
$$r_i=r_{N+1-i}.$$
因为把 \(i\) 换成 \(N+1-i\) 只会交换两个平方项。更重要的是，在左半边它单调下降。直接计算相邻差值可得
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}.$$
所以当 \(i \lt N/2\) 时，必有 \(r_{i+1} \lt r_i\)。这意味着给定阈值以后，可以用二分搜索找到边界处最后一个“仍然重要”的位置，而不必从边缘一直扫到中间。
当 \(M\) 很大时，只要 \(\lvert r_i\rvert \lt 1\)，其 \(M\) 次方就会迅速变得极小。于是中间区域几乎没有贡献，主要贡献只来自左右两端。
取一个阈值 \(0 \lt \rho \lt 1\)，设 \(L\) 为左半边满足 \(r_L \gt \rho\) 的最大下标。由对称性，右半边也保留同样数量的项。于是可以使用近似
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M,$$
这里之所以没有额外的 \(1/2\)，是因为精确公式中的 \(1/2\) 正好被左右两个对称边缘块抵消。
被省略的中间部分共有 \(N-2L\) 个圆盘。在采用加速算法的大规模情形下，这些位置满足 \(\lvert r_i\rvert \le \rho\)，因此误差满足
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M.$$
实现先取 \(\varepsilon=10^{-4}\)，并设置
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M}.$$
随后再把上面的显式误差上界与 \(0.005\) 比较，因为这是保留两位小数时最关键的安全界。如果还不够稳妥，就把阈值再收紧一点并重新计算边缘和。
以 \(E(3,1)=10/9\) 为例。对于 \(N=3\)，两端圆盘满足
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
中间圆盘满足
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}.$$
于是
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
再把这些系数平方，就得到
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}.$$
这些正是实现里先验证的小型精确检查点。
C++、Python 和 Java 实现遵循同一条主线。对较小输入，它们直接计算精确公式
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M,$$
这一步主要用于验证和检查。对超大输入，则切换到加速方案：先计算单个位置的系数，再用二分法找到边缘截断点，只对保留下来的边缘项求和，最后利用对称性恢复总贡献。
真正耗时的是边缘求和，因此实现会把这部分区间切成多个子区间并行累加，最后把部分和合并。算法本质不变，只是把不重要的中间项全部跳过了。
精确方法的时间复杂度是 \(O(N)\)，空间复杂度是 \(O(1)\)。它适合小规模检查，但不可能直接处理 \(N=10^{10}\)。加速方法中，截断点搜索需要 \(O(\log N)\)，边缘求和需要 \(O(L)\)，其中 \(L \ll N\)。空间仍然保持在 \(O(1)\) 量级，只额外使用少量并行部分和。
Имеется \(N\) дисков, все изначально белые. На каждом ходе независимо и равновероятно выбираются два конца \(A,B \in \{1,\dots,N\}\), после чего переворачиваются все диски в замкнутом интервале между ними. Если конкретный диск был перевернут нечётное число раз, он станет чёрным; если чётное число раз, он останется белым.
Нужно найти \(E(N,M)\), то есть математическое ожидание числа белых дисков после \(M\) ходов. Для целевых параметров \(N=10^{10}\) и \(M=4000\) прямое моделирование и прямое суммирование по всем позициям невозможны. Поэтому решение сводит задачу к формуле для одного диска и затем аккуратно отбрасывает центральную часть суммы, контролируя погрешность сверху.
Зафиксируем позицию \(i\). Диск \(i\) не переворачивается за один ход тогда и только тогда, когда оба выбранных конца лежат строго левее него или оба лежат строго правее него. Так как упорядоченные пары \((A,B)\) равномерно распределены среди \(N^2\) вариантов, вероятность отсутствия переворота равна
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}.$$
Тогда вероятность переворота равна
$$p_i=1-q_i.$$
Удобно объединить эти вероятности в подписанный коэффициент
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
Именно это число затем возводится в степень \(M\).
Для диска \(i\) введём знаковую переменную \(S_t \in \{+1,-1\}\): \(+1\) означает белый цвет после \(t\) ходов, \(-1\) означает чёрный. Изначально \(S_0=+1\). Каждый новый ход умножает знак на \(+1\) с вероятностью \(q_i\) и на \(-1\) с вероятностью \(p_i\), поэтому
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
Повторяя это соотношение, получаем
$$\mathbb{E}[S_t]=r_i^t,$$
так как \(\mathbb{E}[S_0]=1\). Индикатор события «диск \(i\) белый после \(M\) ходов» можно записать как
$$\mathbf{1}_{i,\text{white}}=\frac{1+S_M}{2},$$
откуда следует
$$\Pr(\text{диск } i \text{ белый после } M \text{ ходов})=\frac{1+r_i^M}{2}.$$
Тем самым случайный процесс многих переворотов заменяется точной формулой для каждой позиции.
Линейность математического ожидания не требует независимости цветов разных дисков. Поэтому
$$E(N,M)=\sum_{i=1}^{N}\Pr(\text{диск } i \text{ белый после } M \text{ ходов})$$
и, следовательно,
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
Вся задача сводится к эффективному вычислению суммы степеней \(r_i^M\).
Коэффициенты симметричны:
$$r_i=r_{N+1-i}.$$
Это видно сразу из формулы, потому что замена \(i \mapsto N+1-i\) просто меняет местами два квадратных слагаемых. Кроме того, на левой половине последовательность убывает. Действительно,
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}.$$
Значит, при \(i \lt N/2\) выполняется \(r_{i+1} \lt r_i\). Эта монотонность позволяет находить последний существенный индекс на краю двоичным поиском.
При большом \(M\) любое значение с \(\lvert r_i\rvert \lt 1\) после возведения в степень становится очень маленьким. Поэтому вклад центральной части почти исчезает, и основную роль играют лишь две крайние зоны.
Выберем порог \(0 \lt \rho \lt 1\) и обозначим через \(L\) наибольший индекс слева, для которого \(r_L \gt \rho\). По симметрии справа сохраняется столько же слагаемых. Тогда используется приближение
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M,$$
поскольку множитель \(1/2\) из точной формулы компенсируется двумя симметричными краевыми блоками.
В отброшенной середине остаётся \(N-2L\) дисков. В том большом диапазоне \(N\), где работает ускоренный метод, для этих позиций выполняется \(\lvert r_i\rvert \le \rho\). Поэтому погрешность ограничена сверху:
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M.$$
Реализации начинают с \(\varepsilon=10^{-4}\) и выбирают
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M}.$$
После этого явная оценка ошибки сравнивается с \(0.005\), то есть с границей, важной для корректного округления до двух знаков после запятой. Если запас недостаточен, порог немного ужесточается и краевая сумма пересчитывается.
Проверка \(E(3,1)=10/9\) непосредственно получается из формулы. При \(N=3\) крайние диски имеют
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
а центральный диск имеет
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}.$$
Следовательно,
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
Если возвести те же коэффициенты в квадрат, то получим
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}.$$
Именно такие точные малые контрольные значения используются в реализациях перед вычислением большого случая.
Реализации на C++, Python и Java устроены одинаково. Для небольших входов они напрямую вычисляют точную формулу
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M,$$
что удобно для тестов и контрольных примеров. Для очень больших входов используется ускоренный путь: вычисляется коэффициент для одного диска, двоичным поиском находится граница на краю, затем суммируются только сохранённые краевые члены, а симметрия восстанавливает общий вклад.
Наиболее дорогая часть вычисления - это суммирование краевой полосы. Поэтому реализация делит этот диапазон между несколькими рабочими потоками или процессами и затем складывает частичные суммы. Математика остаётся той же; меняется только способ быстрого вычисления.
Точный метод имеет сложность \(O(N)\) по времени и \(O(1)\) по памяти. Он подходит для малых проверок, но совершенно непригоден при \(N=10^{10}\). Ускоренный метод тратит \(O(\log N)\) на поиск границы и \(O(L)\) на суммирование сохранённых краевых членов, где \(L \ll N\). Память остаётся \(O(1)\), если не считать нескольких частичных накопителей для параллельного суммирования.
لدينا \(N\) قرصاً، وجميعها بيضاء في البداية. في كل خطوة نختار الطرفين \(A,B \in \{1,\dots,N\}\) بصورة مستقلة ومتساوية الاحتمال، ثم نقلب كل الأقراص داخل الفترة المغلقة بينهما. القرص الذي يُقلب عدداً فردياً من المرات ينتهي أسود، والذي يُقلب عدداً زوجياً من المرات يبقى أبيض.
المطلوب هو \(E(N,M)\)، أي العدد المتوقع للأقراص البيضاء بعد \(M\) خطوة. وعند القيم المستهدفة \(N=10^{10}\) و\(M=4000\) لا يمكن الاعتماد على المحاكاة المباشرة ولا على جمعٍ مباشر عبر جميع المواضع. لذلك يعتمد الحل على صيغة مغلقة لقرص واحد، ثم يحذف المنطقة الوسطى من المجموع بعد ضبط خطأ هذا الحذف ضبطاً صارماً.
ثبّت القرص عند الموضع \(i\). هذا القرص لا يُقلب في خطوة واحدة إذا وفقط إذا كان الطرفان المختاران كلاهما على يساره تماماً أو كلاهما على يمينه تماماً. وبما أن الأزواج المرتبة \((A,B)\) تتوزع بالتساوي على \(N^2\) احتمالاً، فإن احتمال عدم القلب في خطوة واحدة هو
$$q_i=\frac{(i-1)^2+(N-i)^2}{N^2}.$$
ومن ثم فإن احتمال القلب هو
$$p_i=1-q_i.$$
ومن الأنسب جمع هاتين الكميتين في معامل ذي إشارة:
$$r_i=q_i-p_i=2q_i-1=\frac{2\big((i-1)^2+(N-i)^2\big)-N^2}{N^2}.$$
وهذا هو المقدار الذي ترفعه التطبيقات إلى القوة \(M\).
للقرص \(i\) نعرّف متغير إشارة \(S_t \in \{+1,-1\}\): القيمة \(+1\) تعني أن القرص أبيض بعد \(t\) خطوة، والقيمة \(-1\) تعني أنه أسود. في البداية لدينا \(S_0=+1\). كل خطوة جديدة تضرب الإشارة في \(+1\) باحتمال \(q_i\) وفي \(-1\) باحتمال \(p_i\). لذلك
$$\mathbb{E}[S_{t+1}\mid S_t]=r_i\,S_t.$$
وبتكرار أخذ التوقع نحصل على
$$\mathbb{E}[S_t]=r_i^t,$$
لأن \(\mathbb{E}[S_0]=1\). أما مؤشر كون القرص \(i\) أبيض بعد \(M\) خطوة فيمكن كتابته على الصورة
$$\mathbf{1}_{i,\text{white}}=\frac{1+S_M}{2}.$$
إذا رمزنا لاحتمال كون القرص \(i\) أبيض بعد \(M\) خطوة بالرمز \(P_i(M)\)، فإن
$$P_i(M)=\frac{1+r_i^M}{2}.$$
وبذلك يتحول المسار العشوائي الطويل إلى مساهمة مغلقة لكل موضع على حدة.
خطية التوقع لا تحتاج إلى استقلال ألوان الأقراص. لذلك
$$E(N,M)=\sum_{i=1}^{N}P_i(M)$$
ومن ثم
$$E(N,M)=\sum_{i=1}^{N}\frac{1+r_i^M}{2}=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M.$$
إذن لبّ المسألة هو حساب مجموع \(r_i^M\) بكفاءة.
المعاملات متناظرة تماماً حول الوسط:
$$r_i=r_{N+1-i}.$$
كما أنها تتناقص رتابياً في النصف الأيسر. فبطرح حدين متجاورين نجد
$$r_{i+1}-r_i=\frac{4(2i-N)}{N^2}.$$
ومن ثم إذا كان \(i \lt N/2\) فإن \(r_{i+1} \lt r_i\). هذه الحقيقة مهمة برمجياً لأنها تسمح بتحديد آخر موضع مهم عند الحافة بواسطة بحث ثنائي بدلاً من المسح الكامل حتى المنتصف.
وعندما تكون \(M\) كبيرة فإن أي قيمة تحقق \(\lvert r_i\rvert \lt 1\) تصبح ضئيلة جداً بعد رفعها إلى القوة \(M\). لذلك يكاد كل الإسهام المفيد يأتي من الحافتين، بينما تخبو مساهمة الوسط بسرعة شديدة.
نختار عتبة \(0 \lt \rho \lt 1\)، ولتكن \(L\) أكبر فهرس في الجهة اليسرى يحقق \(r_L \gt \rho\). وبفعل التناظر نحتفظ بعدد مماثل من الحدود في الجهة اليمنى. عندها تصبح المقاربة
$$E(N,M)\approx \frac{N}{2}+\sum_{i=1}^{L} r_i^M,$$
إذ إن العامل \(1/2\) الموجود في الصيغة الدقيقة يُعادَل بوجود كتلتين متناظرتين على الحافتين.
الجزء المهمل في الوسط يحوي \(N-2L\) قرصاً. وفي نطاق \(N\) الكبير الذي تُستخدم فيه الطريقة المسرّعة، تحقق هذه الحدود \(\lvert r_i\rvert \le \rho\). لذلك يكون الخطأ محدوداً بـ
$$\left|E(N,M)-\left(\frac{N}{2}+\sum_{i=1}^{L} r_i^M\right)\right|\le \frac{1}{2}(N-2L)\rho^M.$$
تبدأ التطبيقات باختيار \(\varepsilon=10^{-4}\)، ثم تأخذ
$$\rho=\left(\frac{2\varepsilon}{N}\right)^{1/M}.$$
بعد ذلك تُقارن القيمة الصريحة لحد الخطأ مع \(0.005\)، وهو الحد الحاسم لضمان التقريب الصحيح إلى منزلتين عشريتين. وإذا لم يكن الأمان كافياً تُشدَّد العتبة قليلاً ويعاد حساب مجموع الحافة.
تتحقق العلاقة \(E(3,1)=10/9\) مباشرة من الصيغة. عندما \(N=3\) يكون للقرصين الطرفيين
$$q_1=q_3=\frac{4}{9},\qquad r_1=r_3=-\frac{1}{9},$$
أما القرص الأوسط فله
$$q_2=\frac{2}{9},\qquad r_2=-\frac{5}{9}.$$
ومن ثم
$$E(3,1)=\frac{3}{2}+\frac{1}{2}\left(-\frac{1}{9}-\frac{5}{9}-\frac{1}{9}\right)=\frac{10}{9}.$$
وبتربيع هذه المعاملات نحصل كذلك على
$$E(3,2)=\frac{3}{2}+\frac{1}{2}\left(\frac{1}{81}+\frac{25}{81}+\frac{1}{81}\right)=\frac{5}{3}.$$
وهذان مثالان صغيران من نقاط التحقق الدقيقة التي تستخدمها التطبيقات قبل الحساب الكبير.
تتبع تطبيقات C++ وPython وJava البنية نفسها. في المُدخلات الصغيرة تُحسب الصيغة الدقيقة
$$E(N,M)=\frac{N}{2}+\frac{1}{2}\sum_{i=1}^{N} r_i^M$$
مباشرة، وهذا مفيد للتحقق والاختبارات. أما في المُدخلات الضخمة فتنتقل التطبيقات إلى النسخة المسرّعة: تحسب معامل القرص المفرد، ثم تحدد موضع القطع عند الحافة ببحث ثنائي، ثم تجمع فقط الحدود المحتفَظ بها، وأخيراً تستخدم التناظر لاسترجاع الإسهام الكلي.
أغلى خطوة حسابياً هي مجموع الحافة، لذلك توزَّع هذه الفترة على عدة عمال ثم تُجمع المجاميع الجزئية في النهاية. الرياضيات لا تتغير؛ الذي يتغير فقط هو طريقة التقييم السريعة.
الطريقة الدقيقة تحتاج إلى زمن \(O(N)\) وذاكرة \(O(1)\)، وهي مناسبة للحالات الصغيرة فقط. أما عند \(N=10^{10}\) فذلك غير ممكن. الطريقة المسرّعة تحتاج إلى \(O(\log N)\) لتحديد موضع القطع و\(O(L)\) لحساب حدود الحافة المحتفَظ بها، حيث \(L \ll N\). وتبقى الذاكرة \(O(1)\) باستثناء عدد قليل من المجاميع الجزئية اللازمة للتنفيذ المتوازي.