For a given \(n\), the quantity to compute is an expected value \(E(n)\) coming from the unfair-race model. The key simplification used by the implementation is that this expectation can be written as the finite sum
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
The target input is \(n=10^6\), so a direct evaluation based on factorials or repeated binomial-coefficient construction would spend most of its time rebuilding the same information. The program instead walks through the terms sequentially and updates each one from the previous one by a compact multiplicative ratio.
The whole method rests on turning the exact summand into a first-term-plus-ratio recurrence. That replaces heavy combinatorial arithmetic by a single linear pass.
Define
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
Then
$$E(n)=\sum_{k=1}^{n}T_k.$$
The last term is especially simple:
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
So it is convenient to separate it and write
$$E(n)=1+\sum_{k=1}^{n-1}T_k.$$
The first nontrivial term is
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}.$$
This matches exactly the starting value used by the implementations.
Instead of recomputing \(T_{k+1}\) from scratch, compare it with \(T_k\):
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
Using
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1},$$
the factors simplify cleanly to
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2).$$
Therefore the whole series can be generated from the recurrence
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}.$$
This is the central algebraic reduction: one exact starting term plus one exact ratio produces every remaining summand.
For large \(n\), both factors in the ratio are close to \(1\). Multiplying powers that are individually near \(1\) is numerically safer in logarithmic form:
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
Exponentiating gives back the ratio:
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
This is why the implementations use a numerically stable \(\log(1+x)\) routine rather than forming the powers directly at every step. It avoids unnecessary cancellation when \(k\) or \(n-k\) is large.
Several useful properties follow immediately from the closed form.
Every term is positive, so the running sum grows monotonically.
The summand is symmetric:
$$T_k=T_{n-k}\qquad (1\le k\le n-1),$$
because
$$\binom{n}{k}=\binom{n}{n-k}$$
and swapping \(k\) with \(n-k\) leaves the remaining factors unchanged. The implementations still keep the simpler full sweep from left to right, but this symmetry is a good consistency check when deriving the formula.
For \(n=4\), the four summands are
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
Hence
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
This matches the numerical checkpoint used by the implementations and shows concretely how the summation formula behaves.
The C++, Python, and Java implementations all follow the same plan. They first handle the trivial case \(n\le 1\), for which the expected value is \(1\). For \(n>1\), they initialize the running term with
$$T_1=\left(\frac{n-1}{n}\right)^{n-1},$$
and initialize the running total with the already known terminal contribution \(1\) plus this first nontrivial term.
They then loop through \(k=1,2,\dots,n-2\). In each iteration, the implementation computes the logarithm of the ratio from Step 3, exponentiates it, multiplies the current term by that ratio, and adds the result to the total. This produces the sequence \(T_2,T_3,\dots,T_{n-1}\) in order without ever rebuilding a factorial or a binomial coefficient.
The same code path also confirms small benchmark values such as \(E(3)=17/9\), \(E(4)=2.21875\), \(E(5)=2.5104\), and \(E(10)=3.66021568\). Once those checkpoints agree, the implementations evaluate the required large input and print the result rounded to four decimal places.
The algorithm performs one loop over \(k=1\) to \(n-2\), and each iteration uses only a constant amount of floating-point arithmetic. Therefore the running time is \(O(n)\). The method stores only the current term, the accumulated total, and a few temporary values, so the memory usage is \(O(1)\). This is precisely why the recurrence is practical even for \(n=10^6\).
Für ein gegebenes \(n\) soll ein Erwartungswert \(E(n)\) aus dem Modell des unfairen Rennens berechnet werden. Die entscheidende Vereinfachung der Implementierungen besteht darin, dass sich dieser Erwartungswert als endliche Summe schreiben lässt:
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
Für die eigentliche Eingabe \(n=10^6\) wäre eine direkte Auswertung über Fakultäten oder immer neu konstruierte Binomialkoeffizienten unnötig teuer. Stattdessen durchläuft das Programm die Summanden nacheinander und erzeugt jeden neuen Summanden aus dem vorherigen über ein kurzes multiplikatives Verhältnis.
Die gesamte Methode beruht darauf, den exakten Summanden in eine Anfangsbedingung plus Quotientenrekurrenz umzuschreiben. Dadurch wird schwerfällige kombinatorische Arithmetik durch einen einzigen linearen Durchlauf ersetzt.
Definiere
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
Dann gilt
$$E(n)=\sum_{k=1}^{n}T_k.$$
Der letzte Term ist besonders einfach:
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
Daher ist es praktisch, ihn abzutrennen und
$$E(n)=1+\sum_{k=1}^{n-1}T_k$$
zu schreiben. Der erste nichttriviale Summand ist
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}.$$
Genau mit diesem Wert starten die Implementierungen.
Statt \(T_{k+1}\) jedes Mal neu zu berechnen, vergleichen wir es mit \(T_k\):
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
Mit
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1}$$
vereinfacht sich das zu
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2).$$
Damit erhalten wir die Rekurrenz
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}.$$
Das ist die zentrale algebraische Reduktion: Ein exakter Startwert und ein exakter Quotient erzeugen alle restlichen Summanden.
Für großes \(n\) liegen beide Faktoren des Quotienten nahe bei \(1\). Numerisch stabiler ist daher die Logarithmenform:
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
Durch Exponentiation erhält man den Quotienten zurück:
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
Deshalb verwenden die Implementierungen eine numerisch stabile \(\log(1+x)\)-Auswertung, anstatt in jeder Iteration die Potenzen direkt auszurechnen. So wird unnötige Auslöschung vermieden, wenn \(k\) oder \(n-k\) groß ist.
Aus der geschlossenen Form folgen sofort einige nützliche Beobachtungen.
Jeder Summand ist positiv, also wächst die laufende Summe monoton.
Außerdem ist der Summand symmetrisch:
$$T_k=T_{n-k}\qquad (1\le k\le n-1),$$
denn
$$\binom{n}{k}=\binom{n}{n-k}.$$
Vertauscht man \(k\) und \(n-k\), bleiben auch die übrigen Faktoren unverändert. Die Implementierungen behalten trotzdem den einfacheren vollständigen Durchlauf von links nach rechts bei; die Symmetrie ist aber eine gute Plausibilitätskontrolle.
Für \(n=4\) lauten die vier Summanden
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
Also
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
Genau dieser Wert erscheint auch als Kontrollwert in den Implementierungen und zeigt konkret, wie die Summenformel arbeitet.
Die Implementierungen in C++, Python und Java folgen alle demselben Plan. Zuerst behandeln sie den trivialen Fall \(n\le 1\), für den der Erwartungswert gleich \(1\) ist. Für \(n>1\) initialisieren sie den laufenden Summanden mit
$$T_1=\left(\frac{n-1}{n}\right)^{n-1},$$
und setzen die laufende Summe sofort auf den bereits bekannten Endbeitrag \(1\) plus diesen ersten nichttrivialen Term.
Dann durchläuft die Implementierung \(k=1,2,\dots,n-2\). In jedem Schritt wird der Logarithmus des Quotienten aus Schritt 3 berechnet, exponentiert, mit dem aktuellen Summanden multipliziert und zum Total addiert. So entstehen \(T_2,T_3,\dots,T_{n-1}\) der Reihe nach, ohne jemals Fakultäten oder Binomialkoeffizienten neu aufzubauen.
Zusätzlich werden kleine Referenzwerte wie \(E(3)=17/9\), \(E(4)=2.21875\), \(E(5)=2.5104\) und \(E(10)=3.66021568\) geprüft. Erst danach wird die große Zieleingabe ausgewertet und das Ergebnis mit vier Nachkommastellen ausgegeben.
Der Algorithmus benötigt genau eine Schleife über \(k=1\) bis \(n-2\), und jede Iteration führt nur konstant viele Gleitkommaoperationen aus. Die Laufzeit beträgt daher \(O(n)\). Gespeichert werden nur der aktuelle Summand, die akkumulierte Summe und einige temporäre Werte, also ist der Speicherverbrauch \(O(1)\). Gerade diese Rekurrenz macht die Berechnung für \(n=10^6\) praktikabel.
Verilen bir \(n\) için, unfair race modelinden gelen bir beklenen değer \(E(n)\) hesaplanır. Uygulamanın kullandığı temel sadeleşme, bu beklenen değerin sonlu bir toplam olarak yazılabilmesidir:
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
Hedef giriş \(n=10^6\) olduğu için, faktöriyelleri ya da binom katsayılarını her adımda baştan üretmek gereksiz derecede pahalı olurdu. Bunun yerine program terimleri sırayla gezer ve her yeni terimi bir öncekinden kısa bir çarpımsal oranla elde eder.
Bütün yöntem, tam toplam terimini bir başlangıç değeri ve oran bağıntısı biçimine çevirmeye dayanır. Böylece ağır kombinatorik hesap, tek bir doğrusal geçişe indirgenir.
Şunu tanımlayalım:
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
O zaman
$$E(n)=\sum_{k=1}^{n}T_k.$$
Son terim çok basittir:
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
Bu yüzden onu ayırıp
$$E(n)=1+\sum_{k=1}^{n-1}T_k$$
şeklinde yazmak kullanışlıdır. İlk trivial olmayan terim ise
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}$$
olur. Uygulamalar tam olarak bu başlangıç değeriyle başlar.
\(T_{k+1}\) terimini her seferinde sıfırdan hesaplamak yerine, onu \(T_k\) ile karşılaştıralım:
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
Burada
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1}$$
olduğu için oran sadeleşir ve
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2)$$
elde edilir. Dolayısıyla
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}$$
bağıntısı tüm terimleri üretir. Asıl cebirsel kazanım budur.
Büyük \(n\) için orandaki iki çarpan da \(1\)'e çok yakındır. Bu nedenle logaritmik biçim daha kararlıdır:
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
Sonra üs alınarak oran geri elde edilir:
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
Bu yüzden uygulamalar, her adımda kuvvetleri doğrudan kurmak yerine sayısal olarak kararlı bir \(\log(1+x)\) değerlendirmesi kullanır. Böylece \(k\) ya da \(n-k\) büyükken hassasiyet kaybı azaltılır.
Kapalı formdan bazı yararlı özellikler hemen çıkar.
Her terim pozitiftir; dolayısıyla kısmi toplam monoton artar.
Ayrıca toplam terimi simetriktir:
$$T_k=T_{n-k}\qquad (1\le k\le n-1),$$
çünkü
$$\binom{n}{k}=\binom{n}{n-k}$$
ve \(k\) ile \(n-k\) yer değiştirince diğer çarpanlar da aynı kalır. Uygulamalar yine de soldan sağa tam tarama yapar; ancak bu simetri, formülün doğru kurulduğunu kontrol etmek için faydalıdır.
\(n=4\) olduğunda dört terim şunlardır:
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
Böylece
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
Bu değer, uygulamaların kullandığı küçük testlerden biriyle birebir uyuşur ve toplamın nasıl davrandığını somut biçimde gösterir.
C++, Python ve Java uygulamalarının matematiksel çekirdeği aynıdır. Önce \(n\le 1\) durumu ele alınır; bu durumda beklenen değer doğrudan \(1\)'dir. \(n>1\) için ilk çalışan terim
$$T_1=\left(\frac{n-1}{n}\right)^{n-1}$$
olarak başlatılır ve toplam da önceden bilinen son katkı \(1\) ile bu ilk terimin toplamı olarak ayarlanır.
Daha sonra uygulama \(k=1,2,\dots,n-2\) üzerinde döner. Her adımda 3. adımdaki logaritmik oran hesaplanır, üssü alınır, mevcut terim bu oranla çarpılır ve sonuca eklenir. Böylece \(T_2,T_3,\dots,T_{n-1}\) sırasıyla elde edilir; faktöriyel ya da binom katsayısı hiç yeniden kurulmaz.
Aynı yaklaşım küçük doğrulama noktalarında da kontrol edilir: \(E(3)=17/9\), \(E(4)=2.21875\), \(E(5)=2.5104\) ve \(E(10)=3.66021568\). Bu değerler sağlandıktan sonra büyük hedef girdi hesaplanır ve çıktı dört ondalık basamakla yazdırılır.
Algoritma \(k=1\) ile \(n-2\) arasında tek bir döngü çalıştırır ve her yinelemede sabit sayıda kayan noktalı işlem yapar. Bu yüzden zaman karmaşıklığı \(O(n)\)'dir. Saklanan durum sadece mevcut terim, birikimli toplam ve birkaç geçici değerden oluştuğu için bellek kullanımı \(O(1)\)'dir. Reküransın asıl gücü, \(n=10^6\) için bile uygulanabilir olmasıdır.
Para un valor dado de \(n\), hay que calcular un valor esperado \(E(n)\) asociado al modelo de la carrera injusta. La simplificación clave utilizada por la implementación es que dicho valor esperado puede escribirse como la suma finita
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
La entrada objetivo es \(n=10^6\), así que una evaluación directa con factoriales o con reconstrucción repetida de coeficientes binomiales sería innecesariamente costosa. En lugar de eso, el programa recorre los términos en orden y obtiene cada término nuevo a partir del anterior mediante una razón multiplicativa compacta.
Todo el método consiste en transformar el sumando exacto en una recurrencia formada por un primer término y una razón entre vecinos. Eso sustituye aritmética combinatoria pesada por un único recorrido lineal.
Definimos
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
Entonces
$$E(n)=\sum_{k=1}^{n}T_k.$$
El último término es especialmente simple:
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
Por eso conviene separarlo y escribir
$$E(n)=1+\sum_{k=1}^{n-1}T_k.$$
El primer término no trivial es
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}.$$
Ese es exactamente el valor inicial usado por las implementaciones.
En vez de recalcular \(T_{k+1}\) desde cero, lo comparamos con \(T_k\):
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
Usando
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1},$$
la expresión se simplifica a
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2).$$
Por tanto, la recurrencia queda
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}.$$
Esta es la reducción algebraica central: un término inicial exacto y una razón exacta generan todos los sumandos restantes.
Cuando \(n\) es grande, ambos factores de la razón están muy cerca de \(1\). Por estabilidad numérica resulta mejor trabajar con logaritmos:
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
Luego se recupera la razón mediante la exponencial:
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
Por eso las implementaciones usan una rutina estable para \(\log(1+x)\) en vez de formar potencias directas en cada iteración. Así se evita pérdida de precisión cuando \(k\) o \(n-k\) es grande.
La forma cerrada revela varias propiedades útiles.
Cada sumando es positivo, de modo que la suma parcial crece de forma monótona.
Además, el término es simétrico:
$$T_k=T_{n-k}\qquad (1\le k\le n-1),$$
porque
$$\binom{n}{k}=\binom{n}{n-k}$$
y al intercambiar \(k\) por \(n-k\) los demás factores permanecen iguales. Las implementaciones conservan el barrido completo de izquierda a derecha por simplicidad, pero esta simetría sirve como comprobación matemática.
Si \(n=4\), los cuatro sumandos son
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
Entonces
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
Ese valor coincide con uno de los puntos de comprobación de las implementaciones y muestra de forma concreta cómo funciona la suma.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero resuelven el caso trivial \(n\le 1\), donde el valor esperado es \(1\). Para \(n>1\), inicializan el término corriente con
$$T_1=\left(\frac{n-1}{n}\right)^{n-1},$$
y fijan la suma acumulada como el aporte final ya conocido, \(1\), más este primer término no trivial.
Después recorren \(k=1,2,\dots,n-2\). En cada iteración, la implementación calcula el logaritmo de la razón del Paso 3, toma la exponencial, multiplica el término actual por esa razón y añade el resultado al total. Así se obtienen \(T_2,T_3,\dots,T_{n-1}\) en orden, sin reconstruir jamás factoriales ni coeficientes binomiales.
El mismo procedimiento también valida varios valores pequeños: \(E(3)=17/9\), \(E(4)=2.21875\), \(E(5)=2.5104\) y \(E(10)=3.66021568\). Tras comprobar esas referencias, las implementaciones evalúan la entrada grande pedida y muestran el resultado con cuatro cifras decimales.
El algoritmo realiza un único bucle sobre \(k=1\) hasta \(n-2\), y cada iteración usa una cantidad constante de operaciones en coma flotante. Por tanto, el tiempo total es \(O(n)\). Solo se almacenan el término actual, la suma acumulada y unas pocas cantidades temporales, de modo que la memoria es \(O(1)\). Esa es la razón por la que la recurrencia sigue siendo práctica incluso para \(n=10^6\).
对于给定的 \(n\)，需要计算一个来自 unfair race 模型的期望值 \(E(n)\)。实现采用的关键化简是：这个期望值可以写成一个完全显式的有限和
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
真正要计算的输入是 \(n=10^6\)。如果每一项都重新构造阶乘或二项式系数，代价会非常高，而且很多中间信息都在重复。程序因此不直接逐项重算，而是先求出第一个非平凡项，再通过相邻项之间的乘法比值把整列项顺次推出来。
整个方法的核心，是把精确求和公式改写成“首项 + 相邻比值递推”的形式。这样做以后，原本笨重的组合计算就变成了一次线性扫描。
记
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
那么总期望就是
$$E(n)=\sum_{k=1}^{n}T_k.$$
其中最后一项最简单：
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
因此把它单独拿出来会更方便：
$$E(n)=1+\sum_{k=1}^{n-1}T_k.$$
第一个非平凡项为
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}.$$
实现正是从这个值开始的。也就是说，只要能快速从 \(T_k\) 推到 \(T_{k+1}\)，整个求和问题就解决了。
与其每次从头计算 \(T_{k+1}\)，不如先考察它和 \(T_k\) 的商：
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
利用二项式系数的基本恒等式
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1},$$
可以把上式整理成
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2).$$
于是递推关系就是
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}.$$
这是整个解法最重要的一步。它说明只要知道一个精确首项和一个精确比值公式，就能按顺序生成所有剩余项，而不必重复构造组合表达式。
当 \(n\) 很大时，上述比值中的两个因子都非常接近 \(1\)。直接逐项做幂运算并不稳妥，因为浮点误差会在长循环中累积。更稳健的做法是先取对数：
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
再通过指数函数恢复原比值：
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
实现采用的正是这一形式。原因在于 \(\log(1+x)\) 在 \(x\) 很小时可以更稳定地处理“接近 1 的微小修正”，从而减少消差误差。对 \(n=10^6\) 这样的输入，这种数值处理方式非常重要。
从闭式表达式还能直接看出几个有用事实。
第一，每一项都为正，因此部分和是单调增加的。
第二，求和项具有对称性：
$$T_k=T_{n-k}\qquad (1\le k\le n-1).$$
这是因为
$$\binom{n}{k}=\binom{n}{n-k},$$
并且把 \(k\) 与 \(n-k\) 交换后，幂上的两个因子只是互换了位置，整体值不变。实现并没有专门利用这个对称性去做半边求和，因为完整的从左到右扫描已经足够简单而且高效；不过在推导公式时，这个对称性是非常好的自检工具。
取 \(n=4\) 时，四个求和项分别为
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
所以
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
这个值正好对应实现中的一个小规模校验点，也清楚展示了公式的实际含义。
C++、Python 和 Java 实现使用的是同一套数学流程。首先处理平凡情况 \(n\le 1\)，此时期望值直接等于 \(1\)。当 \(n>1\) 时，程序把当前项初始化为
$$T_1=\left(\frac{n-1}{n}\right)^{n-1},$$
同时把累计和初始化为“末项 \(1\) + 首个非平凡项”。这样做以后，剩余工作就只是沿着 \(k=1,2,\dots,n-2\) 往前推进。
在每一次循环中，实现都会先计算第 3 步中的对数比值，再对它取指数，接着用这个比值更新当前项，并把新项加到总和中。于是 \(T_2,T_3,\dots,T_{n-1}\) 按顺序被生成出来，全程都不需要重建阶乘，也不需要重新求二项式系数。
这几份实现还会核对若干小输入的参考值，例如 \(E(3)=17/9\)、\(E(4)=2.21875\)、\(E(5)=2.5104\)、\(E(10)=3.66021568\)。这些检查通过后，再计算题目要求的大输入，并将结果保留四位小数输出。
算法只进行一次从 \(k=1\) 到 \(n-2\) 的循环，每一步都只包含常数次浮点运算，因此时间复杂度为 \(O(n)\)。所需存储仅包括当前项、累计和以及少量临时量，所以空间复杂度为 \(O(1)\)。也正因为如此，这个递推方案才能轻松处理 \(n=10^6\) 级别的输入。
Для заданного \(n\) требуется вычислить математическое ожидание \(E(n)\), возникающее в модели unfair race. Ключевое упрощение, используемое реализациями, состоит в том, что это ожидание записывается в виде конечной суммы
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
Целевое значение равно \(n=10^6\), поэтому прямое вычисление через факториалы или многократное построение биномиальных коэффициентов было бы слишком дорогим. Вместо этого программа проходит по сумме последовательно и получает каждый следующий член из предыдущего при помощи компактного мультипликативного отношения.
Весь метод строится на том, чтобы заменить тяжёлую комбинаторную формулу рекуррентным описанием: первый член плюс отношение соседних членов. После этого задача сводится к одному линейному проходу.
Обозначим
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
Тогда
$$E(n)=\sum_{k=1}^{n}T_k.$$
Последний член особенно прост:
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
Поэтому удобно отделить его и написать
$$E(n)=1+\sum_{k=1}^{n-1}T_k.$$
Первый нетривиальный член равен
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}.$$
Именно с этого значения начинают реализации.
Вместо того чтобы каждый раз вычислять \(T_{k+1}\) с нуля, сравним его с \(T_k\):
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
Используя тождество
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1},$$
получаем упрощение
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2).$$
Отсюда рекурсия
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}.$$
Это и есть главная алгебраическая идея решения: точный стартовый член и точное отношение порождают все остальные слагаемые.
При больших \(n\) оба множителя в отношении очень близки к \(1\). Поэтому численно устойчивее сначала взять логарифм:
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
А затем восстановить само отношение через экспоненту:
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
Именно поэтому реализации используют устойчивое вычисление \(\log(1+x)\), а не строят степени напрямую на каждом шаге. Такой подход уменьшает потерю точности, когда \(k\) или \(n-k\) велики.
Из замкнутой формулы сразу следуют полезные свойства.
Каждый член положителен, поэтому частичная сумма растёт монотонно.
Кроме того, слагаемое симметрично:
$$T_k=T_{n-k}\qquad (1\le k\le n-1),$$
поскольку
$$\binom{n}{k}=\binom{n}{n-k}$$
и замена \(k\) на \(n-k\) не меняет остальные множители. Реализации всё равно оставляют простой полный проход слева направо, но эта симметрия полезна как проверка правильности вывода.
Если \(n=4\), то четыре слагаемых таковы:
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
Следовательно,
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
Это ровно одно из контрольных значений, используемых реализациями, и наглядная демонстрация того, как работает формула.
Реализации на C++, Python и Java используют одну и ту же математическую схему. Сначала они обрабатывают тривиальный случай \(n\le 1\), где ответ равен \(1\). Для \(n>1\) текущий член инициализируется значением
$$T_1=\left(\frac{n-1}{n}\right)^{n-1},$$
а накопленная сумма сразу получает уже известный конечный вклад \(1\) плюс этот первый нетривиальный член.
Далее код проходит по \(k=1,2,\dots,n-2\). На каждой итерации вычисляется логарифм отношения из Шага 3, затем берётся экспонента, текущий член умножается на найденное отношение, и новый член добавляется к сумме. Так последовательно получаются \(T_2,T_3,\dots,T_{n-1}\), причём факториалы и биномиальные коэффициенты нигде не пересчитываются.
Тем же путём проверяются малые контрольные значения: \(E(3)=17/9\), \(E(4)=2.21875\), \(E(5)=2.5104\) и \(E(10)=3.66021568\). После этого вычисляется требуемый большой вход, а ответ выводится с округлением до четырёх знаков после запятой.
Алгоритм содержит один цикл по \(k\) от \(1\) до \(n-2\), и в каждой итерации выполняется только константное число операций с плавающей точкой. Следовательно, время работы равно \(O(n)\). Хранятся лишь текущий член, накопленная сумма и несколько временных величин, так что память составляет \(O(1)\). Именно поэтому рекуррентный подход остаётся практичным даже при \(n=10^6\).
لعددٍ معطى \(n\)، المطلوب حساب قيمة متوقعة \(E(n)\) ناتجة عن نموذج السباق غير العادل. الفكرة الأساسية التي تعتمدها التطبيقات هي أن هذه القيمة المتوقعة يمكن كتابتها على صورة مجموع منتهٍ صريح:
$$E(n)=\sum_{k=1}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}.$$
القيمة المستهدفة هي \(n=10^6\)، ولذلك فإن الحساب المباشر باستخدام المضروبات أو إعادة بناء معاملات ثنائية الحد في كل مرة سيكون مكلفًا بلا داعٍ. بدلًا من ذلك، يمر البرنامج على الحدود بالتتابع ويولِّد كل حد جديد من الحد السابق باستعمال نسبة ضربٍ موجزة.
جوهر الحل هو تحويل الحد الدقيق في المجموع إلى وصف من نوع "حد أول + نسبة بين حدين متجاورين". بهذه الصورة تختفي الحسابات التوافقية الثقيلة ويكفي مرور خطي واحد.
لنعرّف
$$T_k=\binom{n}{k}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}\qquad (1\le k\le n).$$
وعندئذٍ
$$E(n)=\sum_{k=1}^{n}T_k.$$
الحد الأخير بسيط جدًا:
$$T_n=\binom{n}{n}\left(\frac{n}{n}\right)^n\left(\frac{0}{n}\right)^0=1.$$
ولذلك من المريح فصله وكتابة
$$E(n)=1+\sum_{k=1}^{n-1}T_k.$$
أما أول حد غير بديهي فهو
$$T_1=\binom{n}{1}\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{n-1}=\left(\frac{n-1}{n}\right)^{n-1}.$$
وهذا هو تمامًا مقدار البداية الذي تنطلق منه التطبيقات.
بدلًا من إعادة حساب \(T_{k+1}\) من الصفر، نقارنه بالحد \(T_k\):
$$\frac{T_{k+1}}{T_k}=\frac{\binom{n}{k+1}}{\binom{n}{k}}\cdot\frac{(k+1)^{k+1}}{k^k}\cdot\frac{(n-k-1)^{n-k-1}}{(n-k)^{n-k}}.$$
وباستخدام العلاقة
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1},$$
تتبسط الصيغة إلى
$$\frac{T_{k+1}}{T_k}=\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}\qquad (1\le k\le n-2).$$
ومن ثم نحصل على العلاقة التكرارية
$$T_{k+1}=T_k\left(\frac{k+1}{k}\right)^k\left(\frac{n-k-1}{n-k}\right)^{n-k-1}.$$
هذه هي الخطوة الجبرية الحاسمة: حد ابتدائي دقيق مع نسبة دقيقة يكفيان لتوليد جميع الحدود المتبقية.
عندما يكون \(n\) كبيرًا، فإن العاملين في النسبة يكونان قريبين جدًا من \(1\). لهذا يصبح العمل باللوغاريتمات أكثر استقرارًا عدديًا:
$$\log\frac{T_{k+1}}{T_k}=k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right).$$
ثم نعيد بناء النسبة نفسها عبر الدالة الأسية:
$$\frac{T_{k+1}}{T_k}=\exp\left(k\log\left(1+\frac{1}{k}\right)+(n-k-1)\log\left(1-\frac{1}{n-k}\right)\right).$$
ولهذا تستخدم التطبيقات صيغة مستقرة لـ \(\log(1+x)\) بدل تكوين القوى مباشرة في كل دورة. هذه المعالجة تقلل فقدان الدقة عندما يكون \(k\) أو \(n-k\) كبيرًا.
من الصيغة المغلقة تظهر عدة خصائص نافعة مباشرة.
كل حد موجب، ولذلك فإن المجموع الجزئي يزداد على نحو رتيب.
كما أن الحدود متناظرة:
$$T_k=T_{n-k}\qquad (1\le k\le n-1),$$
لأن
$$\binom{n}{k}=\binom{n}{n-k}$$
ولأن تبديل \(k\) مع \(n-k\) لا يغيّر العوامل الأخرى إلا بتبادل مواضعها. لا تستغل التطبيقات هذا التناظر لتقسيم العمل إلى نصفين، لأن المرور الكامل من اليسار إلى اليمين أبسط بما فيه الكفاية، لكنه يبقى فحصًا رياضيًا ممتازًا لصحة الاشتقاق.
إذا أخذنا \(n=4\)، فإن حدود المجموع الأربعة هي
$$T_1=\binom{4}{1}\left(\frac{1}{4}\right)\left(\frac{3}{4}\right)^3=\left(\frac{3}{4}\right)^3=\frac{27}{64},$$
$$T_2=\binom{4}{2}\left(\frac{2}{4}\right)^2\left(\frac{2}{4}\right)^2=6\cdot\frac{1}{16}=\frac{24}{64},$$
$$T_3=\binom{4}{3}\left(\frac{3}{4}\right)^3\left(\frac{1}{4}\right)=\frac{27}{64},$$
$$T_4=1.$$
وبالتالي
$$E(4)=\frac{27}{64}+\frac{24}{64}+\frac{27}{64}+1=\frac{142}{64}=\frac{71}{32}=2.21875.$$
وهذه القيمة تطابق إحدى نقاط التحقق الصغيرة المستخدمة في التطبيقات، وتوضح بوضوح كيفية عمل الصيغة.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها. أولًا تعالج الحالة البديهية \(n\le 1\)، حيث تكون القيمة المتوقعة مساوية لـ \(1\). وعندما يكون \(n>1\)، يبدأ الحد الجاري بالقيمة
$$T_1=\left(\frac{n-1}{n}\right)^{n-1},$$
ويبدأ المجموع التراكمي بالقيمة \(1\) الخاصة بالحد النهائي مضافًا إليها هذا الحد الأول غير البديهي.
بعد ذلك تدور الحلقة على \(k=1,2,\dots,n-2\). في كل دورة يحسب التنفيذ لوغاريتم النسبة من الخطوة 3، ثم يأخذ الأسية، ثم يحدِّث الحد الجاري بضربه في هذه النسبة، ثم يضيفه إلى المجموع. بهذه الطريقة تُولَّد الحدود \(T_2,T_3,\dots,T_{n-1}\) بالتتابع من غير إعادة بناء أي مضروب أو أي معامل ثنائي.
كما تُفحص قيم مرجعية صغيرة مثل \(E(3)=17/9\) و\(E(4)=2.21875\) و\(E(5)=2.5104\) و\(E(10)=3.66021568\). وبعد نجاح هذه الاختبارات، تُحسب قيمة الإدخال الكبيرة المطلوبة وتُطبع النتيجة مقربة إلى أربع منازل عشرية.
تحتوي الخوارزمية على حلقة واحدة فقط من \(k=1\) إلى \(n-2\)، وكل تكرار يستخدم عددًا ثابتًا من عمليات الفاصلة العائمة. لذلك يكون زمن التنفيذ \(O(n)\). أمّا الذاكرة فلا تتعدى الحد الجاري والمجموع التراكمي وعددًا قليلًا من القيم المؤقتة، أي \(O(1)\). وهذا بالضبط ما يجعل هذه العلاقة التكرارية عملية حتى عندما يكون \(n=10^6\).