We throw \(k\) defects independently and uniformly onto \(n\) chips. Each defect is placed separately, so there are exactly \(n^k\) equally likely outcomes. The goal is to find the probability that at least one chip receives three or more defects.
Let \(E\) be the event that some chip receives at least three defects. It is much easier to count the complementary event
$$E^c=\{\text{every chip receives at most two defects}\}.$$
Then
$$\Pr(E)=1-\Pr(E^c).$$
So the real task is to count all placements in which occupancies are only \(0\), \(1\), or \(2\).
Suppose exactly \(i\) chips receive two defects. Then exactly \(k-2i\) chips receive one defect, and the remaining \(n-(k-i)\) chips receive none. The parameter \(i\) can range only over
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
We count placements with exactly \(i\) double chips in two steps.
Step A: choose how the \(k\) labeled defects are grouped into \(i\) unordered pairs and \(k-2i\) singles. The number of such groupings is
$$\frac{k!}{2^i\,i!\,(k-2i)!}.$$
The factor \(2^i\) removes the order inside each pair, and \(i!\) removes the order among the pairs themselves.
Step B: send these \(k-i\) groups to distinct chips. Since the groups are effectively ordered as “\(i\) pair-slots followed by \(k-2i\) single-slots”, the number of injective chip assignments is the falling factorial
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
Therefore the number of valid placements in the \(i\)-th layer is
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$$
Since the total number of equally likely placements is \(n^k\), the probability of the \(i\)-th layer is
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
Summing over all admissible \(i\) gives the complement:
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
hence
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$$
The source code checks the small case \(k=3\), \(n=7\).
If one chip gets three defects, then all three labeled defects must land on the same chip. There are exactly \(7\) such placements, one for each chip, out of
$$7^3=343$$
total placements. So
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
This is exactly the checkpoint used by the C++ solution.
Evaluating every \(P_i\) from scratch is possible, but the Python and Java solutions use a more efficient recurrence. Divide \(P_i\) by \(P_{i-1}\):
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$$
Equivalently, in the exact form used in the code,
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
So once \(P_0\) is known, each next term can be updated in constant time.
For the real parameters \((k,n)=(20000,10^6)\), the raw factorials and products are astronomically large or tiny. Direct floating-point multiplication would overflow or underflow long before the final answer is reached. The implementations therefore work with
$$\log P_i$$
sum the logarithms of multiplicative factors, and only then recover \(P_i\) with exp.
1) Base layer. For \(i=0\), no chip has two defects, so all \(k\) defects land on distinct chips. The code computes
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right)$$
in log form.
2) Incremental update. Python and Java keep a running variable logp for \(\log P_i\) and update it using the ratio above, rather than recomputing the whole expression each time.
3) Accumulating the complement. The variable answer starts at \(1\), then subtracts each \(P_i\). After the loop, what remains is exactly \(\Pr(E)\).
4) Two implementation styles. The C++ version shows the formula more literally and recomputes the two logarithmic sums for each \(i\), which is simpler but slower. The Python and Java versions use the recurrence, which is the intended efficient idea.
The direct layer-by-layer recomputation costs about \(O(k^2)\). The optimized recurrence used by the Python and Java solutions reduces this to \(O(k)\) time, because each new layer is obtained from the previous one in constant work. Extra memory is \(O(1)\).
\(k\) Defekte werden unabhängig und gleichverteilt auf \(n\) Chips geworfen. Jeder Defekt wird einzeln platziert, also gibt es genau \(n^k\) gleich wahrscheinliche Ausgänge. Gesucht ist die Wahrscheinlichkeit, dass mindestens ein Chip drei oder mehr Defekte erhält.
Sei \(E\) das Ereignis „irgendein Chip hat mindestens drei Defekte“. Einfacher ist das Komplement
$$E^c=\{\text{jeder Chip hat hoechstens zwei Defekte}\}.$$
Dann gilt
$$\Pr(E)=1-\Pr(E^c).$$
Angenommen, genau \(i\) Chips tragen jeweils zwei Defekte. Dann tragen genau \(k-2i\) Chips jeweils einen Defekt und alle übrigen Chips keinen. Also liegt
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
Schritt A: Die \(k\) markierten Defekte werden in \(i\) ungeordnete Paare und \(k-2i\) Einzeldefekte zerlegt. Das geht auf
$$\frac{k!}{2^i\,i!\,(k-2i)!}$$
Arten. Dabei entfernt \(2^i\) die Reihenfolge innerhalb der Paare und \(i!\) die Reihenfolge der Paare untereinander.
Schritt B: Diese \(k-i\) Gruppen werden injektiv auf verschiedene Chips gelegt. Das liefert den fallenden Faktor
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
Somit ist die Zahl aller Belegungen dieser Klasse
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$$
Da insgesamt \(n^k\) gleich wahrscheinliche Platzierungen existieren, ist
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
Also
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
und damit
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$$
Der Quellcode prüft den kleinen Fall \(k=3\), \(n=7\).
Damit ein Chip drei Defekte erhält, müssen alle drei markierten Defekte auf denselben Chip fallen. Dafür gibt es genau \(7\) Möglichkeiten, eine pro Chip, unter insgesamt
$$7^3=343$$
Platzierungen. Also
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
Genau dieser Wert wird in C++ als Checkpoint kontrolliert.
Die Python- und Java-Lösungen berechnen die Summanden nicht jeweils von Grund auf neu, sondern benutzen
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$$
In derselben Form wie im Code:
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
Hat man also \(P_0\), dann folgt jeder weitere Summand in \(O(1)\).
Für die echten Parameter \((20000,10^6)\) wären direkte Fakultäten und Produkte numerisch unbeherrschbar. Deshalb speichern die Implementierungen \(\log P_i\), addieren Logarithmen und exponentieren erst am Ende des jeweiligen Terms.
1) Basisterm. Für \(i=0\) müssen alle Defekte auf verschiedenen Chips landen. Daher
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right),$$
was im Log-Raum aufgebaut wird.
2) Inkrementelles Update. Python und Java halten logp = \log P_i laufend aktuell und nutzen den Quotienten aus dem vorherigen Punkt.
3) Akkumulation des Komplements. answer startet bei \(1\) und subtrahiert alle \(P_i\). Am Ende bleibt genau \(\Pr(E)\) übrig.
4) Zwei Implementationsstile. C++ zeigt die Formel unmittelbarer und berechnet die Log-Summen für jedes \(i\) erneut, was einfacher, aber langsamer ist. Python und Java verwenden die rekursive Aktualisierung.
Die direkte Neuberechnung aller Schichten kostet ungefähr \(O(k^2)\). Mit der Rekurrenz aus Python und Java sinkt der Aufwand auf \(O(k)\), weil jeder neue Summand in konstanter Zeit aus dem vorherigen entsteht. Der Zusatzspeicher ist \(O(1)\).
\(k\) adet defect, \(n\) çipe bağımsız ve eş olasılıkla atılıyor. Her defect ayrı ayrı yerleştirildiği için toplam olası sonuç sayısı tam olarak \(n^k\)'dir. Amaç, en az bir çipin üç veya daha fazla defect alması olasılığını bulmaktır.
\(E\): “en az bir çipte \(\ge 3\) defect var” olsun. O zaman
$$E^c=\{\text{her çip en fazla 2 defect alıyor}\}$$
için
$$\Pr(E)=1-\Pr(E^c).$$
Dolayısıyla asıl iş, dağılımda hiçbir çipin \(3\) ya da daha fazlasını almaması durumunu saymaktır.
Eğer tam \(i\) çipte ikişer defect varsa, o zaman tam \(k-2i\) çipte birer defect vardır; geri kalan çipler boştur. Bu yüzden
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
Aşama A: \(k\) etiketli defect'i, \(i\) tane sırasız çift ve \(k-2i\) tane tekil öğe halinde grupla. Bunun sayısı
$$\frac{k!}{2^i\,i!\,(k-2i)!}$$
olur. Burada \(2^i\) her çiftin iç sırasını, \(i!\) ise çiftlerin kendi aralarındaki sırasını siler.
Aşama B: Oluşan \(k-i\) grubu farklı çiplere yerleştir. Bunun sayısı düşen faktöriyel ile verilir:
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
Sonuç olarak tam \(i\) çift dolu çip içeren yerleştirme sayısı
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}$$
olur.
Toplam eş olasılıklı yerleştirme sayısı \(n^k\) olduğu için
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
Dolayısıyla
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
ve aranan cevap
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i$$
şeklindedir.
Koddaki checkpoint küçük örnek olarak \(k=3\), \(n=7\) kullanır.
Bir çipin üç defect alması için üç etiketli defect'in de aynı çipe düşmesi gerekir. Böyle yerleştirme sayısı her çip için bir tane olmak üzere toplam \(7\)'dir. Toplam sonuç sayısı ise
$$7^3=343$$
olduğundan
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
çıkar. C++ sürümü tam bu değeri kontrol eder.
Her \(P_i\) terimini sıfırdan hesaplamak mümkündür; ancak Python ve Java sürümleri daha iyi bir yol kullanır. Formülü \(P_{i-1}\)'e bölersek
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}$$
elde edilir. Kodun kullandığı tamamen eşdeğer biçim ise
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
Böylece \(P_0\) bilindikten sonra her yeni terim sabit zamanda güncellenebilir.
Gerçek problemde \((k,n)=(20000,10^6)\) olduğundan doğrudan faktöriyel ve çarpım hesaplamak taşma ya da aşırı küçülme yaratır. Bu yüzden implementasyonlar
$$\log P_i$$
üzerinden gider; çarpımlar yerine logaritmalar toplanır, sonra gerekirse exp ile geri dönülür.
1) Başlangıç terimi. \(i=0\) için bütün defect'ler farklı çiplere düşmelidir. Bu yüzden
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right)$$
log alanında kurulur.
2) Artımlı güncelleme. Python ve Java, logp = \log P_i değişkenini tutar ve bir önceki terimden yenisine yukarıdaki oranla geçer.
3) Tamamlayıcı toplamı toplamak. answer değişkeni \(1\) ile başlar ve her \(P_i\) terimi çıkarılır. Döngü sonunda geriye doğrudan \(\Pr(E)\) kalır.
4) İki farklı implementasyon stili. C++ kodu formülü daha doğrudan gösterir ve her \(i\) için log toplamlarını yeniden kurar; bu daha sade ama daha yavaştır. Python ve Java ise recurrence kullanır.
Naif katman-katman yeniden hesaplama yaklaşık \(O(k^2)\) zaman alır. Python ve Java'daki oran güncellemesiyle süre \(O(k)\)'ye iner; çünkü her yeni terim sabit iş ile elde edilir. Ek bellek \(O(1)\)'dir.
Se lanzan \(k\) defectos de forma independiente y uniforme sobre \(n\) chips. Como cada defecto se coloca por separado, hay exactamente \(n^k\) resultados equiprobables. Se pide la probabilidad de que al menos un chip reciba tres o más defectos.
Sea \(E\) el evento “algún chip recibe al menos tres defectos”. Es más fácil contar
$$E^c=\{\text{todos los chips reciben como mucho 2 defectos}\}.$$
Entonces
$$\Pr(E)=1-\Pr(E^c).$$
Supongamos que exactamente \(i\) chips reciben dos defectos. Entonces exactamente \(k-2i\) chips reciben uno, y todos los demás reciben cero. Por tanto
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
Paso A: agrupar los \(k\) defectos etiquetados en \(i\) pares no ordenados y \(k-2i\) defectos individuales. Eso puede hacerse de
$$\frac{k!}{2^i\,i!\,(k-2i)!}$$
formas.
Paso B: asignar esos \(k-i\) grupos a chips distintos. El número de asignaciones inyectivas es el factorial descendente
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
Así, el número total de configuraciones de la capa \(i\) es
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$$
Dividiendo por el total \(n^k\), obtenemos
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
Por lo tanto
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
y
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$$
El código comprueba el caso pequeño \(k=3\), \(n=7\).
Para que un chip tenga tres defectos, los tres defectos etiquetados deben caer en el mismo chip. Hay exactamente \(7\) resultados de este tipo entre
$$7^3=343$$
resultados totales. Luego
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
Ese es justamente el checkpoint de la versión en C++.
Python y Java no recalculan cada \(P_i\) desde cero. A partir de la fórmula cerrada se obtiene
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$$
En la forma exacta usada por el código:
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
Así, conocido \(P_0\), cada nuevo término se actualiza en tiempo constante.
Para \((k,n)=(20000,10^6)\), las cantidades intermedias son demasiado grandes o demasiado pequeñas para multiplicarlas directamente con seguridad. Por eso las implementaciones acumulan \(\log P_i\) y solo al final recuperan \(P_i\) mediante exp.
1) Término base. Para \(i=0\), todos los defectos deben caer en chips distintos, luego
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right).$$
2) Actualización incremental. Python y Java mantienen logp = \log P_i y lo actualizan usando el cociente anterior.
3) Acumulación del complemento. La variable answer empieza en \(1\) y va restando cada \(P_i\). Al final queda exactamente \(\Pr(E)\).
4) Dos estilos de implementación. La versión C++ sigue la fórmula de manera más literal y recomputa las sumas logarítmicas para cada \(i\), mientras que Python y Java usan la recurrencia eficiente.
La recomputación directa de todas las capas cuesta aproximadamente \(O(k^2)\). La recurrencia de Python y Java reduce el coste a \(O(k)\), ya que cada capa se obtiene con trabajo constante a partir de la anterior. La memoria extra es \(O(1)\).
把 \(k\) 个缺陷独立且均匀地投到 \(n\) 个芯片上。由于每个缺陷都是单独放置的，因此一共有 \(n^k\) 个等概率结果。题目要求的是“至少有一个芯片得到 3 个及以上缺陷”的概率。
设 \(E\) 表示“某个芯片至少得到 3 个缺陷”。更容易计算的是补事件
$$E^c=\{\text{每个芯片得到的缺陷数都不超过 2}\}.$$
于是
$$\Pr(E)=1-\Pr(E^c).$$
如果恰好有 \(i\) 个芯片各拿到 2 个缺陷，那么必然有 \(k-2i\) 个芯片各拿到 1 个缺陷，其余芯片拿到 0 个。因此
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
步骤 A：把 \(k\) 个带标签的缺陷分成 \(i\) 个无序对和 \(k-2i\) 个单独元素，其数量为
$$\frac{k!}{2^i\,i!\,(k-2i)!}.$$
步骤 B：把这 \(k-i\) 个组注入到不同的芯片上，数量为下降阶乘
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
因此第 \(i\) 层的合法放置数为
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$$
除以总结果数 \(n^k\)，得到
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
于是
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
所以最终答案是
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$$
源码会检查 \(k=3\), \(n=7\) 这个小样例。
要让某个芯片拿到 3 个缺陷，3 个带标签的缺陷必须全部落在同一个芯片上。这样的结果一共有 \(7\) 个，而总结果数为
$$7^3=343.$$
因此
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
这正是 C++ 版本验证的检查值。
Python 和 Java 并不会把每个 \(P_i\) 从头算起，而是使用递推比值
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$$
写成代码中使用的完全等价形式就是
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
因此一旦知道 \(P_0\)，后面的每一项都可以常数时间更新。
对真实参数 \((20000,10^6)\) 而言，直接处理阶乘和长乘积会很快上溢或下溢。实现因此保存 \(\log P_i\)，把乘法变成加法，最后再用 exp 还原对应的概率项。
1) 基础层 \(P_0\)。 当 \(i=0\) 时，所有缺陷必须落到不同芯片，因此
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right).$$
2) 增量更新。 Python 和 Java 保持 logp = \log P_i，并利用上面的比值推进到下一层。
3) 累加补事件。 变量 answer 从 \(1\) 开始，逐项减去 \(P_i\)。循环结束后剩下的正好就是 \(\Pr(E)\)。
4) 两种实现风格。 C++ 版本更直观地重算每一层的对数和，因此更容易看公式；Python 和 Java 则使用高效递推。
直接重算所有层大约需要 \(O(k^2)\) 时间。Python 和 Java 的递推把复杂度降到 \(O(k)\)，因为每个新层只需常数工作。额外空间复杂度为 \(O(1)\)。
\(k\) дефектов независимо и равновероятно распределяются по \(n\) чипам. Поскольку каждый дефект размещается отдельно, всего имеется \(n^k\) равновероятных исходов. Нужно найти вероятность того, что хотя бы один чип получит три или более дефектов.
Пусть \(E\) означает событие «какой-то чип получил не менее трех дефектов». Удобнее считать
$$E^c=\{\text{каждый чип получил не более двух дефектов}\}.$$
Тогда
$$\Pr(E)=1-\Pr(E^c).$$
Пусть ровно \(i\) чипов имеют по два дефекта. Тогда ровно \(k-2i\) чипов имеют по одному дефекту, а остальные ноль. Следовательно,
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
Шаг A: разбить \(k\) помеченных дефектов на \(i\) неупорядоченных пар и \(k-2i\) одиночных элементов. Число таких разбиений равно
$$\frac{k!}{2^i\,i!\,(k-2i)!}.$$
Шаг B: разместить эти \(k-i\) групп по различным чипам. Число таких инъективных размещений равно падающему факториалу
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
Итак, число корректных размещений в слое \(i\):
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$$
Деля на общее число исходов \(n^k\), получаем
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
Значит
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
и потому
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$$
В исходниках есть контроль для \(k=3\), \(n=7\).
Чтобы какой-то чип получил три дефекта, все три помеченных дефекта должны попасть в один и тот же чип. Таких исходов ровно \(7\), а всего исходов
$$7^3=343.$$
Следовательно,
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
Этот результат и проверяет C++-код.
Python и Java не пересчитывают каждый \(P_i\) заново. Из формулы следует
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$$
В полностью эквивалентной записи, прямо совпадающей с кодом:
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
Поэтому, зная \(P_0\), можно получать каждый следующий член за \(O(1)\).
Для реальных параметров \((20000,10^6)\) прямые факториалы и длинные произведения численно нестабильны. Поэтому программы работают с \(\log P_i\), складывают логарифмы и только затем восстанавливают \(P_i\) через exp.
1) Базовый слой. При \(i=0\) все дефекты должны попасть в разные чипы, поэтому
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right).$$
2) Инкрементальное обновление. Python и Java хранят logp = \log P_i и обновляют его по отношению из предыдущего пункта.
3) Накопление дополнения. Переменная answer стартует с \(1\) и вычитает каждое \(P_i\). После цикла остается ровно \(\Pr(E)\).
4) Два стиля реализации. C++-версия ближе к формуле и заново строит логарифмические суммы для каждого \(i\), а Python и Java используют быструю рекуррентную схему.
Прямой пересчет всех слоев стоит примерно \(O(k^2)\). Рекуррентное обновление в Python и Java сокращает время до \(O(k)\), потому что каждый новый слой получается из предыдущего за константное число операций. Дополнительная память: \(O(1)\).
نوزّع \(k\) عيوبًا بشكل مستقل ومتساوٍ على \(n\) شرائح. بما أن كل عيب يُوضَع منفصلًا، فعدد النتائج المتساوية الاحتمال هو \(n^k\). المطلوب هو احتمال أن توجد شريحة واحدة على الأقل تستقبل ثلاثة عيوب أو أكثر.
ليكن \(E\) هو الحدث: «هناك شريحة حصلت على ثلاثة عيوب على الأقل». الأسهل هو حساب
$$E^c=\{\text{كل شريحة تحصل على عيبين كحد أقصى}\}.$$
وعندئذ
$$\Pr(E)=1-\Pr(E^c).$$
افترض أن عدد الشرائح التي تحمل عيبين بالضبط هو \(i\). عندئذ يوجد بالضبط \(k-2i\) شريحة تحمل عيبًا واحدًا، وبقية الشرائح تحمل صفرًا. لذلك
$$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$$
الخطوة A: نقسم العيوب المعلّمة وعددها \(k\) إلى \(i\) أزواج غير مرتبة و\(k-2i\) عناصر منفردة. عدد هذه القسمة هو
$$\frac{k!}{2^i\,i!\,(k-2i)!}.$$
الخطوة B: نضع هذه المجموعات وعددها \(k-i\) في شرائح مختلفة. عدد الطرق هو العامل المتناقص
$$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$$
إذن عدد التوزيعات الصحيحة في الطبقة \(i\) هو
$$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$$
بقسمة ذلك على العدد الكلي \(n^k\) نحصل على
$$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$$
ومن ثم
$$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$$
وبالتالي
$$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$$
الكود يفحص الحالة الصغيرة \(k=3\) و\(n=7\).
لكي تحصل شريحة على ثلاثة عيوب، يجب أن تقع العيوب الثلاثة المعلّمة كلها في الشريحة نفسها. عدد هذه النتائج يساوي \(7\)، بينما العدد الكلي للنتائج هو
$$7^3=343.$$
إذن
$$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$$
وهذا هو مقدار التحقق الموجود في نسخة ++C.
نسختا Python وJava لا تعيدان حساب كل \(P_i\) من الصفر. من الصيغة المغلقة نحصل على
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$$
وبالصيغة المطابقة حرفيًا لما في الكود:
$$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$$
وهكذا، بعد معرفة \(P_0\)، يمكن تحديث كل حد لاحق في زمن ثابت.
عند القيم الحقيقية للمسألة \((20000,10^6)\)، تصبح المضروبات والعوامل ضخمة أو صغيرة جدًا عدديًا. لذلك تحتفظ البرامج بالقيمة \(\log P_i\)، وتحوّل الضرب إلى جمع، ثم تعود إلى \(P_i\) باستخدام exp فقط عند الحاجة.
1) الحد الابتدائي. عندما \(i=0\)، يجب أن تقع كل العيوب في شرائح مختلفة، ولذلك
$$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right).$$
2) التحديث التراكمي. تحتفظ نسختا Python وJava بمتغير logp = \log P_i وتحدّثانه باستخدام النسبة السابقة.
3) تجميع الحدث المتمم. يبدأ المتغير answer من \(1\)، ثم يطرح كل حد \(P_i\). وبعد نهاية الحلقة يبقى بالضبط \(\Pr(E)\).
4) أسلوبان في التنفيذ. نسخة ++C تعرض الصيغة بصورة مباشرة أكثر، لذلك تعيد بناء المجاميع اللوغاريتمية لكل \(i\) من جديد، بينما تستخدم Python وJava التحديث الأسرع.
إعادة حساب جميع الطبقات مباشرة تكلف تقريبًا \(O(k^2)\). أما علاقة التحديث في Python وJava فتخفض الزمن إلى \(O(k)\)، لأن كل طبقة جديدة تُستخرج من السابقة بعمل ثابت. الذاكرة الإضافية \(O(1)\).