Let \(f(n,m)\) denote the number of constrained permutations of sizes \(0,1,\dots,n\) whose inversion count is at most \(m\). The task in Problem 631 is to evaluate
$$f(10^{18},40)\pmod{10^9+7}.$$
A direct enumeration is hopeless: the length bound is astronomically large, and even the unrestricted number of permutations grows far too quickly. The successful approach is to build permutations incrementally, keep only the structural data that still affects future insertions, and use the fact that the process stabilizes once the length is slightly larger than the inversion budget.
The C++, Python, and Java implementations all use the same idea: grow a valid permutation by inserting the new maximum element and summarize every partial permutation by a compact DP state.
Suppose a valid constrained permutation of length \(\ell-1\) has already been formed. To obtain length \(\ell\), insert the value \(\ell\). The implementations parameterize this insertion by the number \(i\) of new inversions created at that step, so
$$0 \le i \le \ell-1.$$
If the remaining inversion budget before insertion is \(r\), then after using contribution \(i\) it becomes
$$r' = r-i.$$
Therefore every legal transition must satisfy \(i \le r\), and the raw upper bound is always
$$i \lt \min(r+1,\ell).$$
This observation turns the inversion condition into a local update rule.
When the new maximum is inserted, the relative order of all older entries stays unchanged. So any newly created forbidden configuration must involve the new maximum itself. That means the entire past can be compressed into two integers in addition to the remaining budget \(r\):
\(a\), the smallest future inversion contribution still allowed by the 132-type restriction;
\(b\), a switching threshold that separates the two structural cases induced by the 21-type restriction.
A partial permutation is therefore represented by the triple
$$ (r,a,b). $$
Two partial permutations with the same triple have the same legal future extensions, so there is no need to store the full permutation explicitly.
At length \(\ell\), a state \((r,a,b)\) may choose any
$$a \le i \lt \min(r+1,\ell).$$
The next state is determined by whether the chosen insertion contribution lies before or after the threshold \(b\):
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
The first branch tightens the future lower bound and shifts the threshold one step to the right. The second branch preserves the current lower bound and replaces the threshold by the chosen contribution. These two cases are the full combinatorial engine of the solver.
Let \(S_\ell(m)\) be the number of valid constrained permutations of exact length \(\ell\) with inversion budget \(m\). After \(\ell\) insertion steps, the DP layer stores exactly these objects, partitioned by state. Since each legal transition creates exactly one valid permutation of the next length, the cumulative quantity required by the problem is
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$$
where the initial \(1\) is the empty permutation. The running total maintained by the implementations is precisely this cumulative count.
The remaining budget always satisfies \(0 \le r \le m\), so \(i\) can never exceed \(m\). Once
$$\ell \ge m+2,$$
the length cap is irrelevant, because \(\min(r+1,\ell)=r+1\). From that point onward, the transition rules depend only on the finite state \((r,a,b)\), not on the actual value of \(\ell\). The exact-length counts therefore enter a stable regime in which each additional length contributes the same amount \(g\) modulo \(10^9+7\). Thus
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
The C++, Python, and Java implementations use this cutoff, and the C++ implementation also performs an explicit one-step check that the layer total has stabilized at the boundary.
If \(m=0\), then every insertion must use
$$i=0.$$
So each length has exactly one legal extension: the new maximum is inserted in the unique way that creates no new inversions. Therefore
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
and hence
$$f(n,0)=1+n.$$
In particular,
$$f(2,0)=3,$$
which matches the checkpoint used by the implementations. The same implementations also reproduce the additional checks \(f(4,5)=32\) and \(f(10,25)=294400\).
The implementation fixes the modulus \(10^9+7\), the target budget \(m=40\), and the target length \(n=10^{18}\). It stores the DP over triples \((r,a,b)\) in flattened arrays, using one array for the current layer and one for the next. The initial layer contains only the empty permutation with full remaining budget and neutral structural boundaries.
For each length from \(1\) through \(\min(n,m+2)\), the implementation scans every reachable state, enumerates every admissible value of \(i\), adds the state count to the cumulative answer, and sends that count to the next state dictated by the two-branch transition rule. All arithmetic is reduced modulo \(10^9+7\).
If \(n \le m+2\), this explicit DP already yields the final answer. Otherwise the implementation sums the stabilized last layer to obtain \(g\), then appends the linear tail \((n-(m+2))g\) modulo \(10^9+7\). The C++ implementation additionally computes one more layer to confirm that the stabilized layer total is unchanged.
The remaining-budget coordinate has \(m+1\) possibilities, and each structural boundary ranges over \(O(m)\) values after the process is truncated at length \(m+2\). So the DP uses \(O(m^3)\) states and \(O(m^3)\) memory. For one fixed layer, each state can try up to \(O(m)\) insertion contributions, giving a straightforward worst-case bound of \(O(m^4)\) work per layer. Since only \(O(m)\) layers are processed explicitly, the overall worst-case time bound is \(O(m^5)\). With \(m=40\), this is easily practical, and after stabilization the dependence on the huge parameter \(n\) drops to \(O(1)\).
Sei \(f(n,m)\) die Anzahl der eingeschränkten Permutationen der Größen \(0,1,\dots,n\), deren Inversionszahl höchstens \(m\) ist. In Problem 631 soll
$$f(10^{18},40)\pmod{10^9+7}$$
berechnet werden. Eine direkte Aufzählung ist aussichtslos: Die Längenschranke ist riesig, und schon ohne Zusatzbedingungen wächst die Zahl der Permutationen viel zu schnell. Deshalb konstruiert die Lösung die Permutationen schrittweise, speichert nur die noch relevante Struktur und nutzt aus, dass sich der Prozess kurz nach der Budgetgrenze stabilisiert.
Die C++-, Python- und Java-Implementierungen verwenden denselben Kern: Eine gültige Permutation wird erzeugt, indem jeweils das neue Maximum eingefügt wird, und jede partielle Permutation wird durch einen kompakten DP-Zustand beschrieben.
Angenommen, eine gültige eingeschränkte Permutation der Länge \(\ell-1\) ist bereits konstruiert. Um Länge \(\ell\) zu erhalten, wird der Wert \(\ell\) eingefügt. Die Implementierungen parametrisieren diesen Schritt durch die Zahl \(i\) der neu entstehenden Inversionen, also
$$0 \le i \le \ell-1.$$
Ist \(r\) das verbleibende Inversionsbudget vor dem Einfügen, dann gilt danach
$$r' = r-i.$$
Jeder gültige Übergang muss also \(i \le r\) erfüllen, und die rohe Obergrenze lautet stets
$$i \lt \min(r+1,\ell).$$
Damit wird die Inversionsbedingung zu einer lokalen Aktualisierungsvorschrift.
Beim Einfügen des neuen Maximums bleibt die relative Reihenfolge aller älteren Elemente unverändert. Deshalb muss jede neu entstehende verbotene Konfiguration das neue Maximum enthalten. Genau das erlaubt es, die gesamte Vergangenheit in zwei zusätzlichen Ganzzahlen neben \(r\) zusammenzufassen:
\(a\), der kleinste zukünftige Inversionsbeitrag, der unter der 132-artigen Bedingung noch zulässig ist;
\(b\), eine Schaltschwelle, die die beiden durch die 21-artige Bedingung bestimmten Strukturfälle trennt.
Ein partielles Objekt wird also durch
$$ (r,a,b) $$
repräsentiert. Zwei partielle Permutationen mit demselben Tripel besitzen dieselben zulässigen Fortsetzungen; die vollständige Permutation muss deshalb nicht gespeichert werden.
Bei Länge \(\ell\) darf ein Zustand \((r,a,b)\) jedes
$$a \le i \lt \min(r+1,\ell)$$
wählen. Der Folgezustand hängt davon ab, ob der gewählte Inversionsbeitrag vor oder nach der Schwelle \(b\) liegt:
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
Im ersten Fall wird die zukünftige Untergrenze verschärft und die Schwelle um eins nach rechts verschoben. Im zweiten Fall bleibt die Untergrenze erhalten, während die Schwelle durch den gewählten Beitrag ersetzt wird. Diese beiden Formeln bilden den gesamten kombinatorischen Kern des Lösers.
Sei \(S_\ell(m)\) die Anzahl gültiger eingeschränkter Permutationen exakter Länge \(\ell\) bei Inversionsbudget \(m\). Nach \(\ell\) Einfügeschritten enthält die DP-Schicht genau diese Objekte, aufgeteilt nach Zuständen. Da jeder zulässige Übergang genau eine gültige Permutation der nächsten Länge erzeugt, ist die gesuchte kumulative Größe
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$$
wobei die anfängliche \(1\) die leere Permutation zählt. Die laufende Summe in den Implementierungen ist genau dieser kumulative Wert.
Das Restbudget erfüllt immer \(0 \le r \le m\), also kann \(i\) niemals größer als \(m\) sein. Sobald
$$\ell \ge m+2,$$
spielt die Längenbeschränkung keine Rolle mehr, denn dann ist \(\min(r+1,\ell)=r+1\). Von diesem Zeitpunkt an hängen die Übergänge nur noch vom endlichen Zustand \((r,a,b)\) ab, nicht mehr vom aktuellen \(\ell\). Die Zahlen exakter Länge gelangen daher in ein stabiles Regime, in dem jede zusätzliche Länge denselben Beitrag \(g\) modulo \(10^9+7\) liefert. Also gilt
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
Die drei Implementierungen verwenden genau diesen Schnitt, und die C++-Implementierung überprüft zusätzlich mit einer weiteren Schicht, dass die Schichtsumme am Rand bereits stabil ist.
Für \(m=0\) muss bei jedem Schritt
$$i=0$$
gelten. Damit besitzt jede Länge genau eine zulässige Fortsetzung: Das neue Maximum wird auf die einzige Weise eingefügt, die keine neue Inversion erzeugt. Somit
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
und daher
$$f(n,0)=1+n.$$
Insbesondere ist
$$f(2,0)=3,$$
genau wie im kleinen Prüfwert der Implementierungen. Dieselben Implementierungen reproduzieren auch die weiteren Kontrollwerte \(f(4,5)=32\) und \(f(10,25)=294400\).
Die Implementierung fixiert das Modulo \(10^9+7\), das Zielbudget \(m=40\) und die Ziellänge \(n=10^{18}\). Die DP über den Tripeln \((r,a,b)\) wird in abgeflachten Arrays gespeichert; ein Array enthält die aktuelle Schicht, ein zweites die nächste. Die Anfangsschicht besteht nur aus der leeren Permutation mit vollem Restbudget und neutralen Strukturgrenzen.
Für jede Länge von \(1\) bis \(\min(n,m+2)\) durchläuft die Implementierung alle erreichbaren Zustände, probiert alle zulässigen Werte \(i\), addiert die Zustandsanzahl zur kumulativen Antwort und überträgt dieselbe Anzahl in den durch die Zweigregel bestimmten Folgezustand. Jede Rechnung erfolgt modulo \(10^9+7\).
Falls \(n \le m+2\), liefert diese explizite DP bereits die Endantwort. Andernfalls summiert die Implementierung die stabilisierte letzte Schicht zu \(g\) und ergänzt dann den linearen Schwanz \((n-(m+2))g\) modulo \(10^9+7\). Die C++-Implementierung berechnet zusätzlich noch eine weitere Schicht, um zu prüfen, dass diese Schichtsumme unverändert bleibt.
Die Koordinate für das Restbudget hat \(m+1\) Möglichkeiten, und jede der beiden Strukturgrenzen nimmt nach dem Abschneiden bei \(m+2\) nur \(O(m)\) Werte an. Damit verwendet die DP \(O(m^3)\) Zustände und \(O(m^3)\) Speicher. In einer festen Schicht kann jeder Zustand bis zu \(O(m)\) verschiedene Einfügebeiträge ausprobieren; daraus folgt die einfache Worst-Case-Schranke \(O(m^4)\) Arbeit pro Schicht. Da nur \(O(m)\) Schichten explizit verarbeitet werden, ergibt sich insgesamt \(O(m^5)\) Zeit. Für \(m=40\) ist das problemlos praktikabel, und nach der Stabilisierung reduziert sich die Abhängigkeit vom riesigen Parameter \(n\) auf \(O(1)\).
\(f(n,m)\), boyutları \(0,1,\dots,n\) arasında olan ve inversion sayısı en fazla \(m\) olan kısıtlı permütasyonların sayısı olsun. Problem 631'de istenen değer
$$f(10^{18},40)\pmod{10^9+7}.$$
Doğrudan sayım mümkün değildir: uzunluk sınırı astronomiktir ve ek kısıtlar olmasa bile permütasyon sayısı çok hızlı büyür. Bu yüzden çözüm, permütasyonları adım adım kurar, geleceği etkilemeye devam eden yapısal bilgiyi küçük bir durumda toplar ve süreç inversion bütçesinin biraz ötesinde sabitlendiği anda doğrusal bir kuyruğa geçer.
C++, Python ve Java uygulamalarının ortak fikri şudur: her geçerli permütasyon, yeni maksimum eleman eklenerek büyütülür ve her ara nesne sıkıştırılmış bir DP durumu ile temsil edilir.
Uzunluğu \(\ell-1\) olan geçerli bir kısıtlı permütasyonun hazır olduğunu düşünelim. Uzunluğu \(\ell\) yapmak için değer \(\ell\) eklenir. Uygulamalar bu eklemeyi, o adımda oluşan yeni inversion sayısı \(i\) ile parametreler:
$$0 \le i \le \ell-1.$$
Eklemeden önce kalan inversion bütçesi \(r\) ise, bu seçimden sonra
$$r' = r-i$$
olur. Dolayısıyla her geçişte \(i \le r\) gerekir ve doğal üst sınır
$$i \lt \min(r+1,\ell)$$
şeklindedir. Böylece inversion koşulu yerel bir güncelleme kuralına dönüşür.
Yeni maksimum eklendiğinde daha eski elemanların kendi aralarındaki göreli sırası değişmez. Bu yüzden yeni oluşabilecek yasak yapıların hepsi mutlaka yeni maksimumu içerir. Uygulamalar bu gözlem sayesinde, kalan bütçe \(r\)'ye ek olarak yalnızca iki tamsayı saklar:
\(a\), 132 tipi kısıttan sonra gelecekte izin verilen en küçük inversion katkısı;
\(b\), 21 tipi kısıttan doğan iki yapısal durumu ayıran eşik.
Dolayısıyla bir ara durum
$$ (r,a,b) $$
üçlüsüyle temsil edilir. Aynı üçlüye sahip iki ara permütasyonun gelecekteki tüm yasal uzantıları aynıdır; tam permütasyonu saklamaya gerek kalmaz.
Uzunluk \(\ell\) iken \((r,a,b)\) durumu şu aralıktaki herhangi bir \(i\) değerini seçebilir:
$$a \le i \lt \min(r+1,\ell).$$
Bir sonraki durum, seçilen katkının \(b\) eşiğinin solunda mı sağında mı kaldığına göre belirlenir:
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
İlk dal, gelecekteki alt sınırı sıkılaştırır ve eşiği bir adım sağa iter. İkinci dal, mevcut alt sınırı korur ve eşiği seçilen katkı ile değiştirir. Çözücünün bütün kombinatorik yükü bu iki formülde toplanır.
\(S_\ell(m)\), inversion bütçesi \(m\) altında tam uzunluğu \(\ell\) olan geçerli kısıtlı permütasyonların sayısı olsun. \(\ell\) ekleme adımından sonraki DP katmanı tam olarak bu nesneleri, durumlara göre ayrılmış halde tutar. Her geçerli geçiş bir sonraki uzunlukta tam bir yeni permütasyon ürettiği için, problemde istenen kümülatif büyüklük
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m)$$
olur. Baştaki \(1\), boş permütasyonu sayar. Uygulamaların tuttuğu çalışan toplam tam olarak budur.
Kalan bütçe her zaman \(0 \le r \le m\) olduğundan \(i\) hiçbir zaman \(m\)'yi geçemez. Bir kez
$$\ell \ge m+2$$
olduğunda, uzunluk sınırı artık etkili değildir; çünkü \(\min(r+1,\ell)=r+1\) olur. Bu noktadan sonra geçiş kuralları gerçek \(\ell\) değerine değil, yalnızca sonlu durum \((r,a,b)\)'ye bağlıdır. Böylece tam uzunluk sayıları, her ilave uzunluğun mod \(10^9+7\) altında aynı miktar \(g\) eklediği kararlı bir rejime girer. Sonuç olarak
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
C++, Python ve Java uygulamaları bu kesme noktasını kullanır; C++ uygulaması ayrıca sınırda katman toplamının sabitlendiğini doğrulamak için bir katman daha üretir.
\(m=0\) ise her ekleme için zorunlu olarak
$$i=0$$
olmalıdır. Bu yüzden her uzunlukta yalnızca tek bir yasal uzatma vardır: yeni maksimum, yeni inversion üretmeyen tek konfigürasyonla eklenir. Dolayısıyla
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
ve buradan
$$f(n,0)=1+n$$
çıkar. Özellikle
$$f(2,0)=3,$$
ki bu, uygulamalardaki küçük kontrol değeriyle aynıdır. Aynı uygulamalar ek olarak \(f(4,5)=32\) ve \(f(10,25)=294400\) kontrollerini de üretir.
Uygulama modül olarak \(10^9+7\), hedef bütçe olarak \(m=40\) ve hedef uzunluk olarak \(n=10^{18}\) sabitlerini kullanır. \((r,a,b)\) üçlüleri üzerindeki DP, düzleştirilmiş dizilerde tutulur; bir dizi mevcut katmanı, diğeri bir sonraki katmanı taşır. Başlangıç katmanında yalnızca boş permütasyon vardır; kalan bütçe tamdır ve yapısal sınırlar nötr durumdadır.
Uzunluk \(1\)'den \(\min(n,m+2)\)'ye kadar giderken uygulama tüm erişilebilir durumları dolaşır, izinli her \(i\) değerini dener, durum sayısını kümülatif cevaba ekler ve aynı sayıyı iki dallı geçiş kuralının belirlediği sonraki duruma yollar. Bütün işlemler \(10^9+7\) modunda yapılır.
Eğer \(n \le m+2\) ise bu açık DP zaten son cevaptır. Aksi halde uygulama kararlı son katmanı toplayıp \(g\)'yi elde eder, sonra da \((n-(m+2))g\) doğrusal kuyruğunu mod \(10^9+7\) altında ekler. C++ uygulaması buna ek olarak bir katman daha hesaplayıp kararlı katman toplamının değişmediğini kontrol eder.
Kalan bütçe ekseninde \(m+1\) olasılık vardır; süreç \(m+2\)'de kesildikten sonra iki yapısal sınırın her biri de \(O(m)\) farklı değer alır. Böylece DP \(O(m^3)\) durum ve \(O(m^3)\) bellek kullanır. Sabit bir katmanda her durum en fazla \(O(m)\) farklı ekleme katkısını deneyebilir; bu da katman başına kaba üst sınır olarak \(O(m^4)\) iş verir. Yalnızca \(O(m)\) katman açıkça işlendiği için toplam en kötü durum süre sınırı \(O(m^5)\) olur. \(m=40\) için bu rahatlıkla uygulanabilir düzeydedir; kararlı rejime geçildikten sonra devasa \(n\) parametresine bağımlılık \(O(1)\)'e iner.
Sea \(f(n,m)\) el número de permutaciones restringidas de tamaños \(0,1,\dots,n\) cuya cantidad de inversiones no supera \(m\). En el Problema 631 se pide calcular
$$f(10^{18},40)\pmod{10^9+7}.$$
Una enumeración directa es imposible: el límite de longitud es gigantesco y, aun sin restricciones extra, el número de permutaciones crece demasiado rápido. La solución correcta construye las permutaciones de forma incremental, guarda sólo la información estructural que sigue influyendo en el futuro y aprovecha que el proceso se estabiliza una vez que la longitud supera ligeramente al presupuesto de inversiones.
Las implementaciones en C++, Python y Java comparten la misma idea: hacer crecer una permutación válida insertando el nuevo máximo y resumir cada permutación parcial mediante un estado compacto de DP.
Supongamos que ya se ha construido una permutación restringida válida de longitud \(\ell-1\). Para pasar a longitud \(\ell\), se inserta el valor \(\ell\). Las implementaciones parametrizan esta inserción por el número \(i\) de nuevas inversiones creadas en ese paso, de modo que
$$0 \le i \le \ell-1.$$
Si antes de insertar quedaba un presupuesto \(r\), después de elegir la contribución \(i\) queda
$$r' = r-i.$$
Por tanto, todo paso legal debe satisfacer \(i \le r\), y el tope natural es siempre
$$i \lt \min(r+1,\ell).$$
Así, la restricción de inversiones se convierte en una regla local de transición.
Cuando se inserta el nuevo máximo, el orden relativo de los elementos antiguos no cambia. Por eso, cualquier configuración prohibida que aparezca por primera vez debe involucrar al nuevo máximo. Gracias a ello, además del presupuesto restante \(r\), basta con guardar dos enteros:
\(a\), la menor contribución futura de inversiones aún permitida por la restricción de tipo 132;
\(b\), un umbral que separa los dos casos estructurales inducidos por la restricción de tipo 21.
Un objeto parcial queda representado por el triple
$$ (r,a,b). $$
Dos permutaciones parciales con el mismo triple tienen exactamente el mismo conjunto de extensiones legales, así que no hace falta recordar toda la permutación.
En longitud \(\ell\), un estado \((r,a,b)\) puede elegir cualquier
$$a \le i \lt \min(r+1,\ell).$$
El siguiente estado depende de si la contribución elegida queda antes o después del umbral \(b\):
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
La primera rama endurece la cota inferior futura y desplaza el umbral una posición a la derecha. La segunda conserva la cota inferior actual y sustituye el umbral por la contribución elegida. Estas dos fórmulas constituyen el núcleo combinatorio completo del algoritmo.
Sea \(S_\ell(m)\) el número de permutaciones restringidas válidas de longitud exacta \(\ell\) con presupuesto \(m\). Tras \(\ell\) inserciones, la capa de la DP contiene precisamente esos objetos, separados por estado. Como cada transición legal crea exactamente una permutación válida de la siguiente longitud, la cantidad acumulada pedida por el problema es
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$$
donde el \(1\) inicial corresponde a la permutación vacía. La suma acumulada mantenida por las implementaciones es exactamente este valor.
El presupuesto restante siempre cumple \(0 \le r \le m\), así que \(i\) nunca puede exceder \(m\). En cuanto
$$\ell \ge m+2,$$
la cota de longitud deja de importar, porque \(\min(r+1,\ell)=r+1\). Desde ese momento, las reglas de transición dependen sólo del estado finito \((r,a,b)\), no del valor concreto de \(\ell\). Por tanto, los conteos de longitud exacta entran en un régimen estable en el que cada longitud adicional aporta la misma cantidad \(g\) módulo \(10^9+7\). Así se obtiene
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
Las implementaciones en C++, Python y Java usan este corte, y la implementación en C++ además verifica con una capa extra que el total por capa ya se ha estabilizado.
Si \(m=0\), toda inserción debe usar
$$i=0.$$
Por lo tanto, en cada paso existe una única extensión legal: el nuevo máximo se coloca de la única manera que no crea inversiones nuevas. En consecuencia,
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
y de ahí
$$f(n,0)=1+n.$$
En particular,
$$f(2,0)=3,$$
lo cual coincide con la comprobación pequeña usada por las implementaciones. Las mismas implementaciones también reproducen los controles adicionales \(f(4,5)=32\) y \(f(10,25)=294400\).
La implementación fija el módulo \(10^9+7\), el presupuesto objetivo \(m=40\) y la longitud objetivo \(n=10^{18}\). La DP sobre triples \((r,a,b)\) se almacena en arreglos lineales, usando un arreglo para la capa actual y otro para la siguiente. La capa inicial contiene solamente la permutación vacía con presupuesto completo y fronteras estructurales neutras.
Para cada longitud entre \(1\) y \(\min(n,m+2)\), la implementación recorre todos los estados alcanzables, enumera todos los valores admisibles de \(i\), añade la cuenta del estado a la respuesta acumulada y envía esa misma cuenta al estado siguiente dictado por la regla de dos ramas. Toda la aritmética se reduce módulo \(10^9+7\).
Si \(n \le m+2\), esa DP explícita ya produce la respuesta final. En caso contrario, la implementación suma la última capa estabilizada para obtener \(g\) y luego añade la cola lineal \((n-(m+2))g\) módulo \(10^9+7\). La versión en C++ también calcula una capa adicional para confirmar que el total estabilizado por capa no cambia.
La coordenada del presupuesto restante tiene \(m+1\) posibilidades, y cada una de las dos fronteras estructurales toma \(O(m)\) valores una vez truncado el proceso en \(m+2\). Por tanto, la DP usa \(O(m^3)\) estados y \(O(m^3)\) memoria. En una capa fija, cada estado puede probar hasta \(O(m)\) contribuciones de inserción, lo que da una cota directa de \(O(m^4)\) trabajo por capa. Como sólo se procesan explícitamente \(O(m)\) capas, la cota total de peor caso es \(O(m^5)\). Con \(m=40\), esto es perfectamente manejable, y tras la estabilización la dependencia respecto del enorme parámetro \(n\) pasa a ser \(O(1)\).
设 \(f(n,m)\) 表示所有长度属于 \(0,1,\dots,n\) 且逆序数不超过 \(m\) 的受限排列总数。Problem 631 要求计算
$$f(10^{18},40)\pmod{10^9+7}.$$
直接枚举根本不可行：长度上界极大，而排列总数本身增长得非常快。可行的办法是把排列按长度逐步构造出来，只保留将来继续插入时仍然有用的结构信息，再利用一个关键事实：当长度稍微超过逆序预算以后，状态转移会进入稳定区间，后续贡献变成线性外推。
C++、Python 和 Java 三个实现采用的是同一个组合思路：每一步都插入当前的新最大值，并把“一个部分排列未来还能怎样扩展”压缩成一个很小的 DP 状态。
假设已经构造出了一个长度为 \(\ell-1\) 的合法受限排列。要得到长度为 \(\ell\) 的排列，就插入值 \(\ell\)。实现里不是直接按“位置”来编号这次插入，而是按这一步新产生的逆序数 \(i\) 来编号，因此总有
$$0 \le i \le \ell-1.$$
如果插入前剩余的逆序预算是 \(r\)，那么选择这一步以后预算变为
$$r' = r-i.$$
所以任何合法扩展都必须满足 \(i \le r\)，于是自然得到上界
$$i \lt \min(r+1,\ell).$$
这就把“逆序数不超过 \(m\)”变成了一个纯局部的状态更新条件。
插入新的最大值时，旧元素之间的相对顺序完全不变。因此，如果某个禁形是在这一步第一次出现的，那么它一定包含这个新最大值。实现正是利用这一点，说明除了剩余预算 \(r\) 之外，只需要再记录两个整数：
\(a\)，它表示在 132 型限制之下，下一次插入时仍然允许的最小逆序贡献；
\(b\)，它表示由 21 型限制诱导出来的分界阈值，用来区分两类不同的更新方式。
于是，一个部分排列可以完全用三元组
$$ (r,a,b) $$
来表示。只要两个部分排列拥有相同的三元组，它们未来的所有合法扩展集合也相同，因此没有必要把整个排列本身存下来。
在长度为 \(\ell\) 时，状态 \((r,a,b)\) 可以选择任意满足
$$a \le i \lt \min(r+1,\ell)$$
的逆序贡献 \(i\)。接下来的状态取决于这个 \(i\) 落在阈值 \(b\) 的哪一侧：
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
第一种情况会把下一步允许的下界抬高，同时把阈值整体向右推进一格。第二种情况保留当前下界，并把阈值改成这次选到的贡献值。求解器的核心组合结构，实际上就全部浓缩在这两条转移式里。
记 \(S_\ell(m)\) 为在逆序预算 \(m\) 下、长度恰好等于 \(\ell\) 的合法受限排列数。做完 \(\ell\) 次插入以后，DP 的这一层恰好就是这些对象，只不过按状态分类存储。因为每一条合法转移都会生成一个下一长度的合法排列，所以题目要求的累计函数就是
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$$
其中最前面的 \(1\) 对应空排列。实现中维护的累计答案，正是这个总和。
由于剩余预算始终满足 \(0 \le r \le m\)，所以 \(i\) 永远不可能超过 \(m\)。一旦
$$\ell \ge m+2,$$
长度本身就不再提供新的约束，因为此时 \(\min(r+1,\ell)=r+1\)。也就是说，从这个长度开始，转移规则只依赖于有限状态 \((r,a,b)\)，不再显式依赖当前的 \(\ell\)。于是“恰好长度为 \(\ell\)”的计数会进入稳定阶段：每增加一个长度，模 \(10^9+7\) 的新增贡献都变成同一个常数 \(g\)。因此有
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
C++、Python 和 Java 实现都利用了这个截断点，而 C++ 实现还会额外做一步转移，确认在边界处按层求和的总量已经稳定下来。
如果 \(m=0\)，那么每一步都只能取
$$i=0.$$
这意味着每个长度都只有一种合法扩展方式：新最大值必须以唯一不会引入新逆序的方式插入。因此
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
从而得到
$$f(n,0)=1+n.$$
特别地，
$$f(2,0)=3,$$
这与实现中使用的小型校验值完全一致。同一套实现还会给出另外两个校验点：\(f(4,5)=32\) 和 \(f(10,25)=294400\)。
实现中固定模数为 \(10^9+7\)，目标参数为 \(m=40\) 与 \(n=10^{18}\)。DP 的状态是三元组 \((r,a,b)\)，实际存储时把三维状态压平成一维数组，并使用两个数组分别表示当前层和下一层。初始层只包含空排列这一种状态，此时剩余预算是满的，两个结构边界也处于中性位置。
对每个长度 \(1,2,\dots,\min(n,m+2)\)，实现都会遍历所有可达状态，枚举所有允许的 \(i\)，把当前状态的计数加入累计答案，再把同样的计数送到由两分支转移规则确定的下一状态。整个过程中所有加法都在 \(10^9+7\) 下取模。
如果 \(n \le m+2\)，这段显式 DP 已经足够给出最终答案。否则，实现先把稳定区间开始前的最后一层求和得到 \(g\)，再补上线性尾项 \((n-(m+2))g\) 模 \(10^9+7\)。C++ 实现还会额外计算一层，用来确认稳定层总和没有发生变化。
剩余预算坐标共有 \(m+1\) 种可能，而两条结构边界在过程截断到 \(m+2\) 以后也都只会取 \(O(m)\) 个值，所以总状态数是 \(O(m^3)\)，内存也是 \(O(m^3)\)。对固定一层来说，每个状态最多会尝试 \(O(m)\) 个插入贡献，因此单层的直接最坏时间界为 \(O(m^4)\)。由于显式处理的层数只有 \(O(m)\)，总的最坏时间界是 \(O(m^5)\)。当 \(m=40\) 时，这个规模非常小；而一旦进入稳定区间，对巨大参数 \(n\) 的依赖就只剩 \(O(1)\) 的线性外推。
Пусть \(f(n,m)\) обозначает число ограниченных перестановок размеров \(0,1,\dots,n\), у которых число инверсий не превышает \(m\). В Problem 631 требуется вычислить
$$f(10^{18},40)\pmod{10^9+7}.$$
Прямой перебор невозможен: ограничение на длину гигантское, а число перестановок растет слишком быстро даже без дополнительных условий. Поэтому решение строит перестановки по шагам, хранит только ту структурную информацию, которая еще влияет на будущие вставки, и использует тот факт, что после небольшой длины сверх бюджета инверсий процесс стабилизируется.
Реализации на C++, Python и Java используют один и тот же прием: валидная перестановка растет за счет вставки нового максимума, а каждая частичная перестановка кодируется компактным DP-состоянием.
Предположим, что уже построена корректная ограниченная перестановка длины \(\ell-1\). Чтобы получить длину \(\ell\), вставляется значение \(\ell\). Реализации параметризуют такую вставку числом \(i\) новых инверсий, возникающих на этом шаге, поэтому
$$0 \le i \le \ell-1.$$
Если перед вставкой оставшийся бюджет инверсий равен \(r\), то после выбора вклада \(i\) он становится
$$r' = r-i.$$
Следовательно, любой допустимый переход должен удовлетворять \(i \le r\), а естественная верхняя граница имеет вид
$$i \lt \min(r+1,\ell).$$
Так условие на число инверсий превращается в локальное правило обновления.
Когда вставляется новый максимум, относительный порядок всех старых элементов не меняется. Значит, любая запрещенная конфигурация, появляющаяся впервые на этом шаге, обязательно содержит новый максимум. Именно поэтому, кроме оставшегося бюджета \(r\), достаточно хранить только два целых параметра:
\(a\) — минимальный будущий вклад в число инверсий, еще разрешенный ограничением типа 132;
\(b\) — порог, отделяющий два структурных случая, возникающих из ограничения типа 21.
Тем самым частичный объект представляется тройкой
$$ (r,a,b). $$
Если две частичные перестановки имеют одну и ту же тройку, то множества их допустимых продолжений совпадают, поэтому хранить всю перестановку целиком не нужно.
На длине \(\ell\) состояние \((r,a,b)\) может выбрать любой вклад
$$a \le i \lt \min(r+1,\ell).$$
Следующее состояние определяется тем, лежит ли выбранный вклад слева или справа от порога \(b\):
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
Первая ветвь ужесточает будущую нижнюю границу и сдвигает порог на одну позицию вправо. Вторая ветвь сохраняет текущую нижнюю границу и заменяет порог выбранным вкладом. Вся комбинаторная суть алгоритма сосредоточена именно в этих двух формулах.
Обозначим через \(S_\ell(m)\) число корректных ограниченных перестановок точной длины \(\ell\) при бюджете инверсий \(m\). После \(\ell\) вставок соответствующий слой DP содержит ровно эти объекты, разбитые по состояниям. Поскольку каждый допустимый переход порождает ровно одну валидную перестановку следующей длины, требуемая накопленная величина равна
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$$
где начальная \(1\) соответствует пустой перестановке. Именно эту накопленную сумму и поддерживают реализации.
Оставшийся бюджет всегда удовлетворяет \(0 \le r \le m\), поэтому вклад \(i\) никогда не превосходит \(m\). Как только
$$\ell \ge m+2,$$
ограничение по длине перестает играть роль, потому что \(\min(r+1,\ell)=r+1\). С этого момента правила перехода зависят только от конечного состояния \((r,a,b)\), а не от самого значения \(\ell\). Поэтому числа перестановок точной длины входят в устойчивый режим, в котором каждая дополнительная длина дает один и тот же вклад \(g\) по модулю \(10^9+7\). Отсюда
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
Реализации на C++, Python и Java используют именно этот срез, а реализация на C++ дополнительно делает еще один шаг, чтобы убедиться, что суммарная масса слоя на границе уже стабилизировалась.
Если \(m=0\), то на каждом шаге обязательно
$$i=0.$$
Значит, для каждой длины существует ровно одно допустимое продолжение: новый максимум вставляется единственным способом, не создающим новых инверсий. Следовательно,
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
и потому
$$f(n,0)=1+n.$$
В частности,
$$f(2,0)=3,$$
что совпадает с малой проверкой, используемой реализациями. Те же реализации также воспроизводят дополнительные контрольные значения \(f(4,5)=32\) и \(f(10,25)=294400\).
В реализации фиксируются модуль \(10^9+7\), целевой бюджет \(m=40\) и целевая длина \(n=10^{18}\). DP по тройкам \((r,a,b)\) хранится в расплющенных массивах: один массив соответствует текущему слою, второй — следующему. Начальный слой содержит только пустую перестановку с полным оставшимся бюджетом и нейтральными структурными границами.
Для каждой длины от \(1\) до \(\min(n,m+2)\) реализация перебирает все достижимые состояния, рассматривает все допустимые значения \(i\), добавляет число способов из текущего состояния к накопленному ответу и отправляет ту же массу в следующее состояние, определяемое правилом с двумя ветвями. Все вычисления ведутся по модулю \(10^9+7\).
Если \(n \le m+2\), этого явного DP уже достаточно для окончательного ответа. Иначе реализация суммирует последнюю устойчивую слойную массу, получая \(g\), а затем добавляет линейный хвост \((n-(m+2))g\) по модулю \(10^9+7\). Версия на C++ дополнительно строит еще один слой, чтобы подтвердить неизменность устойчивой суммы.
Координата оставшегося бюджета имеет \(m+1\) возможных значений, а каждая из двух структурных границ после отсечения на длине \(m+2\) принимает \(O(m)\) значений. Поэтому DP использует \(O(m^3)\) состояний и \(O(m^3)\) памяти. На одном фиксированном слое каждое состояние может проверять до \(O(m)\) вариантов вставки, что дает прямую оценку \(O(m^4)\) работы на слой. Так как явно обрабатывается только \(O(m)\) слоев, общий худший случай равен \(O(m^5)\). При \(m=40\) это очень мало, а после стабилизации зависимость от огромного параметра \(n\) уменьшается до \(O(1)\).
لتكن \(f(n,m)\) هي عدد التبديلات المقيّدة ذات الأطوال \(0,1,\dots,n\) التي لا يتجاوز عدد انعكاساتها \(m\). في Problem 631 نريد حساب
$$f(10^{18},40)\pmod{10^9+7}.$$
العدّ المباشر غير ممكن عمليًا، لأن حد الطول هائل ولأن عدد التبديلات ينمو بسرعة كبيرة جدًا حتى قبل إضافة القيود. لذلك يبني الحل التبديلات خطوة بعد خطوة، ويحتفظ فقط بالمعلومة البنيوية التي ما زالت تؤثر في عمليات الإدراج اللاحقة، ثم يستفيد من حقيقة أن العملية تدخل في نظام مستقر عندما يصبح الطول أكبر بقليل من ميزانية الانعكاسات.
تستعمل تطبيقات C++ وPython وJava الفكرة نفسها: بناء التبديل الصحيح بإدراج العنصر الأعظم الجديد، ثم تلخيص كل تبديل جزئي في حالة DP صغيرة.
افترض أننا بنينا بالفعل تبديلًا مقيّدًا صحيحًا طوله \(\ell-1\). للحصول على طول \(\ell\)، ندرج القيمة \(\ell\). لا تُفهرِس التطبيقات هذا الإدراج بموضعه المباشر، بل بعدد الانعكاسات الجديدة \(i\) التي يضيفها هذا الإدراج، ولذلك يكون دائمًا
$$0 \le i \le \ell-1.$$
إذا كانت ميزانية الانعكاسات المتبقية قبل الإدراج هي \(r\)، فإنها تصبح بعد اختيار \(i\)
$$r' = r-i.$$
إذن كل انتقال صالح يجب أن يحقق \(i \le r\)، ويكون الحد الأعلى الطبيعي دائمًا
$$i \lt \min(r+1,\ell).$$
بهذه الطريقة يتحول قيد الانعكاسات إلى قاعدة تحديث محلية واضحة.
عند إدراج العنصر الأعظم الجديد، يبقى الترتيب النسبي بين العناصر الأقدم كما هو. لذلك فإن أي بنية ممنوعة تظهر لأول مرة في هذه الخطوة لا بد أن تحتوي العنصر الأعظم الجديد نفسه. ولهذا يكفي، بالإضافة إلى الميزانية المتبقية \(r\)، تخزين عددين صحيحين فقط:
\(a\)، وهو أصغر مساهمة مستقبلية في الانعكاسات ما زالت مسموحة تحت القيد من النوع 132؛
\(b\)، وهو عتبة فاصلة بين الحالتين البنيويتين الناتجتين عن القيد من النوع 21.
وبذلك يُمثَّل التبديل الجزئي بالثلاثي
$$ (r,a,b). $$
وأي تبديلين جزئيين لهما الثلاثي نفسه يملكان المجموعة نفسها من الامتدادات الصحيحة في المستقبل، لذلك لا حاجة إلى الاحتفاظ بالتبديل كاملًا.
عند الطول \(\ell\)، تستطيع الحالة \((r,a,b)\) اختيار أي قيمة
$$a \le i \lt \min(r+1,\ell).$$
وتعتمد الحالة التالية على ما إذا كانت المساهمة المختارة تقع قبل العتبة \(b\) أو بعدها:
$$i \lt b \Longrightarrow (r-i,\ i+1,\ b+1),$$
$$i \ge b \Longrightarrow (r-i,\ a,\ i).$$
في الفرع الأول يُشدَّد الحد الأدنى المستقبلي وتتحرك العتبة درجة واحدة إلى اليمين. وفي الفرع الثاني يبقى الحد الأدنى كما هو، بينما تُستبدل العتبة بالمساهمة المختارة. هاتان الصيغتان هما الجوهر التوافقي الكامل للحل.
لنرمز بـ \(S_\ell(m)\) إلى عدد التبديلات المقيّدة الصحيحة ذات الطول الدقيق \(\ell\) تحت ميزانية الانعكاسات \(m\). بعد \(\ell\) عمليات إدراج، تخزن طبقة DP هذه الكائنات بالضبط ولكن موزعة على الحالات المختلفة. وبما أن كل انتقال صالح ينتج تبديلًا صحيحًا واحدًا من الطول التالي، فإن الكمية التراكمية المطلوبة في المسألة هي
$$f(n,m)=1+\sum_{\ell=1}^{n} S_\ell(m),$$
حيث تمثل القيمة الابتدائية \(1\) التبديل الفارغ. والمجموع الجاري الذي تحتفظ به التطبيقات هو هذا المقدار نفسه.
لدينا دائمًا \(0 \le r \le m\)، ولذلك لا يمكن أن تتجاوز \(i\) القيمة \(m\). حالما يصبح
$$\ell \ge m+2,$$
يتوقف حد الطول عن لعب أي دور، لأن \(\min(r+1,\ell)=r+1\). ومنذ تلك اللحظة تعتمد قواعد الانتقال فقط على الحالة المحدودة \((r,a,b)\)، لا على قيمة \(\ell\) نفسها. لذلك تدخل أعداد التبديلات ذات الطول الدقيق في نظام مستقر تضيف فيه كل زيادة في الطول نفس المقدار \(g\) بترديد \(10^9+7\). ومن ثم
$$f(n,m)=f(m+2,m)+(n-(m+2))\,g \pmod{10^9+7}.$$
تستخدم تطبيقات C++ وPython وJava هذا الحد الفاصل، كما أن تطبيق C++ يجري خطوة إضافية ليتأكد من أن مجموع الطبقة قد استقر فعلًا عند هذا الحد.
إذا كان \(m=0\)، فلا بد أن يكون
$$i=0$$
في كل خطوة. وهذا يعني أن كل طول يملك امتدادًا صحيحًا واحدًا فقط: يُدرج العنصر الأعظم الجديد بالطريقة الوحيدة التي لا تولد انعكاسات جديدة. لذلك
$$S_\ell(0)=1 \qquad (\ell \ge 1),$$
ومن ثم
$$f(n,0)=1+n.$$
وبالأخص
$$f(2,0)=3,$$
وهو تمامًا نفس اختبار التحقق الصغير المستخدم في التطبيقات. كما أن التطبيقات نفسها تعيد أيضًا قيمتي التحقق الإضافيتين \(f(4,5)=32\) و\(f(10,25)=294400\).
تثبّت التطبيقات قيمة الترديد \(10^9+7\)، وميزانية الهدف \(m=40\)، وطول الهدف \(n=10^{18}\). ويُخزَّن DP على الثلاثيات \((r,a,b)\) داخل مصفوفات مسطحة، مع مصفوفة للطبقة الحالية وأخرى للطبقة التالية. أما الطبقة الابتدائية فتحتوي فقط على التبديل الفارغ مع ميزانية كاملة وحدود بنيوية محايدة.
لكل طول من \(1\) حتى \(\min(n,m+2)\)، تمرّ التطبيقات على كل حالة قابلة للوصول، وتعدّ جميع القيم المسموح بها لـ \(i\)، ثم تضيف عدد هذه الحالة إلى الجواب التراكمي، وترسل العدد نفسه إلى الحالة التالية التي تحددها قاعدة الانتقال ذات الفرعين. وكل العمليات الحسابية تُختزل بترديد \(10^9+7\).
إذا كان \(n \le m+2\)، فإن هذا DP الصريح يكفي وحده لإنتاج الجواب النهائي. أما إذا كان \(n\) أكبر، فتجمع التطبيقات الطبقة المستقرة الأخيرة للحصول على \(g\)، ثم تضيف الذيل الخطي \((n-(m+2))g\) بترديد \(10^9+7\). ويحسب تطبيق C++ طبقة إضافية أيضًا ليتأكد من أن مجموع الطبقة المستقرة لم يتغير.
إحداثي الميزانية المتبقية يملك \(m+1\) احتمالًا، وكل واحد من الحدين البنيويين يأخذ \(O(m)\) قيمة بعد قطع العملية عند \(m+2\). لذا فإن عدد الحالات هو \(O(m^3)\)، وكذلك الذاكرة \(O(m^3)\). وفي طبقة واحدة يمكن لكل حالة أن تجرب حتى \(O(m)\) قيم مختلفة للإدراج، مما يعطي حدًا مباشرًا مقداره \(O(m^4)\) من العمل لكل طبقة. وبما أن عدد الطبقات المحسوبة صراحة هو \(O(m)\)، فإن حد الزمن الكلي في أسوأ الأحوال هو \(O(m^5)\). وعندما \(m=40\) يكون هذا الحجم صغيرًا جدًا عمليًا، وبعد الوصول إلى الاستقرار تصبح كلفة الاعتماد على \(n\) الهائل ثابتة \(O(1)\).