For lengths \(N=2^m\), the problem asks for the 1-based lexicographic rank of the special unpredictable permutation of \(\{1,\dots,N\}\), reduced modulo \(10^9+7\). A brute-force comparison against all \(N!\) permutations is impossible once \(m\) is large, so the solution follows the recursive structure of the permutation itself and carries its Lehmer code along the same recursion.
Write the target permutation as
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$$
using zero-based positions. Let \(L_N(i)\) be the Lehmer digit at position \(i\), meaning the number of later entries smaller than \(P_N(i)\). Then the 1-based lexicographic rank is
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$$
The central task is therefore to update \(P_N\) and \(L_N\) together when the size doubles.
The recursive construction starts from the first nontrivial power of two, namely \(N=4\):
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
The smaller cases \(N=2\) and \(N=4\) have direct known ranks, so the implementations can begin from this seed. Two boundary facts are already visible and remain true after every doubling step:
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
These identities make the bridge positions in the next stage especially simple.
Assume \(P_N\) is known. The permutation of size \(2N\) is built by sending most old values to odd or even numbers:
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
So the old prefix becomes odd values, most of the new suffix becomes even values, and two bridge positions connect the two blocks. Because \(P_N(0)=1\) and \(P_N(N-1)=N\), the same boundary pattern propagates:
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
Take a position \(0\le i\le N-2\). Its new value is \(2P_N(i)-1\), which is odd. Among later odd values, the relative order is exactly the same as in the old permutation, so the old inversion count \(L_N(i)\) is still present.
There is one extra source of smaller entries: all even numbers
$$2,4,\dots,2P_N(i)-2$$
are smaller than \(2P_N(i)-1\), and after doubling they all lie to the right of position \(i\). The number of such even values is \(P_N(i)-1\). Therefore
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$$
This is the key identity that lets the rank information grow without recomputing inversion counts from scratch.
The bridge position \(N-1\) contains \(2P_N(0)=2\). Since the value \(1\) is fixed at the far left, there is no smaller value anywhere to the right, hence
$$L_{2N}(N-1)=0.$$
The next bridge position \(N\) contains \(2P_N(N-1)-1=2N-1\). To its right there are \(N-1\) even values, and only \(2N\) is larger, so exactly \(N-2\) of them are smaller:
$$L_{2N}(N)=N-2.$$
For the remaining suffix positions \(N+j\) with \(1\le j\le N-1\), everything to the right is also even, and multiplying values by \(2\) preserves order. So those Lehmer digits are copied unchanged:
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
Starting from
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0],$$
the doubling rule gives
$$P_8=[1,5,3,2,7,6,4,8].$$
Using the formulas above, the Lehmer digits become
$$L_8=[0,3,1,0,2,1,0,0].$$
Now evaluate the factorial expansion:
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
This matches the checkpoint used by the implementations and confirms that the recursive Lehmer update is correct.
Repeat the doubling step until \(N=2^m\). At that point the target permutation and its entire Lehmer code are already known, so the required answer is simply
$$R_{2^m}\bmod (10^9+7).$$
No search over permutations is required. The recursion itself contains all of the combinatorial structure needed for the final rank.
The C++, Python, and Java implementations follow the same recipe. They handle the tiny powers of two directly, initialize the seed permutation and seed Lehmer digits for length \(4\), and then double the arrays until the requested size is reached. During each doubling step, the new even suffix is written first, the two bridge entries are inserted next, and the old prefix is updated in place at the end. The right-to-left write order is important because the old values are still needed while the new stage is being assembled.
Once the target length has been built, the implementation computes the lexicographic rank from the Lehmer code. It scans from right to left, maintaining the current factorial weight modulo \(10^9+7\), so it never has to store large factorials explicitly. The same pattern appears in all three language versions, differing only in syntax.
Let \(N=2^m\). The recursive construction touches each array entry only a constant number of times across the sequence of sizes \(4,8,16,\dots,N\). The total work is therefore
$$4+8+16+\cdots+N=O(N).$$
The final rank accumulation from the Lehmer code is another linear pass. Hence the complete running time is \(O(N)=O(2^m)\), and the memory usage is \(O(N)\) because the permutation and Lehmer arrays both have length \(N\).
Für Längen \(N=2^m\) wird der 1-basierte lexikographische Rang der speziellen unvorhersagbaren Permutation von \(\{1,\dots,N\}\) gesucht, reduziert modulo \(10^9+7\). Ein Vergleich mit allen \(N!\) Permutationen ist für große \(m\) unmöglich. Deshalb nutzt die Lösung die rekursive Struktur der Permutation selbst und führt ihren Lehmer-Code entlang derselben Rekursion mit.
Schreiben wir die Zielpermutation als
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$$
wobei die Positionen nullbasiert gezählt werden. Sei \(L_N(i)\) die Lehmer-Ziffer an Position \(i\), also die Anzahl späterer Einträge, die kleiner als \(P_N(i)\) sind. Dann ist der 1-basierte lexikographische Rang
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$$
Die eigentliche Aufgabe besteht also darin, \(P_N\) und \(L_N\) beim Verdoppeln der Größe gemeinsam fortzuschreiben.
Die Rekursion beginnt beim ersten nichttrivialen Zweierpotenz-Fall \(N=4\):
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
Die kleineren Fälle \(N=2\) und \(N=4\) haben direkt bekannte Ränge, daher können die Implementierungen mit diesem Startzustand arbeiten. Schon hier sieht man zwei Randinvarianten, die nach jeder Verdopplung erhalten bleiben:
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
Gerade diese beiden Identitäten machen die Brückenpositionen im nächsten Schritt besonders einfach.
Sei \(P_N\) bekannt. Dann wird die Permutation der Größe \(2N\) gebildet, indem alte Werte auf ungerade bzw. gerade Zahlen abgebildet werden:
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
Das alte Präfix wird also zu ungeraden Werten, der Großteil des neuen Suffixes zu geraden Werten, und zwei Brückenpositionen verbinden beide Blöcke. Wegen \(P_N(0)=1\) und \(P_N(N-1)=N\) setzt sich das Randmuster fort:
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
Betrachte eine Position \(0\le i\le N-2\). Ihr neuer Wert ist \(2P_N(i)-1\), also ungerade. Unter den späteren ungeraden Werten bleibt die relative Ordnung exakt dieselbe wie in der alten Permutation, daher bleibt der alte Inversionsbeitrag \(L_N(i)\) erhalten.
Zusätzlich gibt es kleinere gerade Werte:
$$2,4,\dots,2P_N(i)-2$$
sind alle kleiner als \(2P_N(i)-1\), und nach der Verdopplung liegen sie sämtlich rechts von Position \(i\). Davon gibt es genau \(P_N(i)-1\) Stück. Deshalb gilt
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$$
Das ist die Schlüsselformel, durch die die Ranginformation wachsen kann, ohne die Inversionszahlen jedes Mal neu zu berechnen.
Die Brückenposition \(N-1\) enthält \(2P_N(0)=2\). Da der Wert \(1\) ganz links feststeht, gibt es rechts davon keinen kleineren Wert, also
$$L_{2N}(N-1)=0.$$
Die nächste Brückenposition \(N\) enthält \(2P_N(N-1)-1=2N-1\). Rechts davon stehen \(N-1\) gerade Werte, und nur \(2N\) ist größer. Also sind genau \(N-2\) davon kleiner:
$$L_{2N}(N)=N-2.$$
Für die übrigen Suffixpositionen \(N+j\) mit \(1\le j\le N-1\) gilt: Alles rechts davon ist ebenfalls gerade, und die Multiplikation mit \(2\) erhält die Ordnung. Deshalb werden diese Lehmer-Ziffern unverändert kopiert:
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
Ausgehend von
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0]$$
liefert die Verdopplungsregel
$$P_8=[1,5,3,2,7,6,4,8].$$
Mit den obigen Formeln erhält man die Lehmer-Ziffern
$$L_8=[0,3,1,0,2,1,0,0].$$
Nun wird die Fakultätsdarstellung ausgewertet:
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
Genau dieser Wert erscheint auch als Kontrollpunkt in den Implementierungen und bestätigt die rekursive Lehmer-Aktualisierung.
Der Verdopplungsschritt wird so lange wiederholt, bis \(N=2^m\) erreicht ist. Dann sind die Zielpermutation und ihr kompletter Lehmer-Code bereits bekannt, und die gesuchte Antwort ist einfach
$$R_{2^m}\bmod (10^9+7).$$
Eine Suche über Permutationen ist nicht nötig. Die Rekursion selbst enthält schon die gesamte kombinatorische Struktur des Endrangs.
Die C++-, Python- und Java-Implementierungen folgen demselben Plan. Zunächst behandeln sie die kleinsten Zweierpotenzen direkt, initialisieren dann die Startpermutation und die Start-Lehmer-Ziffern der Länge \(4\), und verdoppeln anschließend beide Felder bis zur gewünschten Größe. In jedem Verdopplungsschritt wird zuerst das neue gerade Suffix geschrieben, danach werden die beiden Brückenwerte gesetzt, und erst am Ende wird das alte Präfix in place aktualisiert. Die Verarbeitung von rechts nach links ist wichtig, weil die alten Werte noch benötigt werden, während der neue Zustand aufgebaut wird.
Sobald die Ziellänge erreicht ist, berechnet die Implementierung den lexikographischen Rang aus dem Lehmer-Code. Dabei läuft sie von rechts nach links und hält das aktuelle Fakultätsgewicht modulo \(10^9+7\) fortlaufend fest. Große Fakultäten müssen also nie explizit gespeichert werden. Dieses Schema ist in allen drei Sprachversionen identisch, nur die Syntax unterscheidet sich.
Sei \(N=2^m\). Die rekursive Konstruktion berührt jeden Array-Eintrag über die Größenfolge \(4,8,16,\dots,N\) hinweg nur konstant oft. Die Gesamtarbeit ist daher
$$4+8+16+\cdots+N=O(N).$$
Die abschließende Rangberechnung aus dem Lehmer-Code ist ein weiterer linearer Durchlauf. Insgesamt ergibt sich also Laufzeit \(O(N)=O(2^m)\) und Speicherbedarf \(O(N)\), da Permutation und Lehmer-Array beide Länge \(N\) haben.
\(N=2^m\) uzunlukları için, \(\{1,\dots,N\}\) kümesi üzerindeki özel kestirilemez permütasyonun 1-bazlı leksikografik sırası istenir ve sonuç \(10^9+7\) modunda verilir. Büyük \(m\) değerlerinde tüm \(N!\) permütasyonla karşılaştırma yapmak imkansızdır. Bu yüzden çözüm, permütasyonun kendi özyinelemeli yapısını izler ve Lehmer kodunu aynı inşa süreci boyunca birlikte taşır.
Hedef permütasyonu
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)]$$
şeklinde, konumları sıfırdan başlayacak biçimde yazalım. \(L_N(i)\), \(i\). konumdaki Lehmer basamağı olsun; yani bu, \(P_N(i)\)'den sonra gelip ondan küçük olan elemanların sayısıdır. O halde 1-bazlı leksikografik sıra
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!$$
olur. Dolayısıyla asıl iş, boyut iki katına çıkarken \(P_N\) ile \(L_N\)'yi birlikte güncelleyebilmektir.
Özyineleme, ilk anlamlı iki kuvveti örneği olan \(N=4\) ile başlar:
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
Daha küçük durumlar olan \(N=2\) ve \(N=4\) için sıra değeri doğrudan bilindiğinden, implementasyonlar bu çekirdek durumdan başlayabilir. Burada görülen iki sınır özelliği her ikiye katlama adımında da korunur:
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
Bir sonraki aşamadaki iki köprü konumunun basit olmasının sebebi tam olarak budur.
\(P_N\) biliniyor olsun. Boyutu \(2N\) olan yeni permütasyon, eski değerlerin büyük kısmını tek ya da çift sayılara dönüştürerek kurulur:
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
Böylece eski ön ek tek değerlere dönüşür, yeni son ekin büyük bölümü çift değerlere dönüşür ve iki köprü konumu bu iki bloğu birbirine bağlar. \(P_N(0)=1\) ve \(P_N(N-1)=N\) olduğundan sınır düzeni devam eder:
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
\(0\le i\le N-2\) olan bir konum alalım. Yeni değeri \(2P_N(i)-1\) olur; yani tektir. Sonraki tek değerler arasındaki göreli sıralama eski permütasyonla tamamen aynı kaldığı için eski terslik katkısı \(L_N(i)\) aynen korunur.
Buna ek olarak daha küçük çift değerler vardır:
$$2,4,\dots,2P_N(i)-2$$
değerlerinin hepsi \(2P_N(i)-1\)'den küçüktür ve ikiye katlama sonrasında bunların tamamı \(i\). konumun sağına yerleşir. Bu tür çift değerlerin sayısı tam olarak \(P_N(i)-1\)'dir. Dolayısıyla
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2)$$
elde edilir. Bu kimlik, terslik sayılarını her aşamada sıfırdan üretmeden sıra bilgisini büyüten temel formüldür.
\(N-1\). köprü konumu \(2P_N(0)=2\) değerini taşır. \(1\) değeri zaten en solda sabit olduğundan, bunun sağında daha küçük hiçbir değer yoktur. Bu yüzden
$$L_{2N}(N-1)=0.$$
Bir sonraki köprü konumu \(N\), \(2P_N(N-1)-1=2N-1\) değerini taşır. Sağında \(N-1\) tane çift değer vardır ve bunlardan yalnızca \(2N\) daha büyüktür. O halde tam olarak \(N-2\) tanesi daha küçüktür:
$$L_{2N}(N)=N-2.$$
Kalan son ek konumları \(N+j\) için (\(1\le j\le N-1\)) sağ taraftaki bütün değerler de çifttir ve \(2\) ile çarpmak sıralamayı bozmaz. Bu nedenle bu Lehmer basamakları doğrudan kopyalanır:
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
Başlangıçta
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0]$$
olsun. İkiye katlama kuralı
$$P_8=[1,5,3,2,7,6,4,8]$$
permütasyonunu verir. Yukarıdaki formüllerle Lehmer basamakları
$$L_8=[0,3,1,0,2,1,0,0]$$
olur. Şimdi faktöriyel açılımını hesaplayalım:
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
Bu değer implementasyonlardaki kontrol noktasıyla aynıdır ve özyinelemeli Lehmer güncellemesinin doğru olduğunu gösterir.
İkiye katlama adımı \(N=2^m\) olana kadar tekrar edilir. Bu noktada hedef permütasyon ve onun tüm Lehmer kodu zaten elimizdedir; dolayısıyla istenen cevap sadece
$$R_{2^m}\bmod (10^9+7)$$
ifadesidir. Permütasyonlar üzerinde arama yapmaya gerek yoktur; son sırayı belirleyen tüm kombinatorik yapı doğrudan bu özyinelemenin içindedir.
C++, Python ve Java implementasyonları aynı planı izler. Önce en küçük iki kuvvet durumlarını doğrudan ele alırlar, sonra uzunluğu \(4\) olan başlangıç permütasyonunu ve başlangıç Lehmer dizisini kurarlar, ardından istenen boyuta ulaşana kadar iki diziyi birlikte ikiye katlarlar. Her ikiye katlama adımında önce yeni çift son ek yazılır, sonra iki köprü değeri yerleştirilir, en son da eski ön ek aynı bellek üzerinde güncellenir. Eski değerlere hâlâ ihtiyaç duyulduğu için sağdan sola ilerleme kritiktir.
Hedef uzunluğa ulaşıldığında implementasyon, leksikografik sırayı Lehmer kodundan hesaplar. Bunun için sağdan sola gidip geçerli faktöriyel katsayısını \(10^9+7\) modunda güncel tutar; böylece büyük faktöriyelleri ayrı ayrı saklamaya gerek kalmaz. Üç dildeki sürümlerin farkı yalnızca sözdizimidir.
\(N=2^m\) olsun. Özyinelemeli inşa, \(4,8,16,\dots,N\) boyutları boyunca her dizi elemanına yalnızca sabit sayıda dokunur. Bu yüzden toplam iş
$$4+8+16+\cdots+N=O(N)$$
olur. Lehmer kodundan son sıra hesabı da bir ek lineer geçiştir. Sonuç olarak toplam süre \(O(N)=O(2^m)\), bellek kullanımı ise hem permütasyon hem de Lehmer dizisi uzunluğu \(N\) olduğu için \(O(N)\)'dir.
Para longitudes \(N=2^m\), el problema pide el rango lexicográfico 1-basado de la permutación impredecible especial de \(\{1,\dots,N\}\), reducido módulo \(10^9+7\). Compararla contra las \(N!\) permutaciones posibles es inviable cuando \(m\) es grande. Por eso la solución sigue la propia estructura recursiva de la permutación y arrastra su código de Lehmer durante esa misma construcción.
Escribamos la permutación objetivo como
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$$
usando posiciones basadas en \(0\). Sea \(L_N(i)\) el dígito de Lehmer en la posición \(i\), es decir, el número de entradas posteriores menores que \(P_N(i)\). Entonces el rango lexicográfico 1-basado es
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$$
Así que el problema central consiste en actualizar \(P_N\) y \(L_N\) al mismo tiempo cuando el tamaño se duplica.
La construcción recursiva empieza en la primera potencia de dos no trivial, \(N=4\):
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
Los casos más pequeños, \(N=2\) y \(N=4\), tienen rangos conocidos de forma directa, así que las implementaciones pueden arrancar desde esta semilla. Ya aquí aparecen dos invariantes de borde que siguen siendo ciertas tras cada duplicación:
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
Estas dos identidades hacen especialmente simples las posiciones puente de la etapa siguiente.
Supongamos conocida \(P_N\). La permutación de tamaño \(2N\) se construye enviando la mayoría de los valores antiguos a números impares o pares:
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
De este modo, el prefijo antiguo se vuelve impar, la mayor parte del nuevo sufijo se vuelve par, y dos posiciones puente conectan ambos bloques. Como \(P_N(0)=1\) y \(P_N(N-1)=N\), el patrón de borde se conserva:
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
Tomemos una posición \(0\le i\le N-2\). Su nuevo valor es \(2P_N(i)-1\), que es impar. Entre los valores impares posteriores, el orden relativo es exactamente el mismo que en la permutación antigua, así que la contribución previa a las inversiones, \(L_N(i)\), se conserva.
Además aparecen valores pares más pequeños:
$$2,4,\dots,2P_N(i)-2$$
son todos menores que \(2P_N(i)-1\), y después de duplicar quedan todos a la derecha de la posición \(i\). Hay exactamente \(P_N(i)-1\) de esos valores pares. Por lo tanto,
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$$
Esta es la identidad clave que permite hacer crecer la información del rango sin recalcular desde cero todos los conteos de inversiones.
La posición puente \(N-1\) contiene \(2P_N(0)=2\). Como el valor \(1\) ya quedó fijo al extremo izquierdo, no existe ningún valor menor a su derecha, y por tanto
$$L_{2N}(N-1)=0.$$
La siguiente posición puente \(N\) contiene \(2P_N(N-1)-1=2N-1\). A su derecha hay \(N-1\) valores pares y solo \(2N\) es mayor, así que exactamente \(N-2\) son menores:
$$L_{2N}(N)=N-2.$$
Para las posiciones restantes del sufijo \(N+j\), con \(1\le j\le N-1\), todo lo que queda a la derecha también es par y multiplicar por \(2\) preserva el orden. Por eso esos dígitos de Lehmer se copian sin cambio:
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
Partiendo de
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0],$$
la regla de duplicación produce
$$P_8=[1,5,3,2,7,6,4,8].$$
Aplicando las fórmulas anteriores, los dígitos de Lehmer pasan a ser
$$L_8=[0,3,1,0,2,1,0,0].$$
Ahora evaluamos la expansión factorial:
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
Ese valor coincide con el punto de control usado por las implementaciones y confirma que la actualización recursiva del código de Lehmer es correcta.
Se repite la duplicación hasta llegar a \(N=2^m\). En ese momento ya se conoce la permutación objetivo y todo su código de Lehmer, así que la respuesta pedida es simplemente
$$R_{2^m}\bmod (10^9+7).$$
No hace falta enumerar ni ordenar permutaciones. La propia recursión contiene toda la estructura combinatoria necesaria para el rango final.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Tratan directamente las potencias de dos más pequeñas, inicializan la permutación semilla y los dígitos de Lehmer para longitud \(4\), y luego duplican ambos arreglos hasta alcanzar el tamaño deseado. En cada paso de duplicación, primero se escribe el nuevo sufijo par, después se insertan las dos entradas puente y finalmente se actualiza in situ el prefijo antiguo. El recorrido de derecha a izquierda es importante porque todavía se necesitan los valores viejos mientras se está ensamblando la nueva etapa.
Cuando ya se alcanzó la longitud objetivo, la implementación calcula el rango lexicográfico a partir del código de Lehmer. Para ello recorre de derecha a izquierda manteniendo el peso factorial actual módulo \(10^9+7\), así que nunca necesita almacenar factoriales gigantes por separado. La lógica es la misma en los tres lenguajes; solo cambia la sintaxis.
Sea \(N=2^m\). La construcción recursiva toca cada entrada de los arreglos solo un número constante de veces a lo largo de los tamaños \(4,8,16,\dots,N\). El trabajo total es entonces
$$4+8+16+\cdots+N=O(N).$$
El recorrido final para acumular el rango desde el código de Lehmer es otra pasada lineal. En consecuencia, el tiempo total es \(O(N)=O(2^m)\) y la memoria usada es \(O(N)\), porque tanto la permutación como el arreglo de Lehmer tienen longitud \(N\).
当长度 \(N=2^m\) 时，本题要求求出特殊的“不可预测”排列在 \(\{1,\dots,N\}\) 上的 1 基字典序排名，并对 \(10^9+7\) 取模。若直接把它和全部 \(N!\) 个排列逐一比较，规模一大就完全不可行。因此，解法抓住这个排列本身的递归构造方式，在扩展排列的同时同步维护它的 Lehmer 码。
把目标排列记为
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$$
这里位置采用从 \(0\) 开始的编号。记 \(L_N(i)\) 为第 \(i\) 个位置上的 Lehmer 数字，也就是在它右侧、比 \(P_N(i)\) 更小的元素个数。那么 1 基字典序排名满足
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$$
于是问题的核心就变成了：当规模从 \(N\) 扩展到 \(2N\) 时，怎样同时更新排列 \(P_N\) 与 Lehmer 码 \(L_N\)。
递归从第一个真正非平凡的二次幂规模 \(N=4\) 开始：
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
更小的情形 \(N=2\) 和 \(N=4\) 的排名可以直接给出，所以实现可以从这个种子状态起步。这个初始状态已经显露出两个边界性质，而且它们在每次翻倍之后都会继续成立：
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
正是这两个不变量，让下一层构造中的两个“桥接位置”变得非常简单。
设 \(P_N\) 已知。构造长度为 \(2N\) 的新排列时，原排列的大部分值会被映射成奇数或偶数：
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
这意味着旧排列的前缀部分会变成奇数值，新后缀的大部分会变成偶数值，而中间的两个桥接位置把这两块结构接起来。由于 \(P_N(0)=1\) 且 \(P_N(N-1)=N\)，边界模式会自动延续：
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
也就是说，每一层构造的第一个元素始终是最小值，最后一个元素始终是最大值。
考虑某个位置 \(0\le i\le N-2\)。它在新排列中的值变成 \(2P_N(i)-1\)，因此一定是奇数。对于右边那些同样来自旧前缀的奇数值来说，彼此的相对大小顺序与旧排列完全一致，所以原本的 Lehmer 贡献 \(L_N(i)\) 会完整保留下来。
但除此之外，还会新增一批更小的偶数值：
$$2,4,\dots,2P_N(i)-2$$
这些数全部都小于 \(2P_N(i)-1\)，并且在翻倍构造完成后，它们都会落在位置 \(i\) 的右侧。这样的偶数恰好有 \(P_N(i)-1\) 个，因此
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$$
这就是整个方法的关键公式。它说明只要知道旧排列的值和旧的 Lehmer 数字，就能直接得到新前缀的 Lehmer 数字，而不需要重新统计所有逆序关系。
第一个桥接位置 \(N-1\) 上放的是 \(2P_N(0)=2\)。因为数值 \(1\) 已经固定在最左端，所以它右边不可能再出现比 \(2\) 更小的值，于是
$$L_{2N}(N-1)=0.$$
下一个桥接位置 \(N\) 上放的是 \(2P_N(N-1)-1=2N-1\)。它右边一共有 \(N-1\) 个偶数值，其中只有 \(2N\) 比它大，所以恰好有 \(N-2\) 个比它小：
$$L_{2N}(N)=N-2.$$
至于其余后缀位置 \(N+j\)（其中 \(1\le j\le N-1\)），右边剩下的元素也全部是偶数，而且把数值统一乘以 \(2\) 不会改变它们之间的大小关系。所以这些位置的 Lehmer 数字可以原封不动地复制：
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
换句话说，新排列的后半段在 Lehmer 码层面基本只是旧结构的平移。
从种子状态
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0]$$
出发，按照翻倍规则可得
$$P_8=[1,5,3,2,7,6,4,8].$$
再用上面的四条更新公式，得到新的 Lehmer 码
$$L_8=[0,3,1,0,2,1,0,0].$$
接下来把 Lehmer 码代入阶乘展开：
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
这个结果与实现中使用的校验值完全一致，因此既验证了排列递推，也验证了 Lehmer 码更新公式。
只要不断重复上面的翻倍步骤，直到 \(N=2^m\) 为止，就能得到题目要求的目标排列以及它的完整 Lehmer 码。于是最终答案就是
$$R_{2^m}\bmod (10^9+7).$$
整个过程中完全不需要显式枚举排列，更不需要把它与所有可能的排列做比较。递归构造本身已经把最终排名所需的组合信息编码进去了。
C++、Python 和 Java 三个实现采用的是同一套思路。它们先直接处理最小的几个二次幂情形，然后初始化长度为 \(4\) 的种子排列和对应的 Lehmer 码，之后不断把数组长度翻倍，直到达到目标规模。每次翻倍时，先写出新的偶数后缀，再填入两个桥接位置，最后就地更新旧前缀。之所以按照从右向左的顺序处理，是因为在构造新一层时，旧层中的值仍然要被继续读取。
当目标长度构造完成后，实现再根据 Lehmer 码计算字典序排名。它从最右端往左扫描，同时维护当前的阶乘权重并在 \(10^9+7\) 下取模，因此不需要单独保存庞大的阶乘表。三种语言版本在算法层面完全一致，区别只是语法形式不同。
令 \(N=2^m\)。在规模序列 \(4,8,16,\dots,N\) 中，递归构造对每个数组位置只会进行常数次处理，因此总工作量为
$$4+8+16+\cdots+N=O(N).$$
最后从 Lehmer 码累加排名还需要一次线性扫描，所以总体时间复杂度是 \(O(N)=O(2^m)\)。空间方面，需要同时保存排列数组和 Lehmer 数组，两者长度都是 \(N\)，因此空间复杂度为 \(O(N)\)。
Для длин \(N=2^m\) требуется найти 1-базированный лексикографический ранг специальной непредсказуемой перестановки множества \(\{1,\dots,N\}\) по модулю \(10^9+7\). Прямое сравнение со всеми \(N!\) перестановками невозможно уже при умеренных значениях \(m\). Поэтому решение использует сам рекурсивный способ построения перестановки и параллельно переносит код Лемера через те же шаги удвоения.
Обозначим целевую перестановку через
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$$
где позиции нумеруются с нуля. Пусть \(L_N(i)\) обозначает цифру кода Лемера в позиции \(i\), то есть количество более поздних элементов, меньших чем \(P_N(i)\). Тогда 1-базированный лексикографический ранг равен
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$$
Значит, главная задача состоит в том, чтобы одновременно обновлять \(P_N\) и \(L_N\) при переходе от размера \(N\) к размеру \(2N\).
Рекурсия начинается с первого нетривиального случая, когда \(N=4\):
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
Меньшие случаи \(N=2\) и \(N=4\) имеют известные ранги напрямую, поэтому реализации стартуют именно с этого состояния. Уже здесь видны два граничных свойства, которые сохраняются после каждого удвоения:
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
Именно эти инварианты делают две мостовые позиции на следующем шаге особенно простыми.
Предположим, что \(P_N\) уже известна. Тогда перестановка размера \(2N\) строится отображением большинства старых значений в нечётные или чётные числа:
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
То есть старый префикс превращается в нечётные значения, большая часть нового суффикса состоит из чётных значений, а две мостовые позиции соединяют эти блоки. Из равенств \(P_N(0)=1\) и \(P_N(N-1)=N\) немедленно следует сохранение границ:
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
Рассмотрим позицию \(0\le i\le N-2\). Её новое значение равно \(2P_N(i)-1\), то есть оно нечётное. Среди последующих нечётных значений относительный порядок полностью совпадает со старой перестановкой, поэтому прежний вклад в число инверсий \(L_N(i)\) сохраняется.
Но появляются и новые меньшие чётные значения:
$$2,4,\dots,2P_N(i)-2$$
все меньше, чем \(2P_N(i)-1\), и после удвоения все они оказываются справа от позиции \(i\). Таких чётных значений ровно \(P_N(i)-1\). Следовательно,
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$$
Это ключевая формула метода: она позволяет наращивать информацию о ранге, не пересчитывая инверсии заново на каждом шаге.
В мостовой позиции \(N-1\) стоит значение \(2P_N(0)=2\). Число \(1\) уже закреплено в самом левом месте, поэтому справа нет ни одного меньшего значения, и
$$L_{2N}(N-1)=0.$$
Следующая мостовая позиция \(N\) содержит \(2P_N(N-1)-1=2N-1\). Справа от неё находится \(N-1\) чётное значение, и только \(2N\) больше, чем \(2N-1\). Значит, ровно \(N-2\) из них меньше:
$$L_{2N}(N)=N-2.$$
Для остальных суффиксных позиций \(N+j\), где \(1\le j\le N-1\), всё справа тоже чётно, а умножение на \(2\) сохраняет порядок. Поэтому эти цифры кода Лемера просто копируются:
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
Стартуем с
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
После одного шага удвоения получаем
$$P_8=[1,5,3,2,7,6,4,8].$$
По формулам выше код Лемера становится равен
$$L_8=[0,3,1,0,2,1,0,0].$$
Теперь вычислим факториальное разложение ранга:
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
Это значение совпадает с контрольной точкой в реализациях и подтверждает правильность рекурсивного обновления кода Лемера.
Описанный шаг удвоения повторяется до тех пор, пока не будет достигнуто \(N=2^m\). К этому моменту целевая перестановка и весь её код Лемера уже построены, а значит ответом становится просто
$$R_{2^m}\bmod (10^9+7).$$
Никакой перебор перестановок не нужен. Вся необходимая комбинаторная информация уже заложена в самой рекурсивной конструкции.
Реализации на C++, Python и Java используют один и тот же план. Сначала они отдельно обрабатывают самые маленькие степени двойки, затем инициализируют стартовую перестановку и стартовый код Лемера длины \(4\), после чего многократно удваивают оба массива до нужного размера. На каждом шаге сначала записывается новый чётный суффикс, затем вставляются две мостовые позиции, и только после этого старый префикс обновляется на месте. Обход справа налево важен, потому что старые значения ещё нужны в момент построения новой стадии.
Когда целевая длина достигнута, реализация вычисляет лексикографический ранг по коду Лемера. Для этого выполняется проход справа налево с поддержанием текущего факториального веса по модулю \(10^9+7\). Поэтому огромные факториалы не приходится хранить явно. Алгоритмически все три версии совпадают; различается только синтаксис языков.
Пусть \(N=2^m\). Рекурсивное построение затрагивает каждый элемент массива лишь константное число раз по всей цепочке размеров \(4,8,16,\dots,N\). Общий объём работы равен
$$4+8+16+\cdots+N=O(N).$$
Финальный проход для накопления ранга из кода Лемера тоже линейный. Следовательно, суммарная временная сложность равна \(O(N)=O(2^m)\), а объём памяти равен \(O(N)\), поскольку и массив перестановки, и массив кода Лемера имеют длину \(N\).
عندما يكون الطول \(N=2^m\)، تطلب المسألة إيجاد الرتبة المعجمية ذات الأساس \(1\) للتبديل الخاص غير المتوقع على المجموعة \(\{1,\dots,N\}\)، مع أخذ الناتج modulo \(10^9+7\). من المستحيل عمليًا مقارنة هذا التبديل بجميع التبديلات الممكنة وعددها \(N!\) عندما يكبر \(m\). لذلك تعتمد الفكرة على تتبع البنية التكرارية للتبديل نفسه، مع تحديث ترميز Lehmer بالتوازي أثناء كل خطوة مضاعفة.
لنكتب التبديل الهدف على الصورة
$$P_N=[P_N(0),P_N(1),\dots,P_N(N-1)],$$
حيث نرقم المواضع ابتداءً من الصفر. ولتكن \(L_N(i)\) هي قيمة Lehmer عند الموضع \(i\)، أي عدد العناصر الواقعة إلى اليمين والتي تكون أصغر من \(P_N(i)\). عندها تكون الرتبة المعجمية ذات الأساس \(1\) هي
$$R_N=1+\sum_{i=0}^{N-1} L_N(i)\,(N-1-i)!.$$
إذن جوهر الحل هو أن نعرف كيف نحدّث كلًا من \(P_N\) و\(L_N\) معًا عندما ينتقل الحجم من \(N\) إلى \(2N\).
تبدأ البنية التكرارية من أول حالة غير بسيطة، وهي \(N=4\):
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
أما الحالتان الأصغر \(N=2\) و\(N=4\) فرتبتهما معروفة مباشرة، لذلك تستطيع التطبيقات أن تبدأ من هذه البذرة. كما تظهر هنا حقيقتان حدّيتان تستمران بعد كل خطوة مضاعفة:
$$P_N(0)=1,\qquad P_N(N-1)=N.$$
وهاتان العلاقتان هما السبب في أن موضعي الربط في المرحلة التالية يصبحان بسيطين جدًا.
افترض أن \(P_N\) معلومة. عندئذ يُبنى التبديل ذو الحجم \(2N\) بتحويل معظم القيم القديمة إلى أعداد فردية أو زوجية:
$$P_{2N}(i)=2P_N(i)-1\qquad (0\le i\le N-2),$$
$$P_{2N}(N-1)=2P_N(0),\qquad P_{2N}(N)=2P_N(N-1)-1,$$
$$P_{2N}(N+j)=2P_N(j)\qquad (1\le j\le N-1).$$
وبذلك يتحول المقطع القديم في البداية إلى قيم فردية، بينما يتحول معظم المقطع الجديد في النهاية إلى قيم زوجية، ويصل بينهما موضعان وسيطان. وبما أن \(P_N(0)=1\) و\(P_N(N-1)=N\)، فإن النمط الحدّي يستمر تلقائيًا:
$$P_{2N}(0)=1,\qquad P_{2N}(2N-1)=2N.$$
خذ موضعًا \(0\le i\le N-2\). قيمته الجديدة هي \(2P_N(i)-1\)، أي إنها فردية. وبين القيم الفردية الواقعة إلى يمينه يبقى ترتيب المقارنة كما كان تمامًا في التبديل القديم، ولذلك يبقى الإسهام القديم في الانعكاسات \(L_N(i)\) موجودًا كما هو.
لكن توجد أيضًا قيم زوجية أصغر:
$$2,4,\dots,2P_N(i)-2$$
وكلها أصغر من \(2P_N(i)-1\)، وبعد خطوة المضاعفة تصبح جميعها إلى يمين هذا الموضع. وعدد هذه القيم الزوجية يساوي بالضبط \(P_N(i)-1\). لذلك نحصل على
$$L_{2N}(i)=L_N(i)+P_N(i)-1\qquad (0\le i\le N-2).$$
وهذه هي العلاقة الأساسية التي تجعلنا نوسّع معلومات الرتبة من غير إعادة حساب أعداد الانعكاسات من البداية في كل مرة.
يحمل موضع الربط \(N-1\) القيمة \(2P_N(0)=2\). وبما أن القيمة \(1\) ثابتة أصلًا في أقصى اليسار، فلا توجد أي قيمة أصغر على يمينه، ومن ثم
$$L_{2N}(N-1)=0.$$
أما موضع الربط التالي \(N\) فيحمل القيمة \(2P_N(N-1)-1=2N-1\). وعلى يمينه توجد \(N-1\) قيم زوجية، ولا تكون أكبر منه إلا القيمة \(2N\) وحدها، ولذلك يوجد بالضبط \(N-2\) قيمة أصغر منه:
$$L_{2N}(N)=N-2.$$
وبالنسبة إلى بقية مواضع الذيل \(N+j\) حيث \(1\le j\le N-1\)، فإن كل ما يوجد إلى اليمين يبقى زوجيًا أيضًا، والضرب في \(2\) لا يغيّر الترتيب. لذلك تُنسخ هذه الأرقام كما هي:
$$L_{2N}(N+j)=L_N(j)\qquad (1\le j\le N-1).$$
نبدأ من
$$P_4=[1,3,2,4],\qquad L_4=[0,1,0,0].$$
وبتطبيق قاعدة المضاعفة نحصل على
$$P_8=[1,5,3,2,7,6,4,8].$$
أما أرقام Lehmer الجديدة فتصبح
$$L_8=[0,3,1,0,2,1,0,0].$$
ثم نحسب التوسع العاملي:
$$\begin{aligned} R_8 &=1+0\cdot 7!+3\cdot 6!+1\cdot 5!+0\cdot 4!+2\cdot 3!+1\cdot 2!+0\cdot 1!+0\cdot 0!\\ &=1+2160+120+12+2\\ &=2295. \end{aligned}$$
وهذه القيمة هي نفسها نقطة التحقق المستخدمة في التطبيقات، وهذا يؤكد صحة التحديث التكراري لترميز Lehmer.
نكرر خطوة المضاعفة حتى نصل إلى \(N=2^m\). عند هذه اللحظة يكون التبديل الهدف وترميز Lehmer الكامل له قد بُنيا بالفعل، وبالتالي تصبح الإجابة المطلوبة هي ببساطة
$$R_{2^m}\bmod (10^9+7).$$
لا حاجة إلى تعداد التبديلات أو فرزها. فالبنية التكرارية نفسها تختزن كل المعلومات التوافقية اللازمة لاستخراج الرتبة النهائية.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تعالج أولًا الحالات الصغيرة مباشرة، ثم تهيئ التبديل الابتدائي وترميز Lehmer الابتدائي للطول \(4\)، وبعد ذلك تضاعف المصفوفتين معًا حتى تصل إلى الحجم المطلوب. في كل خطوة مضاعفة يُكتب الذيل الزوجي الجديد أولًا، ثم يوضع موضعا الربط، ثم تُحدَّث المقدمة القديمة في المكان نفسه. والسبب في السير من اليمين إلى اليسار هو أن القيم القديمة تظل مطلوبة أثناء بناء المرحلة الجديدة.
وبعد اكتمال الطول الهدف، تحسب الشيفرة الرتبة المعجمية انطلاقًا من ترميز Lehmer. ويتم ذلك بمسح من اليمين إلى اليسار مع الاحتفاظ بالوزن العاملي الحالي modulo \(10^9+7\)، لذلك لا حاجة إلى تخزين مضروبات ضخمة بصورة مستقلة. المنطق الخوارزمي متطابق في اللغات الثلاث، والاختلاف يقتصر على الصياغة البرمجية.
لتكن \(N=2^m\). أثناء سلسلة الأحجام \(4,8,16,\dots,N\) يُعالَج كل موضع في المصفوفات عددًا ثابتًا من المرات فقط، ولذلك يكون مجموع العمل
$$4+8+16+\cdots+N=O(N).$$
أما المسح الأخير لتجميع الرتبة من ترميز Lehmer فهو مرور خطي آخر. لذا فزمن التنفيذ الكلي هو \(O(N)=O(2^m)\)، بينما استهلاك الذاكرة هو \(O(N)\) لأن مصفوفتَي التبديل وترميز Lehmer كلتيهما بطول \(N\).