Choose uniformly from all ordered compositions of \(n\) into \(m\) positive integers:
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
After sorting one sampled composition into nondecreasing order, write
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}.$$
The task solved by the code is to compute the expected value of the second shortest piece, namely \(\mathbb{E}[X_{(2)}]\), for the Project Euler parameters \(n=10^7\) and \(m=100\).
By the standard stars-and-bars argument, the number of ordered compositions of \(n\) into \(m\) positive parts is
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}.$$
So every probability in the program is a composition count divided by \(\binom{n-1}{m-1}\).
Because \(X_{(2)}\) is a positive integer, we may use the tail-sum formula
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k).$$
This reduces the whole problem to counting, for each \(k\), how many compositions have second smallest part at least \(k\).
The condition \(X_{(2)}\ge k\) means that at most one part is smaller than \(k\). Equivalently, the composition belongs to one of two disjoint cases:
Case A: all \(m\) parts are at least \(k\).
Case B: exactly one part is in \(\{1,2,\dots,k-1\}\), and the remaining \(m-1\) parts are at least \(k\).
Write \(x_i=y_i+(k-1)\) for every part. Then each \(y_i\ge 1\) and
$$y_1+\cdots+y_m=n-m(k-1).$$
Therefore the number of compositions in Case A is
$$A_k=\binom{n-m(k-1)-1}{m-1}.$$
As usual, this is understood to be \(0\) whenever the top entry is smaller than \(m-1\).
Choose the short position in \(m\) ways. Let that short part have length \(t\), where \(1\le t\le k-1\). The other \(m-1\) parts are at least \(k\), so after subtracting \(k-1\) from each of them we get
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1.$$
For fixed \(t\), the number of such compositions is
$$\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Summing over \(t\) gives
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Now apply the hockey-stick identity:
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}.$$
Hence
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right).$$
Adding the two disjoint cases yields
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}.$$
Dividing by the total number of compositions gives the exact tail used by the solver:
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
Substituting this into the tail-sum identity gives the full expectation. This is the formula implemented in C++, Python, and Java.
The C++ program verifies two test cases before printing the final value. For \((n,m)=(3,2)\), the only compositions are \((1,2)\) and \((2,1)\), so the second shortest piece is always \(2\), hence \(\mathbb{E}[X_{(2)}]=2\).
For \((n,m)=(8,3)\), the denominator is \(\binom{7}{2}=21\). The nonzero tail terms are
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
All later terms are zero, so
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
which matches the checkpoint in the repository.
The implementations avoid constructing huge binomial coefficients directly. They set
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}.$$
Then the tail probability becomes
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k.$$
If the current binomial top is \(a\) and the next step decreases it by \(d\), the ratio update is
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}.$$
This telescoping product is exactly what ratio_binom_drop computes. The variables a_r and a_s track the current top entries for the two numerator terms, while ratio_r and ratio_s hold the normalized values \(R_k\) and \(S_k\). Once a top entry falls below \(r\), that term is set to zero and the loop terminates naturally.
Each loop iteration updates two products of length \(r=m-1\), so one iteration costs \(O(m)\) time. If \(T\) tail levels are nonzero, the full computation costs \(O(Tm)\) time and \(O(1)\) additional memory. Since the top parameters decrease by \(m-1\) or \(m\) at every step, \(T\) is on the order of \(n/(m-1)\). The method is therefore compact in memory and efficient enough for the Project Euler input.
Gleichverteilt wird eine geordnete Komposition von \(n\) in \(m\) positive ganze Teile gewählt:
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
Nach dem Sortieren der Teilstücke in nichtabsteigender Reihenfolge schreiben wir
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}.$$
Gesucht ist der Erwartungswert des zweitkürzesten Stücks, also \(\mathbb{E}[X_{(2)}]\). Genau diese Größe berechnen die C++-, Python- und Java-Lösungen für \(n=10^7\) und \(m=100\).
Mit dem Stars-and-Bars-Argument erhält man für die Anzahl geordneter Kompositionen
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}.$$
Jede im Programm auftauchende Wahrscheinlichkeit ist also ein passender Zähler geteilt durch \(\binom{n-1}{m-1}\).
Da \(X_{(2)}\) eine positive ganzzahlige Zufallsvariable ist, gilt
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k).$$
Damit genügt es, für jedes \(k\) die Anzahl der Kompositionen mit \(X_{(2)}\ge k\) exakt zu bestimmen.
Die Bedingung \(X_{(2)}\ge k\) heißt: Höchstens ein Teil ist kleiner als \(k\). Das zerfällt in zwei disjunkte Fälle:
Fall A: Alle \(m\) Teile sind mindestens \(k\).
Fall B: Genau ein Teil liegt in \(\{1,2,\dots,k-1\}\), die übrigen \(m-1\) Teile sind mindestens \(k\).
Setze für alle Teile \(x_i=y_i+(k-1)\). Dann gilt \(y_i\ge 1\) und
$$y_1+\cdots+y_m=n-m(k-1).$$
Also ist die Anzahl der Kompositionen in Fall A
$$A_k=\binom{n-m(k-1)-1}{m-1}.$$
Ist der obere Binomialparameter kleiner als \(m-1\), wird dieser Ausdruck als \(0\) interpretiert.
Die Position des kurzen Teils kann man in \(m\) Weisen wählen. Hat dieser Teil die Länge \(t\) mit \(1\le t\le k-1\), dann bleiben für die anderen \(m-1\) Teile nach Abzug von \(k-1\)
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1.$$
Für festes \(t\) gibt es daher
$$\binom{n-t-(m-1)(k-1)-1}{m-2}$$
Möglichkeiten. Summiert über alle \(t\) ergibt das
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Mit der Hockey-Stick-Identität folgt
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1},$$
also
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right).$$
Aus \(A_k+B_k\) erhält man
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}.$$
Division durch die Gesamtzahl der Kompositionen liefert genau die im Solver verwendete Formel:
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
Setzt man diese Wahrscheinlichkeit in die Schwanzsummenformel ein, erhält man \(\mathbb{E}[X_{(2)}]\).
Das C++-Programm prüft zwei kleine Testfälle. Für \((n,m)=(3,2)\) gibt es nur \((1,2)\) und \((2,1)\), also ist das zweitkürzeste Stück immer \(2\) und damit \(\mathbb{E}[X_{(2)}]=2\).
Für \((n,m)=(8,3)\) ist der Nenner \(\binom{7}{2}=21\). Die einzigen positiven Schwanzterme sind
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
Danach verschwinden alle weiteren Terme, also
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
genau wie im Checkpoint der Implementierung.
Die Implementierungen berechnen keine riesigen Binomialkoeffizienten direkt. Stattdessen definieren sie
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}.$$
Dann gilt
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k.$$
Sinkt der aktuelle obere Binomialparameter von \(a\) auf \(a-d\), dann wird das Verhältnis per Produktformel aktualisiert:
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}.$$
Genau diese Berechnung übernimmt ratio_binom_drop. Die Variablen a_r und a_s verfolgen die beiden oberen Parameter, ratio_r und ratio_s speichern die normierten Werte \(R_k\) und \(S_k\). Sobald ein oberer Parameter kleiner als \(r\) wird, verschwindet der entsprechende Term und die Schleife endet.
Jede Schleifeniteration aktualisiert zwei Produkte der Länge \(r=m-1\) und kostet damit \(O(m)\) Zeit. Gibt es \(T\) positive Schwanzterme, so beträgt die Gesamtlaufzeit \(O(Tm)\) bei \(O(1)\) Zusatzspeicher. Da die oberen Parameter in jedem Schritt um \(m-1\) beziehungsweise \(m\) sinken, ist \(T\) größenordnungsmäßig \(n/(m-1)\). Der Ansatz ist also speichersparend und für die Zielparameter gut beherrschbar.
\(n\) sayısını \(m\) pozitif tam parçaya ayıran tüm sıralı kompozisyonlar arasından eş olasılıkla seçim yapıyoruz:
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
Seçilen kompozisyonun parça uzunlukları küçükten büyüğe sıralandığında
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}$$
yazılır. Kodun hesapladığı büyüklük ikinci en kısa parçanın beklenen değeri, yani \(\mathbb{E}[X_{(2)}]\) ifadesidir. Depodaki çözümler bunu \(n=10^7\) ve \(m=100\) için hesaplar.
Stars and bars tekniğiyle, \(n\)'in \(m\) pozitif parçaya sıralı ayrışım sayısı
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}$$
olur. Bu yüzden programdaki her olasılık, uygun kompozisyon sayısının \(\binom{n-1}{m-1}\)'e bölünmüş halidir.
\(X_{(2)}\) pozitif tam değerli bir rassal değişken olduğundan
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k)$$
yazabiliriz. Böylece problem, her \(k\) için \(X_{(2)}\ge k\) olayını saymaya indirgenir.
İkinci en kısa parça en az \(k\) ise, \(k\)'den küçük olan parça sayısı en fazla birdir. Bu da iki ayrık duruma bölünür:
Durum A: bütün \(m\) parçalar en az \(k\).
Durum B: tam olarak bir parça \(\{1,2,\dots,k-1\}\) içindedir, kalan \(m-1\) parça ise en az \(k\)'dir.
Her parça için \(x_i=y_i+(k-1)\) yazalım. O zaman \(y_i\ge 1\) ve
$$y_1+\cdots+y_m=n-m(k-1).$$
Dolayısıyla Durum A'daki kompozisyon sayısı
$$A_k=\binom{n-m(k-1)-1}{m-1}$$
olur. Üst parametre \(m-1\)'den küçükse bu terim \(0\) kabul edilir.
Kısa parçanın yeri \(m\) farklı şekilde seçilir. Bu kısa parçanın uzunluğu \(1\le t\le k-1\) olsun. Diğer \(m-1\) parçadan \(k-1\) çıkardığımızda
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1$$
eşitliğini elde ederiz. Sabit \(t\) için sayım
$$\binom{n-t-(m-1)(k-1)-1}{m-2}$$
olur. Tüm \(t\) değerleri üzerinde toplarsak
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}$$
elde edilir. Burada hockey-stick özdeşliği kullanılır:
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}.$$
Böylece
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right)$$
sonucuna ulaşırız.
İki ayrık durumu topladığımızda
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}$$
elde edilir. Toplam kompozisyon sayısına böldüğümüzde, çözümlerin kullandığı kesin formül çıkar:
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
Bunu kuyruk toplam özdeşliğine yerleştirince \(\mathbb{E}[X_{(2)}]\) bulunur.
C++ çözümü sonucu yazdırmadan önce iki küçük örneği test eder. \((n,m)=(3,2)\) için kompozisyonlar yalnızca \((1,2)\) ve \((2,1)\)'dir; ikinci en kısa parça her zaman \(2\) olduğundan \(\mathbb{E}[X_{(2)}]=2\).
\((n,m)=(8,3)\) için payda \(\binom{7}{2}=21\)'dir. Sıfır olmayan kuyruk terimleri şunlardır:
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
Sonraki terimler sıfır olduğundan
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
ve bu değer depodaki checkpoint ile aynıdır.
Kod doğrudan devasa binom katsayıları üretmez. Bunun yerine
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}$$
oranlarını izler. O zaman
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k$$
olur. Üst parametre \(a\) iken bir sonraki adımda \(a-d\)'ye düşüyorsa güncelleme
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}$$
şeklindedir. ratio_binom_drop tam olarak bu çarpımı hesaplar. a_r ve a_s iki üst parametreyi, ratio_r ve ratio_s ise normalize oranları tutar. Üst parametre \(r\)'nin altına indiğinde ilgili terim sıfırlanır ve döngü doğal olarak biter.
Her döngü adımı uzunluğu \(r=m-1\) olan iki çarpımı güncellediği için bir adımın maliyeti \(O(m)\)'dir. Eğer \(T\) adet sıfır olmayan kuyruk seviyesi varsa toplam süre \(O(Tm)\), ek bellek ise \(O(1)\) olur. Üst parametreler her adımda \(m-1\) veya \(m\) kadar azaldığından \(T\), mertebe olarak \(n/(m-1)\) civarındadır. Bu yüzden yöntem hem bellek açısından küçüktür hem de hedef giriş için yeterince hızlıdır.
Se elige uniformemente una composición ordenada de \(n\) en \(m\) enteros positivos:
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
Tras ordenar las longitudes de menor a mayor, escribimos
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}.$$
El objetivo es calcular el valor esperado del segundo trozo más corto, es decir \(\mathbb{E}[X_{(2)}]\). Las tres implementaciones del repositorio resuelven esto para \(n=10^7\) y \(m=100\).
Por stars and bars, el número de composiciones ordenadas de \(n\) en \(m\) partes positivas es
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}.$$
Por tanto, toda probabilidad en el código es un conteo combinatorio dividido por \(\binom{n-1}{m-1}\).
Como \(X_{(2)}\) toma valores enteros positivos, se puede usar
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k).$$
Así, el problema se reduce a contar para cada \(k\) las composiciones cuya segunda parte más pequeña es al menos \(k\).
La condición \(X_{(2)}\ge k\) significa que como mucho una parte es menor que \(k\). Eso se separa en dos casos disjuntos:
Caso A: las \(m\) partes son al menos \(k\).
Caso B: exactamente una parte pertenece a \(\{1,2,\dots,k-1\}\) y las otras \(m-1\) partes son al menos \(k\).
Escribimos \(x_i=y_i+(k-1)\) para todas las partes. Entonces \(y_i\ge 1\) y
$$y_1+\cdots+y_m=n-m(k-1).$$
El número de composiciones del Caso A es
$$A_k=\binom{n-m(k-1)-1}{m-1}.$$
Si el parámetro superior queda por debajo de \(m-1\), este binomial se interpreta como \(0\).
La posición de la parte corta se puede elegir de \(m\) maneras. Si esa parte corta vale \(t\) con \(1\le t\le k-1\), al restar \(k-1\) a las otras \(m-1\) partes obtenemos
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1.$$
Para un \(t\) fijo, el número de posibilidades es
$$\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Sumando sobre todos los \(t\),
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Aplicando la identidad hockey-stick,
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1},$$
y por tanto
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right).$$
Al sumar los dos casos disjuntos se obtiene
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}.$$
Dividiendo por el número total de composiciones aparece exactamente la probabilidad usada por el solver:
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
Insertada en la suma de colas, esta expresión produce \(\mathbb{E}[X_{(2)}]\).
La versión en C++ valida dos ejemplos pequeños. Para \((n,m)=(3,2)\), las únicas composiciones son \((1,2)\) y \((2,1)\); en ambos casos la segunda pieza más corta vale \(2\), así que \(\mathbb{E}[X_{(2)}]=2\).
Para \((n,m)=(8,3)\), el denominador es \(\binom{7}{2}=21\). Los términos no nulos de la cola son
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
No hay más términos positivos, de modo que
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
justo el valor que comprueba el repositorio.
Las implementaciones no forman directamente coeficientes binomiales gigantes. En su lugar fijan
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}.$$
Entonces
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k.$$
Si el parámetro superior actual es \(a\) y el siguiente paso lo reduce en \(d\), el cociente se actualiza con
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}.$$
Eso es exactamente lo que calcula ratio_binom_drop. Las variables a_r y a_s guardan los parámetros superiores actuales, mientras que ratio_r y ratio_s almacenan los cocientes normalizados \(R_k\) y \(S_k\). Cuando el parámetro superior cae por debajo de \(r\), ese término pasa a ser \(0\) y el bucle termina.
Cada iteración actualiza dos productos de longitud \(r=m-1\), así que cuesta \(O(m)\) tiempo. Si existen \(T\) niveles de cola no nulos, el coste total es \(O(Tm)\) con memoria adicional \(O(1)\). Como los parámetros superiores disminuyen en \(m-1\) o \(m\) en cada paso, \(T\) es del orden de \(n/(m-1)\). El método, por tanto, usa memoria constante y resulta práctico para la entrada grande del problema.
在所有把 \(n\) 写成 \(m\) 个正整数有序和的组合中，等概率选取一个：
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
把这 \(m\) 段长度按从小到大排序后记为
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}.$$
题目要求的是第二短那一段的期望值 \(\mathbb{E}[X_{(2)}]\)。仓库中的 C++、Python 和 Java 代码都在计算这个量，并使用参数 \(n=10^7\)、\(m=100\)。
由 stars and bars 可知，把 \(n\) 分成 \(m\) 个正整数有序部分的方案数为
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}.$$
因此程序里的每个概率，都是某个合法组合数再除以 \(\binom{n-1}{m-1}\)。
因为 \(X_{(2)}\) 是正整数值随机变量，所以可以写成
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k).$$
这样问题就化成：对每个 \(k\)，数出有多少个组合满足第二短长度至少为 \(k\)。
\(X_{(2)}\ge k\) 等价于“小于 \(k\) 的部分至多只有一个”。这可以拆成两个互不相交的情形：
情形 A：全部 \(m\) 段都至少为 \(k\)。
情形 B：恰好一段属于 \(\{1,2,\dots,k-1\}\)，其余 \(m-1\) 段都至少为 \(k\)。
对每一段写成 \(x_i=y_i+(k-1)\)。则 \(y_i\ge 1\)，并且
$$y_1+\cdots+y_m=n-m(k-1).$$
所以情形 A 的方案数是
$$A_k=\binom{n-m(k-1)-1}{m-1}.$$
如果上指标小于 \(m-1\)，就按 \(0\) 处理。
先选出那一段偏小的位置，共有 \(m\) 种。设这段的长度为 \(t\)，其中 \(1\le t\le k-1\)。对另外 \(m-1\) 段各减去 \(k-1\) 后，有
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1.$$
固定 \(t\) 时，方案数为
$$\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
于是
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
再用 hockey-stick 恒等式化简：
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}.$$
因此
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right).$$
把两个互斥情形相加得到
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}.$$
再除以总方案数，就得到代码真正使用的公式：
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
把这个结果代回尾和公式，就得到 \(\mathbb{E}[X_{(2)}]\)。
C++ 版本在输出最终结果前会先检查两个小例子。对 \((n,m)=(3,2)\)，只有 \((1,2)\) 与 \((2,1)\) 两个组合，因此第二短长度恒为 \(2\)，所以 \(\mathbb{E}[X_{(2)}]=2\)。
对 \((n,m)=(8,3)\)，分母是 \(\binom{7}{2}=21\)。非零尾项为
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
之后所有项都为零，因此
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
这与仓库中的检查值完全一致。
程序不会直接构造巨大的组合数，而是维护两个归一化比值：
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}.$$
于是有
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k.$$
如果当前上指标是 \(a\)，下一步要减去 \(d\)，则更新公式为
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}.$$
这正是 ratio_binom_drop 所做的事。变量 a_r、a_s 跟踪两个分子中的上指标，ratio_r、ratio_s 保存对应的 \(R_k\)、\(S_k\)。一旦上指标小于 \(r\)，该项就变成 \(0\)，循环也会自然结束。
每次循环都要更新两个长度为 \(r=m-1\) 的乘积，因此单次迭代代价为 \(O(m)\)。若非零尾层数为 \(T\)，总时间复杂度就是 \(O(Tm)\)，额外空间复杂度为 \(O(1)\)。由于上指标每一步都减少 \(m-1\) 或 \(m\)，所以 \(T\) 的数量级约为 \(n/(m-1)\)。对题目的大输入，这个做法在内存和时间上都可接受。
Равновероятно выбирается упорядоченная композиция числа \(n\) в \(m\) положительных частей:
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
После сортировки длин по неубыванию обозначим
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}.$$
Нужно найти математическое ожидание второй по краткости части, то есть \(\mathbb{E}[X_{(2)}]\). Именно это вычисляют решения на C++, Python и Java для параметров \(n=10^7\) и \(m=100\).
По формуле stars and bars число упорядоченных разбиений \(n\) на \(m\) положительных частей равно
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}.$$
Следовательно, любая вероятность в программе есть соответствующий комбинаторный счётчик, делённый на \(\binom{n-1}{m-1}\).
Так как \(X_{(2)}\) принимает положительные целые значения, можно использовать
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k).$$
Значит, задача сводится к точному подсчёту числа композиций, для которых вторая по величине снизу часть не меньше \(k\).
Условие \(X_{(2)}\ge k\) означает, что частей меньше \(k\) не больше одной. Это распадается на два непересекающихся случая:
Случай A: все \(m\) частей не меньше \(k\).
Случай B: ровно одна часть лежит в \(\{1,2,\dots,k-1\}\), а остальные \(m-1\) частей не меньше \(k\).
Положим \(x_i=y_i+(k-1)\) для всех частей. Тогда \(y_i\ge 1\) и
$$y_1+\cdots+y_m=n-m(k-1).$$
Отсюда число композиций в случае A равно
$$A_k=\binom{n-m(k-1)-1}{m-1}.$$
Если верхний параметр биномиального коэффициента меньше \(m-1\), этот член считается равным нулю.
Позицию короткой части можно выбрать \(m\) способами. Пусть её длина равна \(t\), где \(1\le t\le k-1\). Если из остальных \(m-1\) частей вычесть \(k-1\), получим
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1.$$
Для фиксированного \(t\) число вариантов равно
$$\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Суммируя по всем \(t\), имеем
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
Теперь применяется тождество hockey-stick:
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1},$$
поэтому
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right).$$
Складывая два непересекающихся случая, получаем
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}.$$
После деления на общее число композиций выходит точная формула, которую использует решение:
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
Подстановка этой вероятности в формулу суммы хвостов даёт \(\mathbb{E}[X_{(2)}]\).
В версии на C++ есть две проверки. Для \((n,m)=(3,2)\) возможны только композиции \((1,2)\) и \((2,1)\), поэтому вторая по краткости часть всегда равна \(2\), и \(\mathbb{E}[X_{(2)}]=2\).
Для \((n,m)=(8,3)\) знаменатель равен \(\binom{7}{2}=21\). Ненулевые хвостовые члены такие:
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
Дальше все члены равны нулю, так что
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
что совпадает с контрольным значением в репозитории.
Решение не строит огромные биномиальные коэффициенты напрямую. Вместо этого вводятся
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}.$$
Тогда
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k.$$
Если текущий верхний параметр равен \(a\), а на следующем шаге уменьшается на \(d\), используется обновление
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}.$$
Именно это считает функция ratio_binom_drop. Переменные a_r и a_s хранят текущие верхние параметры двух биномиальных коэффициентов, а ratio_r и ratio_s содержат нормированные значения \(R_k\) и \(S_k\). Как только верхний параметр становится меньше \(r\), соответствующий член зануляется, и цикл заканчивается.
На каждой итерации обновляются два произведения длины \(r=m-1\), поэтому одна итерация стоит \(O(m)\) времени. Если ненулевых уровней хвоста \(T\), полная трудоёмкость равна \(O(Tm)\), а дополнительная память составляет \(O(1)\). Поскольку верхние параметры на каждом шаге уменьшаются на \(m-1\) или \(m\), величина \(T\) имеет порядок \(n/(m-1)\). Следовательно, метод использует постоянную память и достаточно эффективен для целевого входа.
نختار بصورة منتظمة من جميع التركيبات المرتبة للعدد \(n\) إلى \(m\) أجزاء صحيحة موجبة:
$$\mathcal{C}_{n,m}=\left\{(x_1,\dots,x_m)\in \mathbb{Z}_{>0}^m : x_1+\cdots+x_m=n\right\}.$$
بعد ترتيب الأطوال تصاعديا نكتب
$$X_{(1)}\le X_{(2)}\le \cdots \le X_{(m)}.$$
المطلوب هو حساب القيمة المتوقعة لطول القطعة الثانية من جهة الأصغر، أي \(\mathbb{E}[X_{(2)}]\). هذا بالضبط ما تنفذه حلول C++ وPython وJava في المستودع عند \(n=10^7\) و\(m=100\).
باستخدام مبدأ stars and bars فإن عدد التركيبات المرتبة للعدد \(n\) إلى \(m\) أجزاء موجبة هو
$$\left|\mathcal{C}_{n,m}\right|=\binom{n-1}{m-1}.$$
إذن كل احتمال في البرنامج هو عدد تركيبي مناسب مقسوما على \(\binom{n-1}{m-1}\).
بما أن \(X_{(2)}\) متغير عشوائي صحيح موجب، فيمكن كتابة
$$\mathbb{E}[X_{(2)}]=\sum_{k\ge 1}\Pr(X_{(2)}\ge k).$$
وهكذا تختزل المسألة إلى عدّ عدد التركيبات التي تحقق \(X_{(2)}\ge k\) لكل قيمة \(k\).
الشرط \(X_{(2)}\ge k\) يعني أن عدد الأجزاء الأصغر من \(k\) لا يتجاوز واحدا. ولذلك ينقسم العد إلى حالتين منفصلتين:
الحالة A: كل الأجزاء \(m\) لا تقل عن \(k\).
الحالة B: يوجد جزء واحد فقط في المجموعة \(\{1,2,\dots,k-1\}\)، بينما الأجزاء \(m-1\) الأخرى لا تقل عن \(k\).
نكتب \(x_i=y_i+(k-1)\) لكل جزء. عندها \(y_i\ge 1\) و
$$y_1+\cdots+y_m=n-m(k-1).$$
ومن ثم يكون عدد التركيبات في الحالة A هو
$$A_k=\binom{n-m(k-1)-1}{m-1}.$$
وإذا صار الحد العلوي أصغر من \(m-1\)، فهذه القيمة تساوي \(0\) بالاصطلاح المستخدم هنا.
يمكن اختيار موضع الجزء القصير بعدد \(m\) طرق. ولنفترض أن طول هذا الجزء هو \(t\) حيث \(1\le t\le k-1\). إذا طرحنا \(k-1\) من كل جزء من الأجزاء الأخرى \(m-1\)، نحصل على
$$z_1+\cdots+z_{m-1}=n-t-(m-1)(k-1),\qquad z_i\ge 1.$$
ولقيمة ثابتة من \(t\)، يكون عدد الاحتمالات
$$\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
وبالتالي
$$B_k=m\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}.$$
وباستخدام هوية hockey-stick نحصل على
$$\sum_{t=1}^{k-1}\binom{n-t-(m-1)(k-1)-1}{m-2}=\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1},$$
ومن ثم
$$B_k=m\left(\binom{n-(m-1)(k-1)-1}{m-1}-\binom{n-m(k-1)-1}{m-1}\right).$$
بجمع الحالتين المنفصلتين نحصل على
$$A_k+B_k=m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}.$$
وبالقسمة على العدد الكلي للتركيبات يظهر التعبير الذي يستخدمه الحل مباشرة:
$$\Pr(X_{(2)}\ge k)=\frac{m\binom{n-(m-1)(k-1)-1}{m-1}-(m-1)\binom{n-m(k-1)-1}{m-1}}{\binom{n-1}{m-1}}.$$
وعند التعويض في هوية مجموع الذيول نحصل على \(\mathbb{E}[X_{(2)}]\).
نسخة C++ تتحقق من مثالين صغيرين قبل طباعة النتيجة النهائية. عندما \((n,m)=(3,2)\)، لا توجد إلا التركيبتان \((1,2)\) و\((2,1)\)، ولذلك تكون القطعة الثانية من جهة الأصغر مساوية دائما لـ \(2\)، أي إن \(\mathbb{E}[X_{(2)}]=2\).
وعندما \((n,m)=(8,3)\)، يكون المقام هو \(\binom{7}{2}=21\). الحدود غير الصفرية هي
$$\Pr(X_{(2)}\ge 1)=1,$$
$$\Pr(X_{(2)}\ge 2)=\frac{3\binom{5}{2}-2\binom{4}{2}}{\binom{7}{2}}=\frac{18}{21}=\frac{6}{7},$$
$$\Pr(X_{(2)}\ge 3)=\frac{3\binom{3}{2}-2\binom{1}{2}}{\binom{7}{2}}=\frac{9}{21}=\frac{3}{7}.$$
وبعد ذلك تصبح جميع الحدود صفرا، لذا
$$\mathbb{E}[X_{(2)}]=1+\frac{6}{7}+\frac{3}{7}=\frac{16}{7},$$
وهو نفس مقدار التحقق الموجود في المستودع.
لا يبني البرنامج معاملات ثنائية ضخمة بصورة مباشرة، بل يتتبع نسبتين مطبعتين:
$$r=m-1,$$
$$R_k=\frac{\binom{n-(m-1)(k-1)-1}{r}}{\binom{n-1}{r}},\qquad S_k=\frac{\binom{n-m(k-1)-1}{r}}{\binom{n-1}{r}}.$$
وعندها يصبح
$$\Pr(X_{(2)}\ge k)=mR_k-(m-1)S_k.$$
إذا كان الحد العلوي الحالي هو \(a\) وينخفض في الخطوة التالية بمقدار \(d\)، فإن التحديث يتم بواسطة
$$\frac{\binom{a-d}{r}}{\binom{a}{r}}=\prod_{j=0}^{r-1}\frac{a-d-j}{a-j}.$$
وهذا هو بالضبط ما تحسبه الدالة ratio_binom_drop. المتغيران a_r وa_s يتابعان الحدين العلويين الحاليين، بينما يحتفظ ratio_r وratio_s بالقيمتين \(R_k\) و\(S_k\). وعندما يصبح الحد العلوي أصغر من \(r\)، يتحول ذلك الحد إلى صفر وتنتهي الحلقة تلقائيا.
كل دورة من الحلقة تحدّث حاصل ضربين طول كل منهما \(r=m-1\)، ولذلك تكلف الدورة الواحدة \(O(m)\) زمنا. إذا كان عدد مستويات الذيل غير الصفرية هو \(T\)، فإن الزمن الكلي يساوي \(O(Tm)\)، مع ذاكرة إضافية \(O(1)\). وبما أن الحدود العلوية تنخفض في كل خطوة بمقدار \(m-1\) أو \(m\)، فإن \(T\) يكون من رتبة \(n/(m-1)\). لذلك فالطريقة ثابتة الذاكرة وعملية بالنسبة لمدخلات المسألة الكبيرة.