Problem 154 asks for the number of coefficients in the expansion of \((x+y+z)^{200000}\) that are divisible by \(10^{12}\). Every coefficient on the layer \(a+b+c=200000\) of Pascal's pyramid has the form
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000.$$
Because \(10^{12}=2^{12}5^{12}\), a coefficient qualifies exactly when it contains at least twelve factors of 2 and at least twelve factors of 5. The implementations never expand the polynomial; they reduce each candidate to two arithmetic tests on precomputed factorial valuations.
The problem is really about the prime exponents inside multinomial coefficients. Once those exponents are written in a reusable form, the huge trinomial layer becomes a structured counting problem.
For any prime \(p\), let \(v_p(m)\) denote the exponent of \(p\) in the prime factorization of \(m\). Then for a trinomial coefficient we have
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n.$$
With \(n=200000\), divisibility by \(10^{12}\) is therefore equivalent to the pair of inequalities
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
No other prime matters. The entire search reduces to deciding, for every admissible triple \((a,b,c)\), whether the 2-adic and 5-adic valuations are both large enough.
The implementations precompute two tables:
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
The key recurrence is
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
Here \(v_p(m)\) is obtained by repeatedly dividing \(m\) by \(p\) until divisibility stops. This recurrence is exactly what the code computes when it walks from \(1\) up to \(200000\). Mathematically it matches Legendre's formula,
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor,$$
but the cumulative table is more convenient for millions of repeated queries.
Once the tables are ready, define the fixed thresholds
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12.$$
Then a triple \((a,b,c)\) contributes to the answer exactly when
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5.$$
This is the central invariant of the solution. The enormous value of \(\binom{200000}{a,b,c}\) is never formed explicitly; the implementation only compares three array lookups against two fixed bounds.
The trinomial coefficient is symmetric in \(a\), \(b\), and \(c\), so the implementations enumerate only ordered triples
$$a\le b\le c,\qquad a+b+c=n.$$
After choosing \(a\) and \(b\), the third value is forced as \(c=n-a-b\). The ordering condition gives the sharp bounds
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
Every accepted ordered triple stands for several coefficients obtained by permuting its coordinates. Its multiplicity is
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b\ne c\ \text{or}\ a\ne b=c,\\ 6,& a,b,c\ \text{all distinct}. \end{cases} $$
So the full triangular layer of Pascal's pyramid is replaced by one sixth-sized ordered region together with a small orbit-size correction.
The real computation uses \(n=200000\), but a smaller example makes the arithmetic transparent. Take \(n=20\) and the ordered triple \((a,b,c)=(4,6,10)\).
For the factor 5,
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
so
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
For the factor 2,
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
hence
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3.$$
This coefficient has only one factor of 5 and three factors of 2, so it fails the \(10^{12}\) test immediately. Because \(4\), \(6\), and \(10\) are all distinct, a successful triple of this shape would contribute 6 coefficients to the final count.
The C++, Python, and Java implementations allocate two arrays of length \(n+1\). For each \(m=1,2,\dots,n\), they count how many times \(m\) is divisible by 2 and by 5, then add those counts to the previous prefix totals. After this pass, every query \(v_2(m!)\) or \(v_5(m!)\) becomes an \(O(1)\) array lookup.
They then loop over \(a\) from \(0\) to \(\lfloor n/3\rfloor\), over \(b\) from \(a\) to \(\lfloor(n-a)/2\rfloor\), and set \(c=n-a-b\). For each ordered triple, the implementation evaluates the two valuation inequalities above. When both hold, it adds 1, 3, or 6 according to whether the triple has three equal entries, exactly two equal entries, or three distinct entries.
The mathematical test is the same in all three languages. The C++ and Python implementations split the outer \(a\)-range into chunks so different workers accumulate disjoint partial totals and combine them at the end. The Java implementation performs the same ordered scan serially.
Building the factorial valuation tables costs \(O(n\log n)\) in the straightforward repeated-division model used by the implementations, and it uses \(O(n)\) memory for the two prefix arrays.
The ordered enumeration visits
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2)$$
candidate pairs \((a,b)\), so the dominant running time is \(O(n^2)\). Restricting to \(a\le b\le c\) saves roughly a factor of six compared with scanning every permutation separately, but the asymptotic order remains quadratic. Memory stays linear because only the two valuation tables and a few counters are needed.
Problem 154 fragt nach der Anzahl der Koeffizienten in der Entwicklung von \((x+y+z)^{200000}\), die durch \(10^{12}\) teilbar sind. Jeder Koeffizient auf der Schicht \(a+b+c=200000\) von Pascals Pyramide hat die Form
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000.$$
Weil \(10^{12}=2^{12}5^{12}\) gilt, ist ein Koeffizient genau dann zulässig, wenn er mindestens zwölf Zweierfaktoren und mindestens zwölf Fünferfaktoren besitzt. Die Implementierungen expandieren das Polynom nie direkt, sondern reduzieren jeden Kandidaten auf zwei Tests mit vorberechneten Fakultätsbewertungen.
Inhaltlich geht es um die Primexponenten von Multinomialkoeffizienten. Sobald diese Exponenten in wiederverwendbarer Form vorliegen, wird aus der riesigen Dreiecksfläche \(a+b+c=200000\) ein systematisches Zählproblem.
Für eine Primzahl \(p\) bezeichne \(v_p(m)\) den Exponenten von \(p\) in der Primfaktorzerlegung von \(m\). Für einen Trinomialkoeffizienten gilt dann
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n.$$
Bei \(n=200000\) ist Teilbarkeit durch \(10^{12}\) also äquivalent zu
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
Weitere Primzahlen spielen keine Rolle. Die gesamte Suche besteht daher darin, für jedes zulässige Tripel \((a,b,c)\) genau diese beiden Bewertungen zu prüfen.
Die Implementierungen berechnen zwei Tabellen vor:
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
Die zugrunde liegende Rekurrenz lautet
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
Dabei erhält man \(v_p(m)\), indem man \(m\) so oft durch \(p\) teilt, bis keine Teilbarkeit mehr vorliegt. Genau diese Rekurrenz wird im Code umgesetzt, wenn die Werte von \(1\) bis \(200000\) aufaddiert werden. Mathematisch stimmt das mit der Legendre-Formel überein,
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor,$$
aber die kumulative Tabelle ist für Millionen wiederholter Abfragen deutlich praktischer.
Nach der Vorberechnung definiert man die festen Schranken
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12.$$
Dann trägt ein Tripel \((a,b,c)\) genau dann zur Antwort bei, wenn
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5.$$
Das ist die zentrale Invariante der gesamten Lösung. Der riesige Wert von \(\binom{200000}{a,b,c}\) wird nie explizit erzeugt; stattdessen vergleicht die Implementierung nur drei Tabellenzugriffe mit zwei festen Grenzwerten.
Der Trinomialkoeffizient ist symmetrisch in \(a\), \(b\) und \(c\). Deshalb durchlaufen die Implementierungen nur geordnete Tripel
$$a\le b\le c,\qquad a+b+c=n.$$
Nach Wahl von \(a\) und \(b\) ist der dritte Wert durch \(c=n-a-b\) festgelegt. Aus der Ordnung folgen die scharfen Grenzen
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
Jedes akzeptierte geordnete Tripel steht für mehrere Koeffizienten, die durch Permutation der drei Koordinaten entstehen. Die Multiplizität ist
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b\ne c\ \text{oder}\ a\ne b=c,\\ 6,& a,b,c\ \text{alle verschieden}. \end{cases} $$
So wird die vollständige Schicht von Pascals Pyramide durch einen etwa sechsmal kleineren geordneten Bereich plus einen kleinen Orbitfaktor ersetzt.
Die eigentliche Aufgabe verwendet \(n=200000\), aber mit einem kleineren Beispiel wird die Arithmetik klarer. Betrachte \(n=20\) und das geordnete Tripel \((a,b,c)=(4,6,10)\).
Für den Faktor 5 gilt
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
also
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
Für den Faktor 2 gilt
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
und damit
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3.$$
Dieser Koeffizient besitzt also nur einen Fünferfaktor und drei Zweierfaktoren und fällt sofort durch den \(10^{12}\)-Test. Da \(4\), \(6\) und \(10\) paarweise verschieden sind, würde ein erfolgreiches Tripel dieser Form 6 Koeffizienten zum Endergebnis beitragen.
Die C++-, Python- und Java-Implementierungen legen zwei Arrays der Länge \(n+1\) an. Für jedes \(m=1,2,\dots,n\) zählen sie, wie oft \(m\) durch 2 beziehungsweise 5 teilbar ist, und addieren diese Beiträge zum vorherigen Präfixwert. Danach ist jede Abfrage von \(v_2(m!)\) oder \(v_5(m!)\) nur noch ein \(O(1)\)-Arrayzugriff.
Anschließend läuft \(a\) von \(0\) bis \(\lfloor n/3\rfloor\), \(b\) von \(a\) bis \(\lfloor(n-a)/2\rfloor\), und \(c=n-a-b\). Für jedes geordnete Tripel prüft die Implementierung die beiden Bewertungsungleichungen. Wenn beide erfüllt sind, addiert sie 1, 3 oder 6, je nachdem ob alle drei Werte gleich sind, genau zwei gleich sind oder alle drei verschieden sind.
Der mathematische Test ist in allen drei Sprachen identisch. Die C++- und Python-Implementierungen teilen den äußeren \(a\)-Bereich in Blöcke auf, sodass verschiedene Worker disjunkte Teilsummen berechnen und am Ende zusammenführen. Die Java-Implementierung führt denselben geordneten Durchlauf seriell aus.
Das Erzeugen der Fakultätsbewertungstabellen kostet im naiven Modell mit wiederholter Division \(O(n\log n)\) Zeit und \(O(n)\) Speicher für die beiden Präfixarrays.
Die geordnete Enumeration besucht
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2)$$
Kandidatenpaare \((a,b)\), also ist die dominante Laufzeit \(O(n^2)\). Die Einschränkung auf \(a\le b\le c\) spart gegenüber einer vollständigen Permutationssuche ungefähr einen Faktor 6, ändert aber nicht die quadratische asymptotische Ordnung. Der Speicher bleibt linear, weil nur die beiden Bewertungstabellen und einige Zähler gehalten werden.
Problem 154, \((x+y+z)^{200000}\) açılımındaki katsayılardan kaç tanesinin \(10^{12}\) ile bölündüğünü sorar. Pascal piramidinin \(a+b+c=200000\) katmanındaki her katsayı
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000$$
şeklindedir. \(10^{12}=2^{12}5^{12}\) olduğundan, bir katsayının uygun olması için hem en az 12 tane 2 çarpanı hem de en az 12 tane 5 çarpanı içermesi gerekir. Uygulamalar polinomu hiç açmaz; her adayı, önceden hesaplanmış faktöriyel değerlemeleri üzerinde yapılan iki teste indirger.
Bu problem özünde multinom katsayılarındaki asal üslerini sayma problemidir. Bu üsler tekrar tekrar kullanılabilecek biçimde yazılınca, dev üçgensel katman düzenli bir sayma bölgesine dönüşür.
Bir asal \(p\) için \(v_p(m)\), \(m\)'nin asal çarpanlara ayrımında \(p\)'nin üssü olsun. O zaman bir trinomial katsayı için
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n$$
olur. \(n=200000\) için \(10^{12}\)'ye bölünebilme tam olarak şu iki koşula denktir:
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
Başka hiçbir asal önemli değildir. Dolayısıyla bütün arama, her geçerli \((a,b,c)\) üçlüsü için bu iki değerin yeterince büyük olup olmadığını kontrol etmeye iner.
Uygulamalar iki tablo önceden hazırlar:
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
Temel bağıntı şudur:
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
Burada \(v_p(m)\), \(m\)'yi \(p\)'ye bölünebildiği sürece ardışık olarak bölerek bulunur. Kodun \(1\)'den \(200000\)'e kadar ilerlerken hesapladığı şey tam olarak bu önek bağıntısıdır. Matematiksel olarak bu, Legendre formülüyle de aynıdır:
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor.$$
Ancak milyonlarca sorgu yapılacağı için kapalı formülü her seferinde kullanmak yerine bu kümülatif tabloyu tutmak çok daha uygundur.
Tablolar hazırlandıktan sonra sabit eşikler
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12$$
tanımlanır. O zaman bir \((a,b,c)\) üçlüsü ancak ve ancak
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5$$
olduğunda sayılır. Çözümün merkezindeki değişmez budur. Devasa \(\binom{200000}{a,b,c}\) sayısı hiçbir zaman açıkça oluşturulmaz; uygulama yalnızca üç tablo okumasını iki sabit sınırla karşılaştırır.
Trinomial katsayı \(a\), \(b\) ve \(c\) değişkenlerinde simetriktir. Bu yüzden uygulamalar yalnızca
$$a\le b\le c,\qquad a+b+c=n$$
koşulunu sağlayan sıralı üçlüleri dolaşır. \(a\) ve \(b\) seçildikten sonra üçüncü değer zorunlu olarak \(c=n-a-b\) olur. Bu sıralama, keskin sınırları verir:
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
Kabul edilen her sıralı üçlü, koordinatların permütasyonlarından gelen birkaç katsayıyı temsil eder. Katkı çarpanı
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b\ne c\ \text{veya}\ a\ne b=c,\\ 6,& a,b,c\ \text{tamamı farklı}. \end{cases} $$
şeklindedir. Böylece Pascal piramidinin tüm katmanı, yaklaşık altıda birlik bir sıralı bölgeye ve küçük bir yörünge çarpanına indirgenir.
Gerçek hesap \(n=200000\) için yapılır, fakat aritmetiği küçük bir örnek daha iyi gösterir. \(n=20\) ve \((a,b,c)=(4,6,10)\) olsun.
5 çarpanı için
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
dolayısıyla
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
2 çarpanı için
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
ve buradan
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3$$
elde edilir. Bu katsayı yalnızca bir tane 5 ve üç tane 2 içerdiği için \(10^{12}\) testini anında geçemez. \(4\), \(6\) ve \(10\) birbirinden farklı olduğundan, bu biçimdeki başarılı bir üçlü son sayıya 6 katsayı eklerdi.
C++, Python ve Java uygulamaları \(n+1\) uzunluğunda iki dizi ayırır. Her \(m=1,2,\dots,n\) için, \(m\)'nin 2'ye ve 5'e kaç kez bölündüğünü sayarlar; sonra bu katkıları bir önceki önek toplamına eklerler. Bu geçişten sonra \(v_2(m!)\) ve \(v_5(m!)\) sorguları \(O(1)\) maliyetli dizi okumalarına dönüşür.
Daha sonra \(a\), \(0\) ile \(\lfloor n/3\rfloor\) arasında; \(b\), \(a\) ile \(\lfloor(n-a)/2\rfloor\) arasında dolaştırılır ve \(c=n-a-b\) alınır. Her sıralı üçlü için iki değerleme eşitsizliği test edilir. İkisi de sağlanırsa, üçlüdeki eşitlik desenine göre 1, 3 veya 6 eklenir.
Matematiksel test üç dilde de aynıdır. C++ ve Python uygulamaları dıştaki \(a\) aralığını parçalara ayırarak farklı çalışanların ayrık kısmi toplamlar üretmesini sağlar ve sonra bunları birleştirir. Java uygulaması aynı sıralı taramayı tek iş parçacığında yürütür.
Faktöriyel değerleme tablolarını oluşturmak, çözümlerde kullanılan basit tekrar-bölme modeliyle \(O(n\log n)\) zaman ve iki önek dizi için \(O(n)\) bellek gerektirir.
Sıralı tarama
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2)$$
adet \((a,b)\) adayı ziyaret eder; dolayısıyla baskın çalışma süresi \(O(n^2)\)'dir. \(a\le b\le c\) kısıtı, her permütasyonu ayrı taramaya göre yaklaşık 6 kat tasarruf sağlar ama asimptotik derecenin kuadratik kalmasını değiştirmez. Bellek doğrusal kalır; çünkü yalnızca iki değerleme tablosu ve birkaç sayaç tutulur.
El problema 154 pide contar cuántos coeficientes de la expansión de \((x+y+z)^{200000}\) son divisibles por \(10^{12}\). Cada coeficiente en la capa \(a+b+c=200000\) de la pirámide de Pascal tiene la forma
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000.$$
Como \(10^{12}=2^{12}5^{12}\), un coeficiente sirve exactamente cuando contiene al menos doce factores de 2 y al menos doce factores de 5. Las implementaciones no expanden el polinomio; convierten cada candidato en dos comprobaciones aritméticas sobre valuaciones factoriales precalculadas.
En esencia, el problema consiste en medir exponentes primos dentro de coeficientes multinomiales. Una vez escrita esa información en tablas reutilizables, la enorme capa tridimensional se convierte en un problema de conteo muy regular.
Para un primo \(p\), sea \(v_p(m)\) el exponente de \(p\) en la factorización prima de \(m\). Entonces, para un coeficiente trinomial,
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n.$$
Con \(n=200000\), la divisibilidad por \(10^{12}\) equivale por tanto a exigir
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
No interviene ningún otro primo. Toda la búsqueda se reduce a decidir, para cada triple admisible \((a,b,c)\), si esas dos valuaciones alcanzan el umbral requerido.
Las implementaciones precalculan dos tablas:
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
La recurrencia clave es
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
Aquí \(v_p(m)\) se obtiene dividiendo repetidamente \(m\) por \(p\) mientras siga siendo divisible. Eso es exactamente lo que calculan los programas al recorrer los enteros desde \(1\) hasta \(200000\). Desde el punto de vista matemático coincide con la fórmula cerrada de Legendre,
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor,$$
pero la tabla acumulada es mucho más útil cuando hay que hacer millones de consultas.
Una vez construidas las tablas, se fijan los umbrales
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12.$$
Entonces un triple \((a,b,c)\) cuenta exactamente cuando
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5.$$
Éste es el invariante central de toda la solución. El enorme coeficiente \(\binom{200000}{a,b,c}\) nunca se forma; la implementación sólo compara tres lecturas de tabla contra dos cotas fijas.
El coeficiente trinomial es simétrico en \(a\), \(b\) y \(c\). Por eso las implementaciones enumeran sólo triples ordenados
$$a\le b\le c,\qquad a+b+c=n.$$
Una vez elegidos \(a\) y \(b\), el tercer valor queda determinado como \(c=n-a-b\). La condición de orden produce las cotas exactas
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
Cada triple ordenado aceptado representa varias posiciones obtenidas al permutar las tres coordenadas. Su multiplicidad es
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b\ne c\ \text{o}\ a\ne b=c,\\ 6,& a,b,c\ \text{todos distintos}. \end{cases} $$
Así, la capa completa de la pirámide de Pascal se reemplaza por una región ordenada de tamaño aproximado a una sexta parte, más un pequeño factor de órbita.
El cálculo real usa \(n=200000\), pero el mecanismo se ve mejor en un ejemplo pequeño. Tomemos \(n=20\) y el triple ordenado \((a,b,c)=(4,6,10)\).
Para el factor 5,
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
y por tanto
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
Para el factor 2,
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
de modo que
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3.$$
Ese coeficiente sólo tiene un factor 5 y tres factores 2, así que falla inmediatamente la condición de \(10^{12}\). Como \(4\), \(6\) y \(10\) son distintos, un triple exitoso de esa forma aportaría 6 coeficientes al conteo final.
Las implementaciones en C++, Python y Java reservan dos arreglos de longitud \(n+1\). Para cada \(m=1,2,\dots,n\), cuentan cuántas veces \(m\) es divisible por 2 y por 5, y suman esas cantidades al prefijo anterior. Después de esta fase, cualquier consulta de \(v_2(m!)\) o \(v_5(m!)\) cuesta sólo una lectura de arreglo en \(O(1)\).
Luego iteran \(a\) desde \(0\) hasta \(\lfloor n/3\rfloor\), \(b\) desde \(a\) hasta \(\lfloor(n-a)/2\rfloor\), y fijan \(c=n-a-b\). Para cada triple ordenado, la implementación evalúa las dos desigualdades de valuación. Si ambas se cumplen, suma 1, 3 o 6 según el patrón de igualdades entre \(a\), \(b\) y \(c\).
La prueba matemática es la misma en los tres lenguajes. Las implementaciones en C++ y Python parten el rango exterior de \(a\) en bloques para que distintos trabajadores acumulen sumas parciales disjuntas y las unan al final. La implementación en Java realiza exactamente el mismo barrido de forma secuencial.
Construir las tablas de valuaciones factoriales cuesta \(O(n\log n)\) en el modelo directo de divisiones repetidas usado por las implementaciones, y requiere \(O(n)\) memoria para los dos arreglos prefijo.
La enumeración ordenada visita
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2)$$
pares candidatos \((a,b)\), así que el tiempo dominante es \(O(n^2)\). La restricción \(a\le b\le c\) ahorra aproximadamente un factor 6 frente a recorrer cada permutación por separado, pero el orden asintótico sigue siendo cuadrático. La memoria permanece lineal porque sólo hacen falta las dos tablas y unos pocos acumuladores.
第 154 题要求统计 \((x+y+z)^{200000}\) 展开式中有多少个系数能被 \(10^{12}\) 整除。Pascal 金字塔在平面 \(a+b+c=200000\) 上的每一个系数都写成
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000.$$
因为 \(10^{12}=2^{12}5^{12}\)，所以一个系数合格，当且仅当它至少含有 12 个因子 2，并且至少含有 12 个因子 5。三个实现都不会真的把多项式展开出来；它们做的是把每个候选三元组化成两个关于阶乘素因子指数的判定。
这道题的核心并不是系数本身有多大，而是这些系数里包含多少个 2 和 5。只要把这两个素数在阶乘中的指数预处理出来，整层 Pascal 金字塔就会变成一个规则清晰的计数问题。
对任意素数 \(p\)，记 \(v_p(m)\) 为 \(m\) 的素因子分解中 \(p\) 的指数。那么三项式系数满足
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n.$$
取 \(n=200000\) 时，系数能被 \(10^{12}\) 整除就等价于同时满足
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
这一步把问题完全压缩成两个素数的估值比较。别的素因子都与题目的整除条件无关，因此整个搜索过程只需要围绕 2 和 5 展开。
实现会先建立两张表：
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
它们满足非常直接的递推关系
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
这里的 \(v_p(m)\) 是通过不断用 \(p\) 去除 \(m\) 得到的，也就是看 \(m\) 最多能被 \(p\) 连续整除多少次。代码正是按这个递推从 \(1\) 一路累加到 \(200000\)。从理论上说，这和 Legendre 公式完全一致：
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor.$$
不过在本题里需要反复查询 \(v_2(a!)\)、\(v_5(a!)\)、\(v_2(b!)\)、\(v_5(c!)\) 这样的值，所以预先存成前缀数组比每次重新套公式要高效得多。
有了前缀表以后，把阈值固定成
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12.$$
那么一个三元组 \((a,b,c)\) 被计入答案，当且仅当
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5.$$
这就是整个算法的核心不变量。程序从头到尾都不会显式构造 \(\binom{200000}{a,b,c}\) 这个天文数字，而只是做常数次数组读取和比较。
三项式系数对 \(a\)、\(b\)、\(c\) 完全对称，所以没有必要把所有排列都单独枚举。实现只遍历满足
$$a\le b\le c,\qquad a+b+c=n$$
的有序三元组。选定 \(a\) 和 \(b\) 之后，第三个数就由 \(c=n-a-b\) 唯一决定。由有序条件可直接得到边界
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
每一个通过测试的有序三元组，其实代表了若干个由坐标重排得到的系数，因此需要乘上对应的重数：
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b\ne c\ \text{或}\ a\ne b=c,\\ 6,& a,b,c\ \text{两两不同}. \end{cases} $$
这一步把原本完整的对称平面压缩成大约六分之一的区域，再用一个很小的乘法修正恢复全部贡献。
真正的题目使用 \(n=200000\)，但为了看清计算过程，用一个小例子更方便。取 \(n=20\)，并考虑有序三元组 \((a,b,c)=(4,6,10)\)。
先看因子 5：
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
所以
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
再看因子 2：
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
于是
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3.$$
这说明该系数只有 1 个因子 5 和 3 个因子 2，显然不可能通过 \(10^{12}\) 的整除要求。另一方面，因为 \(4\)、\(6\)、\(10\) 互不相同，所以如果某个同类型三元组通过测试，它在最终答案中应当贡献 6 个系数。
C++、Python 和 Java 实现都会分配两个长度为 \(n+1\) 的数组。对每个 \(m=1,2,\dots,n\)，程序统计 \(m\) 中含有多少个 2、多少个 5，再把这些数量累加到前一个前缀值上。这样一来，任何 \(v_2(m!)\) 或 \(v_5(m!)\) 的查询都只需要一次 \(O(1)\) 的数组访问。
随后程序枚举 \(a=0,1,\dots,\lfloor n/3\rfloor\)，对每个 \(a\) 再枚举 \(b=a,a+1,\dots,\lfloor(n-a)/2\rfloor\)，并令 \(c=n-a-b\)。对每个有序三元组，它只做前面那两条估值不等式检查。若同时通过，就根据 \(a\)、\(b\)、\(c\) 的相等关系把 1、3 或 6 加入累计答案。
三种语言里的数学判定完全相同。C++ 和 Python 版本把最外层的 \(a\) 区间切成多个不重叠的小块，让不同工作单元分别计算局部计数，最后再把这些部分和合并。Java 版本执行的是同样的有序枚举，只是按单线程顺序完成。
按照实现里“不断整除 2 和 5”的直接做法，建立两张阶乘估值表需要 \(O(n\log n)\) 时间，空间为两张前缀数组的 \(O(n)\)。
有序枚举访问的候选 \((a,b)\) 数量为
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2),$$
因此主导时间复杂度是 \(O(n^2)\)。约束 \(a\le b\le c\) 会把常数因子大致缩小到原来的六分之一，但不会改变二次复杂度这一主阶。额外空间仍然是线性的，因为除了两张表和少量计数器之外，不需要再保存大对象。
В задаче 154 нужно посчитать, сколько коэффициентов в разложении \((x+y+z)^{200000}\) делятся на \(10^{12}\). Каждый коэффициент на слое \(a+b+c=200000\) в пирамиде Паскаля имеет вид
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000.$$
Поскольку \(10^{12}=2^{12}5^{12}\), коэффициент подходит тогда и только тогда, когда в нем есть не менее двенадцати множителей 2 и не менее двенадцати множителей 5. Реальные реализации не раскрывают многочлен явно; они заменяют проверку каждого коэффициента двумя сравнениями с заранее вычисленными факториальными оценками.
С математической точки зрения задача сводится к подсчету показателей простых чисел в мультиномиальных коэффициентах. Как только эти показатели выписаны в табличной форме, огромный слой \(a+b+c=200000\) превращается в вполне регулярную область перебора.
Для простого числа \(p\) обозначим через \(v_p(m)\) показатель степени \(p\) в разложении числа \(m\). Тогда для триномиального коэффициента верно
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n.$$
При \(n=200000\) условие делимости на \(10^{12}\) эквивалентно системе
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
Никакие другие простые числа здесь не важны. Поэтому вся задача сводится к тому, чтобы для каждого допустимого тройственного индекса \((a,b,c)\) проверить только эти две оценки.
Реализации заранее вычисляют две таблицы:
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
Ключевая рекуррентность такова:
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
Здесь \(v_p(m)\) находится простым повторным делением \(m\) на \(p\), пока делимость сохраняется. Именно это и делают программы при проходе от \(1\) до \(200000\). Теоретически это полностью согласуется с формулой Лежандра,
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor,$$
но накопленная таблица намного удобнее, когда одни и те же запросы к \(v_2(m!)\) и \(v_5(m!)\) нужно выполнять миллионы раз.
После построения таблиц вводятся фиксированные пороги
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12.$$
Тогда тройка \((a,b,c)\) попадает в ответ ровно тогда, когда
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5.$$
Это центральный инвариант всего решения. Гигантское число \(\binom{200000}{a,b,c}\) нигде не вычисляется явно; программа оперирует только несколькими чтениями из массивов и двумя сравнениями.
Триномиальный коэффициент симметричен по \(a\), \(b\) и \(c\), поэтому нет смысла перебирать все перестановки отдельно. Реализации рассматривают только упорядоченные тройки
$$a\le b\le c,\qquad a+b+c=n.$$
После выбора \(a\) и \(b\) третья координата уже фиксирована: \(c=n-a-b\). Из условия упорядоченности сразу следуют границы
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
Каждая прошедшая тройка представляет несколько коэффициентов, получающихся перестановкой координат. Ее кратность равна
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b\ne c\ \text{или}\ a\ne b=c,\\ 6,& a,b,c\ \text{все различны}. \end{cases} $$
Тем самым вся симметричная плоскость заменяется примерно шестой частью области и небольшим множителем, зависящим только от совпадений координат.
Настоящая задача использует \(n=200000\), но на меньшем примере арифметика видна лучше. Возьмем \(n=20\) и тройку \((a,b,c)=(4,6,10)\).
Для простого 5 имеем
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
поэтому
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
Для простого 2 имеем
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
и значит
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3.$$
У этого коэффициента только один множитель 5 и три множителя 2, так что условие для \(10^{12}\) он заведомо не проходит. Поскольку \(4\), \(6\) и \(10\) различны, успешная тройка такой формы давала бы вклад 6 в итоговый ответ.
Реализации на C++, Python и Java выделяют два массива длины \(n+1\). Для каждого \(m=1,2,\dots,n\) они считают, сколько раз число \(m\) делится на 2 и на 5, а затем прибавляют эти величины к предыдущим префиксным суммам. После этого любой запрос к \(v_2(m!)\) или \(v_5(m!)\) выполняется одним обращением к массиву за \(O(1)\).
Далее программы перебирают \(a\) от \(0\) до \(\lfloor n/3\rfloor\), затем \(b\) от \(a\) до \(\lfloor(n-a)/2\rfloor\), и определяют \(c=n-a-b\). Для каждой упорядоченной тройки выполняются две проверки оценок. Если обе пройдены, к сумме добавляется 1, 3 или 6 в зависимости от того, совпадают ли все три числа, совпадают только два из них или все три различны.
Математическое правило одно и то же во всех трех языках. Реализации на C++ и Python разбивают внешний диапазон по \(a\) на блоки, чтобы разные рабочие единицы считали непересекающиеся частичные суммы и потом складывали их. Реализация на Java выполняет тот же упорядоченный перебор последовательно.
Построение таблиц факториальных оценок занимает \(O(n\log n)\) времени в прямой модели повторного деления, использованной в реализациях, и \(O(n)\) памяти для двух префиксных массивов.
Упорядоченный перебор посещает
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2)$$
кандидатных пар \((a,b)\), поэтому доминирующее время работы равно \(O(n^2)\). Ограничение \(a\le b\le c\) экономит примерно фактор 6 по сравнению с перебором всех перестановок, но не меняет квадратичный асимптотический порядок. Память остается линейной, поскольку достаточно двух таблиц оценок и нескольких счетчиков.
تطلب المسألة 154 عدَّ عدد المعاملات في توسعة \((x+y+z)^{200000}\) التي تقبل القسمة على \(10^{12}\). كل معامل على الطبقة \(a+b+c=200000\) من هرم باسكال يُكتب على الصورة
$$\binom{200000}{a,b,c}=\frac{200000!}{a!b!c!},\qquad a,b,c\ge 0,\quad a+b+c=200000.$$
وبما أن \(10^{12}=2^{12}5^{12}\)، فإن المعامل يكون مناسبًا إذا وفقط إذا احتوى على ما لا يقل عن 12 عاملًا من 2 وعلى ما لا يقل عن 12 عاملًا من 5. لذلك لا تقوم التطبيقات بتوسيع كثير الحدود حرفيًا، بل تختزل فحص كل معامل إلى اختبارين عدديين يعتمدان على تقييماتٍ محسوبةٍ مسبقًا للعوامل المضروبية.
جوهر المسألة هو حساب أسس العددين الأوليين 2 و5 داخل المعاملات متعددة الحدود. وعندما تُخزَّن هذه المعلومات في جداول قابلة لإعادة الاستخدام، تتحول الطبقة الضخمة من هرم باسكال إلى منطقة عدّ منتظمة يمكن المرور عليها مباشرة.
لكل عدد أولي \(p\)، نرمز بـ \(v_p(m)\) إلى أسّ \(p\) في التحليل الأولي للعدد \(m\). عندئذٍ يحقق معامل ثلاثي الحدود العلاقة
$$v_p\!\left(\binom{n}{a,b,c}\right)=v_p(n!)-v_p(a!)-v_p(b!)-v_p(c!),\qquad a+b+c=n.$$
وعندما يكون \(n=200000\)، فإن القسمة على \(10^{12}\) تكافئ الشرطين
$$v_2\!\left(\binom{n}{a,b,c}\right)\ge 12,\qquad v_5\!\left(\binom{n}{a,b,c}\right)\ge 12.$$
لا تلعب أي أعداد أولية أخرى دورًا هنا. ولذلك فالمسألة كلها تنحصر في التحقق من هذين الشرطين لكل ثلاثية مسموحة \((a,b,c)\).
تحسب التطبيقات جدولين مسبقًا:
$$V_2(m)=v_2(m!),\qquad V_5(m)=v_5(m!),\qquad 0\le m\le n.$$
والعلاقة الأساسية هي
$$V_p(0)=0,\qquad V_p(m)=V_p(m-1)+v_p(m).$$
أما \(v_p(m)\) نفسها فتُستخرج بقسمة \(m\) على \(p\) مرارًا ما دام القسمة ممكنة. وهذا بالضبط ما تنفذه الشيفرة أثناء المرور من \(1\) إلى \(200000\). ومن الناحية النظرية يطابق ذلك صيغة ليجاندر
$$V_p(m)=\sum_{r\ge 1}\left\lfloor\frac{m}{p^r}\right\rfloor,$$
لكن الاحتفاظ بجدول تراكمي هو الأنسب لأن الخوارزمية تحتاج إلى عدد هائل من الاستعلامات المتكررة.
بعد تجهيز الجدولين نعرّف العتبتين الثابتتين
$$T_2=V_2(n)-12,\qquad T_5=V_5(n)-12.$$
وتُقبل الثلاثية \((a,b,c)\) إذا وفقط إذا تحقق
$$V_2(a)+V_2(b)+V_2(c)\le T_2,$$
$$V_5(a)+V_5(b)+V_5(c)\le T_5.$$
هذا هو الثابت المركزي في الحل كله. فالقيمة الضخمة للمعامل \(\binom{200000}{a,b,c}\) لا تُحسَب مباشرةً أبدًا؛ وإنما تُستخدم فقط قراءات قليلة من الجداول ومقارنتان مع حدين ثابتين.
معامل ثلاثي الحدود متناظر في \(a\) و\(b\) و\(c\)، ولذلك لا حاجة لتعداد كل التباديل على حدة. يكفي المرور على الثلاثيات المرتبة التي تحقق
$$a\le b\le c,\qquad a+b+c=n.$$
وبمجرد اختيار \(a\) و\(b\) فإن \(c\) تتحدد آليًا من العلاقة \(c=n-a-b\). ومن شرط الترتيب نحصل مباشرة على الحدود
$$0\le a\le \left\lfloor\frac{n}{3}\right\rfloor,\qquad a\le b\le \left\lfloor\frac{n-a}{2}\right\rfloor.$$
كل ثلاثية مرتبة ناجحة تمثل عدة معاملات ناتجة من تبديل الإحداثيات، ولذلك تُضرب في معامل تعدد يساوي
$$ \operatorname{mult}(a,b,c)= \begin{cases} 1,& a=b=c,\\ 3,& a=b,\ b\ne c\ \text{or}\ a\ne b,\ b=c,\\ 6,& a\lt b\lt c. \end{cases} $$
وبهذا تُستبدل الطبقة المتماثلة كاملةً من هرم باسكال بمنطقة مرتبة أصغر بكثير، مع تصحيح بسيط يعتمد فقط على نمط التساوي بين القيم الثلاث.
المسألة الفعلية تستخدم \(n=200000\)، لكن الحساب يتضح أكثر في مثال صغير. خذ \(n=20\) والثلاثية المرتبة \((a,b,c)=(4,6,10)\).
بالنسبة إلى العامل 5 لدينا
$$V_5(20)=4,\qquad V_5(4)=0,\qquad V_5(6)=1,\qquad V_5(10)=2,$$
ومن ثم
$$v_5\!\left(\binom{20}{4,6,10}\right)=4-(0+1+2)=1.$$
وبالنسبة إلى العامل 2 لدينا
$$V_2(20)=18,\qquad V_2(4)=3,\qquad V_2(6)=4,\qquad V_2(10)=8,$$
لذلك
$$v_2\!\left(\binom{20}{4,6,10}\right)=18-(3+4+8)=3.$$
إذن هذا المعامل يحتوي على عامل واحد من 5 وثلاثة عوامل من 2 فقط، ولذلك يفشل فورًا في شرط القسمة على \(10^{12}\). وبما أن \(4\) و\(6\) و\(10\) متمايزة، فإن ثلاثية ناجحة من هذا الشكل كانت ستضيف 6 معاملات إلى العد النهائي.
تخصص تطبيقات C++ وPython وJava مصفوفتين بطول \(n+1\). ولكل \(m=1,2,\dots,n\) تُحصي الشيفرة عدد مرات قسمة \(m\) على 2 وعدد مرات قسمة \(m\) على 5، ثم تضيف هاتين القيمتين إلى المجاميع التراكمية السابقة. بعد هذه المرحلة يصبح كل استعلام من نوع \(v_2(m!)\) أو \(v_5(m!)\) مجرد قراءة مصفوفة بكلفة \(O(1)\).
بعد ذلك تمر الشيفرة على \(a\) من \(0\) إلى \(\lfloor n/3\rfloor\)، وعلى \(b\) من \(a\) إلى \(\lfloor(n-a)/2\rfloor\)، ثم تضع \(c=n-a-b\). ولكل ثلاثية مرتبة تُطبَّق متراجحتا التقييم المذكورتان أعلاه. وإذا نجحت الثلاثية في الاختبارين، تُضاف \(1\) أو \(3\) أو \(6\) بحسب ما إذا كانت القيم الثلاث متساوية كلها أو كان اثنان منها فقط متساويين أو كانت كلها مختلفة.
الاختبار الرياضي نفسه مشترك بين اللغات الثلاث. إصدارا C++ وPython يقسمان مجال الحلقة الخارجية الخاصة بـ \(a\) إلى كتل مستقلة لكي تحسب وحدات العمل مجاميع جزئية منفصلة ثم تجمعها في النهاية. أما إصدار Java فينفذ المسح المرتب نفسه بصورة تسلسلية.
بناء جدولي تقييمات المضروب يكلف \(O(n\log n)\) زمنًا في نموذج القسمة المتكررة المباشر المستخدم في التطبيقات، ويستهلك \(O(n)\) ذاكرة من أجل مصفوفتين تراكمـيتين.
ويزور التعداد المرتب
$$\sum_{a=0}^{\lfloor n/3\rfloor}\left(\left\lfloor\frac{n-a}{2}\right\rfloor-a+1\right)=\Theta(n^2)$$
من الأزواج المرشحة \((a,b)\)، ولذلك يكون زمن التشغيل المهيمن هو \(O(n^2)\). إن فرض الشرط \(a\le b\le c\) يوفّر تقريبًا عاملًا مقداره 6 مقارنةً بتعداد كل تبديل على حدة، لكنه لا يغيّر الرتبة الأسّية الرئيسية التي تبقى تربيعية. أما الذاكرة فتبقى خطية لأن المطلوب هو الجدولان وبعض المجاميع فقط.