The problem asks for the number of unordered decompositions of \(100\) into at least two positive integers. In partition language, we want every partition of \(100\) except the single-part partition \(100\) itself.
Equivalently, we may count partitions of \(100\) whose largest part is at most \(99\). That quantity is \(p(100)-1=190{,}569{,}291\), and the implementations compute it directly without ever generating the partitions themselves.
The natural state for this problem is a restricted partition count. Instead of asking for all partitions at once, we count how many ways a sum can be formed when only small parts are allowed.
For integers \(s \ge 0\) and \(k \ge 0\), let \(P_k(s)\) be the number of partitions of \(s\) using only parts from the set \(\{1,2,\dots,k\}\). The Project Euler question for a general target \(n\) is therefore
$$P_{n-1}(n).$$
The upper limit is \(n-1\), not \(n\), because allowing the part \(n\) would introduce the trivial one-term partition \(n\), which the problem excludes.
This point of view also matches the generating function
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
For Problem 76 we need the coefficient of \(x^{100}\) in \(\prod_{j=1}^{99}(1-x^j)^{-1}\). Each factor expands as \(1+x^j+x^{2j}+\cdots\), so choosing a term from every factor records how many copies of each allowed part are used.
Fix \(k \ge 1\). Every partition counted by \(P_k(s)\) falls into exactly one of two disjoint classes:
Partitions that do not use the part \(k\), counted by \(P_{k-1}(s)\).
Partitions that use at least one \(k\). Removing one copy of \(k\) leaves a partition of \(s-k\) whose parts are still at most \(k\), counted by \(P_k(s-k)\).
That gives the recurrence
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$$
The boundary conditions are just as important:
$$P_k(0)=1 \quad \text{for all } k\ge 0,\qquad P_0(s)=0 \quad \text{for all } s\gt 0.$$
The first identity says that there is exactly one way to form zero, namely the empty partition. The second says that no positive sum can be formed when no positive parts are available.
The implementations compress the recurrence into one array. After finishing the outer-loop step for a particular part \(k\), the entry at position \(s\) stores exactly \(P_k(s)\).
The update rule is
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$$
Before processing part \(k\), the cell \(\text{ways}[s]\) holds \(P_{k-1}(s)\). Because the inner loop runs upward, the cell \(\text{ways}[s-k]\) has already been updated for the same \(k\), so it holds \(P_k(s-k)\). One in-place addition therefore realizes the recurrence above.
This upward sweep is the key invariant of the whole method. It allows the current part \(k\) to be used repeatedly. If the sweep ran downward, each part would be used at most once, which would solve a different problem.
For \(n=5\), excluding the trivial partition \(5\), the valid decompositions are
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
So the correct answer is \(6\). The array states make the recurrence visible:
After allowing only part \(1\): \([1,1,1,1,1,1]\).
After also allowing part \(2\): \([1,1,2,2,3,3]\).
After also allowing part \(3\): \([1,1,2,3,4,5]\).
After also allowing part \(4\): \([1,1,2,3,5,6]\).
The final value is \(\text{ways}[5]=6\), exactly matching the checkpoint used by the implementations.
The array is created with \(\text{ways}[0]=1\) and every other entry equal to \(0\). That single nonzero value encodes the base fact \(P_k(0)=1\).
The outer loop runs through candidate parts \(1,2,\dots,n-1\). Stopping at \(n-1\) is mathematically deliberate: it removes the one-part decomposition \(n\) from the count. For each part, the inner loop visits all sums from that part up to \(n\) and performs one in-place addition.
Because the inner loop is increasing, the current part may be reused any number of times. That is exactly what partitions require, and it is the reason the one-dimensional array produces unrestricted multiplicities instead of a subset-sum style count.
The C++, Python, and Java implementations all use the same recurrence and the same update order. The C++ and Python versions expose a configurable target \(n\) and also verify the sample case \(n=5\rightarrow 6\) before printing the main answer. The Java version keeps the Project Euler value \(n=100\) directly in a shorter fixed-size program.
After the loops finish, the output cell is \(\text{ways}[n]=P_{n-1}(n)\). For Problem 76 this is \(190{,}569{,}291\).
For each part \(k\in\{1,\dots,n-1\}\), the inner loop performs \(n-k+1\) updates. The exact number of additions is therefore
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$$
That is \(O(n^2)\) time and \(O(n)\) space. When \(n=100\), the program performs exactly \(5049\) in-place additions, so the computation is tiny compared with the size of the answer.
Gesucht ist die Anzahl ungeordneter Zerlegungen von \(100\) in mindestens zwei positive ganze Zahlen. In der Sprache der Partitionen bedeutet das: alle Partitionen von \(100\), außer der einteiligen Partition \(100\) selbst.
Äquivalent dazu kann man Partitionen von \(100\) zählen, deren größter Teil höchstens \(99\) ist. Diese Zahl ist \(p(100)-1=190{,}569{,}291\), und genau diese Größe berechnen die Implementierungen, ohne die Partitionen jemals explizit aufzulisten.
Der passende Zustand für dieses Problem ist eine beschränkte Partitionszahl. Statt alle Partitionen auf einmal zu betrachten, zählt man, wie viele Summen mit zugelassenen Teilen bis zu einer festen Obergrenze gebildet werden können.
Für ganze Zahlen \(s \ge 0\) und \(k \ge 0\) sei \(P_k(s)\) die Anzahl der Partitionen von \(s\), die nur Teile aus \(\{1,2,\dots,k\}\) verwenden. Für ein allgemeines Ziel \(n\) lautet die gesuchte Größe also
$$P_{n-1}(n).$$
Die obere Grenze ist \(n-1\) und nicht \(n\), weil der Teil \(n\) genau die triviale Ein-Teil-Partition \(n\) erzeugen würde, die laut Aufgabe ausgeschlossen werden muss.
Diese Sicht passt auch exakt zur erzeugenden Funktion
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
Für Problem 76 brauchen wir also den Koeffizienten von \(x^{100}\) in \(\prod_{j=1}^{99}(1-x^j)^{-1}\). Jeder Faktor \(1+x^j+x^{2j}+\cdots\) beschreibt, wie oft der Teil \(j\) verwendet wird.
Fixiere \(k \ge 1\). Jede Partition, die zu \(P_k(s)\) beiträgt, gehört genau zu einer von zwei disjunkten Klassen:
Partitionen ohne den Teil \(k\), gezählt durch \(P_{k-1}(s)\).
Partitionen mit mindestens einem \(k\). Entfernt man ein solches \(k\), bleibt eine Partition von \(s-k\) übrig, deren Teile weiterhin höchstens \(k\) sind, also gezählt durch \(P_k(s-k)\).
Daraus folgt die Rekurrenz
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$$
Ebenso wichtig sind die Randbedingungen:
$$P_k(0)=1 \quad \text{für alle } k\ge 0,\qquad P_0(s)=0 \quad \text{für alle } s\gt 0.$$
Die erste Identität sagt, dass es genau eine Darstellung der Summe \(0\) gibt, nämlich die leere Partition. Die zweite sagt, dass mit keinen positiven Teilen auch keine positive Summe gebildet werden kann.
Die Implementierungen komprimieren diese Rekurrenz in ein einziges Array. Nachdem der Außenschritt für einen bestimmten Teil \(k\) beendet ist, enthält der Eintrag an Position \(s\) genau den Wert \(P_k(s)\).
Die Aktualisierung lautet
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$$
Vor der Verarbeitung von \(k\) steht in \(\text{ways}[s]\) der Wert \(P_{k-1}(s)\). Weil die innere Schleife aufsteigend läuft, ist \(\text{ways}[s-k]\) für denselben Wert \(k\) bereits aktualisiert und enthält daher \(P_k(s-k)\). Eine einzige In-Place-Addition realisiert also genau die Rekurrenz.
Dieser aufsteigende Durchlauf ist das entscheidende Invarianzprinzip. Er erlaubt, den aktuellen Teil \(k\) beliebig oft zu verwenden. Bei einem absteigenden Durchlauf dürfte jeder Teil höchstens einmal vorkommen, und das wäre ein anderes Problem.
Für \(n=5\) sind ohne die triviale Partition \(5\) die gültigen Zerlegungen
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
Die richtige Antwort ist also \(6\). Die Zustände des Arrays zeigen die Rekurrenz direkt:
Nach Zulassen von Teil \(1\): \([1,1,1,1,1,1]\).
Nach zusätzlichem Zulassen von Teil \(2\): \([1,1,2,2,3,3]\).
Nach zusätzlichem Zulassen von Teil \(3\): \([1,1,2,3,4,5]\).
Nach zusätzlichem Zulassen von Teil \(4\): \([1,1,2,3,5,6]\).
Damit ist \(\text{ways}[5]=6\), genau wie im Prüfbeispiel der Implementierungen.
Das Array wird mit \(\text{ways}[0]=1\) und sonstigen Nullen erzeugt. Dieser eine Nichtnullwert kodiert die Basisinformation \(P_k(0)=1\).
Die äußere Schleife läuft über die Kandidatenteile \(1,2,\dots,n-1\). Dass sie bei \(n-1\) stoppt, ist mathematisch wesentlich: So wird die Ein-Teil-Zerlegung \(n\) aus der Zählung entfernt. Für jeden Teil besucht die innere Schleife alle Summen von diesem Teil bis \(n\) und führt eine In-Place-Addition aus.
Weil die innere Schleife aufsteigend ist, kann der aktuelle Teil beliebig oft wiederverwendet werden. Genau das verlangen Partitionen, und deshalb liefert das eindimensionale Array eine Zählung mit unbeschränkter Vielfachheit statt eines Teilmengenproblems.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Rekurrenz und dieselbe Aktualisierungsreihenfolge. Die C++- und Python-Versionen erlauben ein frei wählbares Ziel \(n\) und prüfen außerdem den Beispielwert \(n=5\rightarrow 6\), bevor sie das Hauptergebnis ausgeben. Die Java-Version hält dagegen den Euler-Wert \(n=100\) direkt in einem besonders kurzen Programm fest.
Nach Ende der Schleifen steht im Ausgabefeld \(\text{ways}[n]=P_{n-1}(n)\). Für Problem 76 ist das \(190{,}569{,}291\).
Für jeden Teil \(k\in\{1,\dots,n-1\}\) führt die innere Schleife genau \(n-k+1\) Aktualisierungen aus. Die exakte Anzahl von Additionen ist also
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$$
Das ergibt \(O(n^2)\) Zeit und \(O(n)\) Speicher. Für \(n=100\) sind das exakt \(5049\) In-Place-Additionen, also ein sehr kleiner Rechenaufwand im Vergleich zur Größe der Antwort.
Soru, \(100\) sayısının en az iki pozitif tam sayının toplamı olarak kaç farklı sırasız biçimde yazılabildiğini sorar. Yani \(100\)'ün tüm tamsayı bölmelerini sayıyoruz; yalnızca tek terimli \(100\) bölmesini dışarıda bırakıyoruz.
Buna eşdeğer biçimde, en büyük parçası en fazla \(99\) olan \(100\) bölmelerini sayabiliriz. Bu sayı \(p(100)-1=190{,}569{,}291\)'dir ve uygulamalar tam olarak bunu, bölmeleri açıkça üretmeden hesaplar.
Bu problem için en doğal durum tanımı kısıtlı bölüm sayısıdır. Tüm bölmeleri tek seferde saymak yerine, yalnızca belli bir üst sınıra kadar parçalar kullanıldığında kaç farklı toplam elde edilebildiğini izleriz.
\(s \ge 0\) ve \(k \ge 0\) için \(P_k(s)\), yalnızca \(\{1,2,\dots,k\}\) kümesinden parçalar kullanılarak \(s\)'nin kaç farklı şekilde bölünebildiği olsun. O halde genel hedef \(n\) için aradığımız nicelik
$$P_{n-1}(n)$$
olur. Üst sınırın \(n\) değil de \(n-1\) olması tesadüf değildir; çünkü parça olarak \(n\)'ye izin verilirse, sorunun özellikle istemediği tek terimli \(n\) bölmesi de sayılmış olur.
Bu bakış açısı üreteç fonksiyonu ile de birebir örtüşür:
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
Problem 76 için gereken şey, \(\prod_{j=1}^{99}(1-x^j)^{-1}\) çarpımında \(x^{100}\)'ün katsayısıdır. Her faktör \(1+x^j+x^{2j}+\cdots\), parçanın \(j\) tane değil, \(j\) değerinin kaç kez kullanılacağını kodlar.
Sabit bir \(k \ge 1\) seçelim. \(P_k(s)\)'ye katkı veren her bölme tam olarak iki ayrık sınıftan birine girer:
\(k\) parçasını hiç kullanmayan bölmeler; bunların sayısı \(P_{k-1}(s)\)'dir.
En az bir tane \(k\) kullanan bölmeler. Böyle bir bölmeden bir adet \(k\) çıkarılırsa, geriye parçaları yine en fazla \(k\) olan bir \(s-k\) bölmesi kalır; bunun sayısı \(P_k(s-k)\)'dir.
Dolayısıyla temel yineleme
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k)$$
şeklindedir. Sınır koşulları da aynı derecede önemlidir:
$$P_k(0)=1 \quad \text{tüm } k\ge 0 \text{ için},\qquad P_0(s)=0 \quad \text{tüm } s\gt 0 \text{ için}.$$
İlk eşitlik, sıfırı oluşturmanın tek yolunun boş bölme olduğunu söyler. İkinci eşitlik ise hiç pozitif parça yoksa pozitif toplam da üretilemeyeceğini belirtir.
Uygulamalar bu yinelemeyi tek bir diziye sıkıştırır. Dış döngüdeki \(k\) adımı tamamlandığında, \(s\) konumundaki değer tam olarak \(P_k(s)\)'dir.
Güncelleme kuralı
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n)$$
biçimindedir. \(k\) işlenmeden hemen önce \(\text{ways}[s]\) hücresinde \(P_{k-1}(s)\) vardır. İç döngü artan yönde gittiği için \(\text{ways}[s-k]\) aynı \(k\) için daha önce güncellenmiştir ve artık \(P_k(s-k)\) değerini taşır. Böylece tek bir yerinde toplama işlemi, matematiksel yinelemeyi doğrudan uygular.
Bütün yöntemin kalbi bu artan iç döngüdür. Bu sayede mevcut parça \(k\) birden fazla kez kullanılabilir. Döngü azalan yönde çalışsaydı her parça en fazla bir kez seçilirdi; o zaman çözülen problem bölüm sayımı değil, başka bir altküme sayımı olurdu.
\(n=5\) için, tek terimli \(5\) bölmesi hariç geçerli yazılışlar şunlardır:
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
Doğru cevap \(6\)'dır. Dizi durumları yinelemeyi görünür kılar:
Yalnızca \(1\) parçasına izin verildikten sonra: \([1,1,1,1,1,1]\).
\(2\) de eklendikten sonra: \([1,1,2,2,3,3]\).
\(3\) de eklendikten sonra: \([1,1,2,3,4,5]\).
\(4\) de eklendikten sonra: \([1,1,2,3,5,6]\).
Son hücre \(\text{ways}[5]=6\) olur; bu da uygulamaların kullandığı kontrol değeriyle aynıdır.
Dizi \(\text{ways}[0]=1\) ve diğer tüm hücreler \(0\) olacak şekilde kuruludur. Bu tek sıfır olmayan değer, \(P_k(0)=1\) temel gerçeğini temsil eder.
Dış döngü olası parçaları \(1,2,\dots,n-1\) arasında dolaşır. \(n-1\)'de durmak matematiksel olarak zorunludur; böylece tek terimli \(n\) bölmesi baştan dışlanır. Her parça için iç döngü, o parçadan \(n\)'ye kadar olan tüm toplamları ziyaret eder ve yerinde bir toplama yapar.
İç döngü artan yönde olduğu için mevcut parça gerektiği kadar tekrar kullanılabilir. Bölmeler tam olarak bunu ister; bu yüzden tek boyutlu dizi, sınırsız çokluklu kullanım sayısını doğru biçimde verir.
C++, Python ve Java uygulamalarının çekirdek matematiği aynıdır. C++ ve Python sürümleri hedef \(n\) değerini değiştirilebilir tutar ve ana sonucu yazmadan önce \(n=5\rightarrow 6\) kontrolünü yapar. Java sürümü ise Problem Euler ayarı olan \(n=100\)'ü doğrudan kullanan daha kısa bir versiyondur.
Döngüler bittiğinde çıktı hücresi \(\text{ways}[n]=P_{n-1}(n)\) olur. Problem 76 için bu değer \(190{,}569{,}291\)'dir.
Her \(k\in\{1,\dots,n-1\}\) parçası için iç döngü tam olarak \(n-k+1\) güncelleme yapar. Dolayısıyla toplam toplama sayısı
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}$$
olur. Bu da zamanı \(O(n^2)\), belleği \(O(n)\) yapar. \(n=100\) için program tam \(5049\) yerinde toplama yapar; yani cevap büyük olsa da hesaplama küçüktür.
La pregunta pide cuántas descomposiciones sin importar el orden tiene \(100\) como suma de al menos dos enteros positivos. En el lenguaje de particiones, contamos todas las particiones de \(100\) salvo la partición trivial de un solo término, \(100\).
De forma equivalente, podemos contar las particiones de \(100\) cuyo mayor sumando es como mucho \(99\). Esa cantidad es \(p(100)-1=190{,}569{,}291\), y eso es precisamente lo que calculan las implementaciones sin enumerar las particiones una por una.
El estado correcto para este problema es un conteo de particiones restringidas. En vez de pedir todas las particiones de golpe, preguntamos cuántas formas hay de construir una suma cuando solo se permiten partes pequeñas.
Para enteros \(s \ge 0\) y \(k \ge 0\), definimos \(P_k(s)\) como el número de particiones de \(s\) que usan únicamente partes del conjunto \(\{1,2,\dots,k\}\). Entonces, para un objetivo general \(n\), la cantidad buscada es
$$P_{n-1}(n).$$
El límite superior es \(n-1\) y no \(n\) porque permitir la parte \(n\) introduciría exactamente la partición trivial de un solo término, que el enunciado excluye.
La misma idea aparece en la función generadora
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
Para el problema 76 necesitamos el coeficiente de \(x^{100}\) en \(\prod_{j=1}^{99}(1-x^j)^{-1}\). Cada factor \(1+x^j+x^{2j}+\cdots\) representa cuántas copias de la parte \(j\) elegimos.
Fijemos \(k \ge 1\). Toda partición contada por \(P_k(s)\) cae exactamente en una de dos clases disjuntas:
Las que no usan la parte \(k\), contadas por \(P_{k-1}(s)\).
Las que usan al menos un \(k\). Si quitamos una copia de \(k\), queda una partición de \(s-k\) cuyas partes siguen siendo a lo sumo \(k\), contada por \(P_k(s-k)\).
De ahí sale la recurrencia central
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$$
Las condiciones base también son esenciales:
$$P_k(0)=1 \quad \text{para todo } k\ge 0,\qquad P_0(s)=0 \quad \text{para todo } s\gt 0.$$
La primera dice que la suma \(0\) tiene una única representación: la partición vacía. La segunda dice que con ninguna parte positiva disponible no puede formarse una suma positiva.
Las implementaciones comprimen la recurrencia en un solo arreglo. Después de terminar el paso exterior correspondiente a una parte \(k\), la posición \(s\) del arreglo contiene exactamente \(P_k(s)\).
La actualización es
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$$
Antes de procesar \(k\), la celda \(\text{ways}[s]\) guarda \(P_{k-1}(s)\). Como el recorrido interior es ascendente, la celda \(\text{ways}[s-k]\) ya fue actualizada para el mismo \(k\), de modo que ahora contiene \(P_k(s-k)\). Una sola suma en el sitio implementa exactamente la recurrencia matemática.
Ese recorrido ascendente es la invariante decisiva del método. Permite reutilizar la parte actual \(k\) tantas veces como sea necesario. Si el recorrido fuera descendente, cada parte podría usarse como mucho una vez y el algoritmo resolvería otro problema distinto.
Para \(n=5\), excluyendo la partición trivial \(5\), las descomposiciones válidas son
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
Así, la respuesta correcta es \(6\). Los estados del arreglo muestran la recurrencia en acción:
Después de permitir solo la parte \(1\): \([1,1,1,1,1,1]\).
Después de añadir la parte \(2\): \([1,1,2,2,3,3]\).
Después de añadir la parte \(3\): \([1,1,2,3,4,5]\).
Después de añadir la parte \(4\): \([1,1,2,3,5,6]\).
El valor final es \(\text{ways}[5]=6\), exactamente el mismo punto de control que usan las implementaciones.
El arreglo se crea con \(\text{ways}[0]=1\) y todas las demás entradas iguales a \(0\). Ese único valor no nulo codifica la condición base \(P_k(0)=1\).
El bucle exterior recorre las partes candidatas \(1,2,\dots,n-1\). Detenerse en \(n-1\) es una decisión matemática, no un detalle de implementación: así se elimina desde el principio la descomposición trivial \(n\). Para cada parte, el bucle interior visita todas las sumas desde esa parte hasta \(n\) y realiza una suma en el mismo arreglo.
Como el bucle interior avanza de menor a mayor, la parte actual puede reutilizarse tantas veces como haga falta. Eso es exactamente lo que exige el conteo de particiones, y por eso el arreglo unidimensional funciona.
Las implementaciones en C++, Python y Java comparten la misma recurrencia y el mismo orden de actualización. Las versiones de C++ y Python permiten cambiar el valor objetivo \(n\) y además verifican el caso de prueba \(n=5\rightarrow 6\) antes de imprimir la respuesta principal. La versión en Java conserva directamente el valor fijo \(n=100\) en una forma más compacta.
Al terminar los bucles, la casilla final contiene \(\text{ways}[n]=P_{n-1}(n)\). Para el problema 76, eso vale \(190{,}569{,}291\).
Para cada parte \(k\in\{1,\dots,n-1\}\), el bucle interior realiza \(n-k+1\) actualizaciones. El número exacto de sumas es
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$$
Por tanto, el tiempo es \(O(n^2)\) y el espacio es \(O(n)\). Cuando \(n=100\), el programa ejecuta exactamente \(5049\) sumas en el sitio, así que el coste computacional es mínimo aunque la respuesta numérica sea grande.
题目要求计算：把 \(100\) 写成至少两个正整数之和，一共有多少种不同写法。这里顺序不重要，所以 \(1+1+98\) 与 \(98+1+1\) 只算同一种。
用整数拆分的语言来说，我们要的是 \(100\) 的所有拆分里，去掉单项拆分 \(100\) 之后剩下的数量。等价地说，就是只允许部件大小不超过 \(99\) 时，\(100\) 的拆分数。这个值为 \(p(100)-1=190{,}569{,}291\)，而实现代码正是直接计算这个数。
这道题最合适的数学对象不是“直接枚举所有拆分”，而是“限制允许使用的部件大小之后，某个和可以被拆成多少种”。这正好导向一个非常稳定的动态规划状态。
对整数 \(s \ge 0\) 与 \(k \ge 0\)，定义 \(P_k(s)\) 为：只允许使用 \(\{1,2,\dots,k\}\) 这些部件时，把 \(s\) 写成无序和的方案数。于是一般目标 \(n\) 的答案就是
$$P_{n-1}(n).$$
上界必须是 \(n-1\) 而不是 \(n\)。原因非常直接：如果允许部件 \(n\)，就会把单独一个 \(n\) 的平凡拆分也算进去，而题目明确要求“至少两个正整数”。
这个定义还对应同一个生成函数：
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
对 Problem 76 来说，我们需要的是 \(\prod_{j=1}^{99}(1-x^j)^{-1}\) 中 \(x^{100}\) 的系数。每个因子展开成 \(1+x^j+x^{2j}+\cdots\)，表示部件 \(j\) 可以使用 \(0\) 次、\(1\) 次、\(2\) 次，依此类推。
固定某个 \(k \ge 1\)。所有计入 \(P_k(s)\) 的拆分恰好分成两类，而且两类互不重叠：
第一类完全不使用部件 \(k\)，其数量就是 \(P_{k-1}(s)\)。
第二类至少使用一个 \(k\)。如果从这样的拆分里删去一个 \(k\)，剩下的是一个对 \(s-k\) 的拆分，而且部件仍然不超过 \(k\)，因此其数量是 \(P_k(s-k)\)。
于是得到核心递推
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$$
边界条件同样关键：
$$P_k(0)=1 \quad \text{对所有 } k\ge 0,\qquad P_0(s)=0 \quad \text{对所有 } s\gt 0.$$
第一条表示“和为 \(0\)”只有一种方式，即空拆分；第二条表示当没有任何正部件可用时，无法组成正数。
代码没有使用二维表，而是把状态压缩成一个数组。外层循环处理完部件 \(k\) 之后，数组第 \(s\) 个位置保存的正是 \(P_k(s)\)。
更新式是
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$$
在处理部件 \(k\) 之前，\(\text{ways}[s]\) 里存的是 \(P_{k-1}(s)\)。由于内层循环按从小到大的顺序前进，\(\text{ways}[s-k]\) 对同一个 \(k\) 已经更新过，所以那里存放的是 \(P_k(s-k)\)。这样，一次原地加法就正好对应上面的数学递推。
内层循环必须递增，这一点是整个算法最重要的不变量。只有这样，当前部件 \(k\) 才能被重复使用任意多次。如果改成递减循环，那么每个部件至多使用一次，算法就会变成另一类“子集选择”问题，而不是整数拆分。
当 \(n=5\) 时，去掉平凡拆分 \(5\) 以后，合法写法是
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
因此正确答案是 \(6\)。数组状态能把过程看得很清楚：
只允许部件 \(1\) 后，数组为 \([1,1,1,1,1,1]\)。
再允许部件 \(2\) 后，数组为 \([1,1,2,2,3,3]\)。
再允许部件 \(3\) 后，数组为 \([1,1,2,3,4,5]\)。
再允许部件 \(4\) 后，数组为 \([1,1,2,3,5,6]\)。
最后得到 \(\text{ways}[5]=6\)，这正是实现中用来做自检的样例结果。
数组初始化为 \(\text{ways}[0]=1\)，其余位置为 \(0\)。这个唯一的非零值对应数学上的基本事实：和为 \(0\) 只有一种表示方式。
外层循环遍历候选部件 \(1,2,\dots,n-1\)。在 \(n-1\) 处停止不是偶然，而是为了从一开始就排除单项拆分 \(n\)。对于每个部件，内层循环从该部件本身一路走到 \(n\)，并做一次原地累加。
由于内层循环是递增的，当前部件可以被反复使用，这正符合整数拆分的定义。因此这段代码虽然只有一个数组，却真正实现了“部件可无限次使用”的计数。
C++、Python 和 Java 三个实现的核心递推完全一致，差别只在外围包装。C++ 与 Python 版本允许把目标值 \(n\) 改成别的数，并在输出主结果前检查样例 \(n=5\rightarrow 6\)。Java 版本则直接固定使用题目中的 \(n=100\)，因此代码更短。
当双层循环结束时，最终答案就在 \(\text{ways}[n]=P_{n-1}(n)\) 中。对本题而言，这个值就是 \(190{,}569{,}291\)。
对于每个 \(k\in\{1,\dots,n-1\}\)，内层循环执行 \(n-k+1\) 次更新，所以总加法次数恰好是
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$$
因此时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(n)\)。当 \(n=100\) 时，实际只进行 \(5049\) 次原地加法，计算量非常小。
Нужно посчитать, сколькими неупорядоченными способами можно представить число \(100\) в виде суммы хотя бы двух положительных целых чисел. Поэтому записи \(1+1+98\) и \(98+1+1\) считаются одной и той же разбиением.
На языке теории разбиений это означает: взять все разбиения числа \(100\) и исключить единственное одночленное разбиение \(100\). Эквивалентно можно считать разбиения \(100\), у которых наибольшая часть не превосходит \(99\). Это число равно \(p(100)-1=190{,}569{,}291\), и именно его вычисляют реализации.
Удобнее всего рассматривать не сразу все разбиения, а число разбиений при ограничении на максимальную допустимую часть. Это дает естественное динамическое состояние и напрямую совпадает с тем, что делает код.
Для целых \(s \ge 0\) и \(k \ge 0\) обозначим через \(P_k(s)\) число разбиений числа \(s\), в которых разрешены только части из множества \(\{1,2,\dots,k\}\). Тогда для общего целевого значения \(n\) требуется величина
$$P_{n-1}(n).$$
Верхняя граница равна именно \(n-1\), а не \(n\), потому что разрешение части \(n\) добавило бы тривиальное разбиение из одного слагаемого, которое условие запрещает.
Та же идея выражается через производящую функцию
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
В задаче 76 нужен коэффициент при \(x^{100}\) в произведении \(\prod_{j=1}^{99}(1-x^j)^{-1}\). Каждый множитель \(1+x^j+x^{2j}+\cdots\) отвечает выбору числа копий части \(j\).
Зафиксируем \(k \ge 1\). Любое разбиение, учтенное в \(P_k(s)\), попадает ровно в один из двух непересекающихся классов:
Разбиения, в которых часть \(k\) не используется. Их число равно \(P_{k-1}(s)\).
Разбиения, в которых хотя бы один раз используется \(k\). Если удалить одну такую часть, останется разбиение числа \(s-k\), где максимальная разрешенная часть по-прежнему равна \(k\). Таких разбиений \(P_k(s-k)\).
Отсюда получается основная рекурсия
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$$
Граничные условия также обязательны:
$$P_k(0)=1 \quad \text{для всех } k\ge 0,\qquad P_0(s)=0 \quad \text{для всех } s\gt 0.$$
Первое равенство означает, что ноль представляется единственным способом: пустым разбиением. Второе говорит, что положительную сумму невозможно составить, если никаких положительных частей нет.
Вместо двумерной таблицы реализации используют один массив. После завершения внешнего шага для фиксированного значения \(k\) элемент с индексом \(s\) содержит ровно \(P_k(s)\).
Обновление имеет вид
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$$
До обработки части \(k\) в \(\text{ways}[s]\) хранится \(P_{k-1}(s)\). Поскольку внутренний цикл идет по возрастанию, значение \(\text{ways}[s-k]\) для того же \(k\) уже обновлено и равно \(P_k(s-k)\). Поэтому одна операция сложения на месте точно воспроизводит математическую рекурсию.
Именно возрастающий порядок внутреннего цикла является главным инвариантом алгоритма. Он позволяет использовать текущую часть \(k\) многократно. Если бы цикл шел вниз, каждая часть могла бы использоваться не более одного раза, и это была бы уже другая задача.
Для \(n=5\), если исключить тривиальное разбиение \(5\), остаются варианты
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
Значит, правильный ответ равен \(6\). Состояния массива показывают, как это число появляется:
После разрешения только части \(1\): \([1,1,1,1,1,1]\).
После добавления части \(2\): \([1,1,2,2,3,3]\).
После добавления части \(3\): \([1,1,2,3,4,5]\).
После добавления части \(4\): \([1,1,2,3,5,6]\).
Итоговое значение \(\text{ways}[5]=6\) полностью совпадает с контрольным примером в реализациях.
Массив создается так, что \(\text{ways}[0]=1\), а все остальные ячейки равны нулю. Этот единственный ненулевой элемент кодирует базовый факт \(P_k(0)=1\).
Внешний цикл перебирает допустимые части \(1,2,\dots,n-1\). Остановка на \(n-1\) принципиальна: именно так из подсчета сразу исключается одночленное разбиение \(n\). Для каждой части внутренний цикл проходит суммы от этой части до \(n\) и делает одно сложение на месте.
Поскольку внутренний цикл идет по возрастанию, текущую часть можно использовать столько раз, сколько нужно. Именно это и требуется для подсчета разбиений, поэтому одного массива достаточно.
Реализации на C++, Python и Java используют одну и ту же рекурсию и один и тот же порядок обновления. Варианты на C++ и Python позволяют менять целевое значение \(n\) и дополнительно проверяют пример \(n=5\rightarrow 6\) перед выводом основного ответа. Версия на Java оставляет фиксированное значение \(n=100\) и поэтому выглядит компактнее.
После завершения циклов в ячейке \(\text{ways}[n]\) находится \(P_{n-1}(n)\). Для задачи 76 это число равно \(190{,}569{,}291\).
Для каждой части \(k\in\{1,\dots,n-1\}\) внутренний цикл выполняет \(n-k+1\) обновлений. Точное число операций сложения равно
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$$
Следовательно, время работы равно \(O(n^2)\), а память равна \(O(n)\). При \(n=100\) программа делает ровно \(5049\) сложений на месте, так что вычисление очень мало по сравнению с размером результата.
المطلوب هو حساب عدد الطرق غير المرتبة لكتابة \(100\) على صورة مجموع عددين صحيحين موجبين على الأقل. لذلك فإن \(1+1+98\) و\(98+1+1\) تمثلان الطريقة نفسها، لأن ترتيب الحدود لا يغيّر التقسيم.
بلغة تقسيمات الأعداد، نحن نأخذ جميع تقسيمات \(100\) ثم نحذف التقسيم التافه ذي الحد الواحد \(100\). وبصورة مكافئة يمكننا أن نعدّ تقسيمات \(100\) التي لا تتجاوز أكبر قطعة فيها \(99\). هذه القيمة هي \(p(100)-1=190{,}569{,}291\)، وهذا هو العدد الذي تحسبه التطبيقات مباشرة.
الفكرة الصحيحة هنا ليست محاولة توليد جميع التقسيمات، بل تعريف عدد تقسيمات المجموع عندما نسمح فقط بقطع صغيرة حتى حد أعلى معين. هذا التعريف يعطي حالة ديناميكية طبيعية ويطابق ما يفعله الكود خطوة بخطوة.
لأي عددين صحيحين \(s \ge 0\) و\(k \ge 0\)، لنرمز بـ \(P_k(s)\) إلى عدد طرق تقسيم \(s\) باستخدام أجزاء من المجموعة \(\{1,2,\dots,k\}\) فقط. عندئذ تكون الكمية المطلوبة لهدف عام \(n\) هي
$$P_{n-1}(n).$$
يظهر الحد الأعلى \(n-1\) بدلًا من \(n\) لأن السماح بالجزء \(n\) سيضيف تلقائيًا التقسيم الأحادي \(n\)، وهو بالضبط ما تستبعده المسألة.
ويظهر المفهوم نفسه في دالة التوليد
$$\sum_{s\ge 0} P_k(s)x^s=\prod_{j=1}^{k}\frac{1}{1-x^j}.$$
في المسألة 76 نحتاج إلى معامل \(x^{100}\) في \(\prod_{j=1}^{99}(1-x^j)^{-1}\). فكل عامل من الشكل \(1+x^j+x^{2j}+\cdots\) يعبّر عن اختيار عدد النسخ المستعملة من الجزء \(j\).
ثبّت قيمة \(k \ge 1\). كل تقسيم يُحسب ضمن \(P_k(s)\) يقع في واحدة من فئتين منفصلتين تمامًا:
تقسيمات لا تستخدم الجزء \(k\) إطلاقًا، وعددها \(P_{k-1}(s)\).
تقسيمات تستخدم على الأقل نسخة واحدة من \(k\). إذا حذفنا نسخة واحدة من \(k\)، بقي لدينا تقسيم للعدد \(s-k\) مع بقاء جميع الأجزاء أصغر من أو مساوية لـ \(k\)، وعدد هذه التقسيمات هو \(P_k(s-k)\).
ومن هنا تأتي العلاقة الأساسية
$$P_k(s)=P_{k-1}(s)+P_k(s-k)\qquad (s\ge k).$$
كما أن شروط البداية ضرورية:
$$P_k(0)=1 \quad \text{for all } k\ge 0,\qquad P_0(s)=0 \quad \text{for all } s\gt 0.$$
المعادلة الأولى تقول إن تكوين المجموع \(0\) له طريقة واحدة فقط، وهي التقسيم الفارغ. والمعادلة الثانية تقول إن المجموع الموجب لا يمكن تكوينه إذا لم تتوافر أي أجزاء موجبة.
التطبيقات لا تخزن جدولًا ثنائي البعد، بل تضغط الحالة في مصفوفة واحدة. بعد إنهاء خطوة الحلقة الخارجية الخاصة بالجزء \(k\)، تكون الخانة ذات الفهرس \(s\) مساوية تمامًا لـ \(P_k(s)\).
وقاعدة التحديث هي
$$\text{ways}[s]\leftarrow \text{ways}[s]+\text{ways}[s-k]\qquad (s=k,k+1,\dots,n).$$
قبل معالجة \(k\)، تكون القيمة الموجودة في \(\text{ways}[s]\) هي \(P_{k-1}(s)\). ولأن الحلقة الداخلية تسير تصاعديًا، فإن \(\text{ways}[s-k]\) تكون قد حُدِّثت مسبقًا لنفس \(k\)، ولذلك تحمل القيمة \(P_k(s-k)\). وهكذا فإن جمعًا واحدًا في المكان نفسه يحقق العلاقة الرياضية بدقة.
هذا الترتيب التصاعدي هو أهم ثابت منطقي في الخوارزمية. فهو الذي يسمح باستخدام الجزء الحالي \(k\) مرات غير محدودة. ولو سارت الحلقة تنازليًا، لأصبح كل جزء مستخدمًا مرة واحدة كحد أقصى، وعندها نكون قد حللنا مسألة مختلفة تمامًا.
عندما يكون \(n=5\)، وبعد استبعاد التقسيم التافه \(5\)، تكون الكتابات الصحيحة هي
$$4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1.$$
إذن الجواب الصحيح هو \(6\). كما أن حالات المصفوفة توضح كيف يظهر هذا العدد:
بعد السماح بالجزء \(1\) فقط تصبح المصفوفة \([1,1,1,1,1,1]\).
بعد إضافة الجزء \(2\) تصبح \([1,1,2,2,3,3]\).
بعد إضافة الجزء \(3\) تصبح \([1,1,2,3,4,5]\).
بعد إضافة الجزء \(4\) تصبح \([1,1,2,3,5,6]\).
وعليه نحصل في النهاية على \(\text{ways}[5]=6\)، وهي القيمة المرجعية التي تتحقق منها بعض التطبيقات.
تُنشأ المصفوفة بحيث تكون \(\text{ways}[0]=1\) وجميع الخانات الأخرى مساوية للصفر. هذا الإدخال غير الصفري الوحيد يمثل حقيقة البداية \(P_k(0)=1\).
تمر الحلقة الخارجية على الأجزاء المرشحة \(1,2,\dots,n-1\). والتوقف عند \(n-1\) قرار رياضي مقصود، لأنه يستبعد مباشرةً التقسيم الأحادي \(n\). ولكل جزء، تمر الحلقة الداخلية على جميع المجاميع من ذلك الجزء حتى \(n\) وتنفذ عملية جمع واحدة في المكان نفسه.
وبسبب الاتجاه التصاعدي للحلقة الداخلية، يمكن استعمال الجزء الحالي مرات متعددة. وهذا هو المطلوب تمامًا في عدّ التقسيمات، ولذلك تكفي مصفوفة واحدة للحصول على العدد الصحيح.
تستخدم تطبيقات C++ وPython وJava العلاقة نفسها وترتيب التحديث نفسه. نسختا C++ وPython تسمحان بتغيير الهدف \(n\) كما تتحققان من المثال \(n=5\rightarrow 6\) قبل طباعة الجواب الرئيسي. أما نسخة Java فتبقي قيمة المسألة \(n=100\) ثابتة في برنامج أقصر.
بعد انتهاء الحلقتين، تحتوي الخانة الأخيرة على \(\text{ways}[n]=P_{n-1}(n)\). وفي المسألة 76 تكون هذه القيمة \(190{,}569{,}291\).
لكل جزء \(k\in\{1,\dots,n-1\}\)، تنفذ الحلقة الداخلية \(n-k+1\) عملية تحديث. لذلك فإن العدد الدقيق لعمليات الجمع هو
$$\sum_{k=1}^{n-1}(n-k+1)=\frac{(n-1)(n+2)}{2}.$$
إذًا التعقيد الزمني هو \(O(n^2)\)، والتعقيد المكاني هو \(O(n)\). وعند \(n=100\) ينفذ البرنامج \(5049\) عملية جمع في المكان نفسه، لذا فالحساب صغير جدًا رغم أن الجواب نفسه كبير.