A positive integer is called balanced when two subsequence lengths in its decimal digit word are equal: the length of the longest strictly decreasing subsequence and the length of the longest non-strictly increasing subsequence.
For example, \(77429\) is balanced because \(742\) is a strictly decreasing subsequence of length \(3\), while \(779\) is a non-strictly increasing subsequence of length \(3\). The problem gives the checkpoint that there are \(2274\) balanced positive integers below \(10^4\), and asks for the total number of balanced positive integers modulo \(10^9+7\).
The word "total" is not a typo. There are infinitely many positive integers, but only finitely many balanced ones. The solution has to explain that finiteness and then count all of them without iterating through integers.
Write the decimal expansion of a positive integer as a word \(w\) over the ordered alphabet \(\{0,1,\dots,9\}\), with no leading zero. Let
$$I(w)=\text{length of the longest non-strictly increasing subsequence},$$
and
$$D(w)=\text{length of the longest strictly decreasing subsequence}.$$
The integer is balanced exactly when \(I(w)=D(w)\). Direct dynamic programming over all words is not viable because the length is not fixed in the statement. The key is to replace each word by the Young diagram that records these two extremal subsequence lengths at once.
The Robinson-Schensted-Knuth correspondence maps every word \(w\) over a totally ordered alphabet to a partition \(\lambda\), also called the insertion shape. For the version used for words, the first row of \(\lambda\) records the longest weakly increasing subsequence, and the first column records the longest strictly decreasing subsequence:
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
If \(\ell(\lambda)\) denotes the number of rows of the partition, then \(\lambda'_1=\ell(\lambda)\). Therefore a word is balanced exactly when
$$\lambda_1=\ell(\lambda).$$
So the task becomes a sum over Young diagram shapes whose width equals their height. This is why the C++ code never explicitly computes subsequences for long words; it counts all words having each possible RSK shape.
The digit alphabet has only \(10\) symbols. A strictly decreasing subsequence can contain each digit at most once, so \(D(w)\le 10\). If \(w\) is balanced, then \(I(w)=D(w)\le 10\) as well.
Under RSK, this means both the width and the height of \(\lambda\) are at most \(10\). Hence \(\lambda\) fits inside a \(10\times10\) square, and the word length \(|w|=|\lambda|\) is at most \(100\). Every balanced positive integer therefore has at most \(100\) decimal digits. The problem is finite, and the code sets MAX_CELLS to \(10\cdot10=100\).
For a fixed shape \(\lambda\) with \(n=|\lambda|\) cells, RSK gives a pair \((P,Q)\). Here \(Q\) is a standard Young tableau of shape \(\lambda\), while \(P\) is a semistandard Young tableau of the same shape using the \(10\) digit symbols.
The number of standard Young tableaux is given by the hook-length formula:
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
The number of semistandard tableaux over an alphabet of size \(10\) is the hook-content formula:
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
where rows and columns are indexed from \(1\). Thus the number of digit words with RSK shape \(\lambda\) is
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
This is exactly what shape_word_count evaluates modulo \(10^9+7\): it multiplies all hook lengths, multiplies all contents \(10+j-i\), and uses modular inverses for the two hook products.
A partition is stored as non-increasing row lengths \(\lambda_1\ge\lambda_2\ge\cdots\). The recursive enumeration chooses the next row length no larger than the previous one, stops after \(10\) rows, and rejects any shape with more than \(100\) cells.
For every generated shape the code records two sums. If width equals height, it contributes to the count of balanced digit words. If height equals width plus one, it contributes to a separate correction term used for leading zeros:
$$\lambda_1=\ell(\lambda)\quad\text{or}\quad \ell(\lambda)=\lambda_1+1.$$
Only these two categories are needed by the final positive-integer count.
The hook-content count includes all digit words over \(\{0,\dots,9\}\), including words that start with \(0\). A positive integer, however, has a unique decimal representation with no leading zero.
Let \(B(k)\) be the number of balanced digit words of length at most \(k\), counted with leading zeros allowed. Consider a word \(0v\). Because the leading \(0\) is the smallest possible digit, it can be placed before any non-strictly increasing subsequence of \(v\), so
$$I(0v)=I(v)+1.$$
It cannot extend a strictly decreasing subsequence, since no later digit is smaller than \(0\), so
$$D(0v)=D(v).$$
Therefore \(0v\) is balanced exactly when \(D(v)=I(v)+1\), which is the shape condition \(\ell(\lambda)=\lambda_1+1\). The invalid balanced words with a leading zero and total length at most \(k\) are counted by that "decreasing excess" category among tails of length at most \(k-1\).
The one-digit word \(0\) also has to be removed because it represents zero, not a positive integer. Consequently the final count for at most \(k\) digits is
$$T(k)=B(k)-E(k-1)-1,$$
where \(E(k-1)\) is the sum over shapes with height exactly one more than width and at most \(k-1\) cells. The checkpoint \(T(4)=2274\) matches the value given in the problem statement.
factorial precomputes \(n!\) modulo \(10^9+7\) up to \(100\). mod_pow and mod_inverse provide modular division, using Fermat's little theorem because the modulus is prime.
shape_word_count loops over every cell of a partition. For each cell it computes the hook length \(h(i,j)\), the content factor \(10+j-i\), and then combines the hook-length and hook-content formulas into \(N(\lambda)\).
enumerate_partitions recursively lists all partitions fitting inside the \(10\times10\) box. It adds the shape count to balanced when width equals height, and to decreasing_excess when height is one larger than width.
positive_balanced_count(k) first counts all balanced words of length at most \(k\). It then subtracts the leading-zero correction computed from tails of length at most \(k-1\), and subtracts the single word \(0\). The program checks \(k=4\), then evaluates \(k=100\).
The algorithm enumerates partitions inside a \(10\times10\) box, not integers. This is a tiny finite set compared with \(10^{100}\) possible digit strings. For each shape, at most \(100\) cells are processed.
In asymptotic terms for an alphabet of size \(a\), the method enumerates partitions inside an \(a\times a\) square and processes \(O(a^2)\) cells per shape. In this problem \(a=10\), so the running time and memory usage are effectively constant.
Eine positive ganze Zahl heißt balanced, wenn in ihrem Dezimalwort zwei Laengen gleich sind: die Laenge der laengsten streng fallenden Teilfolge und die Laenge der laengsten nicht-streng steigenden Teilfolge.
Zum Beispiel ist \(77429\) balanced, weil \(742\) eine streng fallende Teilfolge der Laenge \(3\) ist, waehrend \(779\) eine nicht-streng steigende Teilfolge der Laenge \(3\) ist. Als Kontrollwert gibt die Aufgabe \(2274\) balanced positive Zahlen unter \(10^4\) an. Gesucht ist die Gesamtzahl aller balanced positiven Zahlen modulo \(10^9+7\).
Das Wort "gesamt" ist hier wesentlich. Es gibt unendlich viele positive ganze Zahlen, aber nur endlich viele balanced Zahlen. Die Loesung muss diese Endlichkeit begruenden und danach alle Faelle zaehlen, ohne Zahlen einzeln zu durchlaufen.
Schreibe die Dezimaldarstellung einer positiven Zahl als Wort \(w\) ueber dem geordneten Alphabet \(\{0,1,\dots,9\}\), ohne fuehrende Null. Definiere
$$I(w)=\text{Laenge der laengsten nicht-streng steigenden Teilfolge},$$
und
$$D(w)=\text{Laenge der laengsten streng fallenden Teilfolge}.$$
Die Zahl ist genau dann balanced, wenn \(I(w)=D(w)\). Eine direkte dynamische Programmierung ueber alle Woerter ist nicht sinnvoll, weil die Wortlaenge in der Aufgabe nicht fest vorgegeben ist. Der zentrale Schritt ist, jedes Wort durch ein Young-Diagramm zu ersetzen, das beide Extremallaengen gleichzeitig speichert.
Die Robinson-Schensted-Knuth-Korrespondenz ordnet jedem Wort \(w\) ueber einem total geordneten Alphabet eine Partition \(\lambda\) zu, die Einfuegeform genannt wird. In der Wort-Version misst die erste Zeile von \(\lambda\) die laengste schwach steigende Teilfolge, und die erste Spalte misst die laengste streng fallende Teilfolge:
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
Bezeichnet \(\ell(\lambda)\) die Anzahl der Zeilen, dann ist \(\lambda'_1=\ell(\lambda)\). Ein Wort ist also genau dann balanced, wenn
$$\lambda_1=\ell(\lambda).$$
Die Aufgabe wird damit zu einer Summe ueber Young-Diagramme, deren Breite gleich ihrer Hoehe ist. Deshalb berechnet der C++-Code fuer lange Woerter keine Teilfolgenlaengen explizit; er zaehlt alle Woerter mit einer gegebenen RSK-Form.
Das Ziffernalphabet besitzt nur \(10\) Symbole. Eine streng fallende Teilfolge kann jede Ziffer hoechstens einmal enthalten, also gilt \(D(w)\le 10\). Ist \(w\) balanced, dann gilt auch \(I(w)=D(w)\le 10\).
In der RSK-Form bedeutet das, dass sowohl Breite als auch Hoehe von \(\lambda\) hoechstens \(10\) sind. Die Form liegt also in einem \(10\times10\)-Quadrat, und die Wortlaenge \(|w|=|\lambda|\) ist hoechstens \(100\). Jede balanced positive Zahl hat daher hoechstens \(100\) Dezimalziffern. Der Code setzt MAX_CELLS folglich auf \(10\cdot10=100\).
Fuer eine feste Form \(\lambda\) mit \(n=|\lambda|\) Zellen liefert RSK ein Paar \((P,Q)\). Dabei ist \(Q\) ein Standard-Young-Tableau der Form \(\lambda\), und \(P\) ist ein semistandard Young-Tableau derselben Form mit den \(10\) Ziffernsymbolen.
Die Anzahl der Standard-Young-Tableaux ergibt sich aus der Hakenlaengenformel:
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
Die Anzahl der semistandard Tableaux ueber einem Alphabet der Groesse \(10\) ergibt sich aus der Haken-Inhalts-Formel:
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
wobei Zeilen und Spalten ab \(1\) nummeriert werden. Die Anzahl der Ziffernwoerter mit RSK-Form \(\lambda\) ist daher
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
Genau diese Groesse berechnet shape_word_count modulo \(10^9+7\): Es multipliziert alle Hakenlaengen, alle Inhaltsfaktoren \(10+j-i\), und benutzt modulare Inverse fuer die zwei Hakenprodukte.
Eine Partition wird als nicht-steigende Zeilenlaengen \(\lambda_1\ge\lambda_2\ge\cdots\) gespeichert. Die Rekursion waehlt die naechste Zeilenlaenge nie groesser als die vorige, stoppt nach \(10\) Zeilen und verwirft Formen mit mehr als \(100\) Zellen.
Fuer jede erzeugte Form werden zwei Summen gepflegt. Ist Breite gleich Hoehe, dann traegt die Form zur Zahl der balanced Ziffernwoerter bei. Ist die Hoehe um eins groesser als die Breite, dann traegt sie zu einem Korrekturterm fuer fuehrende Nullen bei:
$$\lambda_1=\ell(\lambda)\quad\text{oder}\quad \ell(\lambda)=\lambda_1+1.$$
Nur diese beiden Kategorien werden fuer den endgueltigen Zaehler positiver ganzer Zahlen benoetigt.
Die Haken-Inhalts-Zaehlung umfasst alle Ziffernwoerter ueber \(\{0,\dots,9\}\), also auch Woerter, die mit \(0\) beginnen. Eine positive ganze Zahl besitzt aber eine eindeutige Dezimaldarstellung ohne fuehrende Null.
Sei \(B(k)\) die Anzahl balanced Ziffernwoerter der Laenge hoechstens \(k\), wenn fuehrende Nullen erlaubt sind. Betrachte ein Wort \(0v\). Da die fuehrende \(0\) die kleinste moegliche Ziffer ist, kann sie vor jede nicht-streng steigende Teilfolge von \(v\) gesetzt werden, also
$$I(0v)=I(v)+1.$$
Eine streng fallende Teilfolge kann sie nicht verlaengern, weil spaeter keine kleinere Ziffer auftreten kann. Daher gilt
$$D(0v)=D(v).$$
Folglich ist \(0v\) genau dann balanced, wenn \(D(v)=I(v)+1\), also wenn die RSK-Form von \(v\) die Bedingung \(\ell(\lambda)=\lambda_1+1\) erfuellt. Die ungueltigen balanced Woerter mit fuehrender Null und Gesamtlaenge hoechstens \(k\) werden deshalb durch diese Kategorie unter den Endstuecken der Laenge hoechstens \(k-1\) gezaehlt.
Das einstellige Wort \(0\) muss ebenfalls entfernt werden, weil es die Zahl null und keine positive Zahl darstellt. Somit lautet die Endformel fuer hoechstens \(k\) Ziffern
$$T(k)=B(k)-E(k-1)-1,$$
wobei \(E(k-1)\) ueber Formen mit Hoehe genau eins groesser als Breite und hoechstens \(k-1\) Zellen summiert. Der Kontrollwert \(T(4)=2274\) stimmt mit der Aufgabenangabe ueberein.
factorial berechnet \(n!\) modulo \(10^9+7\) bis \(100\) vor. mod_pow und mod_inverse liefern modulare Division, mit dem kleinen Satz von Fermat, da der Modul prim ist.
shape_word_count laeuft ueber jede Zelle einer Partition. Fuer jede Zelle berechnet es die Hakenlaenge \(h(i,j)\), den Inhaltsfaktor \(10+j-i\), und verbindet dann Hakenlaengen- und Haken-Inhalts-Formel zu \(N(\lambda)\).
enumerate_partitions listet rekursiv alle Partitionen im \(10\times10\)-Quadrat auf. Die Formzaehlung wird zu balanced addiert, wenn Breite gleich Hoehe ist, und zu decreasing_excess, wenn die Hoehe um eins groesser ist.
positive_balanced_count(k) zaehlt zuerst alle balanced Woerter der Laenge hoechstens \(k\). Danach subtrahiert es die Fuehrende-Null-Korrektur aus Endstuecken der Laenge hoechstens \(k-1\), sowie das einzelne Wort \(0\). Das Programm prueft \(k=4\) und berechnet anschliessend \(k=100\).
Der Algorithmus enumeriert Partitionen in einem \(10\times10\)-Quadrat, nicht ganze Zahlen. Diese endliche Menge ist winzig im Vergleich zu den \(10^{100}\) moeglichen Ziffernwoertern. Pro Form werden hoechstens \(100\) Zellen verarbeitet.
Asymptotisch fuer ein Alphabet der Groesse \(a\) enumeriert die Methode Partitionen in einem \(a\times a\)-Quadrat und verarbeitet \(O(a^2)\) Zellen pro Form. Hier ist \(a=10\), also sind Laufzeit und Speicherbedarf praktisch konstant.
Bir pozitif tamsayı, ondalık basamak dizisindeki iki alt dizi uzunluğu eşitse balanced olarak adlandırılır: en uzun strictly decreasing alt dizi uzunluğu ve en uzun non-strictly increasing alt dizi uzunluğu.
Örneğin \(77429\) balanced'tır; çünkü \(742\) uzunluğu \(3\) olan strictly decreasing bir alt dizidir, \(779\) ise uzunluğu \(3\) olan non-strictly increasing bir alt dizidir. Problem, \(10^4\)'ten küçük \(2274\) balanced tamsayı olduğunu kontrol değeri olarak verir ve tüm balanced pozitif tamsayıların sayısını \(10^9+7\) modunda ister.
Buradaki "tüm" ifadesi önemlidir. Pozitif tamsayılar sonsuzdur, ama balanced olanlar sonludur. Çözüm önce bu sonluluğu açıklamalı, sonra da sayıları tek tek gezmeden tümünü saymalıdır.
Bir pozitif tamsayının ondalık gösterimini, başında sıfır olmayan ve \(\{0,1,\dots,9\}\) sıralı alfabesi üzerinde yazılmış bir kelime \(w\) olarak düşünelim. Şunları tanımlayalım:
$$I(w)=\text{en uzun non-strictly increasing alt dizi uzunluğu},$$
ve
$$D(w)=\text{en uzun strictly decreasing alt dizi uzunluğu}.$$
Tamsayı tam olarak \(I(w)=D(w)\) olduğunda balanced'tır. Tüm kelimeler üzerinde doğrudan dinamik programlama yapmak uygun değildir, çünkü problemde uzunluk sabit değildir. Ana fikir, her kelimeyi bu iki uç alt dizi uzunluğunu aynı anda kaydeden bir Young diyagramına çevirmektir.
Robinson-Schensted-Knuth karşılığı, tam sıralı bir alfabe üzerindeki her kelime \(w\)'ye bir partition, yani bir yerleştirme şekli \(\lambda\), atar. Kelime sürümünde \(\lambda\)'nın ilk satırı en uzun zayıf artan alt diziyi, ilk sütunu ise en uzun sıkı azalan alt diziyi verir:
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
\(\ell(\lambda)\), partition'ın satır sayısı olsun. O zaman \(\lambda'_1=\ell(\lambda)\). Dolayısıyla bir kelime tam olarak
$$\lambda_1=\ell(\lambda)$$
olduğunda balanced'tır. Böylece problem, genişliği yüksekliğine eşit Young diyagramları üzerinde bir toplama problemine dönüşür. C++ kodunun uzun kelimeler için alt dizi uzunluğu hesaplamamasının nedeni budur; kod, her olası RSK şekline sahip kelimeleri doğrudan sayar.
Basamak alfabesinde yalnızca \(10\) sembol vardır. Strictly decreasing bir alt dizi her basamağı en fazla bir kez içerebilir; bu yüzden \(D(w)\le 10\). Eğer \(w\) balanced ise \(I(w)=D(w)\le 10\) olur.
RSK açısından bu, \(\lambda\)'nın hem genişliğinin hem yüksekliğinin en fazla \(10\) olması demektir. Yani \(\lambda\), \(10\times10\) kare içine sığar ve kelime uzunluğu \(|w|=|\lambda|\) en fazla \(100\)'dür. Her balanced pozitif tamsayının en fazla \(100\) ondalık basamağı vardır. Bu yüzden kod MAX_CELLS değerini \(10\cdot10=100\) olarak kullanır.
Sabit bir \(\lambda\) şekli için hücre sayısı \(n=|\lambda|\) olsun. RSK, kelimeyi bir \((P,Q)\) çiftine dönüştürür. Burada \(Q\), \(\lambda\) şeklinde bir standard Young tableau; \(P\) ise aynı şekilde ve \(10\) basamak sembolünü kullanan bir semistandard Young tableau'dur.
Standard Young tableau sayısı hook-length formülüyle verilir:
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
Alfabe boyutu \(10\) olan semistandard tableau sayısı hook-content formülüyle verilir:
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
burada satır ve sütun indeksleri \(1\)'den başlar. Bu nedenle RSK şekli \(\lambda\) olan basamak kelimelerinin sayısı
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
shape_word_count tam olarak bunu \(10^9+7\) modunda hesaplar: tüm hook uzunluklarını, tüm içerik çarpanlarını \(10+j-i\) çarpar ve iki hook çarpımı için modüler ters kullanır.
Bir partition, artmayan satır uzunlukları \(\lambda_1\ge\lambda_2\ge\cdots\) olarak tutulur. Rekürsif üretim, yeni satır uzunluğunu önceki satırdan büyük seçmez, \(10\) satırdan sonra durur ve \(100\)'den fazla hücreli şekilleri atlar.
Üretilen her şekil için iki toplam tutulur. Genişlik yüksekliğe eşitse şekil balanced basamak kelimelerine katkı verir. Yükseklik genişlikten tam bir fazlaysa, bu şekil baştaki sıfırlar için kullanılacak düzeltme toplamına katkı verir:
$$\lambda_1=\ell(\lambda)\quad\text{veya}\quad \ell(\lambda)=\lambda_1+1.$$
Finalde pozitif tamsayıları saymak için yalnızca bu iki kategori gerekir.
Hook-content sayımı, \(\{0,\dots,9\}\) üzerindeki tüm basamak kelimelerini kapsar; yani \(0\) ile başlayan kelimeleri de sayar. Oysa pozitif bir tamsayının başında sıfır olmayan tek bir ondalık gösterimi vardır.
\(B(k)\), uzunluğu en fazla \(k\) olan ve başta sıfıra izin verilen balanced basamak kelimelerinin sayısı olsun. Bir \(0v\) kelimesine bakalım. Baştaki \(0\), mümkün olan en küçük basamak olduğu için \(v\)'nin her non-strictly increasing alt dizisinin önüne eklenebilir; dolayısıyla
$$I(0v)=I(v)+1.$$
Strictly decreasing bir alt diziyi ise uzatamaz; çünkü daha sonra \(0\)'dan küçük bir basamak gelemez. Bu yüzden
$$D(0v)=D(v).$$
O halde \(0v\) balanced olur ancak ve ancak \(D(v)=I(v)+1\). Bu da RSK şekli için \(\ell(\lambda)=\lambda_1+1\) koşuludur. Toplam uzunluğu en fazla \(k\) olan ve başında sıfır bulunan geçersiz balanced kelimeler, uzunluğu en fazla \(k-1\) olan kuyruklarda bu "decreasing excess" kategorisiyle sayılır.
Tek basamaklı \(0\) kelimesi de çıkarılmalıdır; çünkü o pozitif bir tamsayıyı değil sıfırı temsil eder. Böylece en fazla \(k\) basamak için final formül
$$T(k)=B(k)-E(k-1)-1$$
olur. Burada \(E(k-1)\), yüksekliği genişliğinden tam bir fazla olan ve en fazla \(k-1\) hücre içeren şekillerin toplamıdır. Kontrol değeri \(T(4)=2274\), problemde verilen değerle aynıdır.
factorial, \(100\)'e kadar \(n!\) değerlerini \(10^9+7\) modunda hazırlar. mod_pow ve mod_inverse, mod asal olduğu için Fermat'nın küçük teoremiyle modüler bölmeyi sağlar.
shape_word_count, bir partition'ın her hücresini dolaşır. Her hücre için hook uzunluğu \(h(i,j)\), içerik çarpanı \(10+j-i\) hesaplanır ve hook-length ile hook-content formülleri birleştirilerek \(N(\lambda)\) elde edilir.
enumerate_partitions, \(10\times10\) kutusuna sığan tüm partition'ları rekürsif olarak listeler. Genişlik yüksekliğe eşitse şekil sayısı balanced toplamına, yükseklik bir fazlaysa decreasing_excess toplamına eklenir.
positive_balanced_count(k), önce uzunluğu en fazla \(k\) olan tüm balanced kelimeleri sayar. Sonra uzunluğu en fazla \(k-1\) olan kuyruklardan gelen baştaki sıfır düzeltmesini ve tek başına \(0\) kelimesini çıkarır. Program \(k=4\) kontrolünü yaptıktan sonra \(k=100\) için sonucu hesaplar.
Algoritma tamsayıları değil, \(10\times10\) kutusu içindeki partition'ları üretir. Bu sonlu küme, \(10^{100}\) olası basamak kelimesine göre çok küçüktür. Her şekil için en fazla \(100\) hücre işlenir.
Alfabe boyutu \(a\) olsaydı, yöntem \(a\times a\) kare içindeki partition'ları üretir ve şekil başına \(O(a^2)\) hücre işlerdi. Bu problemde \(a=10\), bu yüzden çalışma zamanı ve bellek kullanımı pratikte sabittir.
Un entero positivo se llama balanced cuando dos longitudes de subsecuencias en su palabra decimal son iguales: la longitud de la subsecuencia estrictamente decreciente más larga y la longitud de la subsecuencia no estrictamente creciente más larga.
Por ejemplo, \(77429\) es balanced porque \(742\) es una subsecuencia estrictamente decreciente de longitud \(3\), mientras que \(779\) es una subsecuencia no estrictamente creciente de longitud \(3\). El enunciado da como control que hay \(2274\) enteros balanced positivos por debajo de \(10^4\), y pide el número total de enteros balanced positivos módulo \(10^9+7\).
La palabra "total" es importante. Hay infinitos enteros positivos, pero solo finitamente muchos son balanced. La solución debe explicar esa finitud y después contarlos todos sin recorrer enteros uno por uno.
Escribimos la expansión decimal de un entero positivo como una palabra \(w\) sobre el alfabeto ordenado \(\{0,1,\dots,9\}\), sin cero inicial. Definimos
$$I(w)=\text{longitud de la subsecuencia no estrictamente creciente más larga},$$
y
$$D(w)=\text{longitud de la subsecuencia estrictamente decreciente más larga}.$$
El entero es balanced exactamente cuando \(I(w)=D(w)\). Una programación dinámica directa sobre todas las palabras no es viable, porque la longitud no está fijada. La idea central es reemplazar cada palabra por el diagrama de Young que almacena simultáneamente esas dos longitudes extremas.
La correspondencia Robinson-Schensted-Knuth asigna a cada palabra \(w\) sobre un alfabeto totalmente ordenado una partición \(\lambda\), llamada forma de inserción. En la versión para palabras, la primera fila de \(\lambda\) registra la subsecuencia débilmente creciente más larga, y la primera columna registra la subsecuencia estrictamente decreciente más larga:
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
Si \(\ell(\lambda)\) es el número de filas de la partición, entonces \(\lambda'_1=\ell(\lambda)\). Por tanto una palabra es balanced exactamente cuando
$$\lambda_1=\ell(\lambda).$$
La tarea se convierte en una suma sobre diagramas de Young cuya anchura coincide con su altura. Por eso el código C++ no calcula subsecuencias explícitamente para palabras largas; cuenta directamente cuántas palabras tienen cada forma RSK posible.
El alfabeto de dígitos tiene solo \(10\) símbolos. Una subsecuencia estrictamente decreciente puede usar cada dígito a lo sumo una vez, así que \(D(w)\le 10\). Si \(w\) es balanced, entonces \(I(w)=D(w)\le 10\).
En términos de RSK, tanto la anchura como la altura de \(\lambda\) son a lo sumo \(10\). Así \(\lambda\) cabe en un cuadrado \(10\times10\), y la longitud \(|w|=|\lambda|\) es a lo sumo \(100\). Todo entero balanced positivo tiene, por tanto, como máximo \(100\) dígitos decimales. El código fija MAX_CELLS en \(10\cdot10=100\).
Para una forma fija \(\lambda\) con \(n=|\lambda|\) celdas, RSK produce un par \((P,Q)\). Aquí \(Q\) es un tableau de Young estándar de forma \(\lambda\), y \(P\) es un tableau semiestándar de la misma forma usando los \(10\) símbolos de dígitos.
El número de tableaux estándar viene dado por la fórmula de longitudes de gancho:
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
El número de tableaux semiestándar sobre un alfabeto de tamaño \(10\) viene dado por la fórmula hook-content:
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
donde filas y columnas se indexan desde \(1\). Por tanto el número de palabras de dígitos con forma RSK \(\lambda\) es
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
Eso es exactamente lo que evalúa shape_word_count módulo \(10^9+7\): multiplica las longitudes de gancho, los factores de contenido \(10+j-i\), y usa inversos modulares para los dos productos de ganchos.
Una partición se guarda como longitudes de filas no crecientes \(\lambda_1\ge\lambda_2\ge\cdots\). La recursión elige cada fila siguiente no mayor que la anterior, se detiene tras \(10\) filas y descarta formas con más de \(100\) celdas.
Para cada forma generada se mantienen dos sumas. Si la anchura coincide con la altura, contribuye al número de palabras balanced. Si la altura es exactamente una unidad mayor que la anchura, contribuye al término de corrección para ceros iniciales:
$$\lambda_1=\ell(\lambda)\quad\text{o}\quad \ell(\lambda)=\lambda_1+1.$$
Solo estas dos categorías son necesarias para el conteo final de enteros positivos.
El conteo hook-content incluye todas las palabras sobre \(\{0,\dots,9\}\), incluidas las que empiezan con \(0\). Un entero positivo, en cambio, tiene una única representación decimal sin cero inicial.
Sea \(B(k)\) el número de palabras balanced de longitud a lo sumo \(k\), permitiendo ceros iniciales. Consideremos una palabra \(0v\). Como el \(0\) inicial es el menor dígito posible, puede ponerse delante de cualquier subsecuencia no estrictamente creciente de \(v\), de modo que
$$I(0v)=I(v)+1.$$
No puede alargar una subsecuencia estrictamente decreciente, porque ningún dígito posterior es menor que \(0\). Por tanto
$$D(0v)=D(v).$$
Así, \(0v\) es balanced exactamente cuando \(D(v)=I(v)+1\), que es la condición de forma \(\ell(\lambda)=\lambda_1+1\). Las palabras balanced inválidas con cero inicial y longitud total a lo sumo \(k\) se cuentan mediante esa categoría de "decreasing excess" en las colas de longitud a lo sumo \(k-1\).
También hay que quitar la palabra de un dígito \(0\), porque representa cero y no un entero positivo. En consecuencia, el conteo final para a lo sumo \(k\) dígitos es
$$T(k)=B(k)-E(k-1)-1,$$
donde \(E(k-1)\) suma las formas con altura exactamente una unidad mayor que la anchura y con a lo sumo \(k-1\) celdas. El control \(T(4)=2274\) coincide con el valor del enunciado.
factorial precalcula \(n!\) módulo \(10^9+7\) hasta \(100\). mod_pow y mod_inverse proporcionan división modular usando el pequeño teorema de Fermat, porque el módulo es primo.
shape_word_count recorre cada celda de una partición. Para cada celda calcula la longitud de gancho \(h(i,j)\), el factor de contenido \(10+j-i\), y combina las fórmulas hook-length y hook-content para obtener \(N(\lambda)\).
enumerate_partitions lista recursivamente todas las particiones que caben en el cuadrado \(10\times10\). Añade la cuenta de la forma a balanced cuando anchura y altura coinciden, y a decreasing_excess cuando la altura es una unidad mayor.
positive_balanced_count(k) primero cuenta todas las palabras balanced de longitud a lo sumo \(k\). Después resta la corrección de cero inicial procedente de colas de longitud a lo sumo \(k-1\), y resta la palabra \(0\). El programa verifica \(k=4\) y luego evalúa \(k=100\).
El algoritmo enumera particiones dentro de un cuadrado \(10\times10\), no enteros. Este conjunto finito es diminuto frente a las \(10^{100}\) posibles palabras de dígitos. Para cada forma se procesan como máximo \(100\) celdas.
Asintóticamente, para un alfabeto de tamaño \(a\), el método enumera particiones dentro de un cuadrado \(a\times a\) y procesa \(O(a^2)\) celdas por forma. En este problema \(a=10\), así que el tiempo y la memoria son efectivamente constantes.
一个正整数称为 balanced，如果它的十进制数字串中两个子序列长度相等：最长严格递减子序列的长度，以及最长非严格递增子序列的长度。
例如 \(77429\) 是 balanced，因为 \(742\) 是长度为 \(3\) 的严格递减子序列，而 \(779\) 是长度为 \(3\) 的非严格递增子序列。题目给出的校验值是：小于 \(10^4\) 的 balanced 正整数有 \(2274\) 个；要求所有 balanced 正整数的总数，结果对 \(10^9+7\) 取模。
这里的“所有”很关键。正整数有无限多个，但 balanced 正整数只有有限多个。解法必须先解释这个有限性，然后在不逐个枚举整数的情况下完成计数。
把正整数的十进制表示看作有序字母表 \(\{0,1,\dots,9\}\) 上的单词 \(w\)，且没有前导零。定义
$$I(w)=\text{最长非严格递增子序列的长度},$$
以及
$$D(w)=\text{最长严格递减子序列的长度}.$$
整数 balanced 当且仅当 \(I(w)=D(w)\)。直接对所有单词做动态规划并不可行，因为题目没有固定长度。关键是用一个 Young 图来代替每个单词，同时记录这两个极值长度。
Robinson-Schensted-Knuth 对应把全序字母表上的每个单词 \(w\) 映射到一个分拆 \(\lambda\)，也就是插入形状。对单词版本而言，\(\lambda\) 的第一行给出最长弱递增子序列，第一列给出最长严格递减子序列：
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
若 \(\ell(\lambda)\) 表示分拆的行数，则 \(\lambda'_1=\ell(\lambda)\)。因此单词 balanced 当且仅当
$$\lambda_1=\ell(\lambda).$$
问题于是变成对宽度等于高度的 Young 图求和。这也是 C++ 代码不对长单词显式计算子序列长度的原因；它直接统计每种 RSK 形状对应的所有单词。
数字字母表只有 \(10\) 个符号。严格递减子序列中每个数字最多出现一次，所以 \(D(w)\le 10\)。如果 \(w\) balanced，则 \(I(w)=D(w)\le 10\)。
在 RSK 形状中，这意味着 \(\lambda\) 的宽度和高度都不超过 \(10\)。因此 \(\lambda\) 位于一个 \(10\times10\) 正方形内，单词长度 \(|w|=|\lambda|\) 至多为 \(100\)。所以每个 balanced 正整数最多有 \(100\) 个十进制数字。代码把 MAX_CELLS 设为 \(10\cdot10=100\)。
固定一个有 \(n=|\lambda|\) 个格子的形状 \(\lambda\)。RSK 给出一对 \((P,Q)\)，其中 \(Q\) 是形状为 \(\lambda\) 的标准 Young tableau，\(P\) 是同一形状、使用 \(10\) 个数字符号的半标准 Young tableau。
标准 Young tableau 的数量由 hook-length 公式给出：
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
字母表大小为 \(10\) 的半标准 tableau 数量由 hook-content 公式给出：
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
其中行、列从 \(1\) 开始编号。因此 RSK 形状为 \(\lambda\) 的数字单词数量是
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
shape_word_count 正是对 \(10^9+7\) 取模计算这个式子：乘上所有 hook 长度，乘上所有 content 因子 \(10+j-i\)，再用模逆处理两个 hook 乘积。
分拆用非递增的行长 \(\lambda_1\ge\lambda_2\ge\cdots\) 保存。递归枚举下一行时不超过上一行，最多 \(10\) 行，并跳过超过 \(100\) 个格子的形状。
对每个生成的形状，代码维护两个和。若宽度等于高度，它贡献给 balanced 数字单词；若高度恰好比宽度大 \(1\)，它贡献给前导零修正项：
$$\lambda_1=\ell(\lambda)\quad\text{或}\quad \ell(\lambda)=\lambda_1+1.$$
最终统计正整数只需要这两类形状。
hook-content 计数包含 \(\{0,\dots,9\}\) 上的所有数字单词，也包括以 \(0\) 开头的单词。但正整数的十进制表示不能有前导零，并且表示唯一。
令 \(B(k)\) 为长度至多 \(k\)、允许前导零的 balanced 数字单词数。考虑单词 \(0v\)。因为开头的 \(0\) 是最小数字，它可以放在 \(v\) 的任意非严格递增子序列前面，所以
$$I(0v)=I(v)+1.$$
它不能延长严格递减子序列，因为后面没有比 \(0\) 更小的数字。因此
$$D(0v)=D(v).$$
于是 \(0v\) balanced 当且仅当 \(D(v)=I(v)+1\)，也就是形状条件 \(\ell(\lambda)=\lambda_1+1\)。总长度至多 \(k\) 且有前导零的无效 balanced 单词，可由长度至多 \(k-1\) 的尾部单词中这个 "decreasing excess" 类别统计。
单个数字 \(0\) 也必须去掉，因为它表示零而不是正整数。因此至多 \(k\) 位的最终计数为
$$T(k)=B(k)-E(k-1)-1,$$
其中 \(E(k-1)\) 是高度恰好比宽度大 \(1\)、且格子数至多 \(k-1\) 的形状之和。校验值 \(T(4)=2274\) 与题目一致。
factorial 预计算到 \(100\) 的 \(n!\)，全部对 \(10^9+7\) 取模。mod_pow 和 mod_inverse 用费马小定理实现模除法，因为模数是素数。
shape_word_count 遍历分拆的每个格子。对每个格子计算 hook 长度 \(h(i,j)\)、content 因子 \(10+j-i\)，然后把 hook-length 和 hook-content 公式合并为 \(N(\lambda)\)。
enumerate_partitions 递归列出 \(10\times10\) 方框内的所有分拆。宽度等于高度时，把该形状的计数加入 balanced；高度大一时，加入 decreasing_excess。
positive_balanced_count(k) 先统计长度至多 \(k\) 的所有 balanced 单词，然后减去长度至多 \(k-1\) 的尾部带来的前导零修正，再减去单词 \(0\)。程序先验证 \(k=4\)，再计算 \(k=100\)。
算法枚举的是 \(10\times10\) 方框中的分拆，而不是整数。这个有限集合远小于 \(10^{100}\) 个可能的数字单词。每个形状最多处理 \(100\) 个格子。
若字母表大小为 \(a\)，方法会枚举 \(a\times a\) 方框中的分拆，并对每个形状处理 \(O(a^2)\) 个格子。本题中 \(a=10\)，所以时间和内存实际都是常数规模。
Положительное целое число называется balanced, если в его десятичной записи совпадают две длины: длина наибольшей строго убывающей подпоследовательности и длина наибольшей нестрого возрастающей подпоследовательности.
Например, \(77429\) является balanced, потому что \(742\) — строго убывающая подпоследовательность длины \(3\), а \(779\) — нестрого возрастающая подпоследовательность длины \(3\). В условии дан контроль: ниже \(10^4\) есть \(2274\) balanced положительных целых. Требуется найти общее число таких положительных целых по модулю \(10^9+7\).
Слово "общее" здесь важно. Положительных целых бесконечно много, но balanced чисел только конечное число. Решение должно сначала объяснить эту конечность, а затем посчитать все случаи без перебора самих чисел.
Запишем десятичное представление положительного числа как слово \(w\) над упорядоченным алфавитом \(\{0,1,\dots,9\}\), без ведущего нуля. Обозначим
$$I(w)=\text{длина наибольшей нестрого возрастающей подпоследовательности},$$
и
$$D(w)=\text{длина наибольшей строго убывающей подпоследовательности}.$$
Число является balanced ровно тогда, когда \(I(w)=D(w)\). Прямая динамика по всем словам не подходит, так как длина в задаче не фиксирована. Главная идея — заменить каждое слово диаграммой Юнга, которая одновременно хранит обе экстремальные длины.
Соответствие Робинсона-Шенстеда-Кнута сопоставляет каждому слову \(w\) над полностью упорядоченным алфавитом разбиение \(\lambda\), называемое формой вставки. Для слов первая строка \(\lambda\) задаёт наибольшую слабо возрастающую подпоследовательность, а первый столбец задаёт наибольшую строго убывающую подпоследовательность:
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
Если \(\ell(\lambda)\) — число строк разбиения, то \(\lambda'_1=\ell(\lambda)\). Значит, слово balanced ровно тогда, когда
$$\lambda_1=\ell(\lambda).$$
Задача превращается в сумму по диаграммам Юнга, у которых ширина равна высоте. Поэтому C++-код не вычисляет подпоследовательности для длинных слов явно; он считает все слова каждой возможной RSK-формы.
В алфавите цифр только \(10\) символов. Строго убывающая подпоследовательность может содержать каждую цифру не более одного раза, поэтому \(D(w)\le 10\). Если \(w\) balanced, то также \(I(w)=D(w)\le 10\).
В терминах RSK это означает, что ширина и высота \(\lambda\) не превосходят \(10\). Следовательно, \(\lambda\) помещается в квадрат \(10\times10\), а длина слова \(|w|=|\lambda|\) не превосходит \(100\). Любое balanced положительное число имеет не более \(100\) десятичных цифр. Поэтому код использует MAX_CELLS со значением \(10\cdot10=100\).
Для фиксированной формы \(\lambda\) с \(n=|\lambda|\) клетками RSK даёт пару \((P,Q)\). Здесь \(Q\) — стандартная таблица Юнга формы \(\lambda\), а \(P\) — полустандартная таблица Юнга той же формы с \(10\) цифровыми символами.
Число стандартных таблиц Юнга задаётся формулой крюков:
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
Число полустандартных таблиц над алфавитом размера \(10\) задаётся hook-content формулой:
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
где строки и столбцы нумеруются с \(1\). Значит, число цифровых слов с RSK-формой \(\lambda\) равно
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
Именно это вычисляет shape_word_count по модулю \(10^9+7\): перемножает длины крюков, множители содержимого \(10+j-i\), и использует модульные обратные для двух крюковых произведений.
Разбиение хранится как невозрастающие длины строк \(\lambda_1\ge\lambda_2\ge\cdots\). Рекурсия выбирает следующую строку не длиннее предыдущей, останавливается после \(10\) строк и отбрасывает формы с более чем \(100\) клетками.
Для каждой формы ведутся две суммы. Если ширина равна высоте, форма даёт вклад в balanced слова. Если высота ровно на один больше ширины, форма даёт вклад в поправку для ведущих нулей:
$$\lambda_1=\ell(\lambda)\quad\text{или}\quad \ell(\lambda)=\lambda_1+1.$$
Для итогового подсчёта положительных целых нужны только эти две категории.
Hook-content подсчёт включает все слова над \(\{0,\dots,9\}\), в том числе начинающиеся с \(0\). Но положительное целое имеет единственную десятичную запись без ведущего нуля.
Пусть \(B(k)\) — число balanced слов длины не более \(k\), если ведущие нули разрешены. Рассмотрим слово \(0v\). Ведущий \(0\) — минимальная цифра, поэтому его можно поставить перед любой нестрого возрастающей подпоследовательностью \(v\), и
$$I(0v)=I(v)+1.$$
Строго убывающую подпоследовательность он не продлевает, так как позже нет цифры меньше \(0\). Поэтому
$$D(0v)=D(v).$$
Следовательно, \(0v\) balanced ровно тогда, когда \(D(v)=I(v)+1\), то есть RSK-форма хвоста удовлетворяет \(\ell(\lambda)=\lambda_1+1\). Недопустимые balanced слова с ведущим нулём и общей длиной не более \(k\) считаются этой категорией среди хвостов длины не более \(k-1\).
Однобуквенное слово \(0\) также нужно удалить, потому что оно представляет ноль, а не положительное число. Поэтому итоговый счёт для не более чем \(k\) цифр равен
$$T(k)=B(k)-E(k-1)-1,$$
где \(E(k-1)\) суммирует формы с высотой ровно на один больше ширины и числом клеток не более \(k-1\). Контроль \(T(4)=2274\) совпадает с условием.
factorial предварительно вычисляет \(n!\) по модулю \(10^9+7\) до \(100\). mod_pow и mod_inverse реализуют модульное деление по малой теореме Ферма, потому что модуль прост.
shape_word_count проходит по каждой клетке разбиения. Для клетки вычисляются длина крюка \(h(i,j)\), множитель содержимого \(10+j-i\), и затем формулы hook-length и hook-content объединяются в \(N(\lambda)\).
enumerate_partitions рекурсивно перечисляет все разбиения внутри квадрата \(10\times10\). Счёт формы добавляется в balanced, когда ширина равна высоте, и в decreasing_excess, когда высота на один больше.
positive_balanced_count(k) сначала считает все balanced слова длины не более \(k\). Затем вычитает поправку ведущего нуля из хвостов длины не более \(k-1\), а также отдельное слово \(0\). Программа проверяет \(k=4\), затем вычисляет \(k=100\).
Алгоритм перечисляет разбиения в квадрате \(10\times10\), а не целые числа. Это конечное множество ничтожно по сравнению с \(10^{100}\) возможными словами из цифр. Для каждой формы обрабатывается не более \(100\) клеток.
Асимптотически для алфавита размера \(a\) метод перечисляет разбиения внутри квадрата \(a\times a\) и обрабатывает \(O(a^2)\) клеток на форму. В данной задаче \(a=10\), поэтому время и память фактически постоянны.
يُسمى العدد الصحيح الموجب balanced إذا تساوى طولان في كلمة أرقامه العشرية: طول أطول متتالية فرعية متناقصة بصرامة، وطول أطول متتالية فرعية متزايدة غير صارمة.
مثلاً، العدد \(77429\) هو balanced لأن \(742\) متتالية فرعية متناقصة بصرامة طولها \(3\)، بينما \(779\) متتالية فرعية متزايدة غير صارمة طولها \(3\). تعطي المسألة نقطة تحقق: يوجد \(2274\) عدداً balanced موجباً أصغر من \(10^4\)، والمطلوب هو العدد الكلي للأعداد balanced الموجبة بترديد \(10^9+7\).
كلمة "الكلي" مهمة هنا. فالأعداد الموجبة لا نهائية، لكن الأعداد balanced منتهية. لذلك يجب أن يشرح الحل سبب الانتهاء، ثم يعد كل الحالات دون المرور على الأعداد واحداً واحداً.
نكتب التمثيل العشري لعدد موجب ككلمة \(w\) على الأبجدية المرتبة \(\{0,1,\dots,9\}\)، من دون صفر بادئ. نستخدم الرمزين \(I(w)\) و\(D(w)\) لهذين الطولين.
\(I(w)\) هو طول أطول متتالية فرعية متزايدة غير صارمة.
\(D(w)\) هو طول أطول متتالية فرعية متناقصة بصرامة.
وبهذا يصبح شرط balanced هو تساوي هذين الطولين.
العدد يكون balanced بالضبط عندما \(I(w)=D(w)\). البرمجة الديناميكية المباشرة على كل الكلمات غير مناسبة لأن الطول غير ثابت في نص المسألة. الفكرة الأساسية هي استبدال كل كلمة بمخطط Young يسجل هذين الطولين المتطرفين معاً.
مراسلة Robinson-Schensted-Knuth تربط كل كلمة \(w\) على أبجدية مرتبة كلياً بقسمة \(\lambda\)، تسمى شكل الإدراج. في نسخة الكلمات، الصف الأول من \(\lambda\) يسجل أطول متتالية فرعية متزايدة بضعف، والعمود الأول يسجل أطول متتالية فرعية متناقصة بصرامة:
$$\lambda_1=I(w),\qquad \lambda'_1=D(w).$$
إذا كانت \(\ell(\lambda)\) هي عدد صفوف القسمة، فإن \(\lambda'_1=\ell(\lambda)\). لذلك تكون الكلمة balanced بالضبط عندما
$$\lambda_1=\ell(\lambda).$$
هكذا تتحول المسألة إلى جمع على مخططات Young التي يساوي عرضها ارتفاعها. لهذا لا يحسب كود C++ أطوال المتتاليات الفرعية صراحة للكلمات الطويلة، بل يعد كل الكلمات ذات كل شكل RSK ممكن.
أبجدية الأرقام تحتوي على \(10\) رموز فقط. المتتالية الفرعية المتناقصة بصرامة لا يمكن أن تحتوي الرقم نفسه أكثر من مرة، ولذلك \(D(w)\le 10\). وإذا كانت \(w\) balanced فلدينا أيضاً \(I(w)=D(w)\le 10\).
في RSK، هذا يعني أن عرض \(\lambda\) وارتفاعها لا يتجاوزان \(10\). إذن \(\lambda\) تقع داخل مربع \(10\times10\)، وطول الكلمة \(|w|=|\lambda|\) لا يتجاوز \(100\). لذلك كل عدد balanced موجب يملك على الأكثر \(100\) رقماً عشرياً. يستخدم الكود MAX_CELLS بالقيمة \(10\cdot10=100\).
لشكل ثابت \(\lambda\) فيه \(n=|\lambda|\) خلية، تعطي RSK زوجاً \((P,Q)\). هنا \(Q\) هو tableau Young قياسي بالشكل \(\lambda\)، و\(P\) هو tableau Young شبه قياسي بالشكل نفسه ويستخدم رموز الأرقام العشرة.
عدد tableaux القياسية يعطى بصيغة hook-length:
$$f^\lambda=\frac{n!}{\prod_{c\in\lambda}h(c)}.$$
وعدد tableaux شبه القياسية على أبجدية حجمها \(10\) يعطى بصيغة hook-content:
$$s_\lambda(1^{10})=\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)},$$
حيث ترقم الصفوف والأعمدة بدءاً من \(1\). لذلك فإن عدد كلمات الأرقام ذات شكل RSK يساوي
$$N(\lambda)=f^\lambda s_\lambda(1^{10}) =n!\prod_{(i,j)\in\lambda}\frac{10+j-i}{h(i,j)^2}.$$
هذا بالضبط ما يحسبه shape_word_count بترديد \(10^9+7\): يضرب أطوال الخطاطيف، ويضرب عوامل المحتوى \(10+j-i\)، ويستخدم المعكوسات المعيارية لمنتجي الخطاطيف.
تخزن القسمة كأطوال صفوف غير متزايدة \(\lambda_1\ge\lambda_2\ge\cdots\). تختار العودية طول الصف التالي بحيث لا يزيد على السابق، وتتوقف بعد \(10\) صفوف، وترفض أي شكل فيه أكثر من \(100\) خلية.
لكل شكل مولد يحفظ الكود مجموعين. إذا كان العرض يساوي الارتفاع، يساهم الشكل في عدد كلمات الأرقام balanced. وإذا كان الارتفاع أكبر من العرض بواحد، يساهم في حد التصحيح الخاص بالأصفار البادئة:
$$\lambda_1=\ell(\lambda)\quad\mathrm{or}\quad \ell(\lambda)=\lambda_1+1.$$
هاتان الفئتان فقط هما المطلوبتان في العد النهائي للأعداد الصحيحة الموجبة.
عد hook-content يشمل كل كلمات الأرقام على \(\{0,\dots,9\}\)، بما فيها الكلمات التي تبدأ بـ \(0\). لكن العدد الصحيح الموجب له تمثيل عشري وحيد من دون صفر بادئ.
ليكن \(B(k)\) عدد الكلمات balanced ذات الطول على الأكثر \(k\)، مع السماح بالأصفار البادئة. لننظر إلى الكلمة \(0v\). لأن الصفر البادئ هو أصغر رقم ممكن، يمكن وضعه قبل أي متتالية فرعية متزايدة غير صارمة في \(v\)، لذلك
$$I(0v)=I(v)+1.$$
ولا يمكنه إطالة متتالية فرعية متناقصة بصرامة، لأنه لا يوجد رقم لاحق أصغر من \(0\). لذلك
$$D(0v)=D(v).$$
إذن \(0v\) تكون balanced بالضبط عندما \(D(v)=I(v)+1\)، وهذا هو شرط الشكل \(\ell(\lambda)=\lambda_1+1\). الكلمات balanced غير الصالحة ذات الصفر البادئ والطول الكلي على الأكثر \(k\) تعد بهذه الفئة بين الذيول ذات الطول على الأكثر \(k-1\).
يجب أيضاً حذف الكلمة المفردة \(0\)، لأنها تمثل الصفر لا عدداً موجباً. لذلك يكون العد النهائي حتى \(k\) أرقام هو
$$T(k)=B(k)-E(k-1)-1,$$
حيث \(E(k-1)\) هو مجموع الأشكال التي يزيد ارتفاعها على عرضها بواحد تماماً وبعدد خلايا لا يتجاوز \(k-1\). نقطة التحقق \(T(4)=2274\) توافق نص المسألة.
factorial يحسب \(n!\) مسبقاً حتى \(100\) بترديد \(10^9+7\). وتوفر mod_pow وmod_inverse القسمة المعيارية باستعمال مبرهنة فيرما الصغرى، لأن المعيار عدد أولي.
shape_word_count يمر على كل خلية في القسمة. لكل خلية يحسب طول الخطاف \(h(i,j)\)، وعامل المحتوى \(10+j-i\)، ثم يدمج صيغتي hook-length وhook-content في \(N(\lambda)\).
enumerate_partitions يعدد عودياً كل القسمات داخل مربع \(10\times10\). يضاف عدد الشكل إلى balanced عندما يساوي العرض الارتفاع، وإلى decreasing_excess عندما يكون الارتفاع أكبر بواحد.
positive_balanced_count(k) يعد أولاً كل الكلمات balanced ذات الطول على الأكثر \(k\). ثم يطرح تصحيح الصفر البادئ القادم من الذيول ذات الطول على الأكثر \(k-1\)، ويطرح الكلمة \(0\). يتحقق البرنامج من \(k=4\)، ثم يحسب حالة \(k=100\).
الخوارزمية تعدد القسمات داخل مربع \(10\times10\)، لا الأعداد الصحيحة. هذه مجموعة منتهية صغيرة جداً مقارنة بـ \(10^{100}\) كلمة رقمية ممكنة. لكل شكل تعالج على الأكثر \(100\) خلية.
بصورة تقاربية، لأبجدية حجمها \(a\)، تعدد الطريقة القسمات داخل مربع \(a\times a\) وتعالج \(O(a^2)\) خلية لكل شكل. في هذه المسألة \(a=10\)، لذا فإن الزمن والذاكرة ثابتان عملياً.