Let \(P(x)\) denote the next lexicographically larger permutation of the decimal digits of \(x\). If the digits of \(x\) are already in nonincreasing order, then no larger permutation exists and we define \(P(x)=0\). Problem 925 asks for
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
For \(k=16\), a direct loop over all \(10^{16}-1\) roots is impossible. The solutions therefore do not enumerate roots one by one. Instead they group roots by decimal suffixes and exploit the fact that the low digits of a square depend only on the low digits of the root.
The core idea is to reveal the square from right to left. As soon as the decisive ascent for the next-permutation operation is known, an entire block of roots can be collapsed into a single contribution.
Introduce the digit-permutation correction
$$\Delta(x)=\begin{cases} P(x)-x,&\text{if a larger digit permutation exists},\\ -x,&\text{otherwise}. \end{cases}$$
Then \(x+\Delta(x)=P(x)\), with the second line exactly encoding the convention \(P(x)=0\). Hence
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
The first sum is closed form. Writing \(N=10^k\),
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
So the real problem is to evaluate the correction sum efficiently.
Every positive root \(n<10^k\) can be written uniquely as
$$n=(q\,10^\ell+r)\,10^t,$$
where \(t\ge 0\) is the number of trailing zeros, \(r\) is an \(\ell\)-digit suffix block whose rightmost digit is nonzero, and \(q\) is the still-unknown higher prefix. In the state description, leading zeros inside the width-\(\ell\) block are allowed; that is why blocks such as \(01\) genuinely occur in the recursion.
The implementations start from a one-digit nonzero block \(r=d\in\{1,\dots,9\}\), choose \(t\in\{0,\dots,k-1\}\), and then prepend new digits on the left. Once \(\ell+t\ge k\), every root digit has been fixed and the recursion stops.
For a fixed state \((r,\ell,t)\), all completions share the same low square digits because
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
Thus the lowest \(\ell+2t\) digits of \(n^2\) are already determined by the revealed root suffix and by the trailing-zero count. If we prepend a new digit \(d\in\{0,\dots,9\}\) and set
$$r'=d\,10^\ell+r,$$
then one more square digit becomes visible:
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
The recursion therefore grows a known square suffix one decimal place at a time.
Let the width-\(\ell\) decimal block representing \(r^2\bmod 10^\ell\) be padded with leading zeros if necessary. A crucial invariant is that this block is nonincreasing from left to right in every recursive state that continues deeper. The base case \(\ell=1\) is trivial, and the recursion preserves the invariant precisely by deciding whether to continue or to collapse the branch.
Write
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$$
Here \(a\) is the leftmost digit of the current known square suffix, and \(b\) is the new digit inserted immediately to its left.
If \(b\ge a\), then the enlarged \((\ell+1)\)-digit suffix is still nonincreasing, so the rightmost ascent needed by the next-permutation algorithm has not appeared yet. The branch must be extended further.
If \(b<a\), then the digits to the right were already nonincreasing, and the first ascent from the right is now exactly the boundary \(b\mid a\). That means the pivot of the next-permutation operation has been located completely inside the revealed suffix. Digits farther to the left will remain untouched by the permutation step, so the correction \(\Delta(n^2)\) no longer depends on the unrevealed higher prefix.
After prepending \(d\), there remain
$$m=k-\ell-t-1$$
root digits that have not been chosen yet. There are therefore \(10^m\) completions of the current root state. All corresponding squares share the same revealed suffix
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
Once \(b<a\), every completion whose square has a genuine nonzero prefix to the left of that suffix has the same correction as the representative number \(10^{\ell+1+2t}+u\). This representative need not itself be a square; it is only a convenient number with the same decisive suffix and with a real digit to the left of it.
The only subtle case is the completion with empty higher root prefix. If \((r')^2<10^{\ell+1}\), then that completion produces the actual square \(u\), where the apparent leading zero in the width-\((\ell+1)\) block was only padding. In that one case we must use \(\Delta(u)\) rather than the positive-prefix representative.
So the whole block contributes
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$$
Let \(F(r,\ell,t)\) be the sum of \(\Delta(n^2)\) over all roots consistent with the state \((r,\ell,t)\). For each prepended digit \(d\), with \(r'=d\,10^\ell+r\), the recursion is
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$$
and the base case is
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{when }\ell+t\ge k.$$
Finally, every positive root belongs to exactly one initial state determined by its last nonzero digit and its trailing-zero count, so
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
Start with the branch \(r=3\), \(\ell=1\), \(t=0\). The known square suffix is \(3^2=9\), so \(a=9\). Prepend the digit \(1\): then \(r'=13\) and
$$13^2=169,\qquad 169\bmod 100=69,$$
so \(b=6\). Since \(6<9\), the pivot is fixed at the boundary \(6\mid 9\). Therefore all squares coming from roots ending in \(13\) share the same correction:
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
In each case the change is \(27\), so the branch can be aggregated immediately.
The padding-zero exception is equally important. The width-two block \(01\) represents a real recursive state. For \(1^2=1\), that left zero is not an actual digit, so there is no larger permutation and \(\Delta(1)=-1\). But \(101^2=10201\) has the same visible suffix \(01\) together with a genuine higher prefix, and its next permutation is \(10210\), giving correction \(9\). This is exactly the split handled by the two cases in \(C(r',\ell+1,t)\).
The C++, Python, and Java implementations precompute powers of ten both as ordinary integers and modulo \(10^9+7\). They begin the answer with the closed-form square sum \(\frac{N(N-1)(2N-1)}{6}\) for \(N=10^k\), and then add the correction sum produced by the recursion.
From each initial choice of the last nonzero digit \(d\) and the trailing-zero count \(t\), the implementation prepends digits on the left. At each state it computes the old leftmost known square digit \(a\), tests every extension digit through the new digit \(b\), and applies exactly the mathematical rule above: recurse when \(b\ge a\), collapse the whole branch when \(b<a\).
The aggregation count \(10^m\), the suffix value \(u\), and the padding-zero split are all handled directly from the state parameters. No root in the collapsed block is enumerated individually.
Whenever a leaf or an aggregated representative must be evaluated, the implementation converts the relevant number into a digit array, performs the standard next lexicographic permutation on those digits, and reads the result back modulo \(10^9+7\). If no next permutation exists, the contribution is \(-x\) modulo \(10^9+7\), matching the definition of \(\Delta(x)\).
The three languages differ only in how they store large integers. The recursive structure, the suffix tests, and the block-aggregation formulas are the same in all three versions.
Let \(T(k)\) be the number of suffix states that are actually visited before they either recurse further or collapse into a block contribution. The running time is \(O(T(k)\,k)\): each state tries ten prepended digits, and every representative next-permutation evaluation touches at most \(2k\) decimal digits because the square of a \(k\)-digit root has at most \(2k\) digits.
A trivial upper bound is \(T(k)\le 10^k-1\), since without early collapses the search tree would degenerate into root-by-root enumeration. The speedup comes from the many branches where the inequality \(b<a\) appears early, allowing a whole family of \(10^m\) roots to be replaced by one or two representative evaluations. Memory usage is \(O(k)\) for the power tables and recursion depth, plus temporary digit arrays of length at most \(2k\).
Sei \(P(x)\) die naechstgroessere lexikographische Permutation der Dezimalziffern von \(x\). Falls die Ziffern bereits von links nach rechts nichtzunehmend angeordnet sind, existiert keine groessere Permutation und wir setzen \(P(x)=0\). Gesucht ist
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
Fuer \(k=16\) ist eine direkte Schleife ueber alle \(10^{16}-1\) Wurzeln unmoeglich. Die Loesungen gruppieren die Wurzeln deshalb nach Dezimalsuffixen und nutzen aus, dass die unteren Stellen eines Quadrats nur von den unteren Stellen der Wurzel abhaengen.
Der entscheidende Gedanke ist, das Quadrat von rechts nach links freizulegen. Sobald die relevante Anstiegsstelle fuer die Next-Permutation feststeht, kann ein ganzer Block von Wurzeln auf einmal summiert werden.
Wir definieren die Korrektur
$$\Delta(x)=\begin{cases} P(x)-x,&\text{falls eine groessere Ziffernpermutation existiert},\\ -x,&\text{sonst}. \end{cases}$$
Dann gilt \(x+\Delta(x)=P(x)\), und der zweite Fall kodiert genau die Konvention \(P(x)=0\). Also
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
Der erste Summand ist abgeschlossen bekannt. Mit \(N=10^k\) gilt
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
Uebrig bleibt also die effiziente Berechnung der Korrektursumme.
Jede positive Wurzel \(n<10^k\) besitzt die eindeutige Darstellung
$$n=(q\,10^\ell+r)\,10^t,$$
wobei \(t\ge 0\) die Anzahl der Endnullen ist, \(r\) ein Suffixblock der Breite \(\ell\) mit nichtnulliger letzter Ziffer ist und \(q\) den noch unbekannten hoehere Praefixblock beschreibt. In dieser Zustandsbeschreibung sind Fuehrungsnullen innerhalb des Breitenblocks erlaubt; genau deshalb treten Zustaende wie \(01\) wirklich auf.
Die Implementierungen starten mit einer einstelligen nichtnulligen Endziffer \(r=d\in\{1,\dots,9\}\), waehlen \(t\in\{0,\dots,k-1\}\) und fuegen dann links neue Ziffern an. Sobald \(\ell+t\ge k\) gilt, sind alle Wurzelziffern festgelegt.
Fuer einen festen Zustand \((r,\ell,t)\) haben alle Vollstaendigungen dieselben unteren Quadratstellen, denn
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
Damit sind die letzten \(\ell+2t\) Stellen von \(n^2\) bereits durch den sichtbaren Wurzelsuffix und die Endnullen bestimmt. Wird links eine Ziffer \(d\in\{0,\dots,9\}\) angefuegt und
$$r'=d\,10^\ell+r$$
gesetzt, dann erscheint genau eine weitere Quadratstelle:
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
Die Rekursion vergroessert also den bekannten Quadratsuffix Dezimalstelle fuer Dezimalstelle.
Betrachte den Breitenblock der \(\ell\) Stellen von \(r^2\bmod 10^\ell\), bei Bedarf mit Fuehrungsnullen aufgefuellt. Eine zentrale Invariante lautet: In jedem Zustand, der tiefer verzweigt, ist dieser Block von links nach rechts nichtzunehmend. Fuer \(\ell=1\) ist das trivial, und die Rekursion erhaelt genau diese Eigenschaft.
Setze
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$$
Dabei ist \(a\) die linkeste Ziffer des aktuell bekannten Quadratsuffixes, waehrend \(b\) die neu links eingefuegte Ziffer ist.
Falls \(b\ge a\), bleibt auch der vergroesserte Block nichtzunehmend. Die fuer die Next-Permutation benoetigte rechteste Anstiegsstelle ist also noch nicht sichtbar, und die Rekursion muss weitergehen.
Falls \(b<a\), dann waren alle Ziffern rechts davon bereits nichtzunehmend, und die erste Anstiegsstelle von rechts liegt jetzt exakt an der Grenze \(b\mid a\). Der Pivot der Next-Permutation ist damit vollstaendig innerhalb des bekannten Suffixes lokalisiert. Alles, was weiter links liegt, bleibt bei diesem Permutationsschritt unveraendert; die Korrektur \(\Delta(n^2)\) haengt also nicht mehr vom unbekannten hoehere Praefix ab.
Nach dem Anfuegen von \(d\) bleiben noch
$$m=k-\ell-t-1$$
Wurzelziffern unbestimmt. Es gibt also \(10^m\) Vollstaendigungen des aktuellen Zustands. Alle zugehoerigen Quadrate besitzen denselben freigelegten Suffix
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
Sobald \(b<a\) gilt, hat jede Vollstaendigung, deren Quadrat links von diesem Suffix noch einen echten nichtnulligen Praefix besitzt, dieselbe Korrektur wie die Repraesentationszahl \(10^{\ell+1+2t}+u\). Diese Zahl muss selbst kein Quadrat sein; sie dient nur als bequemer Traeger desselben entscheidenden Suffixes mit einer echten Ziffer links davon.
Nur ein Randfall muss getrennt behandelt werden. Gilt \((r')^2<10^{\ell+1}\), dann erzeugt die Vollstaendigung mit leerem hoehere Wurzelpraefix das echte Quadrat \(u\); die scheinbare linke Null im Breitenblock war dann bloss Padding. Fuer genau diesen Fall ist \(\Delta(u)\) zu verwenden.
Damit lautet der gesamte Blockbeitrag
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$$
Sei \(F(r,\ell,t)\) die Summe aller \(\Delta(n^2)\), die mit dem Zustand \((r,\ell,t)\) vertraeglich sind. Fuer jede neue linke Ziffer \(d\), mit \(r'=d\,10^\ell+r\), gilt
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$$
und der Endfall ist
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{wenn }\ell+t\ge k.$$
Jede positive Wurzel gehoert genau zu einem Anfangszustand, bestimmt durch ihre letzte nichtnullige Ziffer und die Anzahl der Endnullen. Also
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
Betrachte den Ast \(r=3\), \(\ell=1\), \(t=0\). Der bekannte Quadratsuffix ist \(3^2=9\), also \(a=9\). Fuege links die Ziffer \(1\) an: Dann ist \(r'=13\) und
$$13^2=169,\qquad 169\bmod 100=69,$$
also \(b=6\). Wegen \(6<9\) liegt der Pivot genau an der Grenze \(6\mid 9\). Deshalb teilen alle Quadrate von Wurzeln, die auf \(13\) enden, dieselbe Korrektur:
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
In jedem Fall ist die Aenderung \(27\), und der ganze Ast kann sofort aggregiert werden.
Ebenso wichtig ist der Padding-Fall. Der Breitenblock \(01\) ist ein echter Zustand der Rekursion. Fuer \(1^2=1\) ist die linke Null keine reale Ziffer, daher existiert keine groessere Permutation und \(\Delta(1)=-1\). Dagegen besitzt \(101^2=10201\) denselben sichtbaren Suffix \(01\), aber mit echtem hoehere Praefix; die naechste Permutation ist \(10210\) und die Korrektur betraegt \(9\). Genau diesen Unterschied kodieren die zwei Faelle in \(C(r',\ell+1,t)\).
Die Implementierungen in C++, Python und Java berechnen Zehnerpotenzen sowohl als normale Ganzzahlen als auch modulo \(10^9+7\) vor. Anschliessend starten sie den Gesamtwert mit der geschlossenen Quadratsumme \(\frac{N(N-1)(2N-1)}{6}\) fuer \(N=10^k\) und addieren danach die rekursiv ermittelte Korrektursumme.
Ausgehend von jeder moeglichen letzten nichtnulligen Ziffer \(d\) und jeder moeglichen Anzahl von Endnullen \(t\) fuegt die Implementierung links neue Ziffern an. In jedem Zustand berechnet sie die bisher linkeste bekannte Quadratstelle \(a\), testet fuer jede Erweiterungsziffer den neuen Wert \(b\) und wendet exakt die mathematische Regel an: Rekursion bei \(b\ge a\), sofortige Blockaggregation bei \(b<a\).
Die Anzahl \(10^m\), der Suffixwert \(u\) und die Sonderbehandlung des Padding-Nullfalls werden direkt aus den Zustandsparametern gewonnen. Kein Element eines zusammengefassten Blocks wird einzeln durchlaufen.
Wenn ein Blatt oder eine aggregierte Repraesentationszahl ausgewertet werden muss, zerlegt die Implementierung die betreffende Zahl in Ziffern, fuehrt die uebliche naechste lexikographische Permutation aus und liest das Resultat modulo \(10^9+7\) wieder ein. Existiert keine naechste Permutation, wird \(-x\) modulo \(10^9+7\) beigesteuert, genau wie in der Definition von \(\Delta(x)\).
Die drei Sprachversionen unterscheiden sich nur in der Behandlung grosser Ganzzahlen. Rekursionsstruktur, Suffixtests und Blockformeln sind identisch.
Sei \(T(k)\) die Zahl der Suffixzustaende, die tatsaechlich besucht werden, bevor sie weiter verzweigen oder zu einem Blockbeitrag kollabieren. Die Laufzeit ist dann \(O(T(k)\,k)\): Jeder Zustand prueft zehn moegliche linke Ziffern, und jede Repraesentationsauswertung der naechsten Permutation betrachtet hoechstens \(2k\) Dezimalstellen, weil das Quadrat einer \(k\)-stelligen Wurzel maximal \(2k\) Stellen besitzt.
Als triviale obere Schranke gilt \(T(k)\le 10^k-1\), denn ohne fruehe Aggregation wuerde der Suchbaum in eine rootweise Enumeration entarten. Die praktische Beschleunigung kommt gerade daher, dass die Ungleichung \(b<a\) auf vielen Aesten frueh auftaucht und dann einen ganzen Block von \(10^m\) Wurzeln durch ein oder zwei Repraesentationsauswertungen ersetzt. Der Speicherbedarf ist \(O(k)\) fuer Potenztabellen und Rekursionstiefe, zuzueglich temporaerer Ziffernarrays der Laenge hoechstens \(2k\).
\(P(x)\), \(x\) sayisinin ondalik basamaklarinin leksikografik olarak bir sonraki daha buyuk permutasyonu olsun. Basamaklar soldan saga dogru zaten azalmayan degil, tam tersine nonincreasing durumdaysa daha buyuk bir permutasyon yoktur ve \(P(x)=0\) kabul edilir. Problem 925 su toplami ister:
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
\(k=16\) icin \(10^{16}-1\) adet koku tek tek gezmek imkansizdir. Bu nedenle cozumler sayilari tek tek incelemez; kokleri ondalik son eklerine gore gruplar ve bir karenin dusuk basamaklarinin yalnizca kokun dusuk basamaklarina bagli olmasindan yararlanir.
Ana fikir, kareyi sagdan sola acmaktir. Next-permutation isleminin belirleyici yukselisi bir kez bulununca, tek bir dal degil tum bir kok blogu ayni anda toplanabilir.
Asagidaki duzeltme terimini tanimlayalim:
$$\Delta(x)=\begin{cases} P(x)-x,&\text{eger daha buyuk bir basamak permutasyonu varsa},\\ -x,&\text{yoksa}. \end{cases}$$
Boylece \(x+\Delta(x)=P(x)\) olur; ikinci satir tam olarak \(P(x)=0\) kuralini kodlar. Dolayisiyla
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
Ilk toplam kapali formdadir. \(N=10^k\) yazarsak
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
Asil mesele, duzeltme toplamini hizli hesaplamaktir.
Her pozitif \(n<10^k\) sayisi tekil olarak
$$n=(q\,10^\ell+r)\,10^t$$
seklinde yazilabilir. Burada \(t\ge 0\) sondaki sifir sayisidir, \(r\) genisligi \(\ell\) olan ve en sag rakami sifir olmayan son ek blogudur, \(q\) ise henuz acilmamis ust on ektir. Bu durum taniminda genislik sabit oldugu icin blogun icindeki bas sifirlari serbesttir; o yuzden \(01\) gibi bloklar gercekten rekursiyonun parcasi olur.
Uygulamalar \(r=d\in\{1,\dots,9\}\) olan tek basamakli bir blokla baslar, \(t\in\{0,\dots,k-1\}\) secer ve sonra sola yeni rakamlar ekler. \(\ell+t\ge k\) oldugunda kokun tum basamaklari belirlenmis olur ve rekursiyon biter.
Sabit bir \((r,\ell,t)\) durumu icin tum tamamlamalar ayni alt kare basamaklarini verir; cunku
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
Yani \(n^2\) sayisinin en dusuk \(\ell+2t\) basamagi artik yalnizca gorunen kok son ekine ve trailing-zero sayisina baglidir. Sola yeni bir \(d\in\{0,\dots,9\}\) rakami ekleyip
$$r'=d\,10^\ell+r$$
dersek, karede soldan bir basamak daha ortaya cikar:
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
Dolayisiyla rekursiyon, bilinen kare son ekini her adimda bir basamak buyutur.
\(r^2\bmod 10^\ell\) ifadesinin \(\ell\) basamakli blogunu dusunun; gerekiyorsa basa sifir eklenir. Derine inmeye devam eden her durumda bu blog soldan saga nonincreasing tutulur. \(\ell=1\) icin bu zaten dogrudur; rekursiyon da tam olarak bu ozelligi koruyan dallari acik birakir.
Simdi
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor$$
olsun. \(a\), su ana kadar bilinen kare son ekinin en soldaki rakami; \(b\) ise onun hemen soluna yeni eklenen rakamdir.
Eger \(b\ge a\) ise genislemis \((\ell+1)\) basamakli blok da nonincreasing kalir. Bu durumda next-permutation algoritmasinin aradigi en sag yukselis henuz ortaya cikmamistir; dal daha da derinlesmelidir.
Eger \(b<a\) ise, sag taraftaki rakamlar zaten nonincreasing oldugu icin sagdan ilk yukselis tam olarak \(b\mid a\) sinirinda olusur. Boylece pivot, tumuyle bilinen son ek icinde sabitlenmis olur. Pivotun solundaki daha yuksek basamaklar permutasyon adiminda degismeyeceginden, \(\Delta(n^2)\) artik bilinmeyen ust on eke bagli degildir.
\(d\) eklendikten sonra secilmemis kok basamagi sayisi
$$m=k-\ell-t-1$$
olur. Dolayisiyla mevcut kok durumunun \(10^m\) farkli tamamlanisi vardir. Bu tamamlanislarin hepsi ayni gorunen kare son ekini paylasir:
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
\(b<a\) oldugu anda, bu son ekin solunda gercekten sifirdan farkli bir on ek tasiyan her tamamlama, \(10^{\ell+1+2t}+u\) temsilcisinin duzeltmesiyle ayni duzeltmeye sahiptir. Bu temsilci ille de bir kare olmak zorunda degildir; amac yalnizca ayni belirleyici son eki ve solunda gercek bir rakami tasiyan uygun bir sayi secmektir.
Ince ayar gerektiren tek durum, ust kok on ekinin bos olmasidir. Eger \((r')^2<10^{\ell+1}\) ise, bu tamamlama gercek kare olarak dogrudan \(u\) verir; genislikten gelen gorunen sol sifir sadece dolgu sifiridir. Bu tek durumda \(\Delta(u)\) kullanilmalidir.
Sonuc olarak blogun katkisi
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1} \end{cases}$$
olur.
\(F(r,\ell,t)\), \((r,\ell,t)\) durumuyla uyumlu tum kokler icin \(\Delta(n^2)\) toplami olsun. Her yeni sol rakam \(d\) icin, \(r'=d\,10^\ell+r\) yazarak
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a \end{cases}$$
elde edilir. Taban durum ise
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{eger }\ell+t\ge k$$
seklindedir. Her pozitif kok, son sifir olmayan rakami ile trailing-zero sayisina gore tam bir baslangic durumuna duser; dolayisiyla
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
\(r=3\), \(\ell=1\), \(t=0\) daliyla baslayalim. Bilinen kare son eki \(3^2=9\) oldugundan \(a=9\) olur. Sola \(1\) ekleyelim: o zaman \(r'=13\) ve
$$13^2=169,\qquad 169\bmod 100=69,$$
dolayisiyla \(b=6\) bulunur. \(6<9\) oldugu icin pivot tam olarak \(6\mid 9\) sinirinda sabittir. Bu nedenle \(13\) ile biten tum koklerin kareleri ayni duzeltmeyi paylasir:
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
Her durumda fark \(27\) oldugu icin bu dal hemen paketlenebilir.
Dolgu sifiri istisnasi da ayni derecede onemlidir. Genisligi iki olan \(01\) blogu rekursiyonda gercek bir durumdur. \(1^2=1\) icin soldaki sifir gercek bir basamak degildir; bu yuzden daha buyuk permutasyon yoktur ve \(\Delta(1)=-1\) olur. Ama \(101^2=10201\) ayni gorunen \(01\) son ekine sahiptir ve solunda gercek bir ust kisim vardir; sonraki permutasyon \(10210\) oldugundan duzeltme \(9\) olur. \(C(r',\ell+1,t)\) icindeki iki durum ayrimi tam olarak bunu yakalar.
C++, Python ve Java uygulamalari once on kuvvetlerini hem normal tam sayi olarak hem de \(10^9+7\) modunda hazirlar. Ardindan \(N=10^k\) icin \(\frac{N(N-1)(2N-1)}{6}\) formuluyle kareler toplami baslangica eklenir; kalan kisim rekursiyonla uretilen duzeltme toplamidir.
Her muhtemel son sifir olmayan rakam \(d\) ve her trailing-zero sayisi \(t\) icin uygulama sola yeni rakamlar ekler. Her durumda eski en soldaki kare rakami \(a\) hesaplanir, her uzanti icin yeni rakam \(b\) test edilir ve matematik tam olarak uygulanir: \(b\ge a\) ise rekursiyon derinlesir, \(b<a\) ise tum dal blok halinde toplanir.
\(10^m\) carpani, \(u\) son eki ve dolgu sifiri istisnasi dogrudan durum parametrelerinden cikarilir. Toplanan bir bloktaki kokler tek tek gezilmez.
Bir yaprak ya da toplu temsilci degeri hesaplanirken uygulama ilgili sayiyi rakam dizisine cevirir, standart leksikografik sonraki permutasyonu uygular ve sonucu \(10^9+7\) modunda geri okur. Sonraki permutasyon yoksa katkı \(-x\) mod \(10^9+7\) olarak eklenir; bu da \(\Delta(x)\) tanimiyla birebir uyumludur.
Uc dil arasindaki fark yalnizca buyuk tamsayi altyapisidir. Rekursiyon yapisi, son-ek testleri ve blok toplama formulleri aynidir.
\(T(k)\), derine inmeye devam etmeden once gercekten ziyaret edilen son-ek durumlarinin sayisi olsun. Calisma suresi \(O(T(k)\,k)\) olur: her durumda sola eklenecek on rakam denenir ve her temsilci next-permutation hesabinda en fazla \(2k\) ondalik basamak islenir; cunku \(k\) basamakli bir kokun karesi en fazla \(2k\) basamaklidir.
Basit bir ust sinir \(T(k)\le 10^k-1\) seklindedir; cunku erken toplama hic olmasa arama agaci kokleri tek tek saymaya indirgenir. Hiz kazanci, \(b<a\) esitsizliginin bircok dalda erken ortaya cikmasindan gelir; o anda \(10^m\) buyuklugundeki tum bir kok ailesi bir veya iki temsilci hesabiyla degistirilir. Bellek kullanimi, on kuvvet tabloları ve rekursiyon derinligi icin \(O(k)\), buna ek olarak da uzunlugu en fazla \(2k\) olan gecici rakam dizileridir.
Sea \(P(x)\) la siguiente permutacion lexicograficamente mayor de las cifras decimales de \(x\). Si las cifras ya estan ordenadas de izquierda a derecha de forma no creciente, entonces no existe una permutacion mayor y definimos \(P(x)=0\). El problema pide calcular
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
Para \(k=16\), recorrer una por una las \(10^{16}-1\) raices es inviable. Por eso las soluciones no iteran raiz por raiz, sino que agrupan las raices por sufijos decimales y aprovechan que las cifras bajas de un cuadrado dependen solo de las cifras bajas de la raiz.
La idea central es revelar el cuadrado de derecha a izquierda. En cuanto queda fijado el ascenso decisivo de la operacion de siguiente permutacion, se puede sumar de golpe un bloque entero de raices.
Introducimos la correccion
$$\Delta(x)=\begin{cases} P(x)-x,&\text{si existe una permutacion mayor},\\ -x,&\text{si no existe}. \end{cases}$$
Entonces \(x+\Delta(x)=P(x)\), y la segunda linea representa exactamente la convencion \(P(x)=0\). Por tanto
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
La primera suma tiene formula cerrada. Si \(N=10^k\),
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
Todo el trabajo real se concentra, por tanto, en la suma de correcciones.
Cada raiz positiva \(n<10^k\) se escribe de forma unica como
$$n=(q\,10^\ell+r)\,10^t,$$
donde \(t\ge 0\) es el numero de ceros finales, \(r\) es un bloque sufijo de anchura \(\ell\) cuya ultima cifra no es cero, y \(q\) es el prefijo superior todavia desconocido. En esta descripcion de estado se permiten ceros a la izquierda dentro del bloque de anchura fija; por eso aparecen de verdad estados como \(01\).
Las implementaciones arrancan con un bloque de una sola cifra no nula \(r=d\in\{1,\dots,9\}\), eligen \(t\in\{0,\dots,k-1\}\) y luego van anteponiendo nuevas cifras. Cuando \(\ell+t\ge k\), todas las cifras de la raiz ya quedaron fijadas.
Para un estado fijo \((r,\ell,t)\), todas las completaciones comparten las mismas cifras bajas del cuadrado, porque
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
Eso significa que las ultimas \(\ell+2t\) cifras de \(n^2\) quedan determinadas por el sufijo de la raiz y por el numero de ceros finales. Si anteponemos una nueva cifra \(d\in\{0,\dots,9\}\) y definimos
$$r'=d\,10^\ell+r,$$
entonces se revela una cifra mas del cuadrado:
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
La recursion va ampliando asi el sufijo conocido del cuadrado una posicion decimal por vez.
Consideremos el bloque de anchura \(\ell\) que representa \(r^2\bmod 10^\ell\), rellenado con ceros a la izquierda si hace falta. Una invariante esencial es que, en cualquier estado que sigue descendiendo, ese bloque es no creciente de izquierda a derecha. Para \(\ell=1\) esto es automatico, y la recursion conserva justamente esa propiedad.
Escribimos
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$$
Aqui \(a\) es la cifra mas a la izquierda del sufijo cuadratico ya conocido, y \(b\) es la nueva cifra insertada justo a su izquierda.
Si \(b\ge a\), el bloque ampliado de \(\ell+1\) cifras sigue siendo no creciente. En ese caso el ascenso mas a la derecha que necesita el algoritmo de siguiente permutacion todavia no ha aparecido, y la rama debe continuar.
Si \(b<a\), las cifras a la derecha ya eran no crecientes y, por tanto, el primer ascenso visto desde la derecha aparece exactamente en la frontera \(b\mid a\). El pivote queda asi localizado por completo dentro del sufijo ya revelado. Todo lo que esta mas a la izquierda permanecera intacto bajo la operacion de siguiente permutacion, de modo que \(\Delta(n^2)\) deja de depender del prefijo superior que aun no se conoce.
Despues de anteponer \(d\), quedan
$$m=k-\ell-t-1$$
cifras de la raiz todavia no elegidas. Por consiguiente, el estado actual tiene \(10^m\) completaciones posibles. Todas ellas comparten el mismo sufijo cuadratico visible
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
Una vez que \(b<a\), toda completacion cuyo cuadrado tenga un prefijo real no nulo a la izquierda de ese sufijo comparte la misma correccion que el representante \(10^{\ell+1+2t}+u\). Ese representante no necesita ser un cuadrado autentico; solo sirve para conservar el mismo sufijo decisivo y garantizar una cifra real a la izquierda.
Hay una unica sutileza. Si \((r')^2<10^{\ell+1}\), la completacion con prefijo superior vacio produce como cuadrado real exactamente \(u\); el cero que parecia estar a la izquierda dentro del bloque de anchura fija era solo relleno. En ese caso singular hay que usar \(\Delta(u)\).
La contribucion total del bloque es entonces
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$$
Sea \(F(r,\ell,t)\) la suma de \(\Delta(n^2)\) sobre todas las raices compatibles con el estado \((r,\ell,t)\). Para cada nueva cifra izquierda \(d\), con \(r'=d\,10^\ell+r\), se obtiene
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$$
y el caso base es
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{cuando }\ell+t\ge k.$$
Cada raiz positiva cae en un unico estado inicial determinado por su ultima cifra no nula y por su numero de ceros finales. Por eso
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
Consideremos la rama \(r=3\), \(\ell=1\), \(t=0\). El sufijo cuadratico conocido es \(3^2=9\), asi que \(a=9\). Si anteponemos la cifra \(1\), obtenemos \(r'=13\) y
$$13^2=169,\qquad 169\bmod 100=69,$$
de modo que \(b=6\). Como \(6<9\), el pivote queda fijado exactamente en la frontera \(6\mid 9\). Por tanto, todos los cuadrados de raices terminadas en \(13\) comparten la misma correccion:
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
En los tres casos la diferencia es \(27\), asi que la rama puede agregarse de inmediato.
La excepcion del cero de relleno es igual de importante. El bloque de anchura dos \(01\) es un estado real de la recursion. Para \(1^2=1\), ese cero izquierdo no es una cifra verdadera; por eso no existe una permutacion mayor y \(\Delta(1)=-1\). En cambio, \(101^2=10201\) presenta el mismo sufijo visible \(01\), pero con un prefijo superior real; su siguiente permutacion es \(10210\) y la correccion pasa a ser \(9\). Esa diferencia es exactamente la que separan los dos casos de \(C(r',\ell+1,t)\).
Las implementaciones en C++, Python y Java precalculan potencias de diez tanto como enteros ordinarios como modulo \(10^9+7\). Despues inician la respuesta con la suma cerrada de cuadrados \(\frac{N(N-1)(2N-1)}{6}\) para \(N=10^k\), y solo luego anaden la suma de correcciones obtenida por recursion.
Desde cada eleccion inicial de la ultima cifra no nula \(d\) y del numero de ceros finales \(t\), la implementacion va anteponiendo cifras. En cada estado calcula la cifra izquierda actual \(a\), prueba cada extension mediante la nueva cifra \(b\) y aplica exactamente la regla matematica: continuar si \(b\ge a\), colapsar toda la rama si \(b<a\).
El factor \(10^m\), el sufijo \(u\) y el tratamiento especial del cero de relleno se deducen directamente de los parametros del estado. Ninguna raiz de un bloque colapsado se enumera por separado.
Cuando hay que evaluar una hoja o un representante agregado, la implementacion convierte el numero correspondiente en un arreglo de cifras, ejecuta la rutina estandar de siguiente permutacion lexicografica y vuelve a leer el resultado modulo \(10^9+7\). Si no existe siguiente permutacion, la contribucion es \(-x\) modulo \(10^9+7\), tal como exige la definicion de \(\Delta(x)\).
Las tres versiones difieren solo en la infraestructura de enteros grandes. La estructura recursiva, las pruebas sobre el sufijo y las formulas de agregacion son comunes a las tres.
Sea \(T(k)\) el numero de estados de sufijo que realmente se visitan antes de seguir descendiendo o de colapsar en una contribucion de bloque. El tiempo total es \(O(T(k)\,k)\): cada estado prueba diez cifras a la izquierda, y cada evaluacion representativa de siguiente permutacion toca como mucho \(2k\) cifras decimales, porque el cuadrado de una raiz de \(k\) cifras tiene a lo sumo \(2k\) cifras.
Una cota superior trivial es \(T(k)\le 10^k-1\), ya que sin colapsos tempranos el arbol de busqueda degeneraria en una enumeracion raiz por raiz. La mejora practica aparece porque la desigualdad \(b<a\) surge pronto en muchas ramas, reemplazando un bloque completo de \(10^m\) raices por una o dos evaluaciones representativas. El consumo de memoria es \(O(k)\) para las tablas de potencias y la profundidad recursiva, mas arreglos temporales de cifras de longitud como mucho \(2k\).
设 \(P(x)\) 表示 \(x\) 的十进制数字按字典序得到的下一个更大排列。如果这些数字已经从左到右非增，那么更大的排列不存在，此时规定 \(P(x)=0\)。题目要求计算
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
当 \(k=16\) 时，根的数量达到 \(10^{16}-1\)，逐个平方、逐个做下一排列显然不可行。三份实现都采用同一个思路：不是按整数逐个处理，而是按根的十进制后缀分组，因为平方的低位只由根的低位决定。
整套方法可以概括为一句话：从右向左逐步揭示平方数的后缀，一旦“下一排列”真正起作用的那个最右上升位置已经被锁定，就把整棵分支一次性求和。
定义修正量
$$\Delta(x)=\begin{cases} P(x)-x,&\text{如果存在更大的数字排列},\\ -x,&\text{如果不存在}. \end{cases}$$
于是 \(x+\Delta(x)=P(x)\)，第二种情况恰好对应“没有下一排列时值为 \(0\)”这一题目约定。因此
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
第一项是标准闭式。令 \(N=10^k\)，则
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
所以真正困难的部分，只剩下如何高效求出所有平方的修正量之和。
任意一个正整数根 \(n<10^k\) 都可以唯一写成
$$n=(q\,10^\ell+r)\,10^t.$$
这里 \(t\ge 0\) 是末尾零的个数，\(r\) 是一个宽度为 \(\ell\) 的低位块，并且该块最右端数字非零，\(q\) 是尚未展开的更高前缀。需要特别说明的是：在状态表示里，固定宽度块内部允许出现前导零，所以像 \(01\) 这样的块并不是假的，而是递归中真实存在的状态。
实现从一位非零块 \(r=d\in\{1,\dots,9\}\) 出发，再选定 \(t\in\{0,\dots,k-1\}\)，然后不断向左补数字。当 \(\ell+t\ge k\) 时，根的所有十进制位都已经确定，递归结束。
对固定状态 \((r,\ell,t)\)，所有完成方式都有同样的平方低位，因为
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
这意味着 \(n^2\) 的最低 \(\ell+2t\) 位只由当前已经看到的根后缀和尾零个数决定。一旦在左边再补一位 \(d\in\{0,\dots,9\}\)，令
$$r'=d\,10^\ell+r,$$
就会多揭示出平方后缀的一位：
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
因此，这个递归不是随意地扩展根，而是在逐位扩展“已经确定的平方后缀”。
考察 \(r^2\bmod 10^\ell\) 对应的 \(\ell\) 位十进制块；如果位数不够，就在左边补零。一个关键不变量是：凡是还要继续向下扩展的状态，这个固定宽度块从左到右一定是非增的。对 \(\ell=1\) 这显然成立，而递归正是通过分支判断来保持这一性质。
记
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$$
其中 \(a\) 是当前已知平方后缀最左边的那一位，\(b\) 是新补到它左边的那一位。
如果 \(b\ge a\)，那么扩展后的 \(\ell+1\) 位块仍然是非增的。也就是说，下一排列算法从右往左寻找的那个最右上升位置还没有出现，递归必须继续往左展开。
如果 \(b<a\)，那么右侧原本已经是非增的，于是从右往左看到的第一个上升恰好发生在边界 \(b\mid a\) 上。此时下一排列的枢轴已经完全落在当前已知后缀内部。枢轴左边的更高位在这一操作中不会被改动，所以 \(\Delta(n^2)\) 从这一刻开始不再依赖尚未展开的高位前缀。
补上数字 \(d\) 之后，还剩下
$$m=k-\ell-t-1$$
个根数字没有决定，因此当前根状态共有 \(10^m\) 种完成方式。它们的平方都共享同一个已经揭示出来的后缀
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
一旦 \(b<a\)，只要某个完成方式对应的平方在这个后缀左边确实还存在一个非零前缀，它的修正量就和代表数 \(10^{\ell+1+2t}+u\) 完全相同。这个代表数未必真的是某个根的平方，它只是一个方便的代理对象：后缀结构完全一样，而且左边保证有真实数字存在。
唯一需要拆开的边界情况是“更高根前缀为空”。如果 \((r')^2<10^{\ell+1}\)，那么这个特殊完成方式的真实平方就是 \(u\) 本身，宽度块里看见的那个左侧零只是为了对齐而补上的虚拟零。对这一种情况，必须使用 \(\Delta(u)\)。
于是整块贡献写成
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$$
设 \(F(r,\ell,t)\) 表示所有与状态 \((r,\ell,t)\) 相容的根对应的 \(\Delta(n^2)\) 之和。对每个新补上的左侧数字 \(d\)，令 \(r'=d\,10^\ell+r\)，则有递推
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$$
而递归终点是
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{当 }\ell+t\ge k.$$
每个正整数根都恰好落在一个初始状态中，这个状态由“最后一个非零数字”与“尾零个数”唯一确定，因此
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
先看分支 \(r=3\)、\(\ell=1\)、\(t=0\)。此时已知平方后缀是 \(3^2=9\)，所以 \(a=9\)。若在左边补上数字 \(1\)，得到 \(r'=13\)，并且
$$13^2=169,\qquad 169\bmod 100=69,$$
于是 \(b=6\)。因为 \(6<9\)，枢轴恰好固定在 \(6\mid 9\) 这个边界上。因此所有末尾是 \(13\) 的根，其平方都有相同的修正量：
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
这三者的变化量都等于 \(27\)，所以整条分支可以立刻折叠。
再看前导零的特殊情形。宽度为两位的块 \(01\) 是递归里的真实状态。对 \(1^2=1\) 来说，这个左零并不是数字本身的一部分，因此不存在更大的排列，\(\Delta(1)=-1\)。但 \(101^2=10201\) 具有同样可见的 \(01\) 后缀，却同时带有真实的高位前缀；它的下一排列是 \(10210\)，修正量变成 \(9\)。这正是 \(C(r',\ell+1,t)\) 中两种情况要分开的原因。
C++、Python 和 Java 实现都会先预计算十的幂，既保存普通整数形式，也保存模 \(10^9+7\) 的形式。然后先把闭式平方和 \(\frac{N(N-1)(2N-1)}{6}\)（其中 \(N=10^k\)）加入答案，剩下的部分由递归来提供。
从每个可能的最后非零数字 \(d\) 和每个可能的尾零数 \(t\) 出发，程序不断向左补数字。在每个状态里，它先求出当前最左已知平方数字 \(a\)，再对每个扩展数字算出新的 \(b\)，并严格按照上面的数学规则执行：若 \(b\ge a\) 就继续递归，若 \(b<a\) 就把整棵子树一次性聚合。
\(10^m\) 的倍数、后缀值 \(u\) 以及“补零但没有真实高位”的特殊分支，全部都直接由状态参数计算出来。被聚合的块不会再逐个枚举根。
当递归走到叶子，或者已经可以用代表数做整块求值时，程序会把相应整数转成数字数组，执行标准的字典序下一排列，再把结果按 \(10^9+7\) 取模读回。如果不存在下一排列，那么贡献就是 \(-x\) 在模 \(10^9+7\) 下的表示，这与 \(\Delta(x)\) 的定义完全一致。
三种语言之间的差别只在于大整数的承载方式不同；递归结构、后缀判定和整块聚合公式完全相同。
记 \(T(k)\) 为在真正运行中被访问到的后缀状态数目，这些状态在继续向下递归或折叠成整块贡献之前都会被处理一次。总时间复杂度可以写成 \(O(T(k)\,k)\)：每个状态会尝试十个左扩展数字，而每次代表性“下一排列”求值最多只会处理 \(2k\) 位十进制数字，因为一个 \(k\) 位根的平方最多有 \(2k\) 位。
一个显然的上界是 \(T(k)\le 10^k-1\)；如果从来没有提前折叠，搜索树最终就会退化成逐根枚举。真正的加速来自大量分支会很早满足 \(b<a\)，于是一个规模为 \(10^m\) 的整块根直接被一到两个代表值替代。空间复杂度是 \(O(k)\)，主要来自十次幂表、递归深度以及长度最多为 \(2k\) 的临时数字数组。
Пусть \(P(x)\) обозначает следующую по лексикографическому порядку большую перестановку десятичных цифр числа \(x\). Если цифры уже расположены слева направо в невозрастающем порядке, то большей перестановки нет, и мы считаем \(P(x)=0\). Требуется найти
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
При \(k=16\) количество корней равно \(10^{16}-1\), поэтому прямой перебор невозможен. Решения работают не с отдельными числами, а с десятичными суффиксами корня, используя тот факт, что младшие цифры квадрата определяются только младшими цифрами самого корня.
Основная идея такова: квадрат раскрывается справа налево. Как только становится известной та самая правая точка роста, от которой зависит операция следующей перестановки, целое поддерево состояний можно сложить сразу.
Введем поправку
$$\Delta(x)=\begin{cases} P(x)-x,&\text{если большая перестановка существует},\\ -x,&\text{если не существует}. \end{cases}$$
Тогда \(x+\Delta(x)=P(x)\), а второй случай в точности выражает соглашение \(P(x)=0\). Поэтому
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
Первая сумма вычисляется по стандартной формуле. Если \(N=10^k\), то
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
Следовательно, вся содержательная часть задачи сводится к быстрой сумме поправок.
Любой положительный корень \(n<10^k\) можно единственным образом записать в виде
$$n=(q\,10^\ell+r)\,10^t,$$
где \(t\ge 0\) равно числу конечных нулей, \(r\) есть суффиксный блок ширины \(\ell\) с ненулевой последней цифрой, а \(q\) описывает еще не раскрытый старший префикс. В этой модели состояния разрешены ведущие нули внутри блока фиксированной ширины; поэтому блоки вида \(01\) действительно возникают в рекурсии.
Реализации стартуют с одноцифрового ненулевого блока \(r=d\in\{1,\dots,9\}\), выбирают \(t\in\{0,\dots,k-1\}\), а затем дописывают цифры слева. Когда \(\ell+t\ge k\), все цифры корня уже определены, и рекурсия завершается.
Для фиксированного состояния \((r,\ell,t)\) все завершения имеют одинаковые младшие цифры квадрата, потому что
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
Иными словами, последние \(\ell+2t\) цифр числа \(n^2\) уже определены увиденным суффиксом корня и числом конечных нулей. Если теперь приписать слева новую цифру \(d\in\{0,\dots,9\}\) и положить
$$r'=d\,10^\ell+r,$$
то становится видна еще одна цифра квадрата:
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
Рекурсия тем самым на каждом шаге удлиняет известный квадратный суффикс ровно на одну десятичную позицию.
Рассмотрим \(\ell\)-значный блок, соответствующий \(r^2\bmod 10^\ell\), с ведущими нулями при необходимости. Ключевой инвариант состоит в том, что во всех состояниях, которые продолжают углубляться, этот блок идет слева направо невозрастающе. Для \(\ell=1\) это очевидно, а рекурсия специально поддерживает именно такое свойство.
Обозначим
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$$
Здесь \(a\) - левая цифра уже известного квадратного суффикса, а \(b\) - новая цифра, вставленная непосредственно слева от нее.
Если \(b\ge a\), то расширенный блок длины \(\ell+1\) по-прежнему невозрастающий. Значит, самая правая точка роста, которую ищет алгоритм следующей перестановки, еще не появилась, и ветвь надо продолжать.
Если \(b<a\), то все цифры справа уже были невозрастающими, и первый рост при просмотре справа налево возникает ровно на границе \(b\mid a\). Следовательно, опорная позиция следующей перестановки уже полностью локализована внутри известного суффикса. Все более старшие цифры слева останутся неизменными, поэтому \(\Delta(n^2)\) больше не зависит от неизвестного старшего префикса.
После добавления цифры \(d\) остаются невыбранными
$$m=k-\ell-t-1$$
цифр корня. Значит, у текущего состояния имеется \(10^m\) завершений. Все соответствующие квадраты имеют один и тот же раскрытый суффикс
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
Как только выполнено \(b<a\), любое завершение, квадрат которого имеет слева от этого суффикса реальный ненулевой префикс, дает ту же поправку, что и представитель \(10^{\ell+1+2t}+u\). Этот представитель не обязан быть настоящим квадратом; он нужен лишь как удобное число с тем же решающим суффиксом и с реальной цифрой слева.
Существует один тонкий крайний случай. Если \((r')^2<10^{\ell+1}\), то завершение с пустым старшим префиксом корня дает в точности квадрат \(u\); видимый слева ноль в блоке фиксированной ширины был лишь выравниванием. Для этого единственного случая нужно брать \(\Delta(u)\).
Итак, вклад всего блока равен
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$$
Пусть \(F(r,\ell,t)\) обозначает сумму \(\Delta(n^2)\) по всем корням, совместимым с состоянием \((r,\ell,t)\). Для каждой новой левой цифры \(d\), где \(r'=d\,10^\ell+r\), имеем
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$$
а базовый случай таков:
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{при }\ell+t\ge k.$$
Каждый положительный корень принадлежит ровно одному начальному состоянию, задаваемому его последней ненулевой цифрой и числом конечных нулей. Поэтому
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
Возьмем ветвь \(r=3\), \(\ell=1\), \(t=0\). Известный квадратный суффикс равен \(3^2=9\), значит \(a=9\). Если добавить слева цифру \(1\), получится \(r'=13\), и
$$13^2=169,\qquad 169\bmod 100=69,$$
поэтому \(b=6\). Так как \(6<9\), опорная позиция фиксируется на границе \(6\mid 9\). Следовательно, все квадраты корней, оканчивающихся на \(13\), имеют одну и ту же поправку:
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
Во всех трех случаях разность равна \(27\), поэтому ветвь можно сразу агрегировать.
Не менее важен случай с добитым нулем. Блок ширины два \(01\) является реальным состоянием рекурсии. Для \(1^2=1\) этот левый ноль не является настоящей цифрой, поэтому большей перестановки нет и \(\Delta(1)=-1\). Но у \(101^2=10201\) виден тот же суффикс \(01\), однако сверху уже есть настоящий префикс; следующая перестановка равна \(10210\), и поправка становится \(9\). Именно это разделение и закодировано в двух случаях формулы \(C(r',\ell+1,t)\).
Реализации на C++, Python и Java заранее вычисляют степени десяти как обычные числа и по модулю \(10^9+7\). Затем они начинают ответ с закрытой формулы суммы квадратов \(\frac{N(N-1)(2N-1)}{6}\) для \(N=10^k\), после чего добавляют поправочный вклад, полученный рекурсией.
Из каждого начального выбора последней ненулевой цифры \(d\) и числа конечных нулей \(t\) программа дописывает цифры слева. В каждом состоянии она вычисляет текущую левую известную цифру квадрата \(a\), проверяет для каждого расширения новое значение \(b\) и точно следует математическому правилу: рекурсивно углубляться при \(b\ge a\), немедленно схлопывать блок при \(b<a\).
Множитель \(10^m\), суффикс \(u\) и особый случай с добитым нулем выводятся непосредственно из параметров состояния. Корни внутри агрегированного блока по отдельности не перечисляются.
Когда нужно оценить лист или агрегированного представителя, реализация переводит соответствующее число в массив цифр, выполняет стандартную операцию следующей лексикографической перестановки и считывает результат по модулю \(10^9+7\). Если следующей перестановки нет, вклад равен \(-x\) по модулю \(10^9+7\), как и требует определение \(\Delta(x)\).
Различия между тремя языками сводятся лишь к механике больших целых чисел. Структура рекурсии, проверки суффикса и формулы блоковой агрегации совпадают полностью.
Пусть \(T(k)\) обозначает число суффиксных состояний, которые реально посещаются до того, как они либо углубятся дальше, либо схлопнутся в блоковый вклад. Тогда время работы равно \(O(T(k)\,k)\): в каждом состоянии перебираются десять новых цифр, а каждая представительская проверка следующей перестановки затрагивает не более \(2k\) десятичных цифр, поскольку квадрат \(k\)-значного корня имеет не более \(2k\) цифр.
Тривиальная верхняя оценка такова: \(T(k)\le 10^k-1\). Без ранних схлопываний дерево поиска выродилось бы в перебор корней по одному. Практический выигрыш возникает потому, что неравенство \(b<a\) на многих ветвях появляется рано, и тогда целое семейство из \(10^m\) корней заменяется одной или двумя представительскими оценками. Память расходуется как \(O(k)\) на таблицы степеней, глубину рекурсии и временные массивы цифр длины не более \(2k\).
لنرمز بـ \(P(x)\) إلى الترتيب التالي الاكبر معجميا لأرقام \(x\) العشرية. إذا كانت الأرقام مرتبة من اليسار إلى اليمين على نحو غير متزايد، فلا يوجد ترتيب اكبر، وعندئذ نضع \(P(x)=0\). المطلوب هو حساب
$$S(k)=\sum_{n=1}^{10^k-1} P(n^2)\pmod{10^9+7}.$$
عندما يكون \(k=16\)، يصبح المرور على جميع الجذور وعددها \(10^{16}-1\) واحدا واحدا مستحيلا عمليا. لذلك لا تعالج الحلول كل جذر بمفرده، بل تجمع الجذور بحسب اللواحق العشرية، مستفيدة من حقيقة أن الخانات الدنيا في المربع تعتمد فقط على الخانات الدنيا في الجذر.
الفكرة المحورية هي كشف المربع من اليمين إلى اليسار. وبمجرد أن يتحدد موضع الصعود الحاسم الذي تتحكم به خوارزمية الترتيب التالي، يمكن جمع فرع كامل دفعة واحدة بدل متابعة كل عنصر فيه منفصلا.
نعرف حد التصحيح
$$\Delta(x)=\begin{cases} P(x)-x,&\text{if a larger permutation exists},\\ -x,&\text{otherwise}. \end{cases}$$
وعندئذ يصبح \(x+\Delta(x)=P(x)\)، والحالة الثانية تمثل بالضبط اتفاق المسألة على أن القيمة تساوي \(0\) عندما لا يوجد ترتيب تال. لذلك
$$S(k)\equiv \sum_{n=1}^{10^k-1} n^2+\sum_{n=1}^{10^k-1}\Delta(n^2)\pmod{10^9+7}.$$
الجزء الأول يملك صيغة مغلقة مباشرة. إذا وضعنا \(N=10^k\)، فإن
$$\sum_{n=1}^{10^k-1} n^2=\sum_{n=0}^{N-1} n^2=\frac{N(N-1)(2N-1)}{6}.$$
إذن جوهر المسألة هو حساب مجموع حدود التصحيح بسرعة.
كل جذر موجب \(n<10^k\) يكتب على نحو وحيد بالشكل
$$n=(q\,10^\ell+r)\,10^t,$$
حيث \(t\ge 0\) هو عدد الأصفار النهائية، و\(r\) كتلة لاحقة عرضها \(\ell\) وينتهي رقمها الأيمن برقم غير صفري، و\(q\) هو البادئة العليا التي لم تُكشف بعد. في هذا الوصف تسمح الحالة بوجود أصفار بادئة داخل الكتلة ذات العرض الثابت، ولهذا تظهر في العودية كتل مثل \(01\) فعلا وليست مجرد كتابة شكلية.
تبدأ التطبيقات بكتلة من رقم واحد غير صفري \(r=d\in\{1,\dots,9\}\)، ثم تختار \(t\in\{0,\dots,k-1\}\)، وبعد ذلك تضيف أرقاما جديدة من اليسار. وعندما يصبح \(\ell+t\ge k\)، تكون كل خانات الجذر قد تحددت وتنتهي العودية.
في الحالة الثابتة \((r,\ell,t)\)، تشترك جميع الإتمامات في الخانات الدنيا نفسها من المربع، لأن
$$n^2=(q\,10^\ell+r)^2\,10^{2t}\equiv r^2\,10^{2t}\pmod{10^{\ell+2t}}.$$
هذا يعني أن أدنى \(\ell+2t\) خانة من \(n^2\) قد تحددت بالفعل بواسطة لاحقة الجذر المرئية وعدد الأصفار النهائية. وإذا أضفنا رقما جديدا \(d\in\{0,\dots,9\}\) إلى اليسار وكتبنا
$$r'=d\,10^\ell+r,$$
فإن خانة جديدة من المربع تنكشف:
$$n^2\equiv (r')^2\,10^{2t}\pmod{10^{\ell+1+2t}}.$$
وبذلك تكبر اللاحقة المعروفة للمربع منزلة عشرية واحدة في كل خطوة.
انظر إلى الكتلة ذات العرض \(\ell\) التي تمثل \(r^2\bmod 10^\ell\)، مع إضافة أصفار في اليسار إذا لزم الأمر. هناك ثابت أساسي يقول إن هذه الكتلة تكون غير متزايدة من اليسار إلى اليمين في كل حالة تستمر العودية بعدها إلى عمق اكبر. عند \(\ell=1\) يكون ذلك بديهيا، والعودية تحافظ على هذه الخاصية بالضبط.
نكتب
$$a=\left\lfloor\frac{r^2\bmod 10^\ell}{10^{\ell-1}}\right\rfloor,\qquad b=\left\lfloor\frac{(r')^2\bmod 10^{\ell+1}}{10^\ell}\right\rfloor.$$
العدد \(a\) هو الرقم الأيسر في لاحقة المربع المعروفة حاليا، و\(b\) هو الرقم الجديد الذي دخل مباشرة على يساره.
إذا كان \(b\ge a\)، فإن الكتلة الموسعة ذات الطول \(\ell+1\) تبقى غير متزايدة. وهذا يعني أن موضع الصعود الأيمن الذي تبحث عنه خوارزمية الترتيب التالي لم يظهر بعد، وبالتالي يجب متابعة التوسع.
أما إذا كان \(b<a\)، فبما أن جميع الخانات إلى اليمين كانت غير متزايدة من قبل، فإن أول صعود عند الفحص من اليمين إلى اليسار يقع بالضبط على الحد \(b\mid a\). عند هذه اللحظة يكون المحور قد تحدد بالكامل داخل اللاحقة المكشوفة. وكل ما يقع إلى اليسار منه يبقى كما هو أثناء عملية الترتيب التالي، ولذلك لا تعود \(\Delta(n^2)\) معتمدة على البادئة العليا غير المكشوفة.
بعد إضافة الرقم \(d\)، يبقى
$$m=k-\ell-t-1$$
رقما من أرقام الجذر لم يُختر بعد. ولذلك توجد \(10^m\) إتمامات ممكنة للحالة الحالية. وجميع هذه الإتمامات تشترك في اللاحقة المكشوفة نفسها من المربع:
$$u=\big((r')^2\bmod 10^{\ell+1}\big)\,10^{2t}.$$
بمجرد تحقق \(b<a\)، فإن كل إتمام يكون لمربعه بادئة حقيقية غير صفرية إلى يسار هذه اللاحقة يملك التصحيح نفسه الذي يملكه الممثل \(10^{\ell+1+2t}+u\). هذا الممثل لا يلزم أن يكون مربعا فعليا؛ إنه مجرد عدد مريح يحمل اللاحقة الحاسمة نفسها ومعه رقم حقيقي على يسارها.
هناك حالة دقيقة واحدة. إذا كان \((r')^2<10^{\ell+1}\)، فإن الإتمام الذي يملك بادئة عليا فارغة يعطي المربع الحقيقي \(u\) نفسه؛ أما الصفر الظاهر على اليسار داخل الكتلة ذات العرض الثابت فلم يكن إلا صفرا للحشو. في هذه الحالة الوحيدة يجب استعمال \(\Delta(u)\).
ومن ثم يصبح إسهام الكتلة كلها
$$C(r',\ell+1,t)= \begin{cases} \Delta(u)+(10^m-1)\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2<10^{\ell+1},\\ 10^m\,\Delta\!\left(10^{\ell+1+2t}+u\right),&(r')^2\ge 10^{\ell+1}. \end{cases}$$
لنرمز بـ \(F(r,\ell,t)\) إلى مجموع قيم \(\Delta(n^2)\) على جميع الجذور الموافقة للحالة \((r,\ell,t)\). ولكل رقم جديد يضاف من اليسار \(d\)، حيث \(r'=d\,10^\ell+r\)، تكون العلاقة
$$F(r,\ell,t)=\sum_{d=0}^{9} \begin{cases} C(r',\ell+1,t),&b<a,\\ F(r',\ell+1,t),&b\ge a, \end{cases}$$
أما حالة النهاية فهي
$$F(r,\ell,t)=\Delta\!\left((r\,10^t)^2\right)\qquad\text{when }\ell+t\ge k.$$
كل جذر موجب ينتمي إلى حالة ابتدائية وحيدة يحددها آخر رقم غير صفري فيه وعدد أصفاره النهائية. لذلك
$$\sum_{n=1}^{10^k-1}\Delta(n^2)=\sum_{d=1}^{9}\sum_{t=0}^{k-1}F(d,1,t).$$
لنأخذ الفرع \(r=3\)، و\(\ell=1\)، و\(t=0\). لاحقة المربع المعروفة هي \(3^2=9\)، وبالتالي \(a=9\). إذا أضفنا الرقم \(1\) إلى اليسار صار \(r'=13\)، ولدينا
$$13^2=169,\qquad 169\bmod 100=69,$$
ومن ثم \(b=6\). ولأن \(6<9\)، فقد تحدد المحور تماما على الحد \(6\mid 9\). لذلك تشترك جميع المربعات الناتجة من الجذور المنتهية بـ \(13\) في التصحيح نفسه:
$$169\to 196,\qquad 113^2=12769\to 12796,\qquad 213^2=45369\to 45396.$$
وفي الحالات الثلاث يكون الفرق \(27\)، ولذلك يمكن جمع الفرع كله مباشرة.
أما استثناء صفر الحشو فهو مهم بالقدر نفسه. فالكتلة ذات العرض اثنين \(01\) هي حالة حقيقية في العودية. بالنسبة إلى \(1^2=1\)، هذا الصفر الأيسر ليس رقما فعليا، ولذلك لا يوجد ترتيب اكبر وتكون \(\Delta(1)=-1\). لكن \(101^2=10201\) يملك اللاحقة المرئية نفسها \(01\) مع بادئة علوية حقيقية، وتصبح permutation التالية \(10210\) فيكون التصحيح \(9\). لهذا السبب تحديدا تفصل صيغة \(C(r',\ell+1,t)\) بين الحالتين.
تقوم تطبيقات C++ وPython وJava بحساب قوى العدد \(10\) مسبقا، سواء كأعداد صحيحة عادية أو بترديد \(10^9+7\). ثم تبدأ الجواب بصيغة مجموع المربعات المغلقة \(\frac{N(N-1)(2N-1)}{6}\) حيث \(N=10^k\)، وبعدها تضيف مجموع التصحيحات الناتج من العودية.
انطلاقا من كل اختيار مبدئي لآخر رقم غير صفري \(d\) ولكل عدد ممكن من الأصفار النهائية \(t\)، تضيف الخوارزمية أرقاما من اليسار. وفي كل حالة تحسب الرقم الأيسر الحالي في لاحقة المربع \(a\)، ثم تختبر لكل امتداد القيمة الجديدة \(b\)، وتطبق القاعدة الرياضية نفسها حرفيا: استمرار العودية عندما \(b\ge a\)، وتجميع الفرع كله عندما \(b<a\).
العامل \(10^m\)، وقيمة اللاحقة \(u\)، والانقسام الخاص بحالة صفر الحشو كلها تُستخرج مباشرة من معلمات الحالة. ولا يجري تعداد أي جذر داخل كتلة جرى تجميعها بالفعل.
عندما تصل العودية إلى ورقة نهائية، أو عندما يكفي ممثل واحد لتقييم كتلة كاملة، يحول التطبيق العدد المعني إلى مصفوفة من الأرقام، ويطبق خوارزمية الترتيب المعجمي التالي القياسية، ثم يقرأ الناتج بترديد \(10^9+7\). وإذا لم يوجد ترتيب تال، فإن المساهمة تكون \(-x\) modulo \(10^9+7\)، وهو ما يطابق تعريف \(\Delta(x)\) تماما.
الاختلاف بين اللغات الثلاث يقتصر على البنية المستخدمة للأعداد الكبيرة. أما شجرة الحالات، واختبارات اللاحقة، وصيغ تجميع الكتل فهي واحدة في الجميع.
لنرمز بـ \(T(k)\) إلى عدد حالات اللواحق التي تُزار فعليا قبل أن تستمر إلى عمق اكبر أو تنهار في مساهمة كتلية واحدة. زمن التنفيذ يساوي \(O(T(k)\,k)\): ففي كل حالة تُجرَّب عشرة أرقام ممكنة على اليسار، وكل تقييم تمثيلي لعملية الترتيب التالي يلامس في أقصاه \(2k\) رقما عشريا، لأن مربع جذر مكوّن من \(k\) خانات لا يتجاوز \(2k\) خانة.
وهناك حد علوي بديهي هو \(T(k)\le 10^k-1\). فلو لم يحدث أي تجميع مبكر، لتحولت الشجرة إلى تعداد مباشر للجذور واحدا واحدا. ويأتي التسارع العملي من أن المتباينة \(b<a\) تظهر مبكرا في كثير من الفروع، وعندها تُستبدل عائلة كاملة حجمها \(10^m\) من الجذور بتقييم تمثيلي واحد أو اثنين. استهلاك الذاكرة هو \(O(k)\) لجداول قوى العشرة وعمق المكدس العودي، إضافة إلى مصفوفات أرقام مؤقتة طولها في أقصى حال \(2k\).