Start with an \(m \times m\) square and remove an \(n \times n\) square from the lower-right corner, where \(0 \le n \lt m\). The remaining gnomon has \(m^2-n^2\) cells. We must count the ways to place the integers \(1,2,\dots,m^2-n^2\) so that every row increases from left to right and every column increases from top to bottom, then evaluate the count modulo \(76543217\).
Let \(p=m-n\). As a Ferrers diagram, the gnomon is the partition
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
The first \(p\) rows have length \(m\), while the last \(n\) rows have length \(p\). Therefore the total number of cells is
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
A valid numbering of the gnomon is exactly a standard Young tableau of this shape.
If \(T(m,n)\) denotes the number of valid numberings, the Frame-Robinson-Thrall formula gives
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$
where \(h(u)\) is the hook length of cell \(u\): the number of cells to its right, plus the number below it, plus the cell itself.
So the problem reduces to evaluating the hook product for this particular gnomon shape.
Using \(1\)-based coordinates \((i,j)\), the diagram naturally splits into a \(p \times p\) corner square and two \(p \times n\) arms.
In the top-left square, both the row length and column length are \(m\). Hence
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
In the top-right arm, write \(j=p+b\) with \(1 \le b \le n\). The row still has length \(m\), but the column length is only \(p\), so
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
In the bottom-left arm, write \(i=p+a\) with \(1 \le a \le n\). Now the row length is \(p\) and the column length is \(m\), giving
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
The last two formulas describe the same multiset of hook lengths, so the two arms contribute identical factors.
Let \(H\) be the product of all hook lengths. We write
$$H=P_A \cdot P_B^2,$$
where \(P_A\) is the contribution of the \(p \times p\) corner square and \(P_B\) is the contribution of one arm.
For the corner square, fix a row \(i\). As \(j\) runs from \(1\) to \(p\), the hooks are consecutive integers, so
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
Multiplying over all \(i=1,\dots,p\) gives
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
For one arm, fixing \(i\) yields another consecutive block:
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
Therefore
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
The lower-left arm has the same hook multiset, so its contribution is another factor of \(P_B\).
Substituting the factorization of \(H\) into the hook-length formula yields
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
Here \(p=m-n\). This is exactly the product decomposition used by the C++, Python, and Java implementations.
For \(m=5\) and \(n=3\), we have \(p=2\) and \(m^2-n^2=16\). The formulas above give
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$
Hence
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
and therefore
$$T(5,3)=\frac{16!}{83607552}=250250.$$
This matches the exact checkpoint used by the implementation. A second consistency check is
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
The implementation follows the formula directly. It computes \((m^2-n^2)!\bmod M\), precomputes factorials up to \(2m-1\), evaluates the two short ratio blocks \(P_A\) and \(P_B\), multiplies them into the full hook product \(H\), and then replaces division by a modular inverse.
Since \(M=76543217\) is prime, Fermat's little theorem gives
$$x^{-1}\equiv x^{M-2}\pmod{M}.$$
So the final modular computation is
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$
The dominant cost is computing \((m^2-n^2)!\bmod M\), which takes \(O(m^2-n^2)\) modular multiplications. Building the factorial table up to \(2m-1\) and evaluating the two ratio blocks costs only \(O(m)\) time. The memory usage is \(O(m)\) because the implementation stores only the short factorial table.
Man beginnt mit einem \(m \times m\)-Quadrat und entfernt aus der rechten unteren Ecke ein \(n \times n\)-Quadrat, wobei \(0 \le n \lt m\) gilt. Das verbleibende Gnomon besitzt \(m^2-n^2\) Zellen. Gesucht ist die Anzahl der Belegungen mit \(1,2,\dots,m^2-n^2\), bei denen jede Zeile von links nach rechts und jede Spalte von oben nach unten streng wächst. Das Ergebnis soll modulo \(76543217\) berechnet werden.
Setze \(p=m-n\). Als Ferrers-Diagramm entspricht die Form der Partition
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
Die ersten \(p\) Zeilen haben also Länge \(m\), die letzten \(n\) Zeilen Länge \(p\). Damit ist die Gesamtzahl der Zellen
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
Eine zulässige Nummerierung ist genau ein Standard-Young-Tableau dieser Form.
Bezeichne die Anzahl der gültigen Nummerierungen mit \(T(m,n)\). Dann liefert die Frame-Robinson-Thrall-Formel
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$
wobei \(h(u)\) die Hakenlänge der Zelle \(u\) ist: Zellen rechts davon, plus Zellen darunter, plus die Zelle selbst.
Damit reduziert sich das Problem auf die explizite Berechnung des Hakenprodukts für diese spezielle Gnomon-Form.
Mit \(1\)-basierten Koordinaten \((i,j)\) zerfällt das Diagramm natürlich in ein \(p \times p\)-Eckquadrat und zwei \(p \times n\)-Arme.
Im linken oberen Quadrat haben sowohl Zeilen- als auch Spaltenlänge den Wert \(m\). Deshalb gilt
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
Im oberen rechten Arm schreibe \(j=p+b\) mit \(1 \le b \le n\). Die Zeile hat weiterhin Länge \(m\), die Spalte aber nur Länge \(p\). Also
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
Im linken unteren Arm schreibe \(i=p+a\) mit \(1 \le a \le n\). Nun hat die Zeile Länge \(p\) und die Spalte Länge \(m\), also
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
Die letzten beiden Formeln erzeugen dieselbe Multimenge von Hakenlängen; beide Arme tragen also denselben Faktor bei.
Sei \(H\) das Produkt aller Hakenlängen. Dann schreiben wir
$$H=P_A \cdot P_B^2,$$
wobei \(P_A\) zum \(p \times p\)-Eckquadrat gehört und \(P_B\) zum Beitrag eines Arms.
Fixiert man im Eckquadrat eine Zeile \(i\), so bilden die Hakenlängen eine Folge aufeinanderfolgender Zahlen. Daher
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
Über alle \(i=1,\dots,p\) folgt
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
Für einen Arm erhält man bei festem \(i\) analog
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
Somit
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
Da der linke untere Arm dieselbe Hakenmultimenge besitzt, erscheint \(P_B\) insgesamt zweimal.
Setzt man diese Zerlegung in die Hakenlängenformel ein, erhält man
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
Hier ist \(p=m-n\). Genau diese Produktzerlegung wird in den C++-, Python- und Java-Implementierungen verwendet.
Für \(m=5\) und \(n=3\) gilt \(p=2\) und \(m^2-n^2=16\). Die Formeln liefern
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$
Also
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
und damit
$$T(5,3)=\frac{16!}{83607552}=250250.$$
Das stimmt mit dem exakten Kontrollwert der Implementierung überein. Ein weiterer modularer Test ist
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
Die Implementierung folgt der Formel direkt. Zuerst wird \((m^2-n^2)!\bmod M\) berechnet. Danach werden Fakultäten bis \(2m-1\) vorab gespeichert, die beiden Quotientenblöcke \(P_A\) und \(P_B\) ausgewertet und zum gesamten Hakenprodukt \(H\) kombiniert. Die Division wird dann durch ein modulares Inverses ersetzt.
Da \(M=76543217\) prim ist, liefert der kleine Satz von Fermat
$$x^{-1}\equiv x^{M-2}\pmod{M}.$$
Somit berechnet die Implementierung am Ende
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$
Der dominante Aufwand ist die Berechnung von \((m^2-n^2)!\bmod M\); dafür werden \(O(m^2-n^2)\) modulare Multiplikationen benötigt. Die kurze Fakultätstabelle bis \(2m-1\) und die beiden Quotientenblöcke kosten nur \(O(m)\) Zeit. Der Speicherverbrauch beträgt \(O(m)\), weil lediglich diese kurze Fakultätstabelle gehalten wird.
\(0 \le n \lt m\) olacak şekilde önce bir \(m \times m\) kare alınır, sonra sağ alt köşedeki \(n \times n\) kare çıkarılır. Geriye kalan gnomon biçiminin \(m^2-n^2\) hücresi vardır. Bu hücrelere \(1,2,\dots,m^2-n^2\) sayıları öyle yerleştirilmelidir ki her satır soldan sağa, her sütun yukarıdan aşağıya sıkı biçimde artsın. İstenen değer bu sayımın \(76543217\) modundaki sonucudur.
\(p=m-n\) olsun. Ferrers diyagramı açısından gnomon şu bölüntüye karşılık gelir:
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
İlk \(p\) satırın uzunluğu \(m\), son \(n\) satırın uzunluğu ise \(p\)'dir. Bu yüzden toplam hücre sayısı
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
Geçerli bir numaralandırma, tam olarak bu şeklin standart Young tablosudur.
Geçerli numaralandırma sayısını \(T(m,n)\) ile gösterelim. Frame-Robinson-Thrall formülü
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)}$$
eşitliğini verir. Burada \(h(u)\), \(u\) hücresinin kanca uzunluğudur: sağındaki hücre sayısı, altındaki hücre sayısı ve hücrenin kendisi.
Dolayısıyla mesele, bu özel gnomon şekli için tüm kanca uzunluklarının çarpımını açık biçimde yazmaktır.
\(1\)-bazlı \((i,j)\) koordinatları kullanalım. Şekil doğal olarak bir \(p \times p\) köşe karesine ve iki adet \(p \times n\) kola ayrılır.
Sol üst karede hem satır hem sütun uzunluğu \(m\) olduğu için
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
Sağ üst kolda \(j=p+b\) ve \(1 \le b \le n\) yazalım. Satır uzunluğu hâlâ \(m\), sütun uzunluğu ise \(p\)'dir. Bu durumda
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
Sol alt kolda \(i=p+a\) ve \(1 \le a \le n\) yazılırsa, satır uzunluğu \(p\), sütun uzunluğu \(m\) olur ve
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
Son iki formül aynı kanca uzunluğu çoklu kümesini verdiği için iki kol aynı çarpanı üretir.
Tüm kanca uzunluklarının çarpımına \(H\) diyelim. Bunu
$$H=P_A \cdot P_B^2$$
şeklinde yazarız. Burada \(P_A\), \(p \times p\) köşe karesinin; \(P_B\) ise tek bir kolun katkısıdır.
Köşe karesinde bir satır \(i\) sabitlenirse, kanca uzunlukları ardışık sayılardır. Dolayısıyla
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
Tüm \(i=1,\dots,p\) için çarpınca
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
Bir kol için sabit \(i\) altında benzer şekilde
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
Böylece
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
Alt soldaki kol aynı kanca değerlerine sahip olduğundan ikinci bir \(P_B\) çarpanı daha gelir.
Bu ayrıştırmayı hook-length formülüne yerleştirince
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
Burada \(p=m-n\). C++, Python ve Java implementasyonları tam olarak bu çarpım ayrıştırmasını uygular.
\(m=5\) ve \(n=3\) için \(p=2\), hücre sayısı da \(m^2-n^2=16\) olur. Yukarıdaki formüller
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144$$
sonuçlarını verir. Dolayısıyla
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
ve buradan
$$T(5,3)=\frac{16!}{83607552}=250250$$
elde edilir. Bu değer implementasyondaki tam sayı kontrolüyle aynıdır. Bir başka modüler doğrulama da şudur:
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
Uygulama formülü doğrudan izler. Önce \((m^2-n^2)!\bmod M\) hesaplanır. Ardından \(2m-1\)'e kadar olan faktöriyeller önceden hazırlanır, kısa oran blokları \(P_A\) ve \(P_B\) bulunur, bunlardan tam kanca çarpımı \(H\) oluşturulur ve bölme işlemi modüler ters ile yapılır.
\(M=76543217\) asal olduğu için Fermat'ın küçük teoremi
$$x^{-1}\equiv x^{M-2}\pmod{M}$$
eşitliğini verir. Böylece son hesap
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}$$
biçimine dönüşür.
Baskın maliyet \((m^2-n^2)!\bmod M\) hesabıdır ve bu \(O(m^2-n^2)\) modüler çarpım gerektirir. \(2m-1\)'e kadar faktöriyel tablosu oluşturmak ve iki oran bloğunu hesaplamak yalnızca \(O(m)\) zaman alır. Bellek kullanımı \(O(m)\)'dir; çünkü yalnızca kısa faktöriyel tablosu saklanır.
Se parte de un cuadrado \(m \times m\) y se elimina de la esquina inferior derecha un cuadrado \(n \times n\), con \(0 \le n \lt m\). El gnomon restante tiene \(m^2-n^2\) celdas. Debemos contar las maneras de colocar los enteros \(1,2,\dots,m^2-n^2\) de modo que cada fila crezca de izquierda a derecha y cada columna crezca de arriba hacia abajo, y después tomar el resultado módulo \(76543217\).
Sea \(p=m-n\). Como diagrama de Ferrers, el gnomon corresponde a la partición
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
Las primeras \(p\) filas tienen longitud \(m\), mientras que las últimas \(n\) filas tienen longitud \(p\). Por tanto, el número total de celdas es
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
Una numeración válida del gnomon es exactamente un tableau estándar de Young con esta forma.
Si \(T(m,n)\) denota el número de numeraciones válidas, la fórmula de Frame-Robinson-Thrall afirma que
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$
donde \(h(u)\) es la longitud de gancho de la celda \(u\): celdas a su derecha, más celdas debajo de ella, más la propia celda.
Así, todo el problema consiste en calcular el producto de ganchos para esta forma concreta.
Usando coordenadas \((i,j)\) con base \(1\), el diagrama se divide de forma natural en un cuadrado \(p \times p\) y dos brazos \(p \times n\).
En el cuadrado superior izquierdo, tanto la longitud de la fila como la de la columna valen \(m\). Entonces
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
En el brazo superior derecho escribimos \(j=p+b\), con \(1 \le b \le n\). La fila sigue teniendo longitud \(m\), pero la columna tiene longitud \(p\), de modo que
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
En el brazo inferior izquierdo escribimos \(i=p+a\), con \(1 \le a \le n\). Ahora la fila tiene longitud \(p\) y la columna longitud \(m\), así que
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
Las dos últimas expresiones generan el mismo multiconjunto de ganchos, por lo que ambos brazos aportan el mismo factor.
Sea \(H\) el producto de todas las longitudes de gancho. Lo escribimos como
$$H=P_A \cdot P_B^2,$$
donde \(P_A\) corresponde al cuadrado \(p \times p\) y \(P_B\) al producto de un solo brazo.
Si fijamos una fila \(i\) en el cuadrado, los ganchos forman un bloque de enteros consecutivos. Por tanto,
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
Multiplicando para \(i=1,\dots,p\) obtenemos
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
Para un brazo, fijar \(i\) produce de nuevo una cadena consecutiva:
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
De ahí se sigue que
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
El brazo inferior izquierdo tiene el mismo multiconjunto de ganchos, así que aporta otro factor \(P_B\).
Sustituyendo esta descomposición en la fórmula de ganchos se obtiene
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
Aquí \(p=m-n\). Esta es exactamente la factorización que usan las implementaciones en C++, Python y Java.
Para \(m=5\) y \(n=3\), tenemos \(p=2\) y \(m^2-n^2=16\). Las fórmulas anteriores dan
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$
Entonces
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
y por consiguiente
$$T(5,3)=\frac{16!}{83607552}=250250.$$
Esto coincide con la comprobación exacta usada por la implementación. Otra verificación modular útil es
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
La implementación sigue la fórmula de manera directa. Calcula \((m^2-n^2)!\bmod M\), precomputa los factoriales hasta \(2m-1\), evalúa los dos bloques cortos \(P_A\) y \(P_B\), los combina en el producto total \(H\) y reemplaza la división por un inverso modular.
Como \(M=76543217\) es primo, el pequeño teorema de Fermat da
$$x^{-1}\equiv x^{M-2}\pmod{M}.$$
Por eso el cálculo final es
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$
El coste dominante es calcular \((m^2-n^2)!\bmod M\), lo que requiere \(O(m^2-n^2)\) multiplicaciones modulares. Construir la tabla de factoriales hasta \(2m-1\) y evaluar los dos cocientes cortos cuesta solo \(O(m)\) tiempo. El uso de memoria es \(O(m)\), porque solo se almacena esa tabla corta de factoriales.
先取一个 \(m \times m\) 的正方形，再从右下角删去一个 \(n \times n\) 的正方形，其中 \(0 \le n \lt m\)。剩下的图形就是题目中的 gnomon，它一共有 \(m^2-n^2\) 个格子。我们要把整数 \(1,2,\dots,m^2-n^2\) 填入这些格子，使得每一行从左到右严格递增、每一列从上到下严格递增，然后把计数结果对 \(76543217\) 取模。
令 \(p=m-n\)。从 Ferrers 图的角度看，这个 gnomon 对应的分拆是
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
也就是说，前 \(p\) 行长度都是 \(m\)，后 \(n\) 行长度都是 \(p\)。因此总格子数为
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
题目要求的合法编号，恰好就是这种形状的标准 Young 表个数。
设合法编号数为 \(T(m,n)\)。Frame-Robinson-Thrall 钩长公式给出
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$
其中 \(h(u)\) 表示格子 \(u\) 的钩长，也就是它右边的格子数、下边的格子数，再加上它自己。
所以关键就在于把这个特定 gnomon 形状的全部钩长乘积写成便于计算的形式。
采用从 \(1\) 开始的坐标 \((i,j)\)。这个图形自然分成一个 \(p \times p\) 的左上角方块，以及两个 \(p \times n\) 的“臂”。
在左上角方块中，行长和列长都等于 \(m\)，因此
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
在右上方的那一臂中，写 \(j=p+b\)，其中 \(1 \le b \le n\)。此时行长仍然是 \(m\)，但列长只有 \(p\)，所以
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
在左下方的那一臂中，写 \(i=p+a\)，其中 \(1 \le a \le n\)。这时行长是 \(p\)，列长是 \(m\)，从而
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
后两种情况产生的是同一组钩长，因此两个“臂”的贡献完全相同。
记全部钩长乘积为 \(H\)。我们把它写成
$$H=P_A \cdot P_B^2,$$
其中 \(P_A\) 来自左上角的 \(p \times p\) 方块，\(P_B\) 来自其中一条“臂”。
对角方块中固定一行 \(i\) 后，钩长构成一段连续整数，因此
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
再对 \(i=1,\dots,p\) 相乘，得到
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
对于一条“臂”，固定 \(i\) 之后同样得到连续整数块：
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
于是
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
左下角那条“臂”具有相同的钩长多重集合，所以再乘一个 \(P_B\)。
把上述分解代回钩长公式，就得到
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
这里 \(p=m-n\)。这正是 C++、Python 和 Java 实现中使用的分解方式。
当 \(m=5,\ n=3\) 时，\(p=2\)，总格子数 \(m^2-n^2=16\)。由上式可得
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$
因此
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
从而
$$T(5,3)=\frac{16!}{83607552}=250250.$$
这与实现中的精确校验值一致。另一个有用的模检验是
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
实现完全按照公式进行。先计算 \((m^2-n^2)!\bmod M\)，再预处理到 \(2m-1\) 为止的阶乘，随后计算两个短的阶乘比 \(P_A\) 和 \(P_B\)，把它们合成为总钩长乘积 \(H\)，最后用模逆替代除法。
因为 \(M=76543217\) 是素数，费马小定理给出
$$x^{-1}\equiv x^{M-2}\pmod{M}.$$
所以最终的模计算是
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$
主要成本是计算 \((m^2-n^2)!\bmod M\)，这需要 \(O(m^2-n^2)\) 次模乘。构造到 \(2m-1\) 的短阶乘表以及计算两个比值块只需要 \(O(m)\) 时间。空间复杂度为 \(O(m)\)，因为实现只保存这张短阶乘表。
Берем квадрат \(m \times m\) и удаляем из его правого нижнего угла квадрат \(n \times n\), где \(0 \le n \lt m\). Оставшаяся фигура-гномон содержит \(m^2-n^2\) клеток. Нужно посчитать число размещений чисел \(1,2,\dots,m^2-n^2\), при которых каждая строка строго возрастает слева направо, а каждый столбец строго возрастает сверху вниз, после чего взять результат по модулю \(76543217\).
Положим \(p=m-n\). В терминах диаграммы Феррерса гномон имеет вид
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
Первые \(p\) строк имеют длину \(m\), а последние \(n\) строк имеют длину \(p\). Поэтому общее число клеток равно
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
Корректная нумерация такой фигуры в точности совпадает со стандартной таблицей Юнга этой формы.
Пусть \(T(m,n)\) обозначает число допустимых нумераций. Тогда формула Фрейма-Робинсона-Тролла дает
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$
где \(h(u)\) есть длина крюка клетки \(u\): число клеток справа, число клеток снизу и сама клетка.
Значит, вся задача сводится к явному вычислению произведения длин крюков для этой конкретной формы.
Используем координаты \((i,j)\), начиная с \(1\). Диаграмма естественно распадается на квадрат \(p \times p\) в верхнем левом углу и два прямоугольных плеча размера \(p \times n\).
В верхнем левом квадрате и длина строки, и длина столбца равны \(m\). Поэтому
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
В правом верхнем плече пишем \(j=p+b\), где \(1 \le b \le n\). Длина строки по-прежнему равна \(m\), а длина столбца равна \(p\), так что
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
В левом нижнем плече пишем \(i=p+a\), где \(1 \le a \le n\). Теперь длина строки равна \(p\), а длина столбца равна \(m\), откуда
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
Последние две формулы дают один и тот же мультимножество длин крюков, значит оба плеча вносят одинаковый множитель.
Обозначим произведение всех длин крюков через \(H\). Тогда
$$H=P_A \cdot P_B^2,$$
где \(P_A\) соответствует квадрату \(p \times p\), а \(P_B\) соответствует одному плечу.
Если в квадрате зафиксировать строку \(i\), то длины крюков образуют подряд идущие целые числа. Поэтому
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
Перемножая по всем \(i=1,\dots,p\), получаем
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
Для одного плеча при фиксированном \(i\) аналогично имеем
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
Следовательно,
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
Поскольку левое нижнее плечо имеет тот же набор длин крюков, появляется второй множитель \(P_B\).
Подставляя это разложение в формулу крюков, получаем
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
Здесь \(p=m-n\). Именно это разложение и используют реализации на C++, Python и Java.
При \(m=5\) и \(n=3\) имеем \(p=2\) и \(m^2-n^2=16\). Формулы дают
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$
Значит,
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
и потому
$$T(5,3)=\frac{16!}{83607552}=250250.$$
Это совпадает с точной проверкой, заложенной в реализации. Еще одна полезная модульная проверка:
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
Реализация буквально следует полученной формуле. Сначала вычисляется \((m^2-n^2)!\bmod M\), затем предварительно считаются факториалы до \(2m-1\), после чего вычисляются два коротких блока отношений \(P_A\) и \(P_B\), из них собирается полное произведение крюков \(H\), а деление заменяется на умножение на обратный элемент по модулю.
Так как \(M=76543217\) является простым числом, малая теорема Ферма дает
$$x^{-1}\equiv x^{M-2}\pmod{M}.$$
Следовательно, окончательный расчет имеет вид
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$
Основное время уходит на вычисление \((m^2-n^2)!\bmod M\), что требует \(O(m^2-n^2)\) модульных умножений. Построение короткой таблицы факториалов до \(2m-1\) и вычисление двух блоков отношений занимает лишь \(O(m)\) времени. Память составляет \(O(m)\), поскольку хранится только эта короткая таблица факториалов.
نبدأ بمربع \(m \times m\)، ثم نحذف من الزاوية اليمنى السفلية مربعًا حجمه \(n \times n\)، حيث \(0 \le n \lt m\). الشكل المتبقي هو gnomon وعدد خلاياه يساوي \(m^2-n^2\). المطلوب هو عدد الطرق لوضع الأعداد \(1,2,\dots,m^2-n^2\) بحيث تكون كل صفوف الشكل متزايدة من اليسار إلى اليمين، وكل أعمدته متزايدة من الأعلى إلى الأسفل، ثم أخذ النتيجة بترديد \(76543217\).
لنضع \(p=m-n\). عند النظر إلى الشكل كأنه مخطط Ferrers نحصل على التقسيم
$$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$$
أي إن أول \(p\) صفوف طول كل واحد منها \(m\)، أما آخر \(n\) صفوف فطول كل واحد منها \(p\). ومن ثم فإن عدد الخلايا الكلي هو
$$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$$
وبهذا تصبح الترميزات الصحيحة للشكل مساوية تمامًا لعدد جداول Young القياسية لهذه الهيئة.
إذا رمزنا لعدد الترميزات الصحيحة بالرمز \(T(m,n)\)، فإن صيغة Frame-Robinson-Thrall تعطي
$$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$$
حيث \(h(u)\) هو طول الخطاف للخلية \(u\): عدد الخلايا الواقعة إلى يمينها، زائد عدد الخلايا الواقعة تحتها، زائد الخلية نفسها.
إذن قلب المسألة هو حساب حاصل ضرب أطوال الخطاطيف لهذه الهيئة الخاصة بطريقة قابلة للتنفيذ بكفاءة.
باستخدام إحداثيات \((i,j)\) التي تبدأ من \(1\)، ينقسم الشكل طبيعيًا إلى مربع زاوي حجمه \(p \times p\) وإلى ذراعين كل منهما بحجم \(p \times n\).
في المربع العلوي الأيسر يكون طول الصف وطول العمود كلاهما مساويين لـ \(m\)، ولذلك
$$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$$
في الذراع العلوية اليمنى نكتب \(j=p+b\) حيث \(1 \le b \le n\). عندئذ يبقى طول الصف مساويًا لـ \(m\)، لكن طول العمود يساوي \(p\)، ومن ثم
$$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$$
وفي الذراع السفلية اليسرى نكتب \(i=p+a\) حيث \(1 \le a \le n\). هنا يصبح طول الصف \(p\) وطول العمود \(m\)، فنحصل على
$$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$$
الصيغتان الأخيرتان تنتجان نفس مجموعة القيم، ولهذا يسهم الذراعان بالعامل نفسه تمامًا.
لنرمز إلى حاصل ضرب جميع أطوال الخطاطيف بالرمز \(H\). نكتبه على الصورة
$$H=P_A \cdot P_B^2,$$
حيث يمثل \(P_A\) مساهمة مربع الزاوية \(p \times p\)، ويمثل \(P_B\) مساهمة ذراع واحدة.
إذا ثبتنا صفًا \(i\) داخل مربع الزاوية، فإن أطوال الخطاطيف في ذلك الصف تكون أعدادًا متتالية، ولذلك
$$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$$
وبضرب ذلك على جميع القيم \(i=1,\dots,p\) نحصل على
$$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$$
أما في ذراع واحدة، فعند تثبيت \(i\) يظهر أيضًا مقطع من أعداد متتالية:
$$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$$
ومن هنا
$$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$$
وبما أن الذراع السفلية اليسرى تمتلك المجموعة نفسها من أطوال الخطاطيف، فإنها تضيف عاملًا ثانيًا من \(P_B\).
بالتعويض في صيغة أطوال الخطاطيف نحصل على
$$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$$
وهنا \(p=m-n\). هذه هي بالضبط طريقة التفكيك التي تعتمدها تطبيقات C++ وPython وJava.
عندما \(m=5\) و\(n=3\)، يكون \(p=2\) ويصبح عدد الخلايا \(m^2-n^2=16\). وتعطي الصيغ السابقة
$$P_A=\frac{8!\,9!}{6!\,7!}=4032,$$
$$P_B=\frac{3!\,4!}{0!\,1!}=144.$$
إذن
$$H=P_A P_B^2=4032 \cdot 144^2=83607552,$$
ومن ثم
$$T(5,3)=\frac{16!}{83607552}=250250.$$
وهذا يطابق قيمة التحقق الدقيقة المستعملة في التنفيذ. وهناك أيضًا تحقق معياري مفيد هو
$$T(10,5)\equiv 61251715 \pmod{76543217}.$$
التنفيذ يتبع الصيغة مباشرة. فهو يحسب أولًا \((m^2-n^2)!\bmod M\)، ثم يجهز جدول العامليات حتى \(2m-1\)، وبعد ذلك يحسب الكتلتين القصيرتين \(P_A\) و\(P_B\)، ويجمعهما في حاصل الضرب الكلي \(H\)، ثم يستبدل القسمة بمقلوب معياري.
وبما أن \(M=76543217\) عدد أولي، فإن مبرهنة فيرما الصغرى تعطي
$$x^{-1}\equiv x^{M-2}\pmod{M}.$$
لذلك تصبح الصيغة المعيارية النهائية
$$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$$
الكلفة المسيطرة هي حساب \((m^2-n^2)!\bmod M\)، وهذا يحتاج إلى \(O(m^2-n^2)\) عملية ضرب معيارية. أما بناء جدول العامليات حتى \(2m-1\) وحساب كتلتي النسب القصيرتين فيكلف فقط \(O(m)\) زمنًا. استهلاك الذاكرة هو \(O(m)\)، لأن التنفيذ لا يخزن إلا جدول العامليات القصير.