For each \(n\), let \(P(n)\) be the number of permutations \(\pi\) of \(\{1,2,\dots,2n\}\) satisfying
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2.$$
The task is to compute \(P(100000000)\) modulo \(10^9+7\). A direct count is completely infeasible, because the ambient space has \((2n)!\) permutations. The solution works only because the two subsequence constraints force the associated Young diagram into an extremely small family.
Define
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
The key move is to stop counting permutations directly and instead count the possible RSK shapes and the number of permutations attached to each such shape.
The Robinson-Schensted correspondence sends every permutation \(\pi\in S_{2n}\) to a partition \(\lambda\vdash 2n\) with
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi).$$
Here \(\lambda_1\) is the first row length, while \(\lambda'_1\) is the first column length, equivalently the total number of rows. Therefore \(\operatorname{LDS}(\pi)\le 2\) means that \(\lambda\) has at most two rows.
So every admissible shape has the form \(\lambda=(a,b)\) with \(a\ge b\ge 0\) and \(a+b=2n\). The bound on the longest increasing subsequence gives \(a\le n+1\). But every two-row partition of size \(2n\) also satisfies \(a\ge (a+b)/2=n\). Hence only two values of \(a\) are possible:
$$a\in\{n,n+1\}.$$
This leaves exactly two admissible shapes,
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1).$$
That is the decisive simplification: the original count over \((2n)!\) permutations collapses to a sum over just two Young shapes.
RSK is a bijection between permutations and pairs \((P,Q)\) of standard Young tableaux of the same shape. If \(f^\lambda\) denotes the number of standard Young tableaux of shape \(\lambda\), then the number of permutations with RSK shape \(\lambda\) is
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2.$$
So once the two admissible shapes are known, the problem is reduced to evaluating \(f^\lambda\) for those two shapes and squaring the resulting tableau counts.
For a two-row shape \((a,b)\), the hook lengths can be written explicitly. In the first row, the leftmost \(b\) cells have hook lengths \(a-j+2\) for \(1\le j\le b\), and the remaining \(a-b\) cells have hook lengths \(a-j+1\) for \(b<j\le a\). In the second row, the hook lengths are \(b-j+1\) for \(1\le j\le b\).
Multiplying them gives
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}.$$
Now the hook-length formula yields
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$
Substituting the two admissible shapes gives
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}.$$
Therefore
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
The first term is the square of the Catalan number \(C_n\). The second term comes from the neighboring shape \((n+1,n-1)\), and there are no other contributions because no other shapes survive the subsequence bounds.
It is convenient to set
$$B_n=\binom{2n}{n}.$$
Then the answer becomes
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}.$$
The identity
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}$$
is what allows the second shape to be expressed using the same central binomial coefficient. This is exactly why the implementations need only one factorial ratio rather than two unrelated binomial computations.
For the target value \(n=100000000\), we have \(2n=200000000<10^9+7\). So \(n!\), \(n+1\), and \(n+2\) are all nonzero modulo the prime \(10^9+7\), and every denominator in the closed form is invertible.
When \(n=2\), the admissible shapes are \((2,2)\) and \((3,1)\). The hook-length formula gives
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3.$$
Hence
$$P(2)=2^2+3^2=13.$$
So among the \(4!=24\) permutations of \(\{1,2,3,4\}\), exactly 13 satisfy \(\operatorname{LIS}(\pi)\le 3\) and \(\operatorname{LDS}(\pi)\le 2\). This is the smallest nontrivial checkpoint used to confirm the closed form.
The C++, Python, and Java implementations all evaluate the closed form above. None of them constructs Young tableaux or searches through permutations for the target case.
The implementation multiplies the integers \(1,2,\dots,2n\) modulo \(10^9+7\). When the loop reaches \(n\), it records the current product, so the same pass produces both \(n!\) and \((2n)!\). From these two quantities it forms
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}.$$
Next the implementation computes the modular inverses of \(n!\), \(n+1\), and \(n+2\) by fast exponentiation and Fermat's little theorem,
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
With those inverses available, it evaluates the contribution of the shape \((n,n)\), the contribution of the shape \((n+1,n-1)\), squares both values, adds them, and reduces modulo \(10^9+7\). The whole computational core is just a linear sweep plus a constant number of modular exponentiations.
One compiled implementation also performs brute-force verification for very small \(n\), checking that direct enumeration agrees with the closed form and that known small answers are reproduced. Those checks validate the mathematics, but they are separate from the large-\(n\) computation.
The dominant cost is the single loop from \(1\) to \(2n\), so the runtime is \(O(n)\). The modular inverses require only a constant number of exponentiations, each costing \(O(\log(10^9+7))\), which does not change the overall asymptotic bound. Memory usage is \(O(1)\), because only a few scalar accumulators are stored. The tiny brute-force checks run only for fixed small inputs and therefore do not affect the asymptotic complexity.
Für jedes \(n\) sei \(P(n)\) die Anzahl der Permutationen \(\pi\) von \(\{1,2,\dots,2n\}\) mit
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2.$$
Gesucht ist \(P(100000000)\) modulo \(10^9+7\). Ein direktes Zählen ist ausgeschlossen, denn der zugrunde liegende Raum hat \((2n)!\) Elemente. Die Lösung funktioniert nur deshalb, weil die beiden Teilfolgen-Schranken die zugehörige Young-Form auf eine winzige Menge möglicher Fälle einschränken.
Wir definieren
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
Der entscheidende Schritt besteht darin, nicht mehr die Permutationen selbst zu zählen, sondern die möglichen RSK-Formen und die Anzahl der Permutationen pro Form.
Die Robinson-Schensted-Korrespondenz ordnet jeder Permutation \(\pi\in S_{2n}\) eine Partition \(\lambda\vdash 2n\) zu, wobei
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi).$$
\(\lambda_1\) ist die Länge der ersten Zeile, \(\lambda'_1\) die Länge der ersten Spalte und damit zugleich die Zahl der Zeilen. Also bedeutet \(\operatorname{LDS}(\pi)\le 2\), dass \(\lambda\) höchstens zwei Zeilen besitzt.
Jede zulässige Form hat daher die Gestalt \(\lambda=(a,b)\) mit \(a\ge b\ge 0\) und \(a+b=2n\). Aus der Schranke für die längste steigende Teilfolge folgt \(a\le n+1\). Andererseits gilt für jede Zweizeilenpartition von \(2n\) immer \(a\ge (a+b)/2=n\). Somit bleiben nur zwei Möglichkeiten:
$$a\in\{n,n+1\}.$$
Also sind genau die beiden Formen
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1)$$
zulässig. Damit bricht die ursprüngliche Zählung über \((2n)!\) Permutationen auf eine Summe über nur zwei Young-Formen zusammen.
RSK ist eine Bijektion zwischen Permutationen und Paaren \((P,Q)\) standardisierter Young-Tableaux gleicher Form. Bezeichnet \(f^\lambda\) die Anzahl standardisierter Young-Tableaux der Form \(\lambda\), dann ist die Zahl der Permutationen mit RSK-Form \(\lambda\)
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2.$$
Hat man also die zwei zulässigen Formen identifiziert, muss man nur noch deren Tableau-Anzahlen bestimmen und anschließend quadrieren.
Für eine Zweizeilenform \((a,b)\) lassen sich die Hakenlängen explizit schreiben. In der ersten Zeile haben die linken \(b\) Kästchen die Hakenlängen \(a-j+2\) für \(1\le j\le b\), die restlichen \(a-b\) Kästchen die Hakenlängen \(a-j+1\) für \(b<j\le a\). In der zweiten Zeile stehen die Hakenlängen \(b-j+1\) für \(1\le j\le b\).
Ihr Produkt ist
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}.$$
Mit der Hook-Length-Formel folgt daraus
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$
Für die beiden zulässigen Formen ergibt das
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}.$$
Also erhält man
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
Der erste Summand ist das Quadrat der Catalan-Zahl \(C_n\). Der zweite Summand stammt von der Nachbarform \((n+1,n-1)\); weitere Beiträge gibt es nicht.
Es ist praktisch,
$$B_n=\binom{2n}{n}$$
zu setzen. Dann lautet die Antwort
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}.$$
Die Identität
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}$$
erlaubt es, auch den zweiten Formbeitrag mit derselben zentralen Binomialzahl auszudrücken. Genau deshalb brauchen die Implementierungen nur einen Fakultätsquotienten und nicht zwei unabhängige Binomialberechnungen.
Für den Zielwert \(n=100000000\) gilt \(2n=200000000<10^9+7\). Also sind \(n!\), \(n+1\) und \(n+2\) modulo der Primzahl \(10^9+7\) alle invertierbar.
Für \(n=2\) sind die zulässigen Formen \((2,2)\) und \((3,1)\). Die Hook-Length-Formel liefert
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3.$$
Damit
$$P(2)=2^2+3^2=13.$$
Unter den \(4!=24\) Permutationen von \(\{1,2,3,4\}\) erfüllen also genau 13 die Bedingungen \(\operatorname{LIS}(\pi)\le 3\) und \(\operatorname{LDS}(\pi)\le 2\). Das ist der kleinste nichttriviale Kontrollwert für die geschlossene Formel.
Die C++-, Python- und Java-Implementierungen werten alle dieselbe geschlossene Formel aus. Für den eigentlichen Zielwert wird weder ein Tableau konstruiert noch eine Permutation enumeriert.
Die Implementierung multipliziert die Zahlen \(1,2,\dots,2n\) modulo \(10^9+7\). Sobald die Schleife den Wert \(n\) erreicht, wird das Zwischenprodukt gespeichert. Auf diese Weise entstehen \(n!\) und \((2n)!\) in demselben Durchlauf. Daraus wird
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}$$
gebildet.
Anschließend berechnet die Implementierung die modularen Inversen von \(n!\), \(n+1\) und \(n+2\) per schneller Exponentiation und dem kleinen Satz von Fermat,
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Mit diesen Inversen wird der Beitrag der Form \((n,n)\) berechnet, ebenso der Beitrag der Form \((n+1,n-1)\); danach werden beide Werte quadriert, addiert und modulo \(10^9+7\) reduziert. Der Rechenkern ist also nur ein linearer Durchlauf plus konstant viele modulare Potenzierungen.
Eine kompilierte Implementierung ergänzt das durch eine brute-force-Prüfung für sehr kleine \(n\), sodass direkte Enumeration und geschlossene Formel gegeneinander verglichen werden können. Diese Tests validieren die Herleitung, gehören aber nicht zum eigentlichen Großrechenweg.
Die dominante Arbeit ist die einzelne Schleife von \(1\) bis \(2n\), also beträgt die Laufzeit \(O(n)\). Die modularen Inversen brauchen nur konstant viele Exponentiationen der Kosten \(O(\log(10^9+7))\), was die Gesamtschranke nicht ändert. Der Speicherbedarf ist \(O(1)\), weil nur wenige skalare Akkumulatoren gehalten werden. Die kleinen brute-force-Tests laufen nur für feste Mini-Eingaben und beeinflussen die Asymptotik nicht.
Her \(n\) için \(P(n)\), \(\{1,2,\dots,2n\}\) kümesinin
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2$$
koşullarını sağlayan \(\pi\) permütasyonlarının sayısı olsun. Sorulan şey \(P(100000000)\) değerini \(10^9+7\) modunda bulmaktır. Doğrudan sayım imkansızdır; çünkü arka planda \((2n)!\) tane permütasyon vardır. Çözüm ancak bu iki alt dizi kısıtının ilgili Young şeklini çok küçük bir aileye indirmesi sayesinde mümkün olur.
Şunu tanımlayalım:
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
Asıl fikir, permütasyonları tek tek saymayı bırakıp RSK şekillerini ve her şekle düşen permütasyon sayısını saymaktır.
Robinson-Schensted eşlemesi her \(\pi\in S_{2n}\) permütasyonunu,
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi)$$
özelliğine sahip bir \(\lambda\vdash 2n\) bölmesine götürür. Burada \(\lambda_1\) ilk satır uzunluğu, \(\lambda'_1\) ise ilk sütun uzunluğu, dolayısıyla toplam satır sayısıdır. Bu yüzden \(\operatorname{LDS}(\pi)\le 2\) demek, \(\lambda\) en fazla iki satırlıdır demektir.
O halde her geçerli şekil \(\lambda=(a,b)\) biçimindedir; burada \(a\ge b\ge 0\) ve \(a+b=2n\). En uzun artan alt dizi sınırı \(a\le n+1\) verir. Öte yandan iki satırlı her \(2n\) hücreli şekil için \(a\ge (a+b)/2=n\) zorunludur. Dolayısıyla \(a\) sadece şu iki değeri alabilir:
$$a\in\{n,n+1\}.$$
Böylece yalnızca şu iki Young şekli kalır:
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1).$$
Asıl sadeleşme budur. Başlangıçta \((2n)!\) permütasyon üzerinde duran problem, sonunda yalnızca iki şeklin katkısına iner.
RSK, permütasyonlar ile aynı şekle sahip standart Young tabloları çiftleri \((P,Q)\) arasında bir bijeksiyondur. Eğer \(f^\lambda\), şekil \(\lambda\) için standart Young tablo sayısıysa, RSK şekli \(\lambda\) olan permütasyon sayısı
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2$$
olur. Yani iki izinli şekil bulununca geriye sadece bu iki şeklin tablo sayısını hesaplayıp karelerini almak kalır.
\((a,b)\) biçimindeki iki satırlı bir şekil için kanca uzunlukları açıkça yazılabilir. İlk satırda soldaki \(b\) hücrenin kanca uzunlukları \(1\le j\le b\) için \(a-j+2\), kalan \(a-b\) hücrenin kanca uzunlukları ise \(b<j\le a\) için \(a-j+1\) olur. İkinci satırdaki kanca uzunlukları da \(1\le j\le b\) için \(b-j+1\)'dir.
Bu çarpım
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}$$
şeklinde sadeleşir. Hook-length formülünü uygularsak
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}$$
elde edilir. İzin verilen iki şekli yerine koyunca
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}$$
çıkar. Sonuç olarak
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
İlk terim Catalan sayısı \(C_n\)'nin karesidir. İkinci terim ise komşu şekil \((n+1,n-1)\)'den gelir; başka şekil kalmadığı için başka katkı da yoktur.
Şimdi
$$B_n=\binom{2n}{n}$$
yazalım. O zaman cevap
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}$$
olur. Burada
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}$$
özdeşliği, ikinci şeklin katkısını da aynı merkezi binom katsayısı üzerinden yazmamızı sağlar. Kodun yalnızca tek bir faktöriyel oranı hesaplamasının sebebi tam olarak budur.
Hedef değerde \(n=100000000\) olduğundan \(2n=200000000<10^9+7\) olur. Bu nedenle \(n!\), \(n+1\) ve \(n+2\) asal mod \(10^9+7\) altında sıfır değildir ve hepsinin tersi vardır.
\(n=2\) için geçerli şekiller \((2,2)\) ve \((3,1)\)'dir. Hook-length formülü
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3$$
sonucunu verir. Dolayısıyla
$$P(2)=2^2+3^2=13.$$
Yani \(\{1,2,3,4\}\)'ün \(4!=24\) permütasyonu içinde tam 13 tanesi \(\operatorname{LIS}(\pi)\le 3\) ve \(\operatorname{LDS}(\pi)\le 2\) koşullarını sağlar. Bu değer, kapalı formülü doğrulamak için kullanılan en küçük anlamlı kontrol noktasıdır.
C++, Python ve Java uygulamalarının üçü de yukarıdaki kapalı formülü hesaplar. Hedef girdi için ne Young tablosu üretilir ne de permütasyon aranır.
Uygulama \(1,2,\dots,2n\) sayılarını \(10^9+7\) modunda çarpar. Döngü \(n\)'e geldiğinde o andaki çarpımı saklar; böylece aynı geçişte hem \(n!\) hem de \((2n)!\) elde edilir. Bundan da
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}$$
hesabı kurulur.
Daha sonra uygulama \(n!\), \(n+1\) ve \(n+2\) için modüler tersleri hızlı üs alma ve Fermat'nın küçük teoremi ile bulur:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Bu terslerle önce \((n,n)\) şeklinin katkısı, sonra \((n+1,n-1)\) şeklinin katkısı hesaplanır; iki değer karelenir, toplanır ve \(10^9+7\) moduna indirilir. Yani hesaplama çekirdeği lineer bir geçiş ve sabit sayıda modüler üs almadan ibarettir.
Derlenmiş uygulamalardan biri ayrıca çok küçük \(n\) değerleri için brute-force doğrulaması yapar; böylece doğrudan sayım ile kapalı formülün uyuştuğu görülür. Bu adım büyük giriş için kullanılan algoritmanın parçası değildir, sadece matematiksel türetimi sınar.
Baskın maliyet \(1\)'den \(2n\)'e kadar olan tek döngüdür; dolayısıyla çalışma süresi \(O(n)\)'dir. Modüler tersler için gereken üs alma işlemleri sabit sayıdadır ve her biri \(O(\log(10^9+7))\) maliyetlidir; bu da toplam asimptotiği değiştirmez. Bellek kullanımı \(O(1)\)'dir, çünkü sadece birkaç skaler biriktirici tutulur. Küçük brute-force kontroller sabit boyutlu girdilerle sınırlı olduğundan asimptotik sınırı etkilemez.
Para cada \(n\), sea \(P(n)\) el número de permutaciones \(\pi\) de \(\{1,2,\dots,2n\}\) que satisfacen
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2.$$
La tarea es calcular \(P(100000000)\) módulo \(10^9+7\). Contar directamente es inviable, porque el espacio total tiene \((2n)!\) permutaciones. El enfoque solo funciona porque las dos restricciones sobre subsecuencias obligan a que el diagrama de Young asociado pertenezca a una familia extremadamente pequeña.
Definimos
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
La idea central es dejar de contar permutaciones de forma directa y pasar a contar las formas RSK posibles y cuántas permutaciones produce cada una.
La correspondencia de Robinson-Schensted asocia a cada permutación \(\pi\in S_{2n}\) una partición \(\lambda\vdash 2n\) tal que
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi).$$
Aquí \(\lambda_1\) es la longitud de la primera fila, mientras que \(\lambda'_1\) es la longitud de la primera columna, es decir, también el número total de filas. Por tanto, \(\operatorname{LDS}(\pi)\le 2\) significa que \(\lambda\) tiene como mucho dos filas.
Así, toda forma admisible puede escribirse como \(\lambda=(a,b)\) con \(a\ge b\ge 0\) y \(a+b=2n\). La cota sobre la subsecuencia creciente más larga impone \(a\le n+1\). Pero en toda partición de dos filas con \(2n\) celdas se cumple también \(a\ge (a+b)/2=n\). Por ello, solo hay dos posibilidades:
$$a\in\{n,n+1\}.$$
En consecuencia, las únicas formas permitidas son
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1).$$
Esa es la reducción decisiva: el conteo original sobre \((2n)!\) permutaciones se convierte en una suma sobre solo dos formas de Young.
RSK es una biyección entre permutaciones y pares \((P,Q)\) de tableaux de Young estándar con la misma forma. Si \(f^\lambda\) denota el número de tableaux estándar de forma \(\lambda\), entonces el número de permutaciones con forma RSK igual a \(\lambda\) es
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2.$$
Por tanto, una vez identificadas las dos formas admisibles, el problema queda reducido a evaluar \(f^\lambda\) en esos dos casos y elevar al cuadrado ambos conteos.
Para una forma de dos filas \((a,b)\), las longitudes de gancho pueden escribirse explícitamente. En la primera fila, las \(b\) celdas de la izquierda tienen longitudes \(a-j+2\) para \(1\le j\le b\), y las \(a-b\) celdas restantes tienen longitudes \(a-j+1\) para \(b<j\le a\). En la segunda fila, las longitudes son \(b-j+1\) para \(1\le j\le b\).
Su producto es
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}.$$
La fórmula de hook-length da entonces
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$
Al sustituir las dos formas admisibles obtenemos
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}.$$
Por lo tanto,
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
El primer sumando es el cuadrado del número de Catalan \(C_n\). El segundo procede de la forma vecina \((n+1,n-1)\), y no aparecen más términos porque ninguna otra forma sobrevive a las restricciones.
Es útil escribir
$$B_n=\binom{2n}{n}.$$
Con esa notación, la respuesta toma la forma
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}.$$
La identidad
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}$$
permite expresar también el segundo término usando el mismo coeficiente binomial central. Precisamente por eso las implementaciones solo necesitan un cociente factorial central y unas pocas inversiones modulares.
Para el valor objetivo \(n=100000000\), se tiene \(2n=200000000<10^9+7\). En consecuencia, \(n!\), \(n+1\) y \(n+2\) son invertibles módulo la prima \(10^9+7\).
Cuando \(n=2\), las formas admisibles son \((2,2)\) y \((3,1)\). La fórmula de hook-length produce
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3.$$
Así,
$$P(2)=2^2+3^2=13.$$
Entre las \(4!=24\) permutaciones de \(\{1,2,3,4\}\), exactamente 13 cumplen \(\operatorname{LIS}(\pi)\le 3\) y \(\operatorname{LDS}(\pi)\le 2\). Ese es el primer punto de control no trivial para verificar la fórmula cerrada.
Las implementaciones en C++, Python y Java evalúan la fórmula cerrada anterior. Para el caso objetivo no construyen tableaux ni recorren permutaciones.
La implementación multiplica los enteros \(1,2,\dots,2n\) módulo \(10^9+7\). Cuando el bucle alcanza \(n\), guarda el producto parcial, de modo que la misma pasada entrega \(n!\) y \((2n)!\). Con ello forma
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}.$$
Después calcula los inversos modulares de \(n!\), \(n+1\) y \(n+2\) mediante exponenciación rápida y el pequeño teorema de Fermat,
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Con esos inversos evalúa la contribución de la forma \((n,n)\), la contribución de la forma \((n+1,n-1)\), eleva ambas al cuadrado, las suma y reduce el resultado módulo \(10^9+7\). El núcleo algorítmico es, por tanto, una pasada lineal y un número constante de exponenciaciones modulares.
Una implementación compilada añade además comprobaciones por fuerza bruta para valores muy pequeños de \(n\), verificando que la enumeración directa coincide con la fórmula cerrada. Esas pruebas validan la derivación, pero no forman parte del algoritmo para el caso grande.
El coste dominante es el único bucle desde \(1\) hasta \(2n\), por lo que el tiempo es \(O(n)\). Las inversiones modulares requieren solo un número constante de exponenciaciones de coste \(O(\log(10^9+7))\), lo cual no altera la cota total. El espacio es \(O(1)\), porque solo se mantienen unos pocos acumuladores escalares. Las verificaciones exhaustivas se ejecutan únicamente para entradas diminutas y no afectan a la complejidad asintótica.
对每个 \(n\)，记 \(P(n)\) 为满足下列条件的排列 \(\pi\) 的个数，其中 \(\pi\) 是 \(\{1,2,\dots,2n\}\) 的一个排列：
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2.$$
题目要求计算 \(P(100000000)\bmod 10^9+7\)。如果直接在 \((2n)!\) 个排列里做筛选，这个问题根本无法处理。真正可行的原因是，这两个子序列约束会把排列在 RSK 对应下的 Young 形状压缩到极少数情形。
记
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
核心思路是不再直接数排列，而是改成数可能出现的 RSK 形状，以及每种形状对应多少个排列。
Robinson-Schensted 对应会把每个 \(\pi\in S_{2n}\) 映到一个分拆 \(\lambda\vdash 2n\)，并满足
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi).$$
这里 \(\lambda_1\) 是第一行长度，\(\lambda'_1\) 是第一列长度，而第一列长度也正好等于总行数。因此，\(\operatorname{LDS}(\pi)\le 2\) 等价于 \(\lambda\) 最多只有两行。
于是每个合法形状都可以写成 \(\lambda=(a,b)\)，其中 \(a\ge b\ge 0\) 且 \(a+b=2n\)。另一方面，\(\operatorname{LIS}(\pi)\le n+1\) 给出 \(a\le n+1\)。但任何两行、总大小为 \(2n\) 的形状都满足 \(a\ge (a+b)/2=n\)。所以 \(a\) 只能是下面两种值：
$$a\in\{n,n+1\}.$$
因此，最终只剩下两种可能的 Young 形状：
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1).$$
这一步就是整道题的关键化简。原本需要面对 \((2n)!\) 个排列，现在只需要处理两个形状的贡献。
RSK 给出了排列与同形标准 Young 表对 \((P,Q)\) 之间的双射。如果用 \(f^\lambda\) 表示形状 \(\lambda\) 的标准 Young 表个数，那么 RSK 形状恰好等于 \(\lambda\) 的排列个数就是
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2.$$
所以一旦合法形状只剩两种，问题就被压缩成了两个标准 Young 表计数的平方和。
对两行形状 \((a,b)\) 而言，hook-length 可以直接列出来。第一行左边的 \(b\) 个格子，其 hook-length 为 \(a-j+2\)，其中 \(1\le j\le b\)；第一行剩余的 \(a-b\) 个格子，其 hook-length 为 \(a-j+1\)，其中 \(b<j\le a\)。第二行的 \(b\) 个格子，其 hook-length 为 \(b-j+1\)，其中 \(1\le j\le b\)。
把这些量全部相乘，得到
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}.$$
再套用 hook-length 公式，便有
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$
把两种允许的形状代入，就得到
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}.$$
因此答案为
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
第一项正是 Catalan 数 \(C_n\) 的平方。第二项来自相邻的两行形状 \((n+1,n-1)\)。由于没有第三种合法形状，整个计数就到此为止。
设
$$B_n=\binom{2n}{n}.$$
那么上式可以写成
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}.$$
这里用到了恒等式
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}.$$
这说明第二个形状的贡献也可以完全由同一个中心二项式系数表示出来。正因为如此，程序只需要计算一次中心二项式系数，再配合少量模逆即可。
题目中的目标值是 \(n=100000000\)，于是 \(2n=200000000<10^9+7\)。因此 \(n!\)、\(n+1\)、\(n+2\) 在模素数 \(10^9+7\) 意义下都非零，公式中出现的分母全部可逆。
当 \(n=2\) 时，允许的形状只有 \((2,2)\) 和 \((3,1)\)。由上面的公式可得
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3.$$
所以
$$P(2)=2^2+3^2=13.$$
也就是说，在 \(\{1,2,3,4\}\) 的 \(4!=24\) 个排列中，恰有 13 个同时满足 \(\operatorname{LIS}(\pi)\le 3\) 与 \(\operatorname{LDS}(\pi)\le 2\)。这正是最小的非平凡校验值。
C++、Python 和 Java 实现都在直接计算上面的闭式。对真正的目标输入，它们不会去构造 Young 表，也不会遍历排列空间。
实现先把 \(1,2,\dots,2n\) 在模 \(10^9+7\) 下连乘。当循环走到 \(n\) 时，当前乘积会被记下来，因此同一趟循环就同时得到了 \(n!\) 和 \((2n)!\)。接着利用
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}$$
恢复中心二项式系数。
随后，程序通过快速幂和费马小定理求出 \(n!\)、\(n+1\)、\(n+2\) 的模逆：
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
有了这些逆元之后，就可以计算形状 \((n,n)\) 的贡献和形状 \((n+1,n-1)\) 的贡献，再把它们分别平方，相加，并对 \(10^9+7\) 取模。程序的核心因此只是一次线性扫描和常数次模幂运算。
其中一个编译型实现还会对极小的 \(n\) 做穷举验证，确认直接计数与闭式完全一致。这些校验用于验证推导本身，并不是大输入算法的一部分。
主导成本是从 \(1\) 到 \(2n\) 的那一次循环，因此时间复杂度是 \(O(n)\)。模逆只需要常数次快速幂，每次代价为 \(O(\log(10^9+7))\)，不会改变总的渐近复杂度。空间复杂度是 \(O(1)\)，因为实现只维护少量标量累积量。极小规模的穷举检查只针对固定的小输入，因此不影响整体复杂度结论。
Для каждого \(n\) обозначим через \(P(n)\) число перестановок \(\pi\) множества \(\{1,2,\dots,2n\}\), удовлетворяющих условиям
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2.$$
Нужно вычислить \(P(100000000)\) по модулю \(10^9+7\). Прямой перебор невозможен: пространство всех кандидатов имеет размер \((2n)!\). Решение становится реальным только потому, что оба ограничения на подпоследовательности резко сужают возможную диаграмму Юнга, связанную с перестановкой.
Определим
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
Главная идея состоит в том, чтобы перестать считать сами перестановки и вместо этого посчитать допустимые формы RSK и вклад каждой формы.
Соответствие Робинсона-Шенстеда сопоставляет каждой перестановке \(\pi\in S_{2n}\) разбиение \(\lambda\vdash 2n\), для которого выполняются тождества
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi).$$
Здесь \(\lambda_1\) есть длина первой строки, а \(\lambda'_1\) есть длина первого столбца, то есть одновременно число строк. Поэтому условие \(\operatorname{LDS}(\pi)\le 2\) означает, что у \(\lambda\) не больше двух строк.
Значит, любая допустимая форма имеет вид \(\lambda=(a,b)\), где \(a\ge b\ge 0\) и \(a+b=2n\). Ограничение на наибольшую возрастающую подпоследовательность дает \(a\le n+1\). Но у любой двухстрочной диаграммы размера \(2n\) также есть неравенство \(a\ge (a+b)/2=n\). Следовательно, возможны только два значения:
$$a\in\{n,n+1\}.$$
Итак, остаются ровно две допустимые формы,
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1).$$
Это и есть ключевое упрощение: огромная сумма по \((2n)!\) перестановкам сводится к сумме по двум формам Юнга.
RSK задает биекцию между перестановками и парами \((P,Q)\) стандартных таблиц Юнга одинаковой формы. Если \(f^\lambda\) обозначает число стандартных таблиц Юнга формы \(\lambda\), то число перестановок с формой \(\lambda\) равно
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2.$$
Поэтому после нахождения двух допустимых форм остается лишь вычислить соответствующие значения \(f^\lambda\) и возвести их в квадрат.
Для двухстрочной формы \((a,b)\) длины крюков выписываются явно. В первой строке у левых \(b\) клеток длины равны \(a-j+2\) при \(1\le j\le b\), а у остальных \(a-b\) клеток первой строки длины равны \(a-j+1\) при \(b<j\le a\). Во второй строке длины крюков равны \(b-j+1\) при \(1\le j\le b\).
Произведение всех крюков равно
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}.$$
Тогда формула крюков дает
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$
Подставляя две разрешенные формы, получаем
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}.$$
Следовательно,
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
Первое слагаемое является квадратом числа Каталана \(C_n\). Второе возникает из соседней формы \((n+1,n-1)\). Других слагаемых нет, потому что других допустимых форм нет.
Удобно ввести обозначение
$$B_n=\binom{2n}{n}.$$
Тогда ответ можно записать так:
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}.$$
Тождество
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}$$
показывает, что и второй вклад выражается через тот же центральный биномиальный коэффициент. Именно поэтому в реализации нужен только один факториальный коэффициент и несколько модульных обратных.
Для целевого значения \(n=100000000\) имеем \(2n=200000000<10^9+7\). Следовательно, \(n!\), \(n+1\) и \(n+2\) ненулевые по модулю простого числа \(10^9+7\), а значит все знаменатели обратимы.
При \(n=2\) допустимыми являются формы \((2,2)\) и \((3,1)\). Формула крюков дает
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3.$$
Поэтому
$$P(2)=2^2+3^2=13.$$
То есть среди \(4!=24\) перестановок множества \(\{1,2,3,4\}\) ровно 13 удовлетворяют условиям \(\operatorname{LIS}(\pi)\le 3\) и \(\operatorname{LDS}(\pi)\le 2\). Это первый нетривиальный контроль для замкнутой формулы.
Реализации на C++, Python и Java вычисляют именно эту замкнутую формулу. Для целевого случая они не строят таблицы Юнга и не перебирают перестановки.
Сначала реализация перемножает числа \(1,2,\dots,2n\) по модулю \(10^9+7\). Когда цикл доходит до \(n\), промежуточное произведение сохраняется, так что за тот же проход получаются и \(n!\), и \((2n)!\). Затем вычисляется
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}.$$
После этого находятся модульные обратные к \(n!\), \(n+1\) и \(n+2\) с помощью быстрого возведения в степень и малой теоремы Ферма,
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Имея эти обратные, реализация вычисляет вклад формы \((n,n)\), вклад формы \((n+1,n-1)\), возводит оба значения в квадрат, складывает их и берет результат по модулю \(10^9+7\). По существу алгоритм состоит из линейного прохода и константного числа модульных степеней.
Одна компилируемая реализация дополнительно делает brute-force-проверки для очень малых \(n\), сравнивая прямой перебор с замкнутой формулой. Эти проверки подтверждают вывод, но не являются частью большого вычисления.
Главная работа - это единственный цикл от \(1\) до \(2n\), поэтому время работы равно \(O(n)\). Модульные обратные требуют лишь константного числа возведений в степень стоимости \(O(\log(10^9+7))\), что не меняет итоговую асимптотику. Память равна \(O(1)\), так как хранятся только несколько скалярных накопителей. Малые brute-force-проверки выполняются только на фиксированных микровходах и на асимптотику не влияют.
لكل \(n\)، نرمز بـ \(P(n)\) إلى عدد التبديلات \(\pi\) للمجموعة \(\{1,2,\dots,2n\}\) التي تحقق
$$\operatorname{LIS}(\pi)\le n+1,\qquad \operatorname{LDS}(\pi)\le 2.$$
المطلوب هو حساب \(P(100000000)\) بترديد \(10^9+7\). العد المباشر مستحيل عمليًا، لأن فضاء البحث يحتوي على \((2n)!\) تبديلًا. سبب إمكان الحل هو أن شرطي المتتاليتين الجزئيتين يفرضان على شكل يونغ الموافق تحت مراسلة RSK عددًا ضئيلًا جدًا من الحالات.
نكتب
$$P(n)=\#\left\{\pi\in S_{2n}:\operatorname{LIS}(\pi)\le n+1,\ \operatorname{LDS}(\pi)\le 2\right\}.$$
الفكرة الأساسية هي التوقف عن عدّ التبديلات نفسها، والانتقال بدلًا من ذلك إلى عدّ أشكال RSK الممكنة وعدد التبديلات المرتبطة بكل شكل.
تعطي مراسلة روبنسون-شنستد لكل تبديل \(\pi\in S_{2n}\) قسمة \(\lambda\vdash 2n\) تحقق
$$\lambda_1=\operatorname{LIS}(\pi),\qquad \lambda'_1=\operatorname{LDS}(\pi).$$
\(\lambda_1\) هو طول الصف الأول، أما \(\lambda'_1\) فهو طول العمود الأول، أي عدد الصفوف أيضًا. لذلك فإن الشرط \(\operatorname{LDS}(\pi)\le 2\) يعني أن \(\lambda\) لا تحتوي على أكثر من صفين.
إذن كل شكل مسموح يمكن كتابته على الصورة \(\lambda=(a,b)\) حيث \(a\ge b\ge 0\) و\(a+b=2n\). ومن شرط أطول متتالية تصاعدية نحصل على \(a\le n+1\). لكن أي شكل من صفين ومجموع حجمه \(2n\) يحقق كذلك \(a\ge (a+b)/2=n\). لذلك لا يبقى إلا احتمالان:
$$a\in\{n,n+1\}.$$
ومن ثم فالأشكال المسموح بها هي فقط
$$\lambda=(n,n),\qquad \lambda=(n+1,n-1).$$
هذا هو الاختزال الحاسم. فبدلًا من العد عبر \((2n)!\) تبديلًا، صار المطلوب جمع مساهمتي شكلين فقط.
مراسلة RSK هي تقابل واحد لواحد بين التبديلات وأزواج \((P,Q)\) من جداول يونغ القياسية ذات الشكل نفسه. فإذا رمزنا بعدد الجداول القياسية للشكل \(\lambda\) بالرمز \(f^\lambda\)، فإن عدد التبديلات ذات الشكل \(\lambda\) يساوي
$$\#\{\pi\in S_{2n}:\operatorname{shape}(\pi)=\lambda\}=(f^\lambda)^2.$$
لذلك، بعد معرفة الشكلين المسموحين، لا يبقى إلا حساب \(f^\lambda\) لكل منهما ثم تربيع القيمتين.
بالنسبة إلى الشكل \((a,b)\) ذي الصفين، يمكن كتابة أطوال الخطافات صراحة. في الصف الأول، الخانات \(b\) اليسرى لها أطوال \(a-j+2\) عندما \(1\le j\le b\)، أما الخانات المتبقية في الصف الأول فلها أطوال \(a-j+1\) عندما \(b<j\le a\). وفي الصف الثاني تكون الأطوال \(b-j+1\) عندما \(1\le j\le b\).
وبضرب هذه القيم نحصل على
$$\prod_{u\in(a,b)} h(u)=\left(\prod_{j=1}^{b}(a-j+2)\right)\left(\prod_{j=b+1}^{a}(a-j+1)\right)\left(\prod_{j=1}^{b}(b-j+1)\right)=\frac{(a+1)!\,b!}{a-b+1}.$$
ومن ثم تعطي صيغة الخطافات
$$f^{(a,b)}=\frac{(a+b)!}{\prod_{u\in(a,b)} h(u)}=\frac{a-b+1}{a+1}\binom{a+b}{b}.$$
وبالتعويض عن الشكلين المسموحين نحصل على
$$f^{(n,n)}=\frac{1}{n+1}\binom{2n}{n},$$
$$f^{(n+1,n-1)}=\frac{3}{n+2}\binom{2n}{n-1}=\frac{3n}{(n+1)(n+2)}\binom{2n}{n}.$$
إذن
$$P(n)=\left(\frac{1}{n+1}\binom{2n}{n}\right)^2+\left(\frac{3n}{(n+1)(n+2)}\binom{2n}{n}\right)^2 \pmod{10^9+7}.$$
الحد الأول هو مربع عدد كاتالان \(C_n\)، والحد الثاني يأتي من الشكل المجاور \((n+1,n-1)\). ولا توجد حدود أخرى لأن الشروط لا تسمح بأي شكل ثالث.
من المناسب تعريف
$$B_n=\binom{2n}{n}.$$
وعندها يصبح الجواب
$$P(n)=\left(B_n (n+1)^{-1}\right)^2+\left(3n\,B_n (n+1)^{-1}(n+2)^{-1}\right)^2 \pmod{10^9+7}.$$
والهوية
$$\binom{2n}{n-1}=B_n\frac{n}{n+1}$$
تجعل مساهمة الشكل الثاني تعتمد على المعامل الثنائي المركزي نفسه. ولهذا لا يحتاج التنفيذ إلا إلى نسبة مضروبين مركزية واحدة وعدة معكوسات معيارية.
في الحالة المطلوبة \(n=100000000\) يكون \(2n=200000000<10^9+7\). لذلك فإن \(n!\) و\(n+1\) و\(n+2\) كلها غير منعدمة بترديد العدد الأولي \(10^9+7\)، وجميع المقامات في الصيغة قابلة للعكس.
عندما \(n=2\)، يكون الشكلان المسموحان هما \((2,2)\) و\((3,1)\). وتعطي صيغة الخطافات
$$f^{(2,2)}=\frac{1}{3}\binom{4}{2}=2,\qquad f^{(3,1)}=\frac{3}{4}\binom{4}{1}=3.$$
ومن ثم
$$P(2)=2^2+3^2=13.$$
أي أن 13 تبديلًا فقط من أصل \(4!=24\) تبديلًا للمجموعة \(\{1,2,3,4\}\) تحقق الشرطين \(\operatorname{LIS}(\pi)\le 3\) و\(\operatorname{LDS}(\pi)\le 2\). وهذه أول قيمة غير تافهة تصلح كنقطة تحقق للصيغة المغلقة.
تنفذ نسخ C++ وPython وJava الصيغة المغلقة السابقة مباشرة. وفي الحالة الكبيرة المستهدفة لا تقوم ببناء جداول يونغ ولا باستعراض التبديلات.
يضرب التنفيذ الأعداد \(1,2,\dots,2n\) بترديد \(10^9+7\). وعندما يصل المرور إلى \(n\)، تُحفظ القيمة الجزئية، وبذلك نحصل في المرور نفسه على \(n!\) وعلى \((2n)!\). بعد ذلك تُبنى الكمية
$$\binom{2n}{n}\equiv (2n)!\,(n!)^{-2}\pmod{10^9+7}.$$
ثم تُحسب المعكوسات المعيارية لـ \(n!\) و\(n+1\) و\(n+2\) باستعمال الأس السريع ومبرهنة فيرما الصغرى:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
وبهذه المعكوسات تُحسب مساهمة الشكل \((n,n)\) ومساهمة الشكل \((n+1,n-1)\)، ثم تُربع القيمتان وتُجمعان ويؤخذ الناتج بترديد \(10^9+7\). وهكذا يكون قلب الخوارزمية مجرد مرور خطي واحد وعدد ثابت من عمليات الأس المعياري.
إحدى النسخ المترجمة تجري أيضًا تحققًا brute-force لقيم صغيرة جدًا من \(n\)، للتأكد من تطابق العد المباشر مع الصيغة المغلقة. هذه الفحوص تؤكد الاشتقاق الرياضي، لكنها ليست جزءًا من حساب الحالة الكبيرة.
العمل المهيمن هو الحلقة الوحيدة من \(1\) إلى \(2n\)، ولذلك يكون الزمن \(O(n)\). أما المعكوسات المعيارية فتتطلب عددًا ثابتًا من عمليات الأس بكلفة \(O(\log(10^9+7))\)، وهذا لا يغير الحد الكلي. استهلاك الذاكرة هو \(O(1)\) لأن التنفيذ يحتفظ بعدد قليل من المجمعات العددية فقط. والفحوص الصغيرة جدًا تعمل على مدخلات ثابتة الحجم، لذا لا تؤثر في التعقيد asymptotic.