For each \(n\), the bottles form a triangular stack with
$$T_n=\frac{n(n+1)}2$$
positions. A bottle can only be chosen when no bottle above it is still present. If an exposed bottle is chosen, its contribution is the number of still-active downward paths that start at that bottle. Let \(f_n\) be the total weighted count over all legal fall histories of the \(n\)-row triangle. The task is to compute
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
The exact state recursion is far too large for \(n=10000\), so the solution uses a closed product formula and keeps the brute-force recursion only as a small verification tool.
The implementation rests on two viewpoints: an exact recurrence on active bottle sets, and a closed product formula that collapses the same weighted process into a one-pass modular computation.
Label the bottles by rows \(1,2,\dots,n\), with row \(r\) containing \(r\) bottles. A bottle in row \(r\) depends on the two bottles immediately above it, so the legal states form a directed acyclic graph. For any active set \(S\), let \(\max(S)\) be the exposed bottles, meaning the bottles in \(S\) that have no active parent.
Define \(F(S)\) to be the weighted number of legal ways to remove all bottles in \(S\). If \(u\in\max(S)\), let \(\pi_S(u)\) be the number of directed paths that start at \(u\) and stay entirely inside the active set \(S\). Then the exact recurrence is
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$$
For the full \(n\)-row triangle \(P_n\), the desired quantity is simply
$$f_n=F(P_n).$$
This recurrence is what the exact verifier evaluates for very small \(n\).
Suppose an exposed bottle sits at the top of a complete subtriangle of height \(h\). Every step downward has two geometric choices, left or right, as long as the next bottle exists. Therefore the total number of active downward paths starting from that bottle is
$$1+2+2^2+\cdots+2^{h-1}=2^h-1.$$
It is convenient to denote this path factor by
$$W_h=2^h-1.$$
The first values are \(W_1=1\), \(W_2=3\), \(W_3=7\), \(W_4=15\). These are exactly the numerators that appear in the fast formula.
If we temporarily ignore the weights \(\pi_S(u)\) and only ask for legal removal orders, we are counting linear extensions of the triangular precedence poset. This is the staircase shape of size \(T_n\).
A bottle with \(h\) rows available beneath it has shifted hook length
$$H_h=2h-1.$$
There are \(n-h+1\) bottles of height \(h\), so the product of all hook lengths is
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$$
Hence the unweighted number of legal orders is
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$$
The odd factors \(1,3,5,\dots,2n-1\) are the denominators seen in the final closed form.
The weighted process replaces each height-\(h\) hook contribution by the ratio
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}.$$
Since height \(h\) occurs \(n-h+1\) times in the triangle, the total weighted count becomes
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$$
This is the key formula used by the fast arithmetic loop. It matches the exact recursion on all small cases checked by the verifier.
Define the running ratio product
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$$
Then
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$$
so the closed form can be written as
$$f_n=T_n!\prod_{k=1}^{n}Q_k.$$
Because \(T_n=T_{n-1}+n\), we also get the incremental relation
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$$
This is exactly why the implementation only needs running products rather than a large table of states.
For three rows we have
$$T_3=\frac{3\cdot 4}{2}=6.$$
The height multiplicities are:
$$h=1\text{ appears }3\text{ times},\qquad h=2\text{ appears }2\text{ times},\qquad h=3\text{ appears }1\text{ time}.$$
The corresponding ratios are
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$$
Therefore
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$$
The exact small-state recursion also produces \(1008\), so this example shows the agreement between the structural recurrence and the closed product formula.
The C++, Python, and Java implementations iterate from \(n=1\) to \(10000\) and maintain only a few running quantities. First they update \(2^n \bmod M\), which yields the numerator \(2^n-1\). Then they divide by \(2n-1\) in modular arithmetic using a modular inverse, so the current ratio \(R_n\) is obtained without ever leaving the modulus.
Next the implementation updates two nested products: the prefix product \(Q_n\), and the product of all prefixes \(\prod_{k=1}^{n}Q_k\). In parallel it extends the factorial \(T_n!\) by multiplying the next \(n\) integers, because the triangular number grows from \(T_{n-1}\) to \(T_n\) by exactly \(n\) new positions. Multiplying the triangular factorial by the accumulated prefix product gives \(f_n\), and that value is added to the final sum modulo \(M\).
The C++ implementation also performs a separate exact verification for tiny \(n\). It represents active bottle sets by bitmasks, enumerates the exposed choices, computes the active path count for each choice, and memoizes the recurrence with arbitrary-precision integers. The first several values from that exact recursion are compared against the fast formula before the large \(n\) loop is trusted.
The fast path runs in \(O(N\log M)\) time for \(N=10000\), because each step performs one modular inverse by binary exponentiation. The arithmetic state itself is constant-size, so the streaming formula needs only \(O(1)\) extra memory apart from any optional storage used for checking intermediate values.
The exact verifier is exponential in the number of bottles, which is why it is restricted to very small triangles. Its role is validation, not production computation.
Für jedes \(n\) bilden die Flaschen ein Dreieck mit
$$T_n=\frac{n(n+1)}2$$
Positionen. Eine Flasche darf erst gewählt werden, wenn keine Flasche oberhalb von ihr mehr vorhanden ist. Wird eine freiliegende Flasche gewählt, so ist ihr Beitrag die Anzahl der noch aktiven abwärts gerichteten Pfade, die bei dieser Flasche beginnen. Sei \(f_n\) die gesamte gewichtete Anzahl aller zulässigen Fallverläufe für das \(n\)-reihige Dreieck. Gesucht ist
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
Die exakte Zustandsrekursion ist für \(n=10000\) viel zu groß, daher verwendet die Lösung eine geschlossene Produktformel und behält die brute-forceartige Rekursion nur als kleinen Korrektheitstest.
Die Implementierung beruht auf zwei äquivalenten Sichtweisen: einer exakten Rekursion über aktive Flaschenmengen und einer geschlossenen Produktform, die denselben gewichteten Prozess auf eine einzige modulare Schleife reduziert.
Nummeriere die Flaschen nach Zeilen \(1,2,\dots,n\), wobei Zeile \(r\) genau \(r\) Flaschen enthält. Eine Flasche in Zeile \(r\) hängt von den zwei Flaschen unmittelbar darüber ab, also entsteht ein gerichteter azyklischer Graph. Für eine aktive Menge \(S\) bezeichne \(\max(S)\) die freiliegenden Flaschen, also jene Elemente von \(S\), die keinen aktiven Vorgänger mehr besitzen.
Sei \(F(S)\) die gewichtete Anzahl der zulässigen Möglichkeiten, alle Flaschen aus \(S\) zu entfernen. Für \(u\in\max(S)\) sei \(\pi_S(u)\) die Anzahl gerichteter Pfade, die bei \(u\) beginnen und vollständig innerhalb der aktiven Menge \(S\) verlaufen. Dann gilt die exakte Rekursion
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$$
Für das vollständige \(n\)-Reihen-Dreieck \(P_n\) ist die gesuchte Größe
$$f_n=F(P_n).$$
Genau diese Rekursion wertet der exakte Prüfer für sehr kleine \(n\) aus.
Angenommen, eine freiliegende Flasche steht an der Spitze eines vollständigen Unterdreiecks der Höhe \(h\). Bei jedem Schritt nach unten gibt es geometrisch zwei Möglichkeiten, links oder rechts, solange die nächste Flasche existiert. Daher ist die Gesamtzahl aktiver Abwärtspfade ab dieser Flasche
$$1+2+2^2+\cdots+2^{h-1}=2^h-1.$$
Wir schreiben dafür kurz
$$W_h=2^h-1.$$
Die ersten Werte sind \(W_1=1\), \(W_2=3\), \(W_3=7\), \(W_4=15\). Genau diese Größen erscheinen später als Zähler in der schnellen Formel.
Ignoriert man die Gewichte \(\pi_S(u)\) vorübergehend und zählt nur die legalen Entfernungsreihenfolgen, so zählt man lineare Erweiterungen der dreieckigen Vorrangsordnung. Das ist die Treppenform mit \(T_n\) Elementen.
Eine Flasche mit verbleibender Höhe \(h\) besitzt die verschobene Hakenlänge
$$H_h=2h-1.$$
Von Höhe \(h\) gibt es genau \(n-h+1\) Flaschen, also ist das Produkt aller Hakenlängen
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$$
Damit ist die ungewichtete Anzahl legaler Reihenfolgen
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$$
Die ungeraden Faktoren \(1,3,5,\dots,2n-1\) sind also die Nenner der späteren Endformel.
Im gewichteten Prozess wird jeder Höhen-\(h\)-Beitrag durch das Verhältnis
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}$$
ersetzt. Da Höhe \(h\) genau \(n-h+1\) Mal auftritt, erhält man insgesamt
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$$
Das ist die zentrale Formel des schnellen Rechenwegs. Für alle kleinen Testfälle stimmt sie mit der exakten Rekursion überein.
Definiere das laufende Verhältnisprodukt
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$$
Dann gilt
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$$
und damit lässt sich die geschlossene Formel auch als
$$f_n=T_n!\prod_{k=1}^{n}Q_k$$
schreiben. Weil \(T_n=T_{n-1}+n\) gilt außerdem die inkrementelle Beziehung
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$$
Genau deshalb genügt der Implementierung eine Handvoll laufender Produkte statt einer großen Zustandsstruktur.
Für drei Reihen ist
$$T_3=\frac{3\cdot 4}{2}=6.$$
Die Häufigkeiten der Höhen sind
$$h=1\text{ dreimal},\qquad h=2\text{ zweimal},\qquad h=3\text{ einmal}.$$
Die zugehörigen Verhältnisse lauten
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$$
Also folgt
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$$
Die exakte Zustandsrekursion liefert ebenfalls \(1008\), womit dieses Beispiel die Übereinstimmung beider Sichtweisen demonstriert.
Die C++, Python- und Java-Implementierungen iterieren von \(n=1\) bis \(10000\) und pflegen nur wenige laufende Größen. Zuerst wird \(2^n \bmod M\) aktualisiert; daraus entsteht der Zähler \(2^n-1\). Anschließend wird durch \(2n-1\) in modularer Arithmetik dividiert, also über ein modulares Inverses, sodass das aktuelle Verhältnis \(R_n\) vollständig innerhalb des Moduls berechnet wird.
Danach aktualisiert die Implementierung zwei geschachtelte Produkte: das Präfixprodukt \(Q_n\) und das Produkt aller Präfixe \(\prod_{k=1}^{n}Q_k\). Parallel dazu wird die Fakultät \(T_n!\) erweitert, indem die nächsten \(n\) ganzen Zahlen multipliziert werden, weil die Dreieckszahl von \(T_{n-1}\) auf \(T_n\) genau um \(n\) wächst. Das Produkt aus Dreiecksfakultät und akkumuliertem Präfixprodukt ergibt \(f_n\), und dieser Wert wird modulo \(M\) zur Endsumme addiert.
Die C++-Implementierung führt zusätzlich eine exakte Verifikation für sehr kleine \(n\) aus. Dabei werden aktive Flaschenmengen als Bitmasken dargestellt, freiliegende Wahlmöglichkeiten aufgelistet, die aktiven Pfadgewichte berechnet und die Rekursion mit Ganzzahlen beliebiger Präzision memoisiert. Erst wenn diese kleinen Werte mit der geschlossenen Formel übereinstimmen, wird die große Schleife verwendet.
Der schnelle Rechenweg benötigt \(O(N\log M)\) Zeit für \(N=10000\), weil pro Schritt genau ein modulares Inverses per binärer Exponentiation berechnet wird. Der arithmetische Zustand ist konstant groß, daher genügt dem Streaming-Verfahren \(O(1)\) zusätzlicher Speicher, abgesehen von optionalen Hilfsdaten für Zwischenprüfungen.
Der exakte Prüfer wächst exponentiell mit der Flaschenzahl und wird deshalb nur für sehr kleine Dreiecke eingesetzt. Seine Aufgabe ist Absicherung, nicht die eigentliche Produktion des Ergebnisses.
Her \(n\) için şişeler
$$T_n=\frac{n(n+1)}2$$
konumlu bir üçgen oluşturur. Bir şişe ancak üzerinde artık hiçbir şişe kalmadığında seçilebilir. Açıkta olan bir şişe seçildiğinde katkısı, o şişeden başlayan ve hâlâ aktif olan aşağı yönlü yolların sayısıdır. \(f_n\), \(n\) satırlı üçgen için tüm geçerli düşme geçmişlerinin ağırlıklı toplamı olsun. İstenen değer
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
Doğrudan durum uzayı özyinelemesi \(n=10000\) için aşırı büyük olduğundan çözüm, kapalı bir çarpım formülüne geçer ve kaba kuvvet özyinelemesini sadece küçük bir doğrulama aracı olarak bırakır.
Uygulama iki eşdeğer bakışa dayanır: aktif şişe kümeleri üzerinde tam bir özyineleme ve aynı ağırlıklı süreci tek geçişli modüler hesaba indiren kapalı bir çarpım formülü.
Şişeleri \(1,2,\dots,n\) satırlarına yerleştirelim; \(r\). satırda tam \(r\) şişe vardır. \(r\). satırdaki bir şişe, hemen üstündeki iki şişeye bağlıdır; dolayısıyla elimizde yönlü çevrimsiz bir grafik vardır. Her aktif küme \(S\) için \(\max(S)\), yani aktif ebeveyni kalmamış açık şişeler kümesi olsun.
\(F(S)\), \(S\) içindeki tüm şişeleri kaldırmanın ağırlıklı geçerli sayısı olsun. \(u\in\max(S)\) için \(\pi_S(u)\), \(u\)'dan başlayan ve tamamen aktif küme \(S\) içinde kalan yönlü yol sayısı olsun. O zaman tam özyineleme
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\})$$
şeklindedir. Tam \(n\) satırlı üçgen \(P_n\) için aradığımız büyüklük
$$f_n=F(P_n)$$
olur. Küçük boyutlu tam doğrulayıcı tam olarak bu bağıntıyı hesaplar.
Açıkta duran bir şişenin yüksekliği \(h\) olan tam bir alt üçgenin tepesinde olduğunu düşünelim. Aşağı inerken, bir sonraki şişe mevcut olduğu sürece solda veya sağda iki geometrik seçim vardır. Bu yüzden o şişeden başlayan aktif aşağı yönlü yol sayısı
$$1+2+2^2+\cdots+2^{h-1}=2^h-1$$
olur. Bunu kısaca
$$W_h=2^h-1$$
diye yazalım. İlk değerler \(W_1=1\), \(W_2=3\), \(W_3=7\), \(W_4=15\) olur. Hızlı formüldeki paylar tam olarak bunlardır.
Ağırlıkları \(\pi_S(u)\) bir anlığına yok sayıp sadece geçerli kaldırma sıralarını sayarsak, üçgensel öncelik posetinin lineer uzantılarını saymış oluruz. Bu da \(T_n\) hücreli merdiven şeklidir.
Altında \(h\) satır kalabilen bir şişenin kaydırılmış kanca uzunluğu
$$H_h=2h-1$$
olur. Yüksekliği \(h\) olan tam \(n-h+1\) şişe bulunduğundan tüm kanca uzunluklarının çarpımı
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}$$
şeklindedir. Böylece ağırlıksız geçerli sıra sayısı
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}$$
olur. Son kapalı formdaki \(1,3,5,\dots,2n-1\) tek sayıları bu paydalardan gelir.
Ağırlıklı süreçte her yükseklik \(h\) için katkı
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}$$
oranına dönüşür. Yükseklik \(h\), üçgende \(n-h+1\) kez göründüğü için toplam ağırlıklı sayı
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}$$
olur. Hızlı aritmetik yolunun temel formülü budur. Doğrulayıcı, küçük tüm örneklerde bunun tam özyinelemeyle aynı sonucu verdiğini gösterir.
Şimdi koşan oran çarpımını
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}$$
olarak tanımlayalım. O zaman
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1}$$
olduğu için kapalı formu
$$f_n=T_n!\prod_{k=1}^{n}Q_k$$
şeklinde de yazabiliriz. Ayrıca \(T_n=T_{n-1}+n\) olduğundan
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n$$
bağıntısı elde edilir. İşte bu yüzden uygulamanın büyük bir durum tablosuna değil, sadece birkaç koşan çarpıma ihtiyacı vardır.
Üç satır için
$$T_3=\frac{3\cdot 4}{2}=6$$
olur. Yükseklik tekrar sayıları
$$h=1\text{ için }3,\qquad h=2\text{ için }2,\qquad h=3\text{ için }1$$
şeklindedir. İlgili oranlar
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75$$
olur. Dolayısıyla
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008$$
çıkar. Küçük durumlar için tam özyineleme de aynı \(1008\) değerini verdiğinden, iki yaklaşım burada açıkça örtüşür.
C++, Python ve Java uygulamaları \(n=1\)'den \(10000\)'e kadar ilerler ve yalnızca birkaç koşan büyüklük tutar. Önce \(2^n \bmod M\) güncellenir; bundan \(2^n-1\) payı elde edilir. Sonra \(2n-1\) ile modüler aritmetikte bölme yapılır; yani modüler ters kullanılarak güncel oran \(R_n\) mod dışına çıkmadan hesaplanır.
Bundan sonra uygulama iki iç içe çarpımı günceller: önek çarpımı \(Q_n\) ve tüm öneklerin çarpımı \(\prod_{k=1}^{n}Q_k\). Aynı anda \(T_n!\) değeri de bir önceki üçgensel sayıdan yenisine geçerken eklenen \(n\) tamsayı çarpılarak büyütülür. Üçgensel faktöriyel ile birikmiş önek çarpımının çarpımı \(f_n\)'yi verir ve bu değer sonuca mod \(M\) altında eklenir.
C++ uygulaması ayrıca çok küçük \(n\) değerleri için tam bir doğrulama yapar. Aktif şişe kümeleri bit maskeleriyle temsil edilir, açık seçimler listelenir, her seçim için aktif yol sayısı hesaplanır ve özyineleme büyük tamsayılarla belleğe alınır. Büyük döngüye geçmeden önce ilk birkaç değer kapalı formülle karşılaştırılır.
Hızlı yol, \(N=10000\) için \(O(N\log M)\) zamanda çalışır; çünkü her adımda ikili üs alma ile bir modüler ters hesaplanır. Aritmetik durum sabit boyutlu olduğundan, akışkan formül ara doğrulama için tutulabilecek ek diziler dışında \(O(1)\) ek bellek gerektirir.
Tam doğrulayıcı ise şişe sayısına göre üstel büyür; bu nedenle yalnızca çok küçük üçgenlerde kullanılır. Görevi ana hesabı yapmak değil, formülü doğrulamaktır.
Para cada \(n\), las botellas forman un triángulo con
$$T_n=\frac{n(n+1)}2$$
posiciones. Una botella solo puede elegirse cuando ya no queda ninguna botella encima de ella. Si se elige una botella expuesta, su contribución es el número de caminos descendentes aún activos que parten de esa botella. Sea \(f_n\) el recuento ponderado total de todas las historias legales de caída para el triángulo de \(n\) filas. Debemos calcular
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
La recursión exacta sobre estados es demasiado grande para \(n=10000\), así que la solución usa una fórmula cerrada en producto y deja la recursión exhaustiva solo como verificación pequeña.
La implementación se apoya en dos descripciones equivalentes: una recurrencia exacta sobre conjuntos activos de botellas y una fórmula en producto que condensa el mismo proceso ponderado en un recorrido modular lineal.
Etiquetamos las botellas por filas \(1,2,\dots,n\), con \(r\) botellas en la fila \(r\). Una botella de la fila \(r\) depende de las dos botellas inmediatamente superiores, así que obtenemos un grafo acíclico dirigido. Para un conjunto activo \(S\), denotamos por \(\max(S)\) al conjunto de botellas expuestas, es decir, las que no tienen ningún padre activo.
Sea \(F(S)\) el número ponderado de formas legales de retirar todas las botellas de \(S\). Para \(u\in\max(S)\), sea \(\pi_S(u)\) el número de caminos dirigidos que empiezan en \(u\) y permanecen por completo dentro del conjunto activo \(S\). Entonces
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$$
Para el triángulo completo de \(n\) filas \(P_n\), la cantidad buscada es
$$f_n=F(P_n).$$
Eso es exactamente lo que evalúa el verificador exacto para \(n\) muy pequeño.
Supongamos que una botella expuesta está en la cima de un subtriángulo completo de altura \(h\). En cada paso hacia abajo hay dos elecciones geométricas, izquierda o derecha, siempre que exista la botella siguiente. Por tanto, el número total de caminos descendentes activos que nacen en esa botella es
$$1+2+2^2+\cdots+2^{h-1}=2^h-1.$$
Es útil escribir este factor como
$$W_h=2^h-1.$$
Los primeros valores son \(W_1=1\), \(W_2=3\), \(W_3=7\), \(W_4=15\). Esos números son precisamente los numeradores de la fórmula rápida.
Si por un momento ignoramos los pesos \(\pi_S(u)\) y contamos solo los órdenes legales de retirada, estamos contando extensiones lineales del poset triangular de precedencia. Esa es la forma escalonada de tamaño \(T_n\).
Una botella con \(h\) filas disponibles por debajo tiene longitud de gancho desplazada
$$H_h=2h-1.$$
Hay \(n-h+1\) botellas de altura \(h\), de modo que el producto de todas las longitudes de gancho es
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$$
Así, el número no ponderado de órdenes legales es
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$$
Los factores impares \(1,3,5,\dots,2n-1\) son exactamente los denominadores de la forma final.
En el proceso ponderado, cada contribución de altura \(h\) se convierte en la razón
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}.$$
Como la altura \(h\) aparece \(n-h+1\) veces en el triángulo, obtenemos
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$$
Esta es la fórmula central del camino rápido. Coincide con la recurrencia exacta en todos los casos pequeños comprobados.
Definimos el producto acumulado de razones
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$$
Entonces
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$$
y la fórmula cerrada puede escribirse como
$$f_n=T_n!\prod_{k=1}^{n}Q_k.$$
Además, como \(T_n=T_{n-1}+n\), se obtiene la relación incremental
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$$
Por eso la implementación solo necesita productos acumulados y no una tabla enorme de estados.
Con tres filas tenemos
$$T_3=\frac{3\cdot 4}{2}=6.$$
Las multiplicidades de altura son
$$h=1\text{ tres veces},\qquad h=2\text{ dos veces},\qquad h=3\text{ una vez}.$$
Las razones correspondientes son
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$$
Por tanto
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$$
La recursión exacta de estados pequeños también da \(1008\), así que el ejemplo muestra la coincidencia entre la fórmula y la definición recursiva.
Las implementaciones en C++, Python y Java recorren \(n=1,2,\dots,10000\) y mantienen solo unas pocas cantidades acumuladas. Primero actualizan \(2^n \bmod M\), lo que produce el numerador \(2^n-1\). Luego dividen por \(2n-1\) dentro de la aritmética modular mediante un inverso modular, de modo que la razón actual \(R_n\) queda calculada sin salir del módulo.
Después, la implementación actualiza dos productos anidados: el prefijo \(Q_n\) y el producto de todos los prefijos \(\prod_{k=1}^{n}Q_k\). En paralelo extiende \(T_n!\) multiplicando los siguientes \(n\) enteros, porque el número triangular crece de \(T_{n-1}\) a \(T_n\) añadiendo exactamente \(n\) posiciones. El producto entre el factorial triangular y el producto acumulado de prefijos da \(f_n\), y ese valor se suma al resultado final módulo \(M\).
La implementación en C++ añade además una verificación exacta para \(n\) diminuto. Representa los conjuntos activos mediante máscaras de bits, enumera las botellas expuestas, calcula el número de caminos activos para cada elección y memoriza la recurrencia con enteros de precisión arbitraria. Antes de confiar en el bucle grande, compara los primeros valores exactos con los de la fórmula rápida.
La vía rápida tarda \(O(N\log M)\) para \(N=10000\), porque cada paso calcula un inverso modular mediante exponenciación binaria. El estado aritmético es de tamaño constante, por lo que la fórmula acumulativa necesita \(O(1)\) memoria extra, salvo cualquier almacenamiento opcional usado para revisar valores intermedios.
El verificador exacto es exponencial en el número de botellas y por eso solo se usa para triángulos muy pequeños. Su función es validar la fórmula, no realizar el cálculo grande.
对每个 \(n\)，瓶子排成一个共有
$$T_n=\frac{n(n+1)}2$$
个位置的三角形。只有当某个瓶子上方已经没有瓶子存在时，它才可以被选中。选中一个当前暴露的瓶子时，它的权重等于“从这个瓶子出发、并且完全停留在当前活跃结构中的向下路径总数”。记 \(f_n\) 为 \(n\) 层三角堆的所有合法下落历史的加权总数。题目要求计算
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
如果直接对状态做精确递归，到了 \(n=10000\) 就完全不可行，因此真正的解法使用闭式乘积公式，而把暴力状态递归仅保留为小规模校验。
实现依赖两个等价视角：一个是对活跃瓶子集合的精确递推，另一个是把同一加权过程压缩成单次模运算扫描的乘积公式。
按行编号，行号为 \(1,2,\dots,n\)，第 \(r\) 行有 \(r\) 个瓶子。第 \(r\) 行中的一个瓶子依赖于它正上方的两个瓶子，因此整体形成一个有向无环图。对任意活跃集合 \(S\)，记 \(\max(S)\) 为当前暴露的瓶子集合，也就是在 \(S\) 中没有活跃父节点的那些瓶子。
记 \(F(S)\) 为移除 \(S\) 中全部瓶子的加权合法方式数。若 \(u\in\max(S)\)，则 \(\pi_S(u)\) 表示从 \(u\) 出发且完全留在活跃集合 \(S\) 内的有向路径数。那么精确递推就是
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$$
对于完整的 \(n\) 层三角形 \(P_n\)，目标量就是
$$f_n=F(P_n).$$
小规模精确校验器计算的正是这个递推。
设某个暴露瓶子位于一个高度为 \(h\) 的完整子三角形顶端。只要下一个瓶子存在，每向下一层都有“向左”或“向右”两种几何选择。因此，从该瓶子出发的活跃向下路径总数为
$$1+2+2^2+\cdots+2^{h-1}=2^h-1.$$
把这个局部路径因子记作
$$W_h=2^h-1.$$
前几个值是 \(W_1=1\)、\(W_2=3\)、\(W_3=7\)、\(W_4=15\)。这正是快速公式中分子部分出现的数列。
如果暂时忽略 \(\pi_S(u)\) 这些权重，只问“有多少种合法移除顺序”，那实际上就是在计算这个三角偏序的线性扩张个数，也就是阶梯形 Young 形状对应的计数问题。
一个下面还能延伸 \(h\) 层的瓶子，其移位钩长为
$$H_h=2h-1.$$
高度为 \(h\) 的瓶子共有 \(n-h+1\) 个，所以所有钩长的乘积为
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$$
因此，不带权的合法顺序数是
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$$
最终公式中出现的奇数分母 \(1,3,5,\dots,2n-1\)，正是由这里来的。
在带权过程里，每个高度 \(h\) 的贡献都变成比值
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}.$$
由于高度 \(h\) 在整个三角形中恰好出现 \(n-h+1\) 次，最终得到
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$$
这就是快速实现所依赖的核心闭式。小规模精确递推验证了它在前若干项上的正确性。
定义累计比值积
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$$
则有
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$$
所以闭式也可以写成
$$f_n=T_n!\prod_{k=1}^{n}Q_k.$$
又因为 \(T_n=T_{n-1}+n\)，于是得到增量形式
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$$
这说明实现时根本不需要保存巨大的状态图，只要维护几个滚动乘积即可。
三层时有
$$T_3=\frac{3\cdot 4}{2}=6.$$
各个高度的出现次数为
$$h=1\text{ 出现 }3\text{ 次},\qquad h=2\text{ 出现 }2\text{ 次},\qquad h=3\text{ 出现 }1\text{ 次}.$$
对应比值为
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$$
因此
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$$
小规模精确状态递推独立地也给出 \(1008\)，因此这个例子很好地展示了结构性递推与闭式乘积的一致性。
C++、Python 和 Java 实现都按 \(n=1,2,\dots,10000\) 顺序推进，并且只维护少量滚动变量。首先更新 \(2^n \bmod M\)，从而得到分子 \(2^n-1\)。然后在模运算下除以 \(2n-1\)，也就是通过模逆得到当前比值 \(R_n\)，整个过程始终不离开模 \(M\)。
接着，实现会更新两个嵌套乘积：前缀积 \(Q_n\)，以及所有前缀积的总乘积 \(\prod_{k=1}^{n}Q_k\)。与此同时，还会把三角阶乘 \(T_n!\) 扩展到下一项，因为三角数从 \(T_{n-1}\) 增长到 \(T_n\) 恰好增加了 \(n\) 个整数因子。将三角阶乘与累计前缀积相乘就得到 \(f_n\)，然后把它加到最终答案中并对 \(M\) 取模。
C++ 实现还额外执行一个非常小规模的精确验证。它用位掩码表示活跃瓶子集合，枚举当前暴露的选择，计算每个选择的活跃路径数，并用任意精度整数对递推做记忆化。只有当前几项与闭式公式一致时，才继续执行大规模主循环。
快速主过程的时间复杂度是 \(O(N\log M)\)，这里 \(N=10000\)。原因是每一步都要通过二进制快速幂求一次模逆。就算把算术细节全部算上，流式公式本身只需要常数级额外状态，因此空间复杂度是 \(O(1)\)，只有在为了校验而存储若干中间值时才会额外增加。
精确校验器对瓶子总数呈指数级增长，所以只能用于很小的三角形。它的职责是验证公式，而不是承担最终计算。
Для каждого \(n\) бутылки образуют треугольную укладку из
$$T_n=\frac{n(n+1)}2$$
позиций. Бутылку можно выбрать только тогда, когда над ней уже не осталось ни одной бутылки. Если выбрана открытая бутылка, ее вклад равен числу еще активных нисходящих путей, начинающихся в этой вершине. Пусть \(f_n\) обозначает общий взвешенный счет всех допустимых историй падения для треугольника из \(n\) рядов. Требуется вычислить
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
Точная рекурсия по состояниям слишком велика для \(n=10000\), поэтому в основном решении используется замкнутая формула-произведение, а полный перебор сохраняется только как маленькая проверка корректности.
Реализация опирается на два эквивалентных описания: точную рекурсию по активным наборам бутылок и замкнутую формулу, сводящую тот же взвешенный процесс к одному проходу по модулю.
Пронумеруем бутылки по рядам \(1,2,\dots,n\), причем в ряду \(r\) стоит ровно \(r\) бутылок. Каждая бутылка в ряду \(r\) зависит от двух бутылок непосредственно над ней, поэтому возникает ориентированный ациклический граф. Для активного множества \(S\) обозначим через \(\max(S)\) открытые бутылки, то есть элементы \(S\), у которых больше нет активных родителей.
Пусть \(F(S)\) — взвешенное число допустимых способов убрать все бутылки из \(S\). Для \(u\in\max(S)\) обозначим через \(\pi_S(u)\) число ориентированных путей, начинающихся в \(u\) и целиком остающихся внутри активного множества \(S\). Тогда точная рекурсия имеет вид
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$$
Для полного треугольника из \(n\) рядов \(P_n\) искомая величина равна
$$f_n=F(P_n).$$
Именно эту формулу и вычисляет точный проверяющий блок на очень малых \(n\).
Пусть открытая бутылка стоит на вершине полного под-треугольника высоты \(h\). На каждом шаге вниз есть два геометрических выбора — влево или вправо, пока следующая бутылка существует. Поэтому общее число активных нисходящих путей, стартующих в этой бутылке, равно
$$1+2+2^2+\cdots+2^{h-1}=2^h-1.$$
Обозначим этот локальный множитель через
$$W_h=2^h-1.$$
Первые значения: \(W_1=1\), \(W_2=3\), \(W_3=7\), \(W_4=15\). Именно эти числа появляются в числителях быстрой формулы.
Если временно забыть о весах \(\pi_S(u)\) и считать только допустимые порядки удаления, то мы считаем линейные расширения треугольного poset-а. Это лестничная форма размера \(T_n\).
Бутылка, под которой остается \(h\) рядов, имеет сдвинутую крюковую длину
$$H_h=2h-1.$$
Бутылок высоты \(h\) ровно \(n-h+1\), поэтому произведение всех крюковых длин равно
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$$
Следовательно, невзвешенное число допустимых порядков равно
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$$
Отсюда и появляются нечетные знаменатели \(1,3,5,\dots,2n-1\) в итоговой формуле.
Во взвешенном процессе вклад высоты \(h\) превращается в отношение
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}.$$
Так как высота \(h\) встречается \(n-h+1\) раз, получаем
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$$
Это главная формула быстрого решения. Для всех малых проверенных случаев она совпадает с точной рекурсией.
Введем накопленное произведение отношений
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$$
Тогда
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$$
и замкнутая формула принимает вид
$$f_n=T_n!\prod_{k=1}^{n}Q_k.$$
Поскольку \(T_n=T_{n-1}+n\), получаем и приращение
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$$
Именно поэтому в реализации достаточно нескольких бегущих произведений, а не огромной таблицы состояний.
Для трех рядов имеем
$$T_3=\frac{3\cdot 4}{2}=6.$$
Кратности высот таковы:
$$h=1\text{ встречается }3\text{ раза},\qquad h=2\text{ встречается }2\text{ раза},\qquad h=3\text{ встречается }1\text{ раз}.$$
Соответствующие отношения равны
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$$
Следовательно,
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$$
Точная малая рекурсия тоже дает \(1008\), так что пример наглядно показывает совпадение структурной рекурсии и замкнутой формулы.
Реализации на C++, Python и Java проходят значения \(n=1,2,\dots,10000\) и поддерживают лишь несколько накопленных величин. Сначала обновляется \(2^n \bmod M\), откуда получается числитель \(2^n-1\). Затем выполняется деление на \(2n-1\) в модульной арифметике через модульный обратный элемент, поэтому текущее отношение \(R_n\) вычисляется, не выходя за пределы модуля.
Далее реализация обновляет два вложенных произведения: префиксное произведение \(Q_n\) и произведение всех префиксов \(\prod_{k=1}^{n}Q_k\). Параллельно достраивается факториал треугольного числа \(T_n!\): при переходе от \(T_{n-1}\) к \(T_n\) домножаются ровно следующие \(n\) целых чисел. Произведение треугольного факториала и накопленного префиксного множителя дает \(f_n\), после чего значение добавляется к окончательной сумме по модулю \(M\).
В реализации на C++ дополнительно присутствует точная проверка для крошечных \(n\). Активные множества кодируются битовыми масками, открытые бутылки перебираются явно, для каждого выбора вычисляется число активных путей, а сама рекурсия мемоизируется с использованием целых произвольной точности. Лишь после совпадения первых значений с формулой запускается большой расчет.
Быстрый путь работает за \(O(N\log M)\) времени при \(N=10000\), потому что на каждом шаге требуется один модульный обратный элемент, вычисляемый бинарным возведением в степень. Арифметическое состояние имеет постоянный размер, поэтому потоковая формула использует \(O(1)\) дополнительной памяти, если не считать возможного хранения промежуточных значений для проверки.
Точный проверяющий модуль экспоненциален по числу бутылок и потому применим только к очень маленьким треугольникам. Его назначение — проверка формулы, а не основной расчет.
لكل \(n\)، تُرتَّب الزجاجات على شكل مثلث يحتوي على
$$T_n=\frac{n(n+1)}2$$
موضعًا. ولا يمكن اختيار زجاجة إلا إذا لم تبقَ فوقها أي زجاجة أخرى. وعندما نختار زجاجة مكشوفة، فإن مساهمتها تساوي عدد المسارات الهابطة التي تبدأ منها وتبقى كلّها داخل البنية النشطة الحالية. لنرمز بـ \(f_n\) إلى العدد الموزون الكلي لجميع تواريخ السقوط القانونية في مثلث مكوَّن من \(n\) صفوف. المطلوب هو حساب
$$\sum_{n=1}^{10000} f_n \pmod{M},\qquad M=1{,}000{,}000{,}033.$$
الاستدعاء التكراري الدقيق على فضاء الحالات يصبح هائلًا جدًا عند \(n=10000\)، لذلك يعتمد الحل الفعلي على صيغة جدائية مغلقة، ويُبقي الاستدعاء الكامل فقط كأداة تحقق صغيرة.
تعتمد الفكرة على منظورين متكافئين: علاقة تكرارية دقيقة على مجموعات الزجاجات النشطة، وصيغة جدائية تغلق العملية نفسها وتحولها إلى مرور حسابي واحد بترديد ثابت.
نرقّم الزجاجات بحسب الصفوف \(1,2,\dots,n\)، بحيث يحتوي الصف \(r\) على \(r\) زجاجات. وكل زجاجة في الصف \(r\) تعتمد على الزجاجتين اللتين فوقها مباشرة، ومن ثم نحصل على رسم بياني موجَّه لا دوري. ولكل مجموعة نشطة \(S\)، نرمز بـ \(\max(S)\) إلى مجموعة الزجاجات المكشوفة، أي الزجاجات التي لا تملك والدًا نشطًا داخل \(S\).
ولتكن \(F(S)\) هي القيمة الموزونة لعدد الطرق القانونية لإزالة كل زجاجات \(S\). وإذا كان \(u\in\max(S)\)، فليكن \(\pi_S(u)\) عدد المسارات الموجَّهة التي تبدأ عند \(u\) وتبقى كلها داخل المجموعة النشطة \(S\). عندئذٍ تكون العلاقة الدقيقة
$$F(\varnothing)=1,\qquad F(S)=\sum_{u\in\max(S)} \pi_S(u)\,F(S\setminus\{u\}).$$
وبالنسبة إلى المثلث الكامل ذي \(n\) صفوف \(P_n\)، فإن الكمية المطلوبة هي
$$f_n=F(P_n).$$
وهذه هي الصيغة التي يحسبها المتحقق الدقيق للأحجام الصغيرة جدًا.
افترض أن زجاجة مكشوفة تقع عند قمة مثلث فرعي كامل ارتفاعه \(h\). في كل نزول إلى طبقة أدنى توجد خياران هندسيان، يسار أو يمين، ما دامت الزجاجة التالية موجودة. ولذلك فإن العدد الكلي للمسارات الهابطة النشطة التي تبدأ من تلك الزجاجة يساوي
$$1+2+2^2+\cdots+2^{h-1}=2^h-1.$$
وسنرمز إلى هذا العامل المحلي بالرمز
$$W_h=2^h-1.$$
وأول القيم هي \(W_1=1\)، \(W_2=3\)، \(W_3=7\)، \(W_4=15\). وهذه هي بالضبط الأعداد التي تظهر في بسط الصيغة السريعة.
إذا تجاهلنا أوزان \(\pi_S(u)\) مؤقتًا واكتفينا بعدّ ترتيبات الإزالة القانونية، فإننا نعدّ التمديدات الخطية للترتيب الجزئي المثلثي. وهذا يطابق شكل السلم ذي الحجم \(T_n\).
الزجاجة التي يبقى تحتها \(h\) صفوف تملك طول خطّاف مزاحًا يساوي
$$H_h=2h-1.$$
وبما أن عدد الزجاجات ذات الارتفاع \(h\) هو \(n-h+1\)، فإن حاصل ضرب جميع أطوال الخطاف هو
$$\prod_{h=1}^{n} (2h-1)^{\,n-h+1}.$$
إذًا يكون عدد الترتيبات القانونية غير الموزونة
$$L_n=\frac{T_n!}{\prod_{h=1}^{n}(2h-1)^{\,n-h+1}}.$$
ومن هنا تأتي المقامات الفردية \(1,3,5,\dots,2n-1\) التي تظهر في الصيغة النهائية.
في العملية الموزونة يتحول إسهام كل ارتفاع \(h\) إلى النسبة
$$R_h=\frac{W_h}{H_h}=\frac{2^h-1}{2h-1}.$$
ولأن الارتفاع \(h\) يظهر \(n-h+1\) مرة داخل المثلث، نحصل على
$$f_n=T_n!\prod_{h=1}^{n}\left(\frac{2^h-1}{2h-1}\right)^{n-h+1}.$$
وهذه هي الصيغة الأساسية التي يعتمد عليها المسار السريع، وقد تم التحقق منها على كل الحالات الصغيرة التي يفحصها البرنامج الدقيق.
لنعرّف حاصل الضرب التراكمي للنسب:
$$Q_n=\prod_{h=1}^{n} R_h=\prod_{h=1}^{n}\frac{2^h-1}{2h-1}.$$
عندئذٍ
$$\prod_{k=1}^{n} Q_k=\prod_{h=1}^{n} R_h^{\,n-h+1},$$
ومن ثم يمكن كتابة الصيغة المغلقة على الصورة
$$f_n=T_n!\prod_{k=1}^{n}Q_k.$$
وبما أن \(T_n=T_{n-1}+n\)، نحصل أيضًا على العلاقة الزيادية
$$f_n=f_{n-1}\left(\prod_{t=T_{n-1}+1}^{T_n} t\right)Q_n.$$
ولهذا السبب يكفي التنفيذ أن يحتفظ بعدة حواصل ضرب جارية بدلًا من تمثيل فضاء الحالات بالكامل.
عندما \(n=3\) يكون
$$T_3=\frac{3\cdot 4}{2}=6.$$
وتكون تكرارات الارتفاعات، إذا كتبناها على شكل أزواج \((h,\mathrm{count})\)، هي
$$ (1,3),\qquad (2,2),\qquad (3,1). $$
أما النسب المقابلة فهي
$$R_1=\frac{2^1-1}{1}=1,\qquad R_2=\frac{2^2-1}{3}=1,\qquad R_3=\frac{2^3-1}{5}=\frac75.$$
إذًا
$$f_3=6!\cdot R_1^3 R_2^2 R_3=720\cdot \frac75=1008.$$
كما أن الاستدعاء الدقيق للحالات الصغيرة يعطي \(1008\) أيضًا، وبذلك يوضّح المثال توافق البنية التكرارية مع الصيغة المغلقة.
تسير تطبيقات C++ وPython وJava على القيم \(n=1,2,\dots,10000\) وتحافظ فقط على عدد قليل من الكميات التراكمية. أولًا تُحدَّث القيمة \(2^n \bmod M\)، ومنها نحصل على البسط \(2^n-1\). ثم تُقسَم هذه القيمة على \(2n-1\) داخل الحساب المعياري باستخدام معكوس ضربي معياري، وبذلك تُحسب النسبة الحالية \(R_n\) من دون مغادرة الترديد.
بعد ذلك يحدّث التنفيذ حاصلَي ضرب متداخلين: الحاصل التراكمي \(Q_n\)، ثم حاصل ضرب جميع التراكمات \(\prod_{k=1}^{n}Q_k\). وبالتوازي مع ذلك يوسِّع العامل \(T_n!\) عبر ضرب الأعداد الصحيحة \(n\) الجديدة التي أضيفت عند الانتقال من \(T_{n-1}\) إلى \(T_n\). وعند ضرب العامل المثلثي في الحاصل التراكمي نحصل على \(f_n\)، ثم يُضاف هذا المقدار إلى الجواب النهائي بترديد \(M\).
تضيف نسخة C++ أيضًا تحققًا دقيقًا للأحجام الصغيرة جدًا. فهي تمثل المجموعات النشطة بأقنعة بتية، وتعدّد الزجاجات المكشوفة، وتحسب عدد المسارات النشطة لكل اختيار، ثم تحفظ نتائج العلاقة التكرارية باستخدام أعداد صحيحة ذات دقة غير محدودة. وبعد تطابق القيم الأولى مع الصيغة السريعة يبدأ الحساب الكبير.
المسار السريع يعمل بزمن \(O(N\log M)\) عند \(N=10000\)، لأن كل خطوة تحتاج إلى معكوس معياري واحد محسوب بالرفع السريع للأس. أما الحالة الحسابية نفسها فهي ثابتة الحجم، ولذلك تحتاج الصيغة الجارية إلى ذاكرة إضافية \(O(1)\) فقط، باستثناء أي تخزين اختياري لقيم وسيطة لأغراض التحقق.
أما المتحقق الدقيق فتعقيده أسي في عدد الزجاجات، ولهذا لا يُستخدم إلا على مثلثات صغيرة جدًا. وظيفته إثبات صحة الصيغة، لا تنفيذ الحساب النهائي الكبير.