Define \(\operatorname{nextPerm}(m)\) to be the smallest integer strictly larger than \(m\) that uses exactly the same decimal digits as \(m\). If no larger rearrangement exists, its value is \(0\). The sequence in this problem is
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
and we must evaluate
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
The first terms are still small enough to inspect directly:
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
From that point on, the exact integers become far too large for direct decimal manipulation. The implementations therefore track only two finite-state shadows of the sequence: the residue \(a_n \bmod (10^9+7)\) and the final \(11\) decimal digits of \(a_n\).
The solution is built around one problem-specific decomposition. For large \(n\), the next larger digit permutation of \(a_n\) is obtained by leaving the high decimal prefix alone and changing only the last \(11\) digits. That converts a huge decimal problem into the sum of a modular orbit and a fixed-width tail correction.
The first five terms can be handled exactly. Their next larger digit permutations are
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
So the exact prefix contributes
$$U(5)=0+0+83+1464+2090981=2092528.$$
The real difficulty begins at \(a_6\). After that, the numbers are already too large to compute \(\operatorname{nextPerm}(a_n)\) by operating on the full decimal expansion for anything like \(10^{16}\) terms.
Let
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
Here \(t_n\) is treated as an \(11\)-digit decimal word, with leading zeros when necessary. This is important because next permutation is a positional digit operation, so those leading zeros still occupy digit slots.
Define
$$x_n\equiv a_n\pmod p.$$
Then the recurrence immediately gives
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$
The padded tail at the cutoff point is
$$t_5=00002090918.$$
So beyond the exact prefix, all arithmetic can be advanced inside the finite rings modulo \(p\) and modulo \(10^{11}\).
For the orbit relevant to this problem, the implementations exploit the invariant that from \(n\ge 6\) onward, the standard next-permutation pivot, swap, and suffix reversal all occur inside the last \(11\) decimal positions. If \(\operatorname{nextPerm}_{11}(t)\) denotes the next lexicographic permutation of the \(11\)-digit word \(t\), define
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$
Under that invariant,
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$
Therefore
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
This is the decisive simplification: the huge decimal rearrangement is replaced by a modular term \(x_n\) and a small fixed-width correction. The C++ implementation checks this identity against exact big-integer values for \(n=6,\dots,15\), and the full tail sweep confirms that every visited \(11\)-digit tail on the relevant orbit has a valid next lexicographic rearrangement.
Let
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$
Then for \(N\ge 6\),
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$
So after the first five terms, the task splits into two separate long sums: one over the orbit modulo \(p\), and one over the tail correction along the orbit modulo \(10^{11}\).
The map \(x\mapsto x^2+2 \pmod p\) acts on a finite state space, so the orbit starting from \(x_0=0\) is eventually periodic. The implementations find
$$\mu=39911,\qquad \lambda=21353,$$
where \(\mu\) is the preperiod length and \(\lambda\) is the cycle length. If
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j},$$
then for every \(n\ge \mu\), with
$$r=(n-\mu+1)\bmod\lambda,$$
we get
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$
That turns \(\sum_{n=6}^{N}x_n\) into a prefix-sum query on one precomputed orbit.
The tail sequence also lives in a finite state space. Starting from \(t_5=00002090918\), the implementations iterate
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
and use the fact that the relevant orbit has length
$$L_{\text{tail}}=15625000=8\cdot 5^9.$$
After exactly \(L_{\text{tail}}\) steps, the tail returns to \(t_5\). If
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
and
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$
then
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$
This is the second compression step: a sum over almost \(10^{16}\) indices collapses to one full-cycle sum and one remainder sum.
The transition from \(a_5\) to \(a_6\) shows the mechanism clearly. We have
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
and then
$$a_6=a_5^2+2=4371938082726.$$
Its \(11\)-digit tail is
$$t_6=71938082726.$$
The next lexicographic permutation of this \(11\)-digit word is
$$71938082726\to 71938082762,$$
so
$$\Delta(t_6)=71938082762-71938082726=36.$$
Therefore
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$
This is exactly the same local correction rule later reused for every large term. As a further checkpoint, the exact prefix plus the first five large-regime terms satisfy
$$U(10)\equiv 543870437\pmod p.$$
The C++, Python, and Java implementations first compute the exact contributions for \(n=1,\dots,5\), because those numbers are still small enough for direct decimal next-permutation arithmetic. They then build the orbit of \(x_{n+1}=x_n^2+2\pmod p\), stop when the first repeated state appears, and store prefix sums so that any interval sum of the residue sequence can be answered in constant additional time.
Next, the implementation starts from the padded tail \(00002090918\), advances the recurrence modulo \(10^{11}\), computes the \(11\)-digit next-permutation delta at each step, and accumulates one full orbit sum \(D\). A quotient-remainder split then expands that one-cycle total to all indices from \(n=6\) up to \(n=10^{16}\).
The C++ implementation also performs explicit validations. It checks the exact value of \(U(10)\), compares the decomposition against exact big-integer values for the early large terms, and verifies that the tail returns to its starting point after exactly \(L_{\text{tail}}\) steps. The Python and Java implementations follow the same mathematical decomposition but omit those explicit assertions.
The orbit modulo \(p\) stores \(\mu+\lambda=61264\) states, so that phase costs \(O(\mu+\lambda)\) time and memory. The dominant work is the single sweep over the tail orbit of length \(L_{\text{tail}}=15625000\), plus at most one shorter remainder sweep. Hence the overall complexity is
$$O(\mu+\lambda+L_{\text{tail}})$$
time and
$$O(\mu+\lambda)$$
memory.
The gain is dramatic: the method never tries to materialize \(a_n\) for \(n\) anywhere near \(10^{16}\), and it never runs decimal next-permutation logic on astronomically large integers.
Sei \(\operatorname{nextPerm}(m)\) die kleinste ganze Zahl, die strikt größer als \(m\) ist und genau dieselben Dezimalziffern wie \(m\) verwendet. Falls keine größere Anordnung existiert, ist der Wert \(0\). Die Folge der Aufgabe lautet
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
und gesucht ist
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
Die ersten Werte sind noch überschaubar:
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
Danach explodieren die exakten Zahlen. Deshalb verfolgen die Implementierungen nur zwei endliche Projektionen der Folge weiter: \(a_n \bmod (10^9+7)\) und die letzten \(11\) Dezimalstellen von \(a_n\).
Die Lösung beruht auf einer aufgabenspezifischen Zerlegung. Für große \(n\) wird die nächstgrößere Ziffernpermutation von \(a_n\) dadurch erhalten, dass der hohe Dezimalpräfix unverändert bleibt und nur die letzten \(11\) Stellen umgeordnet werden. Damit zerfällt das Problem in eine modulare Bahn und eine feste kleine Tail-Korrektur.
Die ersten fünf Glieder lassen sich vollständig exakt behandeln. Ihre nächstgrößeren Ziffernpermutationen sind
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
Damit ergibt sich
$$U(5)=0+0+83+1464+2090981=2092528.$$
Die eigentliche Schwierigkeit beginnt bei \(a_6\). Danach sind die Zahlen bereits so groß, dass man \(\operatorname{nextPerm}(a_n)\) nicht mehr auf der vollständigen Dezimaldarstellung für eine Summe der Länge \(10^{16}\) berechnen kann.
Setze
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
Dabei wird \(t_n\) als Dezimalwort der festen Länge \(11\) betrachtet, notfalls mit führenden Nullen. Das ist wichtig, weil der next-permutation-Algorithmus auf Ziffernpositionen arbeitet und führende Nullen ebenfalls Positionen besetzen.
Definiere
$$x_n\equiv a_n\pmod p.$$
Dann folgt unmittelbar aus der Rekursion
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$
Am Übergangspunkt hat der aufgefüllte Tail den Wert
$$t_5=00002090918.$$
Jeder spätere Zustand entsteht also nur noch in den endlichen Ringen modulo \(p\) und modulo \(10^{11}\).
Für die in dieser Aufgabe relevante Bahn nutzen die Implementierungen die Invariante, dass ab \(n\ge 6\) Pivot, Tausch und Suffixumkehr des üblichen next-permutation-Verfahrens vollständig innerhalb der letzten \(11\) Dezimalstellen liegen. Bezeichne mit \(\operatorname{nextPerm}_{11}(t)\) die nächste lexikographische Permutation des \(11\)-stelligen Wortes \(t\), und definiere
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$
Unter dieser Invariante gilt
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$
Damit folgt
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
Genau das macht die Aufgabe handhabbar: Eine gigantische Dezimaloperation schrumpft zu einem modularen Summanden \(x_n\) und einer kleinen Korrektur \(\Delta(t_n)\). Die C++-Implementierung prüft diese Identität für \(n=6,\dots,15\) an exakten Big-Integer-Werten; der vollständige Tail-Durchlauf bestätigt außerdem, dass jeder besuchte \(11\)-stellige Tail auf dieser Bahn überhaupt eine größere lexikographische Anordnung besitzt.
Definiere
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$
Für \(N\ge 6\) wird daraus
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$
Nach den ersten fünf Gliedern bleiben also nur noch zwei lange Summen übrig: eine über die Bahn modulo \(p\) und eine über die Tail-Korrektur modulo \(10^{11}\).
Die Abbildung \(x\mapsto x^2+2 \pmod p\) wirkt auf einer endlichen Zustandsmenge, also wird die von \(x_0=0\) gestartete Bahn schließlich periodisch. Die Implementierungen finden
$$\mu=39911,\qquad \lambda=21353,$$
wobei \(\mu\) die Vorperiode und \(\lambda\) die Periodenlänge ist. Mit
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j}$$
und
$$r=(n-\mu+1)\bmod\lambda$$
gilt für jedes \(n\ge \mu\)
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$
Damit wird \(\sum_{n=6}^{N}x_n\) zu einer Präfixsummenabfrage auf einer einmal vorab berechneten Bahn.
Auch die Tail-Folge lebt auf einem endlichen Zustandsraum. Ausgehend von \(t_5=00002090918\) iterieren die Implementierungen
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
und verwenden, dass die relevante Bahn die Länge
$$L_{\text{tail}}=15625000=8\cdot 5^9$$
hat. Nach genau \(L_{\text{tail}}\) Schritten ist wieder \(t_5\) erreicht. Wenn
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
und
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$
dann folgt
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$
So schrumpft eine Summe über fast \(10^{16}\) Indizes auf eine einzige Vollzyklussumme plus einen Rest.
Der Übergang von \(a_5\) zu \(a_6\) zeigt das Verfahren konkret. Es gilt
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
und dann
$$a_6=a_5^2+2=4371938082726.$$
Sein \(11\)-stelliger Tail ist
$$t_6=71938082726.$$
Die nächste lexikographische Permutation dieses Wortes ist
$$71938082726\to 71938082762,$$
also
$$\Delta(t_6)=71938082762-71938082726=36.$$
Daher
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$
Genau dieselbe lokale Regel wird später für jedes große Glied wiederverwendet. Als zusätzlicher Kontrollwert gilt außerdem
$$U(10)\equiv 543870437\pmod p.$$
Die C++-, Python- und Java-Implementierungen berechnen zunächst die exakten Beiträge für \(n=1,\dots,5\), weil diese Werte noch klein genug für direkte Dezimalarithmetik mit next permutation sind. Danach bauen sie die Bahn von \(x_{n+1}=x_n^2+2\pmod p\) auf, stoppen beim ersten Wiederholungspunkt und speichern Präfixsummen, sodass jede Intervallsumme der Restfolge mit konstanter Zusatzarbeit beantwortet werden kann.
Anschließend startet die Implementierung beim aufgefüllten Tail \(00002090918\), entwickelt die Rekursion modulo \(10^{11}\) weiter, berechnet in jedem Schritt die \(11\)-stellige next-permutation-Differenz und akkumuliert eine vollständige Bahnsumme \(D\). Mit einer Quotient-Rest-Zerlegung wird diese eine Zyklussumme dann auf alle Indizes von \(n=6\) bis \(n=10^{16}\) übertragen.
Die C++-Implementierung führt zusätzlich explizite Tests aus. Sie überprüft den exakten Wert von \(U(10)\), vergleicht die Zerlegung für die frühen großen Terme mit exakten Big-Integer-Werten und bestätigt, dass der Tail nach genau \(L_{\text{tail}}\) Schritten zum Ausgangspunkt zurückkehrt. Die Python- und Java-Implementierungen benutzen dieselbe mathematische Zerlegung, enthalten aber diese ausdrücklichen Assertions nicht.
Die Bahn modulo \(p\) speichert \(\mu+\lambda=61264\) Zustände; dieser Teil kostet also \(O(\mu+\lambda)\) Zeit und Speicher. Die dominierende Arbeit ist der einmalige Durchlauf der Tail-Bahn der Länge \(L_{\text{tail}}=15625000\), plus höchstens ein kürzerer Restdurchlauf. Insgesamt ergibt sich
$$O(\mu+\lambda+L_{\text{tail}})$$
Zeit und
$$O(\mu+\lambda)$$
Speicher.
Der Gewinn ist erheblich: Das Verfahren versucht nie, \(a_n\) für \(n\) in der Größenordnung \(10^{16}\) explizit zu konstruieren, und es wendet next permutation niemals auf astronomisch große vollständige Dezimaldarstellungen an.
\(\operatorname{nextPerm}(m)\), \(m\)'den büyük olan ve \(m\) ile tam olarak aynı ondalık rakamları kullanan en küçük sayı olsun. Böyle bir daha büyük düzen yoksa değer \(0\) kabul edilir. Problemdeki dizi
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
şeklindedir ve hesaplanmak istenen toplam
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
İlk terimler hâlâ açıkça yazılabilir:
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
Bundan sonra tam sayılar çok hızlı büyür. Bu nedenle uygulamalar dizinin yalnızca iki sonlu izdüşümünü takip eder: \(a_n \bmod (10^9+7)\) ve \(a_n\)'in son \(11\) ondalık basamağı.
Çözüm tek bir problem-özel ayrışım üzerine kuruludur. Büyük \(n\) değerlerinde \(a_n\)'in bir sonraki büyük rakam permütasyonu, yüksek ondalık ön eki sabit bırakıp sadece son \(11\) basamağı değiştirerek elde edilir. Böylece dev bir ondalık işlem, modüler bir yörünge ile sabit genişlikli bir kuyruk düzeltmesine ayrılır.
İlk beş terim tam olarak hesaplanabilir. Bunların bir sonraki büyük rakam permütasyonları şöyledir:
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
Dolayısıyla
$$U(5)=0+0+83+1464+2090981=2092528$$
olur. Gerçek zorluk \(a_6\) ile başlar; bundan sonra \(\operatorname{nextPerm}(a_n)\)'i tüm sayının ondalık yazımı üzerinde doğrudan uygulamak, özellikle toplam uzunluğu \(10^{16}\) iken, mümkün değildir.
Şöyle yazalım:
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
Burada \(t_n\) yalnızca bir sayı değil, gerekirse başına sıfır eklenmiş tam \(11\) basamaklı bir ondalık kelime olarak ele alınır. Bu önemlidir; çünkü next-permutation algoritması rakam konumları üzerinde çalışır ve baştaki sıfırlar da bu konumların parçasıdır.
Şimdi
$$x_n\equiv a_n\pmod p$$
tanımını yapalım. O zaman yineleme hemen
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
şeklinde iki sonlu duruma iner. Eşik noktasındaki doldurulmuş kuyruk
$$t_5=00002090918$$
olduğundan, küçük ön ekten sonra bütün ilerleme modulo \(p\) ve modulo \(10^{11}\) halkaları içinde yapılır.
Bu problemdeki yörünge için uygulamaların kullandığı değişmez şudur: \(n\ge 6\) olduktan sonra standart next-permutation algoritmasının pivot seçimi, takası ve son ek ters çevirme adımı tamamen son \(11\) ondalık basamak içinde kalır. \(t\) adlı \(11\) basamaklı kelimenin sözlük sırasına göre bir sonraki permütasyonunu \(\operatorname{nextPerm}_{11}(t)\) ile gösterip
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t$$
tanımını yapalım. Bu değişmez altında
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6)$$
olur. Dolayısıyla
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
Asıl kolaylaştırıcı adım budur: dev bir ondalık permütasyon problemi, modüler terim \(x_n\) ile küçük kuyruk farkı \(\Delta(t_n)\)'ye indirgenir. C++ uygulaması bu özdeşliği \(n=6,\dots,15\) için tam büyük tamsayı değerleriyle sınar; ayrıca tam kuyruk turu, ziyaret edilen her \(11\) basamaklı kuyruğun gerçekten bir sonraki sözlük sıralı düzenlemeye sahip olduğunu doğrular.
Şimdi
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n)$$
olsun. \(N\ge 6\) için
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p$$
elde edilir. Yani ilk beş terimden sonra geriye yalnızca iki uzun toplam kalır: biri modüler yörünge üzerinde, diğeri kuyruk düzeltmeleri üzerinde.
\(x\mapsto x^2+2 \pmod p\) dönüşümü sonlu bir durum kümesinde çalıştığı için \(x_0=0\) ile başlayan yörünge sonunda periyodik olur. Uygulamaların bulduğu değerler
$$\mu=39911,\qquad \lambda=21353$$
şeklindedir; burada \(\mu\) dönem öncesi uzunluk, \(\lambda\) ise dönem uzunluğudur. Eğer
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j}$$
ve
$$r=(n-\mu+1)\bmod\lambda$$
ise, her \(n\ge \mu\) için
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p$$
olur. Böylece \(\sum_{n=6}^{N}x_n\), önceden hesaplanmış bir yörünge üzerindeki ön ek toplamı sorgusuna dönüşür.
Kuyruk dizisi de sonlu bir durum uzayında yaşar. \(t_5=00002090918\)'den başlayarak uygulamalar
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
yinelemesini ilerletir ve ilgili yörüngenin uzunluğunun
$$L_{\text{tail}}=15625000=8\cdot 5^9$$
olduğunu kullanır. Tam \(L_{\text{tail}}\) adım sonra kuyruk yeniden \(t_5\)'e döner. Eğer
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
ve
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}}$$
ise
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p$$
olur. Bu, yaklaşık \(10^{16}\) terimli bir toplamı tek bir tam dönem toplamına ve küçük bir artık toplama indirger.
\(a_5\)'ten \(a_6\)'ya geçiş mekanizmayı açıkça gösterir. Elimizde
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
ve ardından
$$a_6=a_5^2+2=4371938082726$$
vardır. Bunun \(11\) basamaklı kuyruğu
$$t_6=71938082726$$
olur. Bu kelimenin bir sonraki sözlük sıralı permütasyonu
$$71938082726\to 71938082762$$
olduğundan
$$\Delta(t_6)=71938082762-71938082726=36$$
çıkar. Dolayısıyla
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762$$
olur. Daha sonraki bütün büyük terimlerde aynı yerel düzeltme kuralı tekrar kullanılır. Ek bir kontrol noktası olarak
$$U(10)\equiv 543870437\pmod p$$
eşitliği de sağlanır.
C++, Python ve Java uygulamaları önce \(n=1,\dots,5\) için tam katkıları doğrudan hesaplar; çünkü bu değerler hâlâ ondalık next-permutation işlemi için yeterince küçüktür. Sonra \(x_{n+1}=x_n^2+2\pmod p\) yörüngesini kurarlar, ilk tekrarı bulduklarında dururlar ve ön ek toplamlarını saklarlar. Böylece kalıntı dizisinin herhangi bir aralık toplamı sabit ek işlemle bulunabilir.
Daha sonra uygulama doldurulmuş kuyruk \(00002090918\)'den başlar, yinelemeyi modulo \(10^{11}\) altında ilerletir, her adımda \(11\) basamaklı next-permutation farkını hesaplar ve tam bir yörünge toplamı \(D\) biriktirir. Sonrasında bölüm-kalan ayrımı, bu tek dönem toplamını \(n=6\) ile \(n=10^{16}\) arasındaki bütün terimlere genişletir.
C++ uygulaması ayrıca açık doğrulamalar yapar. \(U(10)\)'un tam değerini kontrol eder, ilk büyük terimlerde ayrışımı tam büyük tamsayı değerleriyle karşılaştırır ve kuyruğun tam olarak \(L_{\text{tail}}\) adım sonra başlangıç durumuna döndüğünü sınar. Python ve Java uygulamaları aynı matematiksel ayrışımı kullanır, ancak bu açık assertion'ları içermez.
Modulo \(p\) yörüngesi \(\mu+\lambda=61264\) durum saklar; bu aşamanın zaman ve bellek maliyeti \(O(\mu+\lambda)\)'dır. Baskın maliyet, uzunluğu \(L_{\text{tail}}=15625000\) olan tek bir kuyruk turu ve en fazla bir kısa artık turudur. Toplam karmaşıklık
$$O(\mu+\lambda+L_{\text{tail}})$$
zaman ve
$$O(\mu+\lambda)$$
bellektir.
Asıl kazanç şudur: yöntem, \(n\) değeri \(10^{16}\) mertebesindeyken \(a_n\)'leri açıkça üretmeye hiç kalkışmaz ve astronomik büyüklükteki tam sayılar üzerinde doğrudan ondalık next permutation çalıştırmaz.
Sea \(\operatorname{nextPerm}(m)\) el entero más pequeño estrictamente mayor que \(m\) que usa exactamente los mismos dígitos decimales que \(m\). Si no existe una disposición mayor, el valor es \(0\). La sucesión del problema es
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
y hay que calcular
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
Los primeros valores todavía se pueden escribir explícitamente:
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
Después de eso los enteros exactos crecen demasiado deprisa. Por eso las implementaciones solo siguen dos proyecciones finitas de la sucesión: \(a_n \bmod (10^9+7)\) y los últimos \(11\) dígitos decimales de \(a_n\).
La solución descansa sobre una descomposición muy específica de este problema. Para \(n\) grande, la siguiente permutación mayor de los dígitos de \(a_n\) se obtiene dejando intacto el prefijo decimal alto y modificando solo las últimas \(11\) posiciones. Así, una operación decimal gigantesca se separa en una órbita modular y en una pequeña corrección de cola de anchura fija.
Los primeros cinco términos pueden tratarse exactamente. Sus siguientes permutaciones mayores son
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
Por tanto,
$$U(5)=0+0+83+1464+2090981=2092528.$$
La dificultad real empieza en \(a_6\). A partir de ahí, calcular \(\operatorname{nextPerm}(a_n)\) sobre la expansión decimal completa deja de ser viable si el intervalo llega hasta \(10^{16}\).
Escribimos
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
Aquí \(t_n\) no se interpreta solo como entero, sino como una palabra decimal de exactamente \(11\) dígitos, con ceros a la izquierda cuando haga falta. Eso importa porque el algoritmo de next permutation actúa sobre posiciones de dígitos, y esos ceros iniciales también ocupan posiciones.
Definimos
$$x_n\equiv a_n\pmod p.$$
Entonces la recurrencia original se convierte inmediatamente en
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$
En el punto de corte, la cola rellenada es
$$t_5=00002090918.$$
Así, después del prefijo pequeño, toda la evolución relevante ocurre dentro de los anillos finitos módulo \(p\) y módulo \(10^{11}\).
Para la órbita relevante en este problema, las implementaciones explotan la invariante de que, desde \(n\ge 6\), el pivote, el intercambio y la inversión del sufijo del procedimiento usual de next permutation ocurren por completo dentro de las últimas \(11\) posiciones decimales. Si \(\operatorname{nextPerm}_{11}(t)\) denota la siguiente permutación lexicográfica de la palabra decimal de \(11\) dígitos \(t\), definimos
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$
Bajo esa invariante,
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$
Por consiguiente,
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
Esta es la simplificación decisiva: la enorme operación decimal se sustituye por un término modular \(x_n\) y una corrección pequeña \(\Delta(t_n)\). La implementación en C++ contrasta esta identidad con valores exactos de enteros grandes para \(n=6,\dots,15\), y el barrido completo de la cola confirma además que cada cola visitada en la órbita sí admite una siguiente permutación lexicográfica válida.
Sea
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$
Entonces, para \(N\ge 6\),
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$
Después de los primeros cinco términos solo quedan dos sumas largas: una sobre la órbita módulo \(p\) y otra sobre las correcciones de cola.
La transformación \(x\mapsto x^2+2 \pmod p\) actúa sobre un conjunto finito de estados, así que la órbita que parte de \(x_0=0\) termina entrando en un ciclo. Las implementaciones encuentran
$$\mu=39911,\qquad \lambda=21353,$$
donde \(\mu\) es la longitud preperiódica y \(\lambda\) la longitud del ciclo. Si definimos
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j},$$
entonces para todo \(n\ge \mu\), con
$$r=(n-\mu+1)\bmod\lambda,$$
se cumple
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$
Eso convierte \(\sum_{n=6}^{N}x_n\) en una consulta de suma prefija sobre una única órbita precomputada.
La sucesión de colas también vive en un espacio finito. Empezando en \(t_5=00002090918\), las implementaciones iteran
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
y usan el hecho de que la órbita relevante tiene longitud
$$L_{\text{tail}}=15625000=8\cdot 5^9.$$
Después de exactamente \(L_{\text{tail}}\) pasos, la cola vuelve a \(t_5\). Si
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
y
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$
entonces
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$
Este es el segundo paso de compresión: una suma sobre casi \(10^{16}\) índices se reduce a una suma sobre un ciclo completo y a una suma residual.
La transición de \(a_5\) a \(a_6\) muestra claramente el mecanismo. Tenemos
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
y luego
$$a_6=a_5^2+2=4371938082726.$$
Su cola de \(11\) dígitos es
$$t_6=71938082726.$$
La siguiente permutación lexicográfica de esa palabra es
$$71938082726\to 71938082762,$$
por lo que
$$\Delta(t_6)=71938082762-71938082726=36.$$
Por tanto,
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$
La misma regla local se reutiliza para todos los términos grandes posteriores. Como punto de control adicional, también se cumple
$$U(10)\equiv 543870437\pmod p.$$
Las implementaciones en C++, Python y Java calculan primero las contribuciones exactas para \(n=1,\dots,5\), porque esos valores todavía permiten hacer next permutation directamente en decimal. Después construyen la órbita de \(x_{n+1}=x_n^2+2\pmod p\), se detienen al encontrar el primer estado repetido y guardan sumas prefijas, de modo que cualquier suma por intervalo de la sucesión residual pueda responderse con tiempo constante adicional.
Luego la implementación arranca en la cola rellenada \(00002090918\), avanza la recurrencia módulo \(10^{11}\), calcula en cada paso el delta de next permutation de \(11\) dígitos y acumula una suma total \(D\) sobre una órbita completa. Una descomposición por cociente y resto expande esa contribución de un solo ciclo a todos los índices comprendidos entre \(n=6\) y \(n=10^{16}\).
La implementación en C++ añade además verificaciones explícitas. Comprueba el valor exacto de \(U(10)\), compara la descomposición con valores exactos de enteros grandes para los primeros términos del régimen grande y verifica que la cola vuelva al punto inicial tras exactamente \(L_{\text{tail}}\) pasos. Las implementaciones en Python y Java siguen la misma descomposición matemática, pero no incluyen esas aserciones de forma explícita.
La órbita módulo \(p\) almacena \(\mu+\lambda=61264\) estados, así que esa fase cuesta \(O(\mu+\lambda)\) en tiempo y memoria. El trabajo dominante es el barrido completo de la cola de longitud \(L_{\text{tail}}=15625000\), más como mucho un barrido residual más corto. En conjunto, la complejidad total es
$$O(\mu+\lambda+L_{\text{tail}})$$
en tiempo y
$$O(\mu+\lambda)$$
en memoria.
La ventaja práctica es enorme: el método nunca intenta materializar \(a_n\) cuando \(n\) está cerca de \(10^{16}\), ni aplicar next permutation decimal a enteros astronómicamente grandes.
定义 \(\operatorname{nextPerm}(m)\) 为所有“严格大于 \(m\) 且十进制数字与 \(m\) 完全相同”的整数中最小的那个；如果不存在更大的数字重排，则其值记为 \(0\)。本题中的序列满足
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
需要计算
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
前几项仍然可以直接写出：
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
从这里开始，精确整数的位数暴涨，直接在完整十进制表示上做运算已经不现实。实现因此只保留这个序列的两个有限状态投影：\(a_n \bmod (10^9+7)\) 与 \(a_n\) 的最后 \(11\) 位十进制数字。
本题的核心不是去构造巨大的 \(a_n\)，而是抓住一个专门针对这条递推轨道的分解。从足够大的项开始，\(\operatorname{nextPerm}(a_n)\) 的变化只发生在最后 \(11\) 位十进制尾部，高位前缀保持不变。于是一个原本作用于超大整数的十进制排列问题，被拆成了一个模意义上的主项和一个固定宽度的尾部修正。
前五项可以完全精确地处理。它们的下一个更大数字排列分别是
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
因此
$$U(5)=0+0+83+1464+2090981=2092528.$$
真正的困难从 \(a_6\) 开始。因为从这一项起，若还想在完整十进制整数上反复执行 next permutation，并且把求和范围一直推到 \(10^{16}\)，计算上就完全不可行了。
设
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
这里的 \(t_n\) 不能只当作普通整数，而必须视为长度恰好为 \(11\) 的十进制数字串；必要时前面补零。这样做很重要，因为 next permutation 算法操作的是“数字位置”，前导零同样占据位置。
再定义
$$x_n\equiv a_n\pmod p.$$
那么原始递推立刻给出
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$
在分界点处，补零后的尾部为
$$t_5=00002090918.$$
也就是说，小前缀之后的全部推进都可以在模 \(p\) 与模 \(10^{11}\) 的有限环中完成。
对于本题实际访问到的轨道，实现所利用的关键不变量是：从 \(n\ge 6\) 起，标准 next permutation 过程中的主元查找、交换以及后缀翻转都完全落在最后 \(11\) 位十进制位置内。若把 \(t\) 看成一个 \(11\) 位数字串，并记它的下一个字典序排列为 \(\operatorname{nextPerm}_{11}(t)\)，定义
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$
在这一不变量下，便有
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$
因此
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
这就是整道题最关键的专门化简：原本巨大的十进制重排，被压缩成模 \(p\) 下的项 \(x_n\) 与一个很小的尾部差值 \(\Delta(t_n)\)。C++ 实现把这条恒等式与 \(n=6,\dots,15\) 的精确大整数结果逐项比对；完整的尾部遍历还进一步确认，轨道上访问到的每一个 \(11\) 位尾部都确实存在下一字典序排列。
记
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$
那么当 \(N\ge 6\) 时，总和可以写成
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$
这样一来，在小前缀之后就再也不需要精确构造整个 \(a_n\) 了。问题只剩下两件事：求模 \(p\) 下轨道 \(x_n\) 的长区间和，以及求尾部修正 \(\Delta(t_n)\) 的长区间和。
由于映射 \(x\mapsto x^2+2 \pmod p\) 运行在有限状态集合上，所以从 \(x_0=0\) 出发的轨道最终一定进入循环。程序实际找到的结构是
$$\mu=39911,\qquad \lambda=21353,$$
其中 \(\mu\) 是前导非循环长度，\(\lambda\) 是循环节长度。定义前缀和
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j}.$$
再令
$$r=(n-\mu+1)\bmod\lambda,$$
则对任意 \(n\ge \mu\) 都有
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$
因此 \(\sum_{n=6}^{N}x_n\) 只需要在一条预处理好的轨道上做前缀和查询即可。
尾部序列同样处在有限状态空间里。从 \(t_5=00002090918\) 出发，实现在模 \(10^{11}\) 下迭代
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
并利用这样一个事实：相关轨道的长度为
$$L_{\text{tail}}=15625000=8\cdot 5^9.$$
恰好经过 \(L_{\text{tail}}\) 步后，尾部回到 \(t_5\)。若定义
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
再把项数拆成
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$
便得到
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$
这一步把近 \(10^{16}\) 项的尾部修正和压缩成“一次完整周期 + 一段余数”的计算。
从 \(a_5\) 到 \(a_6\) 的过渡最能说明问题。我们有
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
并且
$$a_6=a_5^2+2=4371938082726.$$
它的 \(11\) 位尾部是
$$t_6=71938082726.$$
这个 \(11\) 位数字串的下一个字典序排列为
$$71938082726\to 71938082762,$$
因此
$$\Delta(t_6)=71938082762-71938082726=36.$$
所以
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$
之后所有大项都复用这条“局部尾部修正”规则。作为额外检查点，还满足
$$U(10)\equiv 543870437\pmod p.$$
C++、Python 和 Java 三个实现首先直接计算 \(n=1,\dots,5\) 的精确贡献，因为这几项仍然可以轻松在十进制层面处理。接着它们构造轨道 \(x_{n+1}=x_n^2+2\pmod p\)，在首次出现重复状态时停止，并保存前缀和，这样任何 \(x_n\) 的区间和都能在预处理之后通过常数次算术运算得到。
随后，实现从补零后的尾部 \(00002090918\) 出发，在模 \(10^{11}\) 下推进递推关系，每一步都计算对应的 \(11\) 位 next permutation 差值，并累计得到一整条轨道的总修正 \(D\)。最后利用整除与余数分解，把这一整周期的贡献扩展到所有 \(n=6\) 到 \(n=10^{16}\) 的项。
C++ 实现还包含显式校验。它检查 \(U(10)\) 的精确值，把这种分解与早期大项的精确大整数结果进行比较，并验证尾部经过恰好 \(L_{\text{tail}}\) 步后回到初始状态。Python 与 Java 实现采用同样的数学拆分，但没有写出这些显式断言。
模 \(p\) 轨道的构造会存储 \(\mu+\lambda=61264\) 个状态，因此这一阶段的时间与空间复杂度都是 \(O(\mu+\lambda)\)。主导耗时的是长度为 \(L_{\text{tail}}=15625000\) 的一次完整尾部遍历，以及最多再做一次更短的余数遍历。因此总复杂度为
$$O(\mu+\lambda+L_{\text{tail}})$$
时间和
$$O(\mu+\lambda)$$
空间。
真正的收益在于：算法从不尝试在 \(n\) 接近 \(10^{16}\) 时显式构造完整的 \(a_n\)，也不对天文级的大整数执行十进制 next permutation。
Пусть \(\operatorname{nextPerm}(m)\) обозначает наименьшее целое число, строго большее \(m\), которое использует в точности те же десятичные цифры, что и \(m\). Если более крупной перестановки этих цифр не существует, значение равно \(0\). Последовательность задачи задается так:
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
и требуется вычислить
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
Первые значения еще можно выписать явно:
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
Дальше точные числа растут слишком быстро. Поэтому реализации отслеживают только две конечные проекции последовательности: \(a_n \bmod (10^9+7)\) и последние \(11\) десятичных цифр числа \(a_n\).
Решение основано на одной специальной для этой задачи декомпозиции. Для больших \(n\) следующая большая перестановка цифр числа \(a_n\) получается так: старший десятичный префикс остается неизменным, а перестановка происходит только внутри последних \(11\) позиций. Благодаря этому огромная десятичная операция распадается на модульную орбиту и маленькую хвостовую поправку фиксированной ширины.
Первые пять членов можно обработать полностью точно. Их следующие большие перестановки цифр равны
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
Значит,
$$U(5)=0+0+83+1464+2090981=2092528.$$
Настоящая трудность начинается с \(a_6\): после этого прямое применение next permutation к полной десятичной записи уже непрактично, особенно если суммировать до \(10^{16}\) членов.
Запишем
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
Здесь \(t_n\) рассматривается не просто как число, а как десятичное слово длины ровно \(11\), при необходимости с ведущими нулями. Это важно, потому что алгоритм next permutation работает с позициями цифр, и ведущие нули тоже занимают позиции.
Определим
$$x_n\equiv a_n\pmod p.$$
Тогда из исходной рекурсии сразу следует
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$
На границе перехода дополненный нулями хвост имеет вид
$$t_5=00002090918.$$
После малого префикса вся нужная динамика развивается только в конечных кольцах по модулям \(p\) и \(10^{11}\).
Для орбиты, возникающей в этой задаче, реализации используют инвариант: начиная с \(n\ge 6\), поиск опорной позиции, обмен и разворот суффикса в стандартном алгоритме next permutation полностью происходят внутри последних \(11\) десятичных позиций. Если \(\operatorname{nextPerm}_{11}(t)\) обозначает следующую лексикографическую перестановку \(11\)-значного слова \(t\), то определим
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$
При этом инварианте
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$
Следовательно,
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
Именно это делает задачу вычислимой: гигантская десятичная перестановка заменяется модульным слагаемым \(x_n\) и маленькой поправкой \(\Delta(t_n)\). Реализация на C++ проверяет это равенство на точных больших числах для \(n=6,\dots,15\), а полный обход хвостовой орбиты дополнительно подтверждает, что каждый встреченный \(11\)-значный хвост действительно имеет следующую лексикографическую перестановку.
Обозначим
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$
Тогда при \(N\ge 6\)
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$
После первых пяти членов задача распадается на две длинные суммы: по модульной орбите \(x_n\) и по хвостовым поправкам.
Отображение \(x\mapsto x^2+2 \pmod p\) действует на конечном множестве состояний, поэтому орбита из \(x_0=0\) в конце концов становится периодической. Реализации находят
$$\mu=39911,\qquad \lambda=21353,$$
где \(\mu\) - длина предпериода, а \(\lambda\) - длина цикла. Введем префиксные суммы
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j}.$$
Если
$$r=(n-\mu+1)\bmod\lambda,$$
то для любого \(n\ge \mu\) выполняется
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$
Значит, \(\sum_{n=6}^{N}x_n\) сводится к запросу префиксной суммы на одной заранее вычисленной орбите.
Та же идея конечного пространства состояний работает и для хвостов. Начиная с \(t_5=00002090918\), реализации итерируют
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
и используют тот факт, что нужная орбита имеет длину
$$L_{\text{tail}}=15625000=8\cdot 5^9.$$
Через ровно \(L_{\text{tail}}\) шагов хвост возвращается к \(t_5\). Если положить
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
и затем разложить число членов как
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$
то получаем
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$
Это вторая стадия сжатия: сумма почти по \(10^{16}\) индексам заменяется одной полной циклической суммой и одной остаточной суммой.
Переход от \(a_5\) к \(a_6\) показывает механизм в явном виде. Имеем
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
а затем
$$a_6=a_5^2+2=4371938082726.$$
Его \(11\)-значный хвост равен
$$t_6=71938082726.$$
Следующая лексикографическая перестановка этого слова равна
$$71938082726\to 71938082762,$$
поэтому
$$\Delta(t_6)=71938082762-71938082726=36.$$
Следовательно,
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$
Та же локальная поправка затем используется для всех последующих больших членов. Дополнительной контрольной точкой служит равенство
$$U(10)\equiv 543870437\pmod p.$$
Реализации на C++, Python и Java сначала напрямую вычисляют точные вклады для \(n=1,\dots,5\), потому что эти значения еще можно удобно обработать в десятичной форме. Затем они строят орбиту \(x_{n+1}=x_n^2+2\pmod p\), останавливаются на первом повторном состоянии и сохраняют префиксные суммы, чтобы после предвычисления любую сумму по диапазону для последовательности \(x_n\) получать за константное число арифметических действий.
После этого реализация стартует из дополненного нулями хвоста \(00002090918\), продвигает рекурсию по модулю \(10^{11}\), на каждом шаге вычисляет \(11\)-значную next-permutation-поправку и накапливает сумму \(D\) на одной полной орбите. Затем разложение на частное и остаток переносит вклад этой одной орбиты на все индексы от \(n=6\) до \(n=10^{16}\).
Реализация на C++ дополнительно содержит явные проверки. Она проверяет точное значение \(U(10)\), сравнивает декомпозицию с точными значениями для ранних больших членов и подтверждает, что хвост возвращается к начальному состоянию ровно через \(L_{\text{tail}}\) шагов. Реализации на Python и Java используют ту же математическую схему, но без этих явных утверждений.
Построение орбиты по модулю \(p\) хранит \(\mu+\lambda=61264\) состояний, поэтому этот этап требует \(O(\mu+\lambda)\) времени и памяти. Доминирующая стоимость - один полный проход по хвостовой орбите длины \(L_{\text{tail}}=15625000\), плюс максимум один более короткий остаточный проход. В итоге общая сложность равна
$$O(\mu+\lambda+L_{\text{tail}})$$
по времени и
$$O(\mu+\lambda)$$
по памяти.
Главный выигрыш состоит в том, что метод вообще не пытается явно строить \(a_n\) для \(n\) порядка \(10^{16}\) и не применяет десятичный next permutation к астрономически большим целым.
لتكن \(\operatorname{nextPerm}(m)\) أصغر عدد صحيح أكبر من \(m\) ويستعمل بالضبط الأرقام العشرية نفسها الموجودة في \(m\). وإذا لم توجد إعادة ترتيب أكبر لتلك الأرقام فالقيمة تساوي \(0\). المتتالية في المسألة هي
$$a_0=0,\qquad a_n=a_{n-1}^2+2,$$
والمطلوب حساب
$$U(N)=\sum_{n=1}^{N}\operatorname{nextPerm}(a_n)\pmod{10^9+7},\qquad N=10^{16}.$$
الحدود الأولى ما زالت قابلة للعرض الصريح:
$$a_1=2,\quad a_2=6,\quad a_3=38,\quad a_4=1446,\quad a_5=2090918,\quad a_6=4371938082726.$$
بعد ذلك تكبر الأعداد الدقيقة بسرعة هائلة. لذلك تتعقب التطبيقات إسقاطين فقط من هذه المتتالية: \(a_n \bmod (10^9+7)\) وآخر \(11\) رقماً عشرياً من \(a_n\).
جوهر الحل هو تفكيك خاص بهذه المسألة. عندما تصبح \(n\) كبيرة، فإن \(\operatorname{nextPerm}(a_n)\) ينتج من إبقاء المقدمة العشرية العليا ثابتة وتغيير آخر \(11\) خانة فقط. وبذلك تتحول عملية عشرية هائلة إلى مجموع مدار معياري وتصحيح صغير ثابت العرض في الذيل.
أول خمسة حدود يمكن التعامل معها بدقة كاملة. وإعادات الترتيب الأكبر التالية لأرقامها هي
$$\operatorname{nextPerm}(2)=0,\qquad \operatorname{nextPerm}(6)=0,\qquad \operatorname{nextPerm}(38)=83,$$
$$\operatorname{nextPerm}(1446)=1464,\qquad \operatorname{nextPerm}(2090918)=2090981.$$
ومن ثم
$$U(5)=0+0+83+1464+2090981=2092528.$$
الصعوبة الحقيقية تبدأ عند \(a_6\)، لأن تنفيذ next permutation مباشرة على التمثيل العشري الكامل ثم جمع \(10^{16}\) حدًا لم يعد عملياً إطلاقاً.
نكتب
$$p=10^9+7,\qquad a_n=10^{11}q_n+t_n,\qquad 0\le t_n<10^{11}.$$
وهنا لا يُنظر إلى \(t_n\) على أنه عدد فقط، بل على أنه كلمة عشرية من \(11\) خانة بالضبط، مع إضافة أصفار بادئة عند الحاجة. وهذا مهم لأن خوارزمية next permutation تعمل على مواضع الأرقام نفسها، والأصفار البادئة تشارك في تلك المواضع.
ولنعرّف
$$x_n\equiv a_n\pmod p.$$
فعندئذ نحصل فوراً من العلاقة الأصلية على
$$x_{n+1}\equiv x_n^2+2\pmod p,\qquad t_{n+1}\equiv t_n^2+2\pmod{10^{11}}.$$
وعند نقطة الفصل يكون الذيل بعد التصفير البادئ
$$t_5=00002090918.$$
وهكذا تنتقل كل الحسابات اللاحقة إلى حلقتين منتهيتين: modulo \(p\) وmodulo \(10^{11}\).
الثابت الحاسم الذي تعتمد عليه التطبيقات لهذه المدار هو أنه ابتداءً من \(n\ge 6\)، فإن البحث عن المحور ثم التبديل ثم قلب اللاحقة في خوارزمية next permutation القياسية يقع كله داخل آخر \(11\) خانة عشرية. إذا رمزنا بـ \(\operatorname{nextPerm}_{11}(t)\) إلى الترتيب المعجمي التالي للكلمة العشرية ذات \(11\) خانة \(t\)، فنعرف
$$\Delta(t)=\operatorname{nextPerm}_{11}(t)-t.$$
وعندئذ، تحت هذا الثابت،
$$\operatorname{nextPerm}(a_n)=10^{11}q_n+\operatorname{nextPerm}_{11}(t_n)=a_n+\Delta(t_n)\qquad (n\ge 6).$$
ومن ثم
$$\operatorname{nextPerm}(a_n)\equiv x_n+\Delta(t_n)\pmod p.$$
هذه هي الخطوة الحاسمة التي تجعل المسألة قابلة للحساب: العملية العشرية العملاقة تُختزل إلى حد معياري \(x_n\) وتصحيح صغير \(\Delta(t_n)\). وتقوم نسخة C++ بمقارنة هذه الهوية مع قيم صحيحة ضخمة دقيقة عندما \(n=6,\dots,15\)، كما يؤكد المسح الكامل للذيل أن كل ذيل يظهر على المدار يملك فعلاً ترتيباً معجمياً تالياً صالحاً.
لنعرّف
$$S_{\text{small}}(N)=\sum_{n=1}^{\min\{N,5\}}\operatorname{nextPerm}(a_n).$$
فعندما \(N\ge 6\) يصبح
$$U(N)\equiv S_{\text{small}}(N)+\sum_{n=6}^{N}x_n+\sum_{n=6}^{N}\Delta(t_n)\pmod p.$$
أي إننا بعد المقدمة القصيرة لم نعد بحاجة إلى بناء \(a_n\) بدقة كاملة. المطلوب فقط مجموع طويل على المدار المعياري \(x_n\)، ومجموع طويل آخر على تصحيحات الذيول.
بما أن التحويل \(x\mapsto x^2+2 \pmod p\) يعمل على فضاء حالات منتهٍ، فلا بد أن يدخل مدار البداية \(x_0=0\) في دورة في النهاية. وتجد التطبيقات
$$\mu=39911,\qquad \lambda=21353,$$
حيث \(\mu\) طول الجزء السابق للدورة و\(\lambda\) طول الدورة نفسها. ولنعرّف المجاميع التراكمية
$$P(n)=\sum_{k=0}^{n}x_k,\qquad C=\sum_{j=0}^{\lambda-1}x_{\mu+j}.$$
وإذا وضعنا
$$r=(n-\mu+1)\bmod\lambda,$$
فإنه لكل \(n\ge \mu\) لدينا
$$P(n)\equiv P(\mu-1)+\left\lfloor\frac{n-\mu+1}{\lambda}\right\rfloor C+\sum_{j=0}^{r-1}x_{\mu+j}\pmod p.$$
وهكذا يتحول \(\sum_{n=6}^{N}x_n\) إلى استعلام مجموعات تراكمية على مدار واحد محسوب مسبقاً.
الفكرة نفسها تنطبق على الذيول. انطلاقاً من \(t_5=00002090918\)، فإن التطبيقات تطور التراجع
$$t_{n+1}\equiv t_n^2+2\pmod{10^{11}}$$
وتستعمل أن المدار المناسب طوله
$$L_{\text{tail}}=15625000=8\cdot 5^9.$$
وبعد \(L_{\text{tail}}\) خطوة تماماً يعود الذيل إلى \(t_5\). وإذا عرفنا
$$D=\sum_{i=0}^{L_{\text{tail}}-1}\Delta(t_{6+i})\pmod p,$$
ثم كتبنا
$$Q=\left\lfloor\frac{N-5}{L_{\text{tail}}}\right\rfloor,\qquad R=(N-5)\bmod L_{\text{tail}},$$
فإن
$$\sum_{n=6}^{N}\Delta(t_n)\equiv QD+\sum_{i=0}^{R-1}\Delta(t_{6+i})\pmod p.$$
وهذه هي خطوة الضغط الثانية: مجموع يمتد تقريباً حتى \(10^{16}\) حدًا يُستبدل بمجموع دورة كاملة ومجموع بقايا.
الانتقال من \(a_5\) إلى \(a_6\) يوضح الآلية مباشرة. لدينا
$$a_5=2090918,\qquad \operatorname{nextPerm}(a_5)=2090981,$$
ثم
$$a_6=a_5^2+2=4371938082726.$$
وذيله المؤلف من \(11\) خانة هو
$$t_6=71938082726.$$
والترتيب المعجمي التالي لهذه الكلمة هو
$$71938082726\to 71938082762,$$
ولذلك
$$\Delta(t_6)=71938082762-71938082726=36.$$
ومن ثم
$$\operatorname{nextPerm}(a_6)=a_6+36=4371938082762.$$
والقاعدة المحلية نفسها تُستعمل بعد ذلك لكل الحدود الكبيرة. وكقيمة تحقق إضافية نجد أيضاً
$$U(10)\equiv 543870437\pmod p.$$
تقوم تطبيقات C++ وPython وJava أولاً بحساب المساهمات الدقيقة للحدود \(n=1,\dots,5\) مباشرة، لأن هذه القيم ما زالت صغيرة بما يكفي لمعالجة next permutation على صورتها العشرية. بعد ذلك تبني المدار \(x_{n+1}=x_n^2+2\pmod p\)، وتتوقف عند أول حالة مكررة، وتخزن المجاميع التراكمية بحيث يمكن بعد التهيئة استخراج أي مجموع على مجال من حدود \(x_n\) بعمليات حسابية ثابتة العدد.
بعد ذلك تبدأ الشيفرة من الذيل المصفّر \(00002090918\)، وتطوّر التراجع modulo \(10^{11}\)، وتحسب في كل خطوة فرق next permutation ذي \(11\) خانة، ثم تجمع قيمة \(D\) على مدار كامل واحد. وبعدها يُستعمل تحليل القسمة إلى خارج وباقٍ لتوسيع مساهمة ذلك المدار الواحد إلى جميع الحدود من \(n=6\) حتى \(n=10^{16}\).
تضيف نسخة C++ فحوصاً صريحة أيضاً. فهي تتحقق من القيمة الدقيقة لـ \(U(10)\)، وتقارن هذا التفكيك مع قيم دقيقة للحدود الكبيرة الأولى، وتؤكد أن الذيل يعود إلى حالته الابتدائية بعد \(L_{\text{tail}}\) خطوة بالضبط. أما نسختا Python وJava فتتبعان التفكيك الرياضي نفسه لكن من دون هذه assertions الصريحة.
يبني المدار المعياري modulo \(p\) عددًا قدره \(\mu+\lambda=61264\) من الحالات المخزنة، ولذلك تكلف هذه المرحلة زمناً وذاكرة من الرتبة \(O(\mu+\lambda)\). أما الكلفة المسيطرة فهي المسح الكامل لمدار الذيل بطول \(L_{\text{tail}}=15625000\)، مع احتمال وجود مسح باقٍ أقصر منه. ومن ثم فالتعقيد الكلي هو
$$O(\mu+\lambda+L_{\text{tail}})$$
زمنياً و
$$O(\mu+\lambda)$$
مكانياً.
والفائدة الجوهرية هنا أن الطريقة لا تحاول أبداً بناء \(a_n\) صراحةً عندما يكون \(n\) بحجم \(10^{16}\)، ولا تطبق next permutation العشري على أعداد فلكية الحجم.