The round-table lottery is reduced, in the implementations, to an expectation kernel and its repeated cumulative sums. The basic quantity is
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
where \(H_n\) is the \(n\)-th harmonic number. From that kernel we define
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$$
The required output is \(S_{20}(10^{14})\) in scientific notation with 10 significant digits. The implementations also use the checkpoints \(E(111)=5.2912\) and \(S_3(100)=5.983679014\times 10^5\).
After the probabilistic part of the problem is simplified, the only primitive quantity that remains is the harmonic number. That is why the first validation step is simply the direct evaluation of
$$E(n)=H_n.$$
So the task is no longer a simulation over many random eliminations. It becomes a summation problem built on reciprocal terms.
Unrolling the recurrence for \(S_r(N)\) shows how often each reciprocal term \(1/j\) appears after \(k\) cumulative sums. For fixed \(j\), it contributes once for every weakly increasing chain
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
The number of such chains is the stars-and-bars coefficient
$$\binom{N-j+k}{k}.$$
Therefore the \(k\)-fold cumulative sum can be written as one explicit sum:
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
This identity already explains why the final algorithm never needs to enumerate anything near \(10^{14}\).
Introduce
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$$
For \(k=0\), this gives \(T_0(N)=H_N=S_0(N)\). Now compare first differences. Using
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
and
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1},$$
we obtain
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$$
The repeated sums satisfy the same recurrence:
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
Since \(S_0(N)=T_0(N)\), induction on \(k\) gives the exact identity
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$$
The closed form reproduces the validation values used by the implementations:
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
For the required parameters, the same formula yields
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$$
Only the argument \(N+k\) is enormous. Small harmonic numbers such as \(H_k\) are summed directly, while the large argument is evaluated with the Euler-Maclaurin expansion
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
At \(n=10^{14}+20\), the neglected tail is far below the requested 10-digit output accuracy.
The C++, Python, and Java implementations all use the same plan. They compute the binomial factor through the short product
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i},$$
which avoids factorial overflow and costs only \(O(k)\) operations because \(k=20\) is fixed. They then evaluate \(H_{N+k}\) with high-precision arithmetic, subtract the directly computed \(H_k\), multiply the two factors, and format the answer in normalized scientific notation.
For the target instance, the binomial product takes \(O(k)\) arithmetic steps, the exact evaluation of \(H_k\) also takes \(O(k)\), and the large harmonic number uses a constant number of asymptotic correction terms. Since \(k=20\) is fixed, the practical cost is \(O(1)\) time and \(O(1)\) memory. The decisive improvement is that the method never iterates up to \(N=10^{14}\).
Die Rundtisch-Lotterie wird in den Implementierungen auf einen Erwartungskern und dessen wiederholte kumulative Summen reduziert. Die Grundgroeße ist
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
wobei \(H_n\) die \(n\)-te harmonische Zahl ist. Darauf aufbauend gilt
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$$
Gesucht ist \(S_{20}(10^{14})\) in wissenschaftlicher Schreibweise mit 10 signifikanten Ziffern. Als Kontrollwerte dienen \(E(111)=5.2912\) und \(S_3(100)=5.983679014\times 10^5\).
Nachdem der probabilistische Teil vereinfacht wurde, bleibt als elementare Bausteingroeße nur noch die harmonische Zahl uebrig. Deshalb ist der erste Test einfach die direkte Auswertung von
$$E(n)=H_n.$$
Damit ist das Problem keine Zufallssimulation mehr, sondern eine Summationsaufgabe ueber Kehrwerte.
Wenn man die Rekursion fuer \(S_r(N)\) aufrollt, sieht man, wie oft jeder Summand \(1/j\) nach \(k\) kumulativen Summen vorkommt. Fuer festes \(j\) erscheint er genau einmal pro schwach wachsender Kette
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
Die Anzahl dieser Ketten ist der Stars-and-Bars-Koeffizient
$$\binom{N-j+k}{k}.$$
Daher gilt
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
Schon diese Darstellung zeigt, warum die endgueltige Methode niemals bis nahe \(10^{14}\) iterieren muss.
Wir definieren
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$$
Fuer \(k=0\) ist \(T_0(N)=H_N=S_0(N)\). Nun vergleichen wir die diskreten Differenzen. Mit
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
und
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1}$$
folgt
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$$
Die wiederholten Summen erfuellen dieselbe Rekursion:
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
Wegen \(S_0(N)=T_0(N)\) liefert Induktion ueber \(k\) die exakte Formel
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$$
Die geschlossene Form reproduziert die in den Implementierungen verwendeten Kontrollwerte:
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
Fuer die gesuchten Parameter ergibt dieselbe Formel
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$$
Nur das Argument \(N+k\) ist riesig. Kleine harmonische Zahlen wie \(H_k\) werden direkt summiert, waehrend fuer das große Argument die Euler-Maclaurin-Entwicklung verwendet wird:
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
Bei \(n=10^{14}+20\) liegt der abgeschnittene Rest weit unter der geforderten Genauigkeit von 10 signifikanten Ziffern.
Die C++-, Python- und Java-Implementierungen folgen demselben numerischen Plan. Der Binomialfaktor wird ueber das kurze Produkt
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i}$$
berechnet. Dadurch werden Fakultaeten vermieden, und wegen des festen \(k=20\) kostet dieser Schritt nur \(O(k)\). Danach wird \(H_{N+k}\) mit hochpraeziser Arithmetik ausgewertet, das direkt berechnete \(H_k\) subtrahiert, beides multipliziert und das Ergebnis normiert wissenschaftlich formatiert.
Fuer den Zielwert benoetigt das Binomialprodukt \(O(k)\) arithmetische Schritte, die exakte Berechnung von \(H_k\) ebenfalls \(O(k)\), und die große harmonische Zahl nur eine konstante Anzahl asymptotischer Korrekturterme. Da \(k=20\) fest ist, ergeben sich praktisch \(O(1)\) Zeit und \(O(1)\) Speicher. Der entscheidende Punkt ist, dass niemals bis \(N=10^{14}\) iteriert wird.
Yuvarlak masa piyangosu, implementasyonlarda bir beklenti cekirdegi ve onun tekrarli kümülatif toplamlari olarak indirgenir. Temel nicelik
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
burada \(H_n\) \(n\). harmonik sayidir. Bunun uzerinden
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1)$$
tanimlanir. Istenen cikti \(S_{20}(10^{14})\) degerinin 10 anlamli basamakli bilimsel gosterimidir. Implementasyonlar ayrica \(E(111)=5.2912\) ve \(S_3(100)=5.983679014\times 10^5\) kontrol noktalarini dogrular.
Olasilik kismi sadeleştirildikten sonra geriye kalan temel nesne harmonik sayidir. Bu nedenle ilk dogrulama dogrudan
$$E(n)=H_n$$
hesabidir. Boylece problem uzun bir rastgele surec simulasyonu olmaktan cikar ve karsilikli terimlerin toplanmasi problemine donusur.
\(S_r(N)\) yinelemesini actigimizda, her \(1/j\) teriminin \(k\) kez birikimli toplama sonrasinda kac kez gorundugu ortaya cikar. Sabit bir \(j\) icin katkı, her zayif artan zincir icin bir kez sayilir:
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
Bu zincirlerin sayisi stars-and-bars katsayisidir:
$$\binom{N-j+k}{k}.$$
Dolayisiyla
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
Bu ifade bile tek basina neden \(10^{14}\) buyuklugunde dogrudan bir donguye gerek olmadigini aciklar.
Simdi
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr)$$
tanimini yapalim. \(k=0\) icin \(T_0(N)=H_N=S_0(N)\) olur. Simdi ayrik farklara bakalim. Su ozdeslikleri kullaniriz:
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1}.$$
Bunlardan
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N)$$
elde edilir. Tekrarli toplamlar da ayni bagintiyi saglar:
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
\(S_0(N)=T_0(N)\) oldugu icin \(k\) uzerinden induksiyonla
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr)}$$
sonucuna ulasiriz.
Kapali form, implementasyonlarin kullandigi kontrol degerlerini aynen uretir:
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
Istenen parametreler icin ayni formül
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}$$
degerini verir.
Gercekten buyuk olan tek arguman \(N+k\)'dir. \(H_k\) gibi kucuk harmonik sayilar dogrudan toplanir; buyuk arguman icin ise Euler-Maclaurin acilimi kullanilir:
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
\(n=10^{14}+20\) icin ihmal edilen kuyruk, istenen 10 anlamli basamaktan cok daha kucuktur.
C++, Python ve Java implementasyonlari ayni sayisal plani izler. Binom carpanı su kisa carpimla hesaplanir:
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i}.$$
Bu yontem faktoriyel tasmasini onler ve \(k=20\) sabit oldugu icin yalnizca \(O(k)\) adim gerekir. Ardindan \(H_{N+k}\) yuksek hassasiyetli aritmetik ile hesaplanir, dogrudan bulunan \(H_k\) cikarilir, iki carpan carpilir ve sonuc normallestirilmis bilimsel gosterimde yazdirilir.
Hedef girdi icin binom carpimi \(O(k)\) aritmetik adim ister, \(H_k\)'nin dogrudan hesabi da \(O(k)\) maliyetlidir ve buyuk harmonik sayi sabit sayida asimptotik duzeltme terimiyle bulunur. \(k=20\) sabit oldugundan pratikte zaman \(O(1)\), bellek \(O(1)\)'dir. Asil kazanc, \(N=10^{14}\) buyuklugune kadar hic dongu kurulmamasidır.
La loteria de la mesa redonda se reduce, en las implementaciones, a un nucleo de esperanza y a sus sumas acumuladas repetidas. La cantidad basica es
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
donde \(H_n\) es el \(n\)-esimo numero armonico. A partir de ahi se define
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$$
La salida pedida es \(S_{20}(10^{14})\) en notacion cientifica con 10 cifras significativas. Las implementaciones tambien verifican los puntos de control \(E(111)=5.2912\) y \(S_3(100)=5.983679014\times 10^5\).
Una vez simplificada la parte probabilistica, el unico objeto elemental que queda es el numero armonico. Por eso la primera comprobacion consiste simplemente en evaluar
$$E(n)=H_n.$$
Asi, el problema deja de ser una simulacion aleatoria larga y pasa a ser un problema de sumacion de reciprocos.
Si desplegamos la recurrencia de \(S_r(N)\), vemos cuantas veces aparece cada termino \(1/j\) despues de \(k\) sumas acumuladas. Para un \(j\) fijo, su contribucion aparece una vez por cada cadena no decreciente
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
El numero de esas cadenas es el coeficiente de stars-and-bars
$$\binom{N-j+k}{k}.$$
Por lo tanto,
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
Esta identidad ya explica por que el algoritmo final no necesita iterar nada cercano a \(10^{14}\).
Definimos
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$$
Para \(k=0\), se tiene \(T_0(N)=H_N=S_0(N)\). Ahora comparamos diferencias discretas. Usando
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
y
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1},$$
se obtiene
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$$
Las sumas repetidas satisfacen exactamente la misma recurrencia:
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
Como \(S_0(N)=T_0(N)\), la induccion sobre \(k\) da la identidad exacta
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$$
La forma cerrada reproduce los valores de validacion usados por las implementaciones:
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
Para los parametros pedidos, la misma formula produce
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$$
El unico argumento realmente enorme es \(N+k\). Los numeros armonicos pequenos, como \(H_k\), se suman de forma directa, mientras que el argumento grande se evalua con la expansion de Euler-Maclaurin:
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
Con \(n=10^{14}+20\), el resto omitido queda muy por debajo de la precision requerida de 10 cifras significativas.
Las implementaciones en C++, Python y Java siguen el mismo plan numerico. Calculan el factor binomial mediante el producto corto
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i},$$
lo que evita el desbordamiento de factoriales y cuesta solo \(O(k)\) operaciones porque \(k=20\) es fijo. Luego evalúan \(H_{N+k}\) con aritmetica de alta precision, restan el \(H_k\) calculado directamente, multiplican ambos factores y formatean el resultado en notacion cientifica normalizada.
Para la entrada objetivo, el producto binomial requiere \(O(k)\) pasos aritmeticos, la evaluacion exacta de \(H_k\) tambien cuesta \(O(k)\), y el numero armonico grande usa un numero constante de terminos de correccion asintotica. Como \(k=20\) es fijo, el coste practico es \(O(1)\) en tiempo y \(O(1)\) en memoria. La mejora decisiva es que nunca se itera hasta \(N=10^{14}\).
在这些实现中，圆桌彩票问题已经被化简成一个期望核心及其反复前缀求和。基本量是
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
其中 \(H_n\) 是第 \(n\) 个调和数。随后定义
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$$
目标是把 \(S_{20}(10^{14})\) 以 10 位有效数字的科学记数法输出。实现还会先检查 \(E(111)=5.2912\) 和 \(S_3(100)=5.983679014\times 10^5\)。
概率过程被整理之后，剩下的基本对象只有调和数，所以第一步验证就是直接计算
$$E(n)=H_n.$$
这意味着问题已经不再是大规模随机模拟，而是如何高效求和倒数项的问题。
把 \(S_r(N)\) 的递推完全展开后，可以看到每个 \(1/j\) 在做了 \(k\) 次累积求和之后会被计算多少次。对固定的 \(j\)，它恰好对应每一条非降链
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
这样的链条数量是 stars-and-bars 系数
$$\binom{N-j+k}{k}.$$
因此
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
这个公式已经说明，最终算法根本不需要做到接近 \(10^{14}\) 的逐项循环。
定义
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$$
当 \(k=0\) 时，\(T_0(N)=H_N=S_0(N)\)。接着比较离散差分。利用
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
以及
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1},$$
可得
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$$
而重复求和满足同样的递推：
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
由于 \(S_0(N)=T_0(N)\)，对 \(k\) 归纳便得到精确公式
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$$
这个闭式公式能准确重现实现在程序中的校验值：
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
对于题目要求的参数，同一公式给出
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$$
真正巨大的只有 \(N+k\)。像 \(H_k\) 这样的较小调和数可以直接求和，而大参数则使用 Euler-Maclaurin 展开：
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
当 \(n=10^{14}+20\) 时，被截断的尾项远远小于 10 位有效数字所要求的误差范围。
C++、Python 和 Java 实现都遵循同一套数值方案。二项式因子通过短乘积
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i}$$
来计算，这样就避免了阶乘溢出，而且由于 \(k=20\) 固定，这一步只需要 \(O(k)\) 次运算。然后程序用高精度算术计算 \(H_{N+k}\)，减去直接求得的 \(H_k\)，再将两部分相乘，并把结果格式化为规范化科学记数法。
对于目标输入，二项式乘积需要 \(O(k)\) 次算术操作，\(H_k\) 的精确求值也需要 \(O(k)\) 项，而大调和数只需要常数个渐近修正项。由于 \(k=20\) 是固定常数，实际复杂度就是 \(O(1)\) 时间和 \(O(1)\) 空间。最关键的是，算法完全不需要循环到 \(N=10^{14}\)。
В реализованных решениях задача о круговом розыгрыше сведена к ядру математического ожидания и его многократным накопительным суммам. Базовая величина равна
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
где \(H_n\) обозначает \(n\)-е гармоническое число. Далее вводится
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$$
Нужно вычислить \(S_{20}(10^{14})\) и вывести ответ в научной записи с 10 значащими цифрами. Перед этим реализации проверяют контрольные значения \(E(111)=5.2912\) и \(S_3(100)=5.983679014\times 10^5\).
После упрощения вероятностной части остается только один элементарный объект: гармоническое число. Поэтому первая проверка сводится к прямому вычислению
$$E(n)=H_n.$$
Тем самым задача перестает быть симуляцией длинного случайного процесса и превращается в задачу о суммировании обратных величин.
Если полностью развернуть рекурсию для \(S_r(N)\), видно, сколько раз каждый член \(1/j\) встречается после \(k\) накопительных сумм. Для фиксированного \(j\) вклад появляется один раз для каждой неубывающей цепочки
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
Число таких цепочек равно коэффициенту stars-and-bars
$$\binom{N-j+k}{k}.$$
Следовательно,
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
Уже эта запись показывает, почему окончательный алгоритм не делает никакого перебора вплоть до \(10^{14}\).
Введем обозначение
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$$
При \(k=0\) имеем \(T_0(N)=H_N=S_0(N)\). Теперь сравним дискретные разности. Используя
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
и
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1},$$
получаем
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$$
Многократные суммы удовлетворяют той же рекурсии:
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
Так как \(S_0(N)=T_0(N)\), индукция по \(k\) дает точное тождество
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$$
Замкнутая формула воспроизводит контрольные значения, используемые в реализациях:
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
Для требуемых параметров та же формула дает
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$$
По-настоящему огромным является только аргумент \(N+k\). Малые гармонические числа, такие как \(H_k\), суммируются напрямую, а большой аргумент вычисляется по разложению Эйлера-Маклорена:
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
При \(n=10^{14}+20\) отброшенный хвост намного меньше ошибки, допустимой для 10 значащих цифр.
Реализации на C++, Python и Java используют один и тот же численный план. Биномиальный множитель считается через короткое произведение
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i},$$
что устраняет переполнение факториалов и требует лишь \(O(k)\) операций, потому что \(k=20\) фиксировано. Затем программа вычисляет \(H_{N+k}\) в высокой точности, вычитает напрямую найденное \(H_k\), перемножает оба множителя и форматирует результат в нормализованной научной записи.
Для целевого входа произведение для биномиального коэффициента требует \(O(k)\) арифметических шагов, точное вычисление \(H_k\) также занимает \(O(k)\), а большое гармоническое число использует только постоянное число асимптотических поправок. Поскольку \(k=20\) фиксировано, практическая сложность равна \(O(1)\) по времени и \(O(1)\) по памяти. Главное преимущество в том, что алгоритм вообще не итерируется до \(N=10^{14}\).
في هذه الحلول تم اختزال مسألة يانصيب المائدة المستديرة إلى نواة للتوقع وإلى مجاميع تراكمية متكررة لهذه النواة. الكمية الأساسية هي
$$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$$
حيث إن \(H_n\) هو العدد التوافقي رقم \(n\). وبعد ذلك نعرّف
$$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$$
المطلوب هو حساب \(S_{20}(10^{14})\) وكتابته بصيغة علمية ذات 10 أرقام معنوية. كما تتحقق الحلول أولًا من القيمتين \(E(111)=5.2912\) و \(S_3(100)=5.983679014\times 10^5\).
بعد تبسيط الجزء الاحتمالي من المسألة لا يبقى إلا كائن أساسي واحد هو العدد التوافقي. لذلك فإن أول فحص في الحل هو مجرد حساب مباشر لـ
$$E(n)=H_n.$$
وهكذا لا تعود المسألة محاكاة طويلة لعملية عشوائية، بل تصبح مسألة جمع لحدود مقلوبة.
عند فك العلاقة العودية الخاصة بـ \(S_r(N)\) بالكامل نرى عدد المرات التي يظهر فيها كل حد \(1/j\) بعد \(k\) مرات من الجمع التراكمي. من أجل \(j\) ثابت، يظهر هذا الحد مرة واحدة لكل سلسلة غير متناقصة من الشكل
$$j\le n_1\le n_2\le \cdots \le n_k\le N.$$
وعدد هذه السلاسل يساوي معامل stars-and-bars
$$\binom{N-j+k}{k}.$$
ولذلك نحصل على
$$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$$
وهذه الصيغة وحدها تفسر لماذا لا تحتاج الخوارزمية النهائية إلى أي دوران حتى حدود قريبة من \(10^{14}\).
لنعرّف
$$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$$
عندما \(k=0\) نحصل على \(T_0(N)=H_N=S_0(N)\). الآن نقارن الفروق المتتالية. باستخدام
$$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$$
$$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$$
وكذلك
$$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1},$$
نصل إلى
$$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$$
أما المجاميع المتكررة فإنها تحقق العلاقة نفسها:
$$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$$
وبما أن \(S_0(N)=T_0(N)\)، فإن الاستقراء على \(k\) يعطي الهوية الدقيقة
$$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$$
الصيغة المغلقة تعيد إنتاج قيم التحقق المستخدمة في الحلول:
$$E(111)=H_{111}\approx 5.2912,$$
$$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$$
وبالنسبة إلى المعاملات المطلوبة نحصل على
$$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$$
القيمة الضخمة فعلًا هي \(N+k\) فقط. أما الأعداد التوافقية الصغيرة مثل \(H_k\) فتُحسب مباشرة، في حين يُستخدم توسع Euler-Maclaurin من أجل الحد الكبير:
$$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$$
وعند \(n=10^{14}+20\) يكون الذيل المهمل أصغر بكثير من حد الخطأ المسموح به لإخراج من 10 أرقام معنوية.
تتبع تطبيقات C++ و Python و Java الخطة العددية نفسها. فهي تحسب العامل الثنائي عبر الجداء القصير
$$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i},$$
وهذا يتجنب فيض المضروبات ولا يحتاج إلا إلى \(O(k)\) عملية لأن \(k=20\) ثابتة. بعد ذلك تُحسب \(H_{N+k}\) بدقة عالية، ويُطرح منها \(H_k\) المحسوب مباشرة، ثم يُضرب العاملان ويُنسق الناتج بصيغة علمية مطبّعة.
بالنسبة إلى الإدخال المطلوب، يحتاج جداء المعامل الثنائي إلى \(O(k)\) خطوة حسابية، كما أن حساب \(H_k\) المباشر يحتاج إلى \(O(k)\)، بينما يُحسب العدد التوافقي الكبير بعدد ثابت من حدود التصحيح الأسيمبتوطي. وبما أن \(k=20\) ثابتة، فإن الكلفة العملية هي \(O(1)\) زمنًا و \(O(1)\) ذاكرةً. والنقطة الحاسمة هي أن الطريقة لا تدور حتى \(N=10^{14}\) إطلاقًا.