A positive integer is called increasing if its digits never decrease from left to right, and decreasing if its digits never increase. A number is non-bouncy when it belongs to at least one of those two families. The task is to count all non-bouncy positive integers below \(10^{100}\).
Direct enumeration is hopeless at this scale, but the implementations show that the problem collapses to pure combinatorics. The answer comes from one count for increasing numbers, one count for decreasing numbers, and one overlap correction.
Let \(N(n)\) denote the number of non-bouncy positive integers below \(10^n\). We count the increasing and decreasing families separately, then use inclusion-exclusion to remove the numbers that were counted twice.
Numbers below \(10^n\) have at most \(n\) digits. For increasing numbers, padding with leading zeros preserves monotonicity: for example, \(134\) becomes \(000134\), which is still weakly increasing. For decreasing numbers that trick fails: \(66420\) is decreasing, but \(066420\) is not. That is why the increasing side is counted in one fixed length \(n\), while the decreasing side is counted length by length.
After padding to exactly \(n\) digits, an increasing number corresponds to a weakly increasing digit string \(a_1 \le a_2 \le \cdots \le a_n\) with each \(a_i \in \{0,1,\dots,9\}\), and not all digits equal to zero. Such a string is completely determined by how many zeros, ones, ..., nines it contains. If those multiplicities are \(x_0,x_1,\dots,x_9\), then
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
By stars and bars, the number of solutions is
$$\binom{n+9}{9}.$$
One of those solutions is the all-zero string, which represents no positive integer, so the total number of increasing positive integers below \(10^n\) is
$$I(n)=\binom{n+9}{9}-1.$$
For decreasing numbers we count each length separately. Fix \(k\in\{1,\dots,n\}\). A decreasing \(k\)-digit number has digits \(d_1 \ge d_2 \ge \cdots \ge d_k\), with \(d_1\neq 0\). Once again the sequence is determined by the multiplicities of the digits \(0,1,\dots,9\): if \(y_j\) is the number of copies of digit \(j\), then
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
Writing the digits in descending order reconstructs exactly one weakly decreasing string, so there are \(\binom{k+9}{9}\) such strings in total. The only forbidden case is \(00\cdots 0\), hence the number of decreasing positive integers with exactly \(k\) digits is
$$D_k=\binom{k+9}{9}-1.$$
Summing over all lengths and using the hockey-stick identity gives
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
A number counted in both families must satisfy \(d_1 \le d_2 \le \cdots \le d_k\) and \(d_1 \ge d_2 \ge \cdots \ge d_k\) at the same time. Therefore every adjacent pair is equal, so all digits are identical. These are exactly the positive repdigits: \(1,2,\dots,9,11,22,\dots,99,\dots\).
For each length \(k\) from 1 to \(n\), there are 9 such numbers, so the overlap is
$$R(n)=9n.$$
With \(n=3\), the formulas give
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27.$$
Therefore
$$N(3)=219+282-27=474,$$
which matches the familiar three-digit count.
Combining the three parts yields
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
Equivalently,
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
For the problem bound \(n=100\), this becomes
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
The C++, Python, and Java implementations do not enumerate any numbers. They compute the required binomial coefficients exactly. The Python version uses the standard combinatorial function from the language library, while the C++ and Java versions build the coefficients multiplicatively so that each division is exact at every step.
Once the two binomial coefficients are available, the implementation evaluates the three terms \(I(n)\), \(D(n)\), and \(R(n)=9n\), then returns \(I(n)+D(n)-R(n)\). One implementation also allows the digit limit \(n\) to vary and checks the known case \(n=6\), where the result is \(12951\); the other two plug in \(n=100\) directly. In every language the algorithm is the same closed-form count described above.
The work is constant-sized for this problem. Only two binomial coefficients are computed, followed by a handful of additions and subtractions. In the multiplicative implementations, those two coefficients require 9 and 10 loop iterations respectively, so the runtime is effectively \(O(1)\).
Space usage is also \(O(1)\) beyond the exact integer values being stored. The only subtlety is numeric range: the arithmetic must be exact, which is why Python uses arbitrary-precision integers, Java uses big integers, and the C++ solution uses a type wide enough to hold all intermediate values for \(n=100\).
Eine positive ganze Zahl heißt steigend, wenn ihre Ziffern von links nach rechts niemals kleiner werden, und fallend, wenn ihre Ziffern niemals größer werden. Nicht-hüpfend ist eine Zahl genau dann, wenn sie zu mindestens einer dieser beiden Familien gehört. Gesucht ist die Anzahl aller nicht-hüpfenden positiven Zahlen unter \(10^{100}\).
Brute Force hilft hier nicht weiter. Die Implementierungen zeigen stattdessen, dass sich die Aufgabe auf reine Kombinatorik reduziert: ein Zählterm für steigende Zahlen, ein Zählterm für fallende Zahlen und eine Korrektur für die doppelt gezählten Fälle.
Sei \(N(n)\) die Anzahl der nicht-hüpfenden positiven Zahlen unter \(10^n\). Wir zählen zuerst die steigenden und die fallenden Zahlen getrennt und ziehen anschließend per Inklusion-Exklusion die Schnittmenge wieder ab.
Zahlen unter \(10^n\) haben höchstens \(n\) Stellen. Bei steigenden Zahlen darf man links mit Nullen auffüllen, ohne die Monotonie zu zerstören: Aus \(134\) wird \(000134\), und die Ziffernfolge bleibt schwach steigend. Bei fallenden Zahlen funktioniert dieser Trick nicht: \(66420\) ist fallend, aber \(066420\) ist es nicht mehr. Deshalb zählt man die steigende Seite in einer einzigen festen Länge \(n\), die fallende Seite jedoch stellenweise nach exakter Länge.
Nach dem Auffüllen auf genau \(n\) Stellen entspricht jede steigende Zahl einer schwach steigenden Ziffernfolge \(a_1 \le a_2 \le \cdots \le a_n\) mit \(a_i \in \{0,1,\dots,9\}\), wobei nicht alle Ziffern null sein dürfen. Eine solche Folge ist vollständig durch die Häufigkeiten der Ziffern \(0,1,\dots,9\) bestimmt. Bezeichnen wir diese Häufigkeiten mit \(x_0,x_1,\dots,x_9\), so gilt
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
Mit Sterne-und-Balken erhält man dafür
$$\binom{n+9}{9}$$
Lösungen. Eine davon ist die reine Nullfolge, die keine positive Zahl repräsentiert. Also ist die Anzahl steigender positiver Zahlen unter \(10^n\)
$$I(n)=\binom{n+9}{9}-1.$$
Für fallende Zahlen zählt man jede Länge getrennt. Fixiere \(k\in\{1,\dots,n\}\). Eine fallende \(k\)-stellige Zahl hat Ziffern \(d_1 \ge d_2 \ge \cdots \ge d_k\) mit \(d_1\neq 0\). Wieder ist die Folge genau durch die Vielfachheiten der Ziffern \(0,1,\dots,9\) bestimmt. Sind \(y_j\) diese Vielfachheiten, so gilt
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
Schreibt man die Ziffern in absteigender Reihenfolge aus, so erhält man zu jeder solchen Wahl genau eine schwach fallende Ziffernfolge. Insgesamt gibt es also \(\binom{k+9}{9}\) Möglichkeiten. Verboten ist nur der Fall \(00\cdots 0\). Damit ist die Anzahl fallender positiver Zahlen mit genau \(k\) Stellen
$$D_k=\binom{k+9}{9}-1.$$
Über alle Längen summiert und mit der Hockey-Stick-Identität vereinfacht ergibt sich
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
Eine Zahl, die gleichzeitig steigend und fallend ist, muss \(d_1 \le d_2 \le \cdots \le d_k\) und zugleich \(d_1 \ge d_2 \ge \cdots \ge d_k\) erfüllen. Also ist jedes benachbarte Ziffernpaar gleich, und damit sind alle Ziffern identisch. Genau das sind die positiven Zahlen mit nur einer wiederholten Ziffer: \(1,2,\dots,9,11,22,\dots,99,\dots\).
Für jede Länge \(k\) von 1 bis \(n\) gibt es davon 9 Stück, also
$$R(n)=9n.$$
Für \(n=3\) liefern die Formeln
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27.$$
Daher ist
$$N(3)=219+282-27=474,$$
genau der bekannte Wert für alle nicht-hüpfenden Zahlen mit höchstens drei Stellen.
Setzt man die drei Teile zusammen, erhält man
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
Äquivalent dazu ist
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
Für die Aufgabenstellung \(n=100\) folgt
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
Die C++-, Python- und Java-Implementierungen zählen keine Zahlen direkt auf. Stattdessen berechnen sie die benötigten Binomialkoeffizienten exakt. Python nutzt dafür eine eingebaute Kombinatorik-Funktion, während C++ und Java die Koeffizienten multiplikativ aufbauen, sodass jede Division unterwegs ohne Rest aufgeht.
Sobald die beiden Binomialkoeffizienten vorliegen, berechnet die Implementierung die drei Terme \(I(n)\), \(D(n)\) und \(R(n)=9n\) und bildet daraus \(I(n)+D(n)-R(n)\). Eine der Implementierungen lässt auch andere Stellenobergrenzen \(n\) zu und prüft den bekannten Fall \(n=6\), bei dem \(12951\) herauskommt; die beiden anderen setzen direkt \(n=100\) ein. In allen drei Sprachen ist die Mathematik identisch.
Für diese Aufgabe ist der Arbeitsaufwand konstant. Es werden nur zwei Binomialkoeffizienten und danach einige Additionen und Subtraktionen berechnet. In den multiplikativen Versionen haben die beiden Schleifen die festen Längen 9 und 10, daher ist die Laufzeit praktisch \(O(1)\).
Auch der Speicherverbrauch ist \(O(1)\), abgesehen von wenigen exakten Ganzzahlen. Wichtig ist nur die Zahlendarstellung: Die Rechnung darf nicht runden, deshalb verwendet Python beliebig große Ganzzahlen, Java BigInteger und C++ einen Typ, der für alle Zwischenwerte bei \(n=100\) breit genug ist.
Bir pozitif tam sayı, rakamları soldan sağa giderken hiç azalmıyorsa artan, hiç artmıyorsa azalan olarak adlandırılır. Bu iki aileden en az birine giren sayılar zıplayıcı olmayan sayılardır. İstenen şey, \(10^{100}\)'ün altındaki tüm zıplayıcı olmayan pozitif tam sayıların sayısını bulmaktır.
Bu ölçekte doğrudan sayma mümkün değildir. Çözüm dosyalarının gösterdiği şey şudur: bütün problem saf kombinatoriğe iner. Sonuç, artan sayılar için bir sayım, azalan sayılar için bir sayım ve çift sayılanlar için bir düzeltmeden oluşur.
\(N(n)\), \(10^n\)'in altındaki zıplayıcı olmayan pozitif tam sayıların sayısı olsun. Önce artan ve azalan aileleri ayrı ayrı sayacağız, sonra kapsama-dışlama ile iki kez sayılanları çıkaracağız.
\(10^n\)'in altındaki sayılar en fazla \(n\) basamaklıdır. Artan sayılarda başa sıfır eklemek monotonluğu bozmaz: örneğin \(134\), \(000134\) olur ve dizi hâlâ zayıf artandır. Azalan sayılarda aynı fikir çalışmaz: \(66420\) azalandır ama \(066420\) artık azalan değildir. Bu yüzden artan tarafı tek seferde sabit uzunluk \(n\) üzerinden, azalan tarafı ise basamak uzunluğuna göre ayrı ayrı saymak gerekir.
Bir artan sayı tam \(n\) basamağa sıfırlarla tamamlandığında, \(a_1 \le a_2 \le \cdots \le a_n\) koşulunu sağlayan bir rakam dizisine dönüşür; burada her \(a_i\), \(\{0,1,\dots,9\}\) kümesindedir ve bütün rakamlar aynı anda sıfır olamaz. Böyle bir diziyi tamamen belirleyen şey, 0, 1, ..., 9 rakamlarının kaç kez göründüğüdür. Bu çokluklar \(x_0,x_1,\dots,x_9\) olsun. O zaman
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
Stars and bars yöntemiyle çözüm sayısı
$$\binom{n+9}{9}$$
olur. Bu çözümlerden biri tamamı sıfır olan dizidir; o da pozitif bir sayıyı temsil etmez. Dolayısıyla \(10^n\)'in altındaki artan pozitif tam sayı sayısı
$$I(n)=\binom{n+9}{9}-1.$$
Azalan tarafta her uzunluğu ayrı ele alırız. \(k\in\{1,\dots,n\}\) sabit olsun. \(k\) basamaklı azalan bir sayı için \(d_1 \ge d_2 \ge \cdots \ge d_k\) ve \(d_1\neq 0\) şartları vardır. Yine dizi, 0'dan 9'a kadar her rakamın kaç kez kullanıldığı ile belirlenir. Bu çokluklar \(y_0,y_1,\dots,y_9\) ise
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
Rakamları büyükten küçüğe yazarak her seçimden tam bir zayıf azalan dizi elde ederiz. Böylece toplam \(\binom{k+9}{9}\) olasılık vardır. Yasak olan tek durum \(00\cdots 0\) dizisidir. Bu yüzden tam \(k\) basamaklı azalan pozitif tam sayı sayısı
$$D_k=\binom{k+9}{9}-1.$$
Bütün uzunluklar üzerinde toplayıp hockey-stick özdeşliğini kullanınca
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
Hem artan hem de azalan sayılan bir sayı, \(d_1 \le d_2 \le \cdots \le d_k\) ve aynı anda \(d_1 \ge d_2 \ge \cdots \ge d_k\) koşullarını sağlamalıdır. Bu da yan yana her iki rakamın eşit olması demektir; yani bütün rakamlar aynıdır. Dolayısıyla çift sayılanlar tam olarak \(1,2,\dots,9,11,22,\dots,99,\dots\) biçimindeki pozitif sayılardır.
Her uzunluk için bunlardan 9 tane vardır, dolayısıyla
$$R(n)=9n.$$
\(n=3\) için formüller
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27$$
verir. O hâlde
$$N(3)=219+282-27=474,$$
ve bu, üç basamağa kadar olan bilinen sayımla tam olarak uyuşur.
Üç parçayı birleştirince
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
elde edilir. Eşdeğer biçimi
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
olur. Problemin istediği \(n=100\) için
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
C++, Python ve Java uygulamaları hiçbir sayıyı tek tek dolaşmaz. Bunun yerine gereken binom katsayılarını doğrudan ve tam olarak hesaplar. Python sürümü standart kombinasyon fonksiyonunu kullanırken C++ ve Java sürümleri katsayıları çarpımsal olarak kurar; böylece her adımda yapılan bölme tam bölmedir.
İki binom katsayısı hazır olduktan sonra uygulama \(I(n)\), \(D(n)\) ve \(R(n)=9n\) terimlerini hesaplar ve \(I(n)+D(n)-R(n)\) sonucunu verir. Uygulamalardan biri basamak sınırını değiştirilebilir tutup \(n=6\) için sonucun \(12951\) olduğunu kontrol eder; diğer ikisi doğrudan \(n=100\) kullanır. Üç dilde de yapılan algoritma aynı kapalı form hesabıdır.
Bu problem için yapılan iş sabit boyutludur. Yalnızca iki binom katsayısı ve ardından birkaç toplama-çıkarma işlemi vardır. Çarpımsal sürümlerde bu katsayılar sırasıyla 9 ve 10 adımlık döngülerle üretildiği için çalışma süresi pratikte \(O(1)\)'dir.
Bellek kullanımı da saklanan birkaç tam sayı dışında \(O(1)\)'dir. Tek dikkat edilmesi gereken nokta sayı aralığıdır: işlemlerin tam yapılması gerekir. Bu nedenle Python keyfi duyarlıklı tamsayılar, Java büyük tamsayılar ve C++ sürümü de \(n=100\) için tüm ara değerleri taşıyabilecek kadar geniş bir tür kullanır.
Un entero positivo es creciente si sus cifras nunca disminuyen de izquierda a derecha, y es decreciente si sus cifras nunca aumentan. Un número es no-bouncy cuando pertenece al menos a una de esas dos familias. La tarea consiste en contar todos los enteros positivos no-bouncy menores que \(10^{100}\).
Enumerarlos uno por uno es imposible, pero las implementaciones muestran que el problema se reduce por completo a combinatoria elemental. El resultado sale de un conteo para los crecientes, otro para los decrecientes y una corrección por intersección.
Sea \(N(n)\) el número de enteros positivos no-bouncy menores que \(10^n\). Contaremos por separado las familias creciente y decreciente, y después aplicaremos inclusión-exclusión para restar los casos contados dos veces.
Los números menores que \(10^n\) tienen a lo sumo \(n\) cifras. Para los crecientes, rellenar con ceros a la izquierda conserva la monotonía: por ejemplo, \(134\) pasa a ser \(000134\), y la secuencia sigue siendo débilmente creciente. Para los decrecientes, ese truco falla: \(66420\) es decreciente, pero \(066420\) ya no lo es. Por eso la parte creciente se cuenta de una sola vez con longitud fija \(n\), mientras que la parte decreciente se cuenta por longitudes exactas.
Tras completar hasta exactamente \(n\) cifras, un número creciente corresponde a una cadena de dígitos débilmente creciente \(a_1 \le a_2 \le \cdots \le a_n\), con cada \(a_i \in \{0,1,\dots,9\}\), y no todas las cifras iguales a cero. Una cadena así queda determinada por cuántas veces aparece cada dígito. Si esas multiplicidades son \(x_0,x_1,\dots,x_9\), entonces
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
Por stars and bars, el número de soluciones es
$$\binom{n+9}{9}.$$
Una de ellas es la cadena formada solo por ceros, que no representa un entero positivo. Por tanto, la cantidad de enteros positivos crecientes menores que \(10^n\) es
$$I(n)=\binom{n+9}{9}-1.$$
Para los decrecientes conviene fijar la longitud. Sea \(k\in\{1,\dots,n\}\). Un número decreciente de \(k\) cifras cumple \(d_1 \ge d_2 \ge \cdots \ge d_k\), con \(d_1\neq 0\). De nuevo, la secuencia queda determinada por las multiplicidades de los dígitos \(0,1,\dots,9\). Si \(y_j\) indica cuántas veces aparece el dígito \(j\), entonces
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
Escribiendo las cifras en orden descendente se reconstruye exactamente una cadena débilmente decreciente, de modo que hay \(\binom{k+9}{9}\) posibilidades en total. El único caso prohibido es \(00\cdots 0\). Así, el número de enteros positivos decrecientes con exactamente \(k\) cifras es
$$D_k=\binom{k+9}{9}-1.$$
Sumando todas las longitudes y usando la identidad del palo de hockey obtenemos
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
Un número contado en ambas familias debe satisfacer \(d_1 \le d_2 \le \cdots \le d_k\) y también \(d_1 \ge d_2 \ge \cdots \ge d_k\). Por tanto, cada par de cifras vecinas es igual, y todas las cifras coinciden. Son exactamente los enteros positivos del tipo \(1,2,\dots,9,11,22,\dots,99,\dots\).
Para cada longitud \(k\) entre 1 y \(n\) hay 9 de ellos, así que
$$R(n)=9n.$$
Con \(n=3\), las fórmulas dan
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27.$$
Por lo tanto,
$$N(3)=219+282-27=474,$$
que coincide con el conteo conocido para todas las cantidades de hasta tres cifras.
Al combinar las tres partes, obtenemos
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
De manera equivalente,
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
Para el límite del problema, \(n=100\), esto se convierte en
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
Las implementaciones en C++, Python y Java no recorren ningún conjunto de números. Calculan directamente los coeficientes binomiales exactos que aparecen en la fórmula. La versión en Python usa la función combinatoria estándar del lenguaje, mientras que las versiones en C++ y Java construyen los coeficientes de forma multiplicativa para que cada división sea exacta.
Una vez disponibles los dos coeficientes binomiales, la implementación evalúa \(I(n)\), \(D(n)\) y \(R(n)=9n\), y luego devuelve \(I(n)+D(n)-R(n)\). Una de las implementaciones también permite variar el límite de cifras \(n\) y verifica el caso conocido \(n=6\), donde el resultado es \(12951\); las otras dos sustituyen \(n=100\) directamente. En los tres lenguajes se usa exactamente el mismo argumento matemático.
El trabajo es de tamaño constante para este problema. Solo se calculan dos coeficientes binomiales y después unas pocas sumas y restas. En las versiones multiplicativas, esos coeficientes requieren 9 y 10 iteraciones respectivamente, así que el tiempo de ejecución es efectivamente \(O(1)\).
El uso de memoria también es \(O(1)\) aparte de guardar unos pocos enteros exactos. El único detalle importante es el rango numérico: la aritmética tiene que ser exacta, por eso Python usa enteros de precisión arbitraria, Java usa enteros grandes y la solución en C++ emplea un tipo suficientemente amplio para todos los valores intermedios cuando \(n=100\).
如果一个正整数的数字从左到右从不下降，就称它为递增数；如果数字从左到右从不上升，就称它为递减数。只要属于这两类中的至少一类，它就是非弹跳数。题目要求统计所有小于 \(10^{100}\) 的非弹跳正整数。
这个规模根本不可能靠枚举完成，但实现代码表明，问题实际上可以完全化成组合计数。最终答案由三部分组成：递增数的个数、递减数的个数，以及两者交集的修正项。
记 \(N(n)\) 为所有小于 \(10^n\) 的非弹跳正整数个数。我们先分别计算递增家族和递减家族，再用容斥原理减去被重复计算的那一部分。
所有小于 \(10^n\) 的整数都至多有 \(n\) 位。对于递增数，可以在左侧补零而不破坏单调性：例如 \(134\) 补成 \(000134\) 之后，数字仍然是弱递增的。对于递减数，这个办法却不成立：\(66420\) 本来是递减的，但补成 \(066420\) 之后就不再递减了。因此，递增数适合一次性按固定长度 \(n\) 来统计，而递减数必须按确切位数分别统计。
把一个递增数补成恰好 \(n\) 位以后，它对应一个满足 \(a_1 \le a_2 \le \cdots \le a_n\) 的数字串，其中每个 \(a_i\) 都属于 \(\{0,1,\dots,9\}\)，并且不能所有位都等于 0。这样的数字串由 0 到 9 各个数字出现的次数完全决定。若这些出现次数分别是 \(x_0,x_1,\dots,x_9\)，那么它们满足
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
这是一个标准的 stars and bars 计数问题，因此解的个数为
$$\binom{n+9}{9}.$$
其中有一种解对应全零串，它不代表任何正整数。所以，小于 \(10^n\) 的递增正整数个数是
$$I(n)=\binom{n+9}{9}-1.$$
对递减数更自然的做法是固定长度。取 \(k\in\{1,\dots,n\}\)。一个 \(k\) 位递减数满足 \(d_1 \ge d_2 \ge \cdots \ge d_k\)，并且首位 \(d_1\neq 0\)。同样地，这个数字串也完全由 0 到 9 各个数字出现的次数决定。若 digit \(j\) 的出现次数是 \(y_j\)，则有
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
一旦这些重数确定，把数字按从大到小的顺序写出来，就得到唯一一个弱递减串。因此总共有 \(\binom{k+9}{9}\) 种可能。唯一非法的是全零串 \(00\cdots 0\)。所以，恰好 \(k\) 位的递减正整数个数为
$$D_k=\binom{k+9}{9}-1.$$
对 \(k=1\) 到 \(n\) 求和，并使用 hockey-stick 恒等式，就得到
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
如果一个数既被算作递增，又被算作递减，那么它必须同时满足 \(d_1 \le d_2 \le \cdots \le d_k\) 和 \(d_1 \ge d_2 \ge \cdots \ge d_k\)。 这迫使每一对相邻数字都相等，因此所有位都相同。也就是说，交集正好是 \(1,2,\dots,9,11,22,\dots,99,\dots\) 这类正整数。
对于每一个长度 \(k\)，这样的数恰好有 9 个，所以交集大小为
$$R(n)=9n.$$
取 \(n=3\)。根据上面的公式，
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27.$$
于是
$$N(3)=219+282-27=474.$$
这正好就是所有不超过三位的非弹跳数总数。这个例子也清楚地展示了三部分是如何拼在一起的。
把三部分合并，得到
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
整理后可写成
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
对题目中的 \(n=100\) 代入，得到
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
C++、Python 和 Java 三个实现都不会真的去遍历候选数字。它们直接计算公式里需要的二项式系数。Python 版本使用语言自带的组合函数；C++ 与 Java 版本则用乘法式的方式逐步构造系数，从而保证每一步除法都是精确的整数除法。
一旦两个二项式系数计算完成，实现就依次求出 \(I(n)\)、\(D(n)\) 和 \(R(n)=9n\)，最后返回 \(I(n)+D(n)-R(n)\)。其中一个实现还允许把位数上界 \(n\) 当作参数，并验证 \(n=6\) 时答案等于 \(12951\)；另外两个实现则直接把 \(n\) 固定为 100。三种语言在算法层面完全一致，都是这个闭式组合计数。
对这道题而言，计算量是常数级的。程序只需要求两个二项式系数，然后做少量加减法。在手工乘法构造系数的版本中，这两段循环长度分别固定为 9 和 10，所以运行时间可以视为 \(O(1)\)。
空间开销同样是 \(O(1)\)，除了保存少数几个精确整数之外没有额外结构。真正需要注意的是数值范围必须完全精确，因此 Python 使用任意精度整数，Java 使用大整数，而 C++ 解法使用对 \(n=100\) 的全部中间结果都足够宽的整数类型。
Положительное целое число называется возрастающим, если его цифры слева направо никогда не убывают, и убывающим, если его цифры слева направо никогда не возрастают. Число является непрыгающим, если оно принадлежит хотя бы одному из этих двух классов. Требуется посчитать все непрыгающие положительные числа, меньшие \(10^{100}\).
Прямой перебор здесь невозможен, но реализации показывают, что задача полностью сводится к комбинаторике. Нужно отдельно посчитать возрастающие числа, отдельно убывающие числа, а затем исправить двойной счет на пересечении.
Обозначим через \(N(n)\) количество непрыгающих положительных чисел, меньших \(10^n\). Сначала посчитаем возрастающее и убывающее семейства по отдельности, а затем применим принцип включения-исключения.
Все числа меньше \(10^n\) имеют не более \(n\) цифр. Для возрастающих чисел можно дополнять запись ведущими нулями, и монотонность не испортится: например, \(134\) превращается в \(000134\), и последовательность цифр остается неубывающей. Для убывающих чисел такой прием не работает: \(66420\) убывает, а \(066420\) уже нет. Поэтому возрастающую часть удобно считать сразу на фиксированной длине \(n\), а убывающую приходится считать по точной длине.
После дополнения до ровно \(n\) цифр возрастающее число превращается в неубывающую строку цифр \(a_1 \le a_2 \le \cdots \le a_n\), где каждый \(a_i\) принадлежит \(\{0,1,\dots,9\}\), и при этом не все цифры равны нулю. Такая строка полностью задается кратностями цифр 0, 1, ..., 9. Если эти кратности равны \(x_0,x_1,\dots,x_9\), то
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
По формуле stars and bars число решений равно
$$\binom{n+9}{9}.$$
Одно из решений соответствует строке из одних нулей, а она не представляет положительное число. Следовательно, количество возрастающих положительных чисел ниже \(10^n\) равно
$$I(n)=\binom{n+9}{9}-1.$$
Для убывающих чисел фиксируем длину. Пусть \(k\in\{1,\dots,n\}\). Убывающее \(k\)-значное число имеет цифры \(d_1 \ge d_2 \ge \cdots \ge d_k\), причем \(d_1\neq 0\). И здесь последовательность однозначно определяется кратностями цифр \(0,1,\dots,9\). Если \(y_j\) обозначает число вхождений цифры \(j\), то
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
Если выписать цифры в невозрастающем порядке, получится ровно одна слабоубывающая строка. Значит, всего существует \(\binom{k+9}{9}\) вариантов. Запрещен только случай \(00\cdots 0\). Поэтому число убывающих положительных чисел ровно из \(k\) цифр равно
$$D_k=\binom{k+9}{9}-1.$$
Суммируя по всем длинам и используя тождество хоккейной клюшки, получаем
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
Если число одновременно посчитано как возрастающее и как убывающее, то оно должно удовлетворять \(d_1 \le d_2 \le \cdots \le d_k\) и одновременно \(d_1 \ge d_2 \ge \cdots \ge d_k\). Значит, каждая соседняя пара цифр совпадает, а следовательно, все цифры одинаковы. Это именно числа вида \(1,2,\dots,9,11,22,\dots,99,\dots\).
Для каждой длины \(k\) от 1 до \(n\) таких чисел 9, поэтому
$$R(n)=9n.$$
При \(n=3\) формулы дают
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27.$$
Следовательно,
$$N(3)=219+282-27=474,$$
что точно совпадает с известным числом непрыгающих значений среди всех чисел с не более чем тремя цифрами.
Собирая три части вместе, получаем
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
То же самое можно записать в виде
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
Для условия задачи, то есть при \(n=100\), выходит
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
Реализации на C++, Python и Java не перебирают числа по одному. Они сразу вычисляют точные биномиальные коэффициенты, входящие в формулу. В Python используется стандартная библиотечная функция для сочетаний, а версии на C++ и Java строят коэффициенты мультипликативно так, чтобы каждое деление на каждом шаге оставалось точным.
После получения двух биномиальных коэффициентов программа вычисляет \(I(n)\), \(D(n)\) и \(R(n)=9n\), а затем возвращает \(I(n)+D(n)-R(n)\). Одна из реализаций также позволяет менять верхнюю границу по числу цифр и проверяет известный случай \(n=6\), где ответ равен \(12951\); две другие сразу подставляют \(n=100\). Во всех трех языках алгоритм одинаков: это прямое вычисление одной и той же замкнутой формулы.
Объем работы здесь постоянен. Нужно вычислить всего два биномиальных коэффициента и затем выполнить несколько сложений и вычитаний. В мультипликативных версиях циклы имеют фиксированную длину 9 и 10, поэтому время работы по сути равно \(O(1)\).
Память также имеет порядок \(O(1)\), не считая хранения нескольких точных целых чисел. Единственный важный технический момент связан с диапазоном значений: арифметика должна быть точной. Поэтому Python использует целые произвольной длины, Java использует большие целые, а решение на C++ берет тип, которого достаточно для всех промежуточных значений при \(n=100\).
يُسمّى العدد الصحيح الموجب تصاعديًا إذا كانت أرقامه من اليسار إلى اليمين لا تنخفض أبدًا، ويُسمّى تنازليًا إذا كانت أرقامه لا ترتفع أبدًا. ويكون العدد غير مرتد إذا انتمى إلى واحدة على الأقل من هاتين العائلتين. المطلوب هو عد جميع الأعداد الصحيحة الموجبة غير المرتدة الأصغر من \(10^{100}\).
العد المباشر مستحيل عند هذا الحد، لكن الحلول البرمجية تُظهر أن المسألة تختزل بالكامل إلى عد تركيبي. النتيجة النهائية تأتي من حد لعد الأعداد التصاعدية، وحد لعد الأعداد التنازلية، ثم تصحيح للتقاطع بينهما.
لنرمز بـ \(N(n)\) إلى عدد الأعداد الصحيحة الموجبة غير المرتدة الأصغر من \(10^n\). سنعد أولًا العائلتين التصاعدية والتنازلية كلًّا على حدة، ثم نستخدم مبدأ الشمول والإقصاء لطرح الأعداد التي عُدّت مرتين.
كل عدد أصغر من \(10^n\) يملك في أقصى الأحوال \(n\) أرقام. في الأعداد التصاعدية يمكن إضافة أصفار في البداية من غير أن تفسد الرتابة: فالعدد \(134\) يصبح \(000134\)، وتبقى السلسلة ضعيفة التصاعد. أما في الأعداد التنازلية فهذه الفكرة لا تعمل: العدد \(66420\) تنازلي فعلًا، لكن \(066420\) لم يعد كذلك. لهذا السبب نعد الطرف التصاعدي دفعة واحدة بطول ثابت \(n\)، بينما نعد الطرف التنازلي حسب الطول الدقيق لكل عدد.
بعد إكمال العدد التصاعدي إلى طول يساوي تمامًا \(n\)، نحصل على سلسلة أرقام تحقق \(a_1 \le a_2 \le \cdots \le a_n\)، حيث كل \(a_i\) ينتمي إلى \(\{0,1,\dots,9\}\)، وليس مسموحًا أن تكون جميع الأرقام صفرًا. وهذه السلسلة تتحدد كليًا بعدد مرات ظهور كل رقم من 0 إلى 9. إذا كانت هذه التكرارات هي \(x_0,x_1,\dots,x_9\)، فلدينا
$$x_0+x_1+\cdots+x_9=n,\qquad x_i\ge 0.$$
وبحسب طريقة stars and bars فإن عدد الحلول هو
$$\binom{n+9}{9}.$$
لكن أحد هذه الحلول يمثل السلسلة الصفرية الخالصة، وهي لا تمثل عددًا موجبًا. لذلك يكون عدد الأعداد الصحيحة الموجبة التصاعدية الأصغر من \(10^n\) هو
$$I(n)=\binom{n+9}{9}-1.$$
في الجهة التنازلية يكون الأسهل هو تثبيت الطول. خذ \(k\in\{1,\dots,n\}\). العدد التنازلي ذو \(k\) أرقام يحقق \(d_1 \ge d_2 \ge \cdots \ge d_k\)، مع الشرط \(d_1\neq 0\). وكما في الحالة السابقة، تتحدد السلسلة نهائيًا بعدد مرات ظهور الأرقام \(0,1,\dots,9\). إذا رمزنا إلى هذه الأعداد بـ \(y_0,y_1,\dots,y_9\)، فإن
$$y_0+y_1+\cdots+y_9=k,\qquad y_j\ge 0.$$
وبمجرد معرفة هذه التكرارات، فإن كتابة الأرقام من الأكبر إلى الأصغر تعطي سلسلة تنازلية ضعيفة وحيدة. إذن يوجد في المجموع \(\binom{k+9}{9}\) احتمالًا. الحالة الوحيدة الممنوعة هي السلسلة \(00\cdots 0\). ومن ثم فإن عدد الأعداد الصحيحة الموجبة التنازلية ذات الطول \(k\) بالضبط هو
$$D_k=\binom{k+9}{9}-1.$$
وبالجمع على جميع الأطوال واستخدام هوية عصا الهوكي نحصل على
$$D(n)=\sum_{k=1}^{n}\left(\binom{k+9}{9}-1\right)=\left(\sum_{k=1}^{n}\binom{k+9}{9}\right)-n=\binom{n+10}{10}-(n+1).$$
إذا كان العدد محسوبًا ضمن العائلتين معًا، فلا بد أن يحقق في آن واحد \(d_1 \le d_2 \le \cdots \le d_k\) و \(d_1 \ge d_2 \ge \cdots \ge d_k\). وهذا يجبر كل رقمين متجاورين على التساوي، أي إن جميع الأرقام متماثلة. وهكذا فإن التقاطع هو بالضبط الأعداد الموجبة من الشكل \(1,2,\dots,9,11,22,\dots,99,\dots\).
لكل طول من 1 إلى \(n\) توجد 9 أعداد من هذا النوع، ولذلك
$$R(n)=9n.$$
عندما \(n=3\)، تعطينا الصيغ
$$I(3)=\binom{12}{9}-1=219,$$
$$D(3)=\binom{13}{10}-4=282,$$
$$R(3)=27.$$
وبالتالي
$$N(3)=219+282-27=474.$$
وهذا يطابق تمامًا العدد المعروف لجميع القيم غير المرتدة ذات الثلاث خانات أو أقل.
بجمع الأجزاء الثلاثة نحصل على
$$N(n)=I(n)+D(n)-R(n)=\left(\binom{n+9}{9}-1\right)+\left(\binom{n+10}{10}-(n+1)\right)-9n.$$
وبشكل مكافئ يمكن كتابتها على الصورة
$$\boxed{N(n)=\binom{n+9}{9}+\binom{n+10}{10}-10n-2.}$$
وعند التعويض بالقيمة المطلوبة في المسألة، أي \(n=100\)، نحصل على
$$N(100)=\binom{109}{9}+\binom{110}{10}-1002=51161058134250.$$
تنفيذات C++ وPython وJava لا تولد الأعداد واحدًا واحدًا. بدلًا من ذلك تحسب مباشرة المعاملات الثنائية الداخلة في الصيغة. إصدار Python يستخدم الدالة المعيارية الخاصة بالتوافيق، بينما يبني إصدارا C++ وJava هذه المعاملات بطريقة ضرب متتابع بحيث يكون كل قسمة أثناء الطريق قسمة صحيحة تمامًا.
بعد الحصول على المعاملين الثنائيين، تحسب الشيفرة القيم \(I(n)\) و\(D(n)\) و\(R(n)=9n\)، ثم تعيد \(I(n)+D(n)-R(n)\). أحد التنفيذات يسمح أيضًا بتغيير حد عدد الأرقام \(n\) ويتحقق من الحالة المعروفة \(n=6\) حيث تكون النتيجة \(12951\)، بينما يضع التنفيذان الآخران \(n=100\) مباشرة. في جميع اللغات الثلاث تبقى الخوارزمية نفسها: تطبيق مباشر لهذه الصيغة المغلقة.
العمل هنا ذو حجم ثابت. فهناك معاملان ثنائيان فقط، ثم عدد صغير من عمليات الجمع والطرح. وفي النسخ التي تبني المعاملات ضربيًا، يكون طول الحلقتين 9 و10 على الترتيب، لذا يمكن اعتبار الزمن \(O(1)\) عمليًا.
أما الذاكرة فهي أيضًا \(O(1)\) إذا استثنينا تخزين بضعة أعداد صحيحة دقيقة. والنقطة التقنية الوحيدة المهمة هي وجوب المحافظة على الدقة التامة، ولذلك يستخدم Python أعدادًا صحيحة غير محدودة الحجم، ويستخدم Java أعدادًا كبيرة، بينما يستخدم حل C++ نوعًا عدديًا يتسع لكل القيم الوسيطة عندما \(n=100\).