There are \(m\) penguins at positions \(1,\ldots,m\). Each step moves one penguin one unit right, provided the destination is empty. For a reachable final position vector \(v\), let \(f(v)\) count the legal sequences of exactly \(n\) moves ending there. We must multiply these counts over every reachable endpoint and evaluate \(F(150,300)\) modulo \(M=1234567891\). [1]
Penguins never change their order. Write their displacements as \(x_i=v_i-i\). Distinct final positions imply \(0\le x_1\le\cdots\le x_m\), so reversing the displacements gives a partition
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
Moving a penguin adds one cell to the corresponding row of this partition, and the destination is free exactly when the enlarged shape remains a partition. Label each added cell by its move number. Labels increase along rows and columns, producing a standard Young tableau. Conversely, reading any such tableau in label order reconstructs a unique legal march. Every partition with at most \(m\) rows is reachable.
The hook length of cell \((i,j)\) is the number of cells strictly to its right or below, plus itself:
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
Here \(\lambda'_j\) is column \(j\)'s height. The hook-length formula therefore gives \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\). [2]
For example, with two penguins and four moves, the possible shapes are \((4)\), \((3,1)\), and \((2,2)\). Their hook products are 24, 8, and 12 respectively, so the path counts are \(4!/24=1\), \(4!/8=3\), and \(4!/12=2\). Multiplying gives the stated value \(F(2,4)=6\). This also illustrates why adding the path counts would answer a different question: each distinct endpoint contributes one factor to the required product.
Let \(p_m(n)\) count partitions of \(n\) with at most \(m\) rows, and let \(H_h(n)\) count all occurrences of hook length \(h\) across those partitions. Multiplying the tableau formula yields
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
We need these aggregate counts, rather than an enumeration of the individual partitions. Define
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
By conjugating partitions, \([q^n]P_m(q)=p_m(n)\). The notation \([q^s]\) means coefficient extraction; a negative index contributes zero. [4]
Represent a partition by its \(m\) distinct, nonnegative beta numbers \(b_i=\lambda_i+m-i\), viewed as occupied positions on an integer line. Their total is \(|\lambda|+\binom m2\). Hooks of length \(h\) correspond exactly to occupied positions \(b\) whose position \(b-h\ge0\) is empty. [3]
Explicitly, the nonnegative empty positions are \(a_j=m+j-1-\lambda'_j\), for \(j\ge1\). Each cell \((i,j)\) pairs \(b_i\) with \(a_j<b_i\), and \(b_i-a_j=h_{i,j}\). Thus the correspondence preserves every hook multiplicity.
For fixed \(m,h\), let \(A_h(q)\) count possible downward bead moves by \(h\), summed over all configurations with weight \(q^{|\lambda|}\). Let \(C_h(q)\) similarly count upward moves, and let \(B_h(q)\) count occupied positions among \(0,\ldots,h-1\). A downward move is auxiliary to this counting argument; it need not be a single penguin step.
Reversing each downward move gives an upward move from a configuration whose partition size is smaller by \(h\). Also, for each configuration, upward choices minus downward choices telescope to the number of its occupied positions below \(h\). Consequently
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
To see the telescoping directly, let \(\eta_a\) be 1 at an occupied position and 0 otherwise. The difference between the two move counts is \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\). Each configuration has finitely many beads, so these sums are well defined.
The hook correspondence means precisely that \(H_h(n)=[q^n]A_h(q)\).
Introduce \(z\) to count beads. The generating function for distinct occupied positions is
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
The latter identity follows by subtracting the staircase \(0,1,\ldots,r-1\) from the increasing bead positions. Requiring position \(a\) to be occupied multiplies \(G\) by \(zq^a/(1+zq^a)\). Expand that factor as \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\), sum over \(0\le a<h\), and extract \(z^m\). With [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
the result is
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
Substitute into \(A_h\) and use \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\). This gives the computable identity
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
Individual expressions may contain negative powers, but their finite sum is the ordinary hook-count generating series. Only the displayed nonnegative coefficient indices need to be computed.
Set \(K=n+\binom m2\), which is \(11475\) for the requested input. All required indices are at most \(K\). Maintain one coefficient array for \(P_r\), beginning with \(P_0=1\). For \(r=0,\ldots,m-1\), set \(j=m-r\) and form the coefficients \(Q_s\) of \(P_r(q)/(1-q^j)\) in increasing order:
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
For each \(h\), accumulate the signed sum of \(Q_{n+d_j-th}\). Then incorporate part size \(r+1\) by the usual increasing-index update \(P[s]\leftarrow P[s]+P[s-r-1]\). After the last update, \(P[n]=p_m(n)\). The two coefficient arrays are reused throughout.
The modulus \(M\) is prime, as verified by a compile-time trial-division check. All bases \(1,\ldots,300\) are nonzero modulo \(M\), so Fermat's theorem permits reducing every exponent modulo \(M-1=1234567890\). The coefficient arrays and hook counts are therefore stored modulo \(M-1\); that modulus itself need not be prime. Binary exponentiation evaluates the numerator and denominator modulo \(M\), and raises the denominator to \(M-2\) to invert it. Unsigned 64-bit arithmetic safely contains each product of two residues modulo \(M\). [6]
The running time is \(O(m(n+m^2)+m^2n+n\log M)\), counting modular arithmetic operations. The coefficient updates cost \(O(mK)\), the hook sums cost \(O(m^2n)\), and modular powers cost \(O(n\log M)\). Auxiliary space is \(O(n+m^2)\).
The optional --self-test performs the following exact checks: [7]
A separate full-size computation independently checked all 300 hook multiplicities and the partition count. It began with unrestricted partitions and subtracted those having more than 150 rows. After conjugation, every excluded partition has a unique first row longer than 150 and a tail of size below 150. Counting the tail hooks and the first-row hooks separately supplies a different calculation of the same aggregates. Both methods give \(p_{150}(300)\equiv221703566\pmod{M-1}\), agree on every hook count modulo \(M-1\), and produce the same final result. This independent comparison is additional validation, separate from the packaged self-tests.
The references below identify the background results used in the derivation. The penguin-to-tableau bijection, the aggregate hook-count identity, and the finite coefficient algorithm are derived explicitly above.
Es stehen \(m\) Pinguine an den Positionen \(1,\ldots,m\). Bei jedem Schritt bewegt sich ein Pinguin um eine Einheit nach rechts, sofern das Zielfeld frei ist. Für einen erreichbaren Endpositionsvektor \(v\) bezeichne \(f(v)\) die Anzahl der zulässigen Folgen von genau \(n\) Bewegungen, die dort enden. Diese Anzahlen sind über sämtliche erreichbaren Endpositionen zu multiplizieren; gesucht ist \(F(150,300)\) modulo \(M=1234567891\). [1]
Die Reihenfolge der Pinguine bleibt erhalten. Schreibe ihre Verschiebungen als \(x_i=v_i-i\). Verschiedene Endpositionen implizieren \(0\le x_1\le\cdots\le x_m\); kehrt man die Reihenfolge der Verschiebungen um, erhält man daher eine Partition
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
Die Bewegung eines Pinguins fügt der entsprechenden Zeile dieser Partition eine Zelle hinzu. Das Zielfeld ist genau dann frei, wenn die vergrößerte Form weiterhin eine Partition ist. Beschrifte jede neue Zelle mit der Nummer ihrer Bewegung. Die Beschriftungen wachsen entlang der Zeilen und Spalten und bilden somit ein Standard-Young-Tableau. Umgekehrt rekonstruiert das Lesen eines solchen Tableaus in der Reihenfolge seiner Beschriftungen eindeutig einen zulässigen Marsch. Jede Partition mit höchstens \(m\) Zeilen ist erreichbar.
Die Hakenlänge einer Zelle \((i,j)\) ist die Anzahl der Zellen in derselben Zeile rechts von ihr oder in derselben Spalte unter ihr, zuzüglich der Zelle selbst:
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
Dabei ist \(\lambda'_j\) die Höhe der Spalte \(j\). Die Hakenlängenformel ergibt daher \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\). [2]
Bei zwei Pinguinen und vier Bewegungen sind beispielsweise die Formen \((4)\), \((3,1)\) und \((2,2)\) möglich. Ihre Hakenprodukte betragen 24, 8 beziehungsweise 12; die Anzahlen der Wege sind somit \(4!/24=1\), \(4!/8=3\) und \(4!/12=2\). Ihre Multiplikation liefert den angegebenen Wert \(F(2,4)=6\). Dies verdeutlicht auch, weshalb eine Addition der Weganzahlen eine andere Frage beantworten würde: Jede unterschiedliche Endposition liefert einen Faktor des gesuchten Produkts.
Sei \(p_m(n)\) die Anzahl der Partitionen von \(n\) mit höchstens \(m\) Zeilen, und zähle \(H_h(n)\) sämtliche Vorkommen der Hakenlänge \(h\) in diesen Partitionen. Die Multiplikation der Tableauformel ergibt
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
Benötigt werden diese zusammengefassten Anzahlen, nicht eine Aufzählung sämtlicher einzelner Partitionen. Definiere
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
Durch Konjugation der Partitionen folgt \([q^n]P_m(q)=p_m(n)\). Die Schreibweise \([q^s]\) bedeutet Koeffizientenextraktion; ein negativer Index liefert null. [4]
Stelle eine Partition durch ihre \(m\) verschiedenen, nichtnegativen Beta-Zahlen \(b_i=\lambda_i+m-i\) dar, aufgefasst als belegte Positionen auf einer ganzzahligen Zahlengeraden. Ihre Summe ist \(|\lambda|+\binom m2\). Haken der Länge \(h\) entsprechen genau den belegten Positionen \(b\), für die die Position \(b-h\ge0\) frei ist. [3]
Die nichtnegativen freien Positionen sind ausdrücklich \(a_j=m+j-1-\lambda'_j\) für \(j\ge1\). Jede Zelle \((i,j)\) verbindet \(b_i\) mit \(a_j<b_i\), wobei \(b_i-a_j=h_{i,j}\) gilt. Diese Zuordnung erhält somit jede Hakenhäufigkeit.
Für feste \(m,h\) zähle \(A_h(q)\) die möglichen Abwärtsbewegungen einer Perle um \(h\), summiert über alle Konfigurationen mit Gewicht \(q^{|\lambda|}\). Entsprechend zähle \(C_h(q)\) die Aufwärtsbewegungen und \(B_h(q)\) die belegten Positionen im Bereich \(0,\ldots,h-1\). Eine Abwärtsbewegung ist ein Hilfsmittel dieses Zählarguments; sie muss keiner einzelnen Pinguinbewegung entsprechen.
Die Umkehrung jeder Abwärtsbewegung ist eine Aufwärtsbewegung aus einer Konfiguration, deren Partitionsgröße um \(h\) kleiner ist. Außerdem ergibt in jeder Konfiguration die Differenz zwischen den Aufwärts- und Abwärtsmöglichkeiten durch Teleskopieren die Anzahl ihrer belegten Positionen unterhalb von \(h\). Folglich
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
Um das Teleskopieren unmittelbar zu sehen, sei \(\eta_a\) an einer belegten Position 1 und andernfalls 0. Die Differenz der beiden Bewegungsanzahlen ist \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\). Jede Konfiguration enthält endlich viele Perlen; diese Summen sind daher wohldefiniert.
Die Hakenzuordnung bedeutet genau, dass \(H_h(n)=[q^n]A_h(q)\) gilt.
Führe \(z\) zum Zählen der Perlen ein. Die erzeugende Funktion für verschiedene belegte Positionen lautet
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
Die zweite Identität folgt, indem man die Treppenfolge \(0,1,\ldots,r-1\) von den aufsteigend geordneten Perlenpositionen abzieht. Die Bedingung, dass Position \(a\) belegt ist, multipliziert \(G\) mit \(zq^a/(1+zq^a)\). Entwickle diesen Faktor als \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\), summiere über \(0\le a<h\) und extrahiere \(z^m\). Mit [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
ergibt sich
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
Setze dies in \(A_h\) ein und verwende \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\). Daraus folgt die berechenbare Identität
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
Einzelne Ausdrücke können negative Potenzen enthalten, ihre endliche Summe ist jedoch die gewöhnliche erzeugende Reihe der Hakenanzahlen. Berechnet werden müssen nur die angezeigten nichtnegativen Koeffizientenindizes.
Setze \(K=n+\binom m2\); für die vorgegebene Eingabe beträgt dieser Wert \(11475\). Alle benötigten Indizes sind höchstens \(K\). Halte ein Koeffizientenfeld für \(P_r\) vor, beginnend mit \(P_0=1\). Setze für \(r=0,\ldots,m-1\) jeweils \(j=m-r\) und bilde die Koeffizienten \(Q_s\) von \(P_r(q)/(1-q^j)\) in aufsteigender Reihenfolge:
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
Berechne für jedes \(h\) die Summe von \(Q_{n+d_j-th}\) mit dem entsprechenden Vorzeichen. Berücksichtige anschließend die Teilgröße \(r+1\) durch die übliche Aktualisierung \(P[s]\leftarrow P[s]+P[s-r-1]\) mit aufsteigendem Index. Nach der letzten Aktualisierung gilt \(P[n]=p_m(n)\). Die beiden Koeffizientenfelder werden während der gesamten Rechnung wiederverwendet.
Der Modul \(M\) ist eine Primzahl; dies wird beim Kompilieren durch Probedivision geprüft. Alle Basen \(1,\ldots,300\) sind modulo \(M\) von null verschieden, weshalb der kleine Satz von Fermat die Reduktion jedes Exponenten modulo \(M-1=1234567890\) erlaubt. Die Koeffizientenfelder und Hakenanzahlen werden deshalb modulo \(M-1\) gespeichert; dieser Modul muss selbst keine Primzahl sein. Binäre Exponentiation berechnet Zähler und Nenner modulo \(M\) und invertiert den Nenner durch Potenzieren mit \(M-2\). Vorzeichenlose 64-Bit-Arithmetik kann jedes Produkt zweier Reste modulo \(M\) sicher darstellen. [6]
Die Laufzeit beträgt \(O(m(n+m^2)+m^2n+n\log M)\), gemessen in modularen arithmetischen Operationen. Die Koeffizientenaktualisierungen kosten \(O(mK)\), die Hakensummen \(O(m^2n)\) und die modularen Potenzen \(O(n\log M)\). Der zusätzliche Speicherbedarf ist \(O(n+m^2)\).
Die optionale Ausführung mit --self-test nimmt folgende exakten Prüfungen vor: [7]
Eine separate Rechnung für die vollständige Zielgröße überprüfte unabhängig alle 300 Hakenhäufigkeiten und die Partitionsanzahl. Sie begann mit unbeschränkten Partitionen und zog diejenigen mit mehr als 150 Zeilen ab. Nach Konjugation hat jede ausgeschlossene Partition eine einzige erste Zeile mit Länge größer als 150 und eine verbleibende Teilpartition mit Größe kleiner als 150. Die getrennte Zählung der Haken dieser Teilpartition und der ersten Zeile liefert eine andere Berechnung derselben Gesamtanzahlen. Beide Methoden ergeben \(p_{150}(300)\equiv221703566\pmod{M-1}\), stimmen bei jeder Hakenanzahl modulo \(M-1\) überein und liefern dasselbe Endergebnis. Dieser unabhängige Vergleich ist eine zusätzliche Validierung außerhalb der mitgelieferten Selbsttests.
Die folgenden Quellen nennen die verwendeten Grundlagen. Die Bijektion zwischen Pinguinmärschen und Tableaux, die Identität für die gesamten Hakenanzahlen und der endliche Koeffizientenalgorithmus werden oben ausdrücklich hergeleitet.
\(m\) penguen, \(1,\ldots,m\) konumlarında durmaktadır. Her adımda, hedef konum boş olmak koşuluyla bir penguen bir birim sağa hareket eder. Ulaşılabilen bir son konum vektörü \(v\) için, burada biten ve tam olarak \(n\) hareketten oluşan geçerli dizilerin sayısını \(f(v)\) ile gösterelim. Ulaşılabilen bütün son durumlar için bu sayıları çarparak \(F(150,300)\) değerini \(M=1234567891\) modülünde hesaplamamız gerekiyor. [1]
Penguenlerin sırası hiçbir zaman değişmez. Yer değiştirmelerini \(x_i=v_i-i\) olarak yazalım. Son konumların birbirinden farklı olması \(0\le x_1\le\cdots\le x_m\) koşulunu verir. Böylece yer değiştirmelerin sırasını ters çevirdiğimizde bir bölüntü elde ederiz:
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
Bir penguenin hareketi, bu bölüntünün ilgili satırına bir hücre ekler. Hedef konumun boş olması, büyütülmüş şeklin yine bir bölüntü olmasıyla tam olarak eşdeğerdir. Eklenen her hücreyi, eklendiği hareketin numarasıyla etiketleyelim. Etiketler satırlarda ve sütunlarda artar; böylece standart bir Young tablosu oluşur. Tersine, böyle bir tabloyu etiket sırasıyla okumak, tek bir geçerli yürüyüşü yeniden kurar. En fazla \(m\) satırı olan her bölüntüye ulaşılabilir.
\((i,j)\) hücresinin kanca uzunluğu, aynı satırda sağında veya aynı sütunda altında bulunan hücrelerin sayısına kendisinin de eklenmesiyle elde edilir:
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
Burada \(\lambda'_j\), \(j\) sütununun yüksekliğidir. Dolayısıyla kanca uzunluğu formülü \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\) sonucunu verir. [2]
Örneğin iki penguen ve dört hareket için mümkün şekiller \((4)\), \((3,1)\) ve \((2,2)\) biçimindedir. Bunların kanca çarpımları sırasıyla 24, 8 ve 12 olduğundan yol sayıları \(4!/24=1\), \(4!/8=3\) ve \(4!/12=2\) olur. Çarpımları, verilen \(F(2,4)=6\) değerini verir. Bu örnek, yol sayılarını toplamanın neden farklı bir soruyu yanıtlayacağını da gösterir: Her farklı son durum, istenen çarpıma bir çarpan olarak katılır.
\(p_m(n)\), \(n\) sayısının en fazla \(m\) satırlı bölüntülerinin sayısı olsun. \(H_h(n)\) ise bu bölüntülerin tümünde \(h\) kanca uzunluğunun toplam görülme sayısını göstersin. Tablo formülünü bütün bölüntüler üzerinde çarparsak
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
elde edilir. Bölüntüleri tek tek sıralamak yerine bu toplam sayılara ihtiyacımız var. Şunu tanımlayalım:
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
Bölüntülerin eşleniğini alarak \([q^n]P_m(q)=p_m(n)\) sonucunu buluruz. \([q^s]\) gösterimi katsayı almayı ifade eder; negatif bir indeksin katkısı sıfırdır. [4]
Bir bölüntüyü, \(m\) tane birbirinden farklı, negatif olmayan beta sayısı \(b_i=\lambda_i+m-i\) ile temsil edelim; bunları tam sayı doğrusu üzerinde dolu konumlar olarak düşünelim. Toplamları \(|\lambda|+\binom m2\) olur. Uzunluğu \(h\) olan kancalar, \(b-h\ge0\) konumu boş olan dolu \(b\) konumlarına tam olarak karşılık gelir. [3]
Açıkça, negatif olmayan boş konumlar \(j\ge1\) için \(a_j=m+j-1-\lambda'_j\) biçimindedir. Her \((i,j)\) hücresi, \(b_i\) ile \(a_j<b_i\) konumlarını eşler ve \(b_i-a_j=h_{i,j}\) sağlanır. Böylece bu eşleme her kanca uzunluğunun görülme sayısını korur.
\(m,h\) sabitken, \(A_h(q)\) bir boncuğun \(h\) birim aşağı hareket etme olanaklarını, bütün düzenler üzerinde \(q^{|\lambda|}\) ağırlığıyla toplasın. Benzer biçimde \(C_h(q)\) yukarı hareketleri, \(B_h(q)\) ise \(0,\ldots,h-1\) arasındaki dolu konumları saysın. Aşağı hareket, bu sayma kanıtında kullanılan yardımcı bir işlemdir; tek bir penguen adımı olmak zorunda değildir.
Her aşağı hareketi tersine çevirmek, bölüntü büyüklüğü \(h\) kadar daha küçük bir düzenden başlayan yukarı hareket verir. Ayrıca her düzende yukarı hareket olanaklarından aşağı hareket olanakları çıkarıldığında, toplamın terimleri teleskopik biçimde sadeleşir ve \(h\) değerinin altındaki dolu konumların sayısı kalır. Dolayısıyla
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
Teleskopik sadeleşmeyi doğrudan görmek için \(\eta_a\), dolu bir konumda 1, diğer konumlarda 0 olsun. İki hareket sayısının farkı \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\) olur. Her düzende sonlu sayıda boncuk bulunduğundan bu toplamlar iyi tanımlıdır.
Kancalarla kurulan eşleme tam olarak \(H_h(n)=[q^n]A_h(q)\) eşitliğini ifade eder.
Boncukları saymak için \(z\) değişkenini kullanalım. Birbirinden farklı dolu konumların üreteç fonksiyonu
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
biçimindedir. İkinci eşitlik, artan sıradaki boncuk konumlarından \(0,1,\ldots,r-1\) basamaklı dizisinin çıkarılmasıyla elde edilir. \(a\) konumunun dolu olmasını şart koşmak, \(G\) fonksiyonunu \(zq^a/(1+zq^a)\) ile çarpar. Bu çarpanı \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\) biçiminde açalım, \(0\le a<h\) üzerinden toplayalım ve \(z^m\) katsayısını alalım. [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
tanımıyla sonuç
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
olur. Bunu \(A_h\) içinde yerine koyup \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\) eşitliğini kullanırsak hesaplanabilir şu özdeşliği buluruz:
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
Tek tek ifadeler negatif üsler içerebilir; ancak sonlu toplamları, kanca sayılarını veren sıradan bir üreteç serisidir. Yalnızca formülde görünen negatif olmayan indekslere ait katsayıların hesaplanması yeterlidir.
\(K=n+\binom m2\) olarak alalım; istenen girdi için bu değer \(11475\) olur. Gerekli bütün indeksler en fazla \(K\) değerindedir. \(P_0=1\) başlangıcıyla, \(P_r\) için tek bir katsayı dizisi tutalım. \(r=0,\ldots,m-1\) için \(j=m-r\) alıp \(P_r(q)/(1-q^j)\) fonksiyonunun \(Q_s\) katsayılarını artan sırayla oluşturalım:
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
Her \(h\) için \(Q_{n+d_j-th}\) terimlerinin uygun işaretli toplamını biriktirelim. Ardından \(r+1\) parça büyüklüğünü, indeksleri artan sırayla dolaşan standart \(P[s]\leftarrow P[s]+P[s-r-1]\) güncellemesiyle dahil edelim. Son güncellemeden sonra \(P[n]=p_m(n)\) olur. İki katsayı dizisi hesaplama boyunca yeniden kullanılır.
\(M\) modülü asaldır; bu, derleme sırasında deneme bölmesiyle doğrulanır. \(1,\ldots,300\) tabanlarının tümü \(M\) modülünde sıfırdan farklı olduğundan Fermat'nın küçük teoremi her üssün \(M-1=1234567890\) modülünde indirgenmesine izin verir. Bu nedenle katsayı dizileri ve kanca sayıları \(M-1\) modülünde tutulur; bu modülün kendisinin asal olması gerekmez. İkili üs alma, payı ve paydayı \(M\) modülünde hesaplar; paydayı tersine çevirmek için \(M-2\) kuvvetine yükseltir. İşaretsiz 64 bit aritmetik, \(M\) modülündeki iki kalanın her çarpımını güvenle tutabilir. [6]
Modüler aritmetik işlemleri sayıldığında çalışma süresi \(O(m(n+m^2)+m^2n+n\log M)\) olur. Katsayı güncellemelerinin maliyeti \(O(mK)\), kanca toplamlarının maliyeti \(O(m^2n)\), modüler kuvvetlerin maliyeti ise \(O(n\log M)\) düzeyindedir. Ek bellek gereksinimi \(O(n+m^2)\) olur.
İsteğe bağlı --self-test seçeneği şu kesin kontrolleri gerçekleştirir: [7]
Hedef boyutta yapılan ayrı bir hesaplama, 300 kanca uzunluğunun tamamının görülme sayısını ve bölüntü sayısını bağımsız olarak doğruladı. Bu hesaplama, kısıtsız bölüntülerden başlayıp 150'den fazla satırı olanları çıkardı. Eşlenik alındığında dışlanan her bölüntünün uzunluğu 150'yi aşan tek bir ilk satırı ve büyüklüğü 150'nin altında kalan bir kuyruk bölüntüsü vardır. Kuyruğun kancalarıyla ilk satırın kancalarını ayrı ayrı saymak, aynı toplamların farklı bir yoldan hesaplanmasını sağlar. Her iki yöntem de \(p_{150}(300)\equiv221703566\pmod{M-1}\) değerini verir, her kanca sayısında \(M-1\) modülünde uyuşur ve aynı sonuca ulaşır. Bu bağımsız karşılaştırma, kodla birlikte sunulan öz sınamalardan ayrı bir ek doğrulamadır.
Aşağıdaki kaynaklar, türetmede kullanılan temel sonuçları gösterir. Penguen hareketleriyle tablolar arasındaki bire bir eşleme, toplam kanca sayısı özdeşliği ve sonlu katsayı algoritması yukarıda açıkça türetilmiştir.
Hay \(m\) pingüinos en las posiciones \(1,\ldots,m\). En cada paso, un pingüino avanza una unidad hacia la derecha, siempre que la posición de destino esté vacía. Para un vector de posiciones finales alcanzable \(v\), sea \(f(v)\) el número de secuencias válidas de exactamente \(n\) movimientos que terminan allí. Debemos multiplicar estas cantidades para todos los destinos alcanzables y calcular \(F(150,300)\) módulo \(M=1234567891\). [1]
Los pingüinos nunca cambian de orden. Escribamos sus desplazamientos como \(x_i=v_i-i\). Las posiciones finales distintas implican \(0\le x_1\le\cdots\le x_m\); por tanto, al invertir el orden de los desplazamientos obtenemos una partición
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
Mover un pingüino añade una casilla a la fila correspondiente de esta partición, y el destino está libre exactamente cuando la forma ampliada sigue siendo una partición. Etiquetemos cada nueva casilla con el número de su movimiento. Las etiquetas crecen a lo largo de las filas y las columnas, formando una tabla de Young estándar. Recíprocamente, leer una tabla de este tipo en orden de sus etiquetas reconstruye una única marcha válida. Toda partición con a lo sumo \(m\) filas es alcanzable.
La longitud de gancho de una casilla \((i,j)\) es el número de casillas situadas estrictamente a su derecha en la misma fila o debajo en la misma columna, más la propia casilla:
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
Aquí \(\lambda'_j\) es la altura de la columna \(j\). La fórmula de las longitudes de gancho da, por tanto, \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\). [2]
Por ejemplo, con dos pingüinos y cuatro movimientos, las formas posibles son \((4)\), \((3,1)\) y \((2,2)\). Sus productos de longitudes de gancho son 24, 8 y 12, respectivamente, de modo que los números de caminos son \(4!/24=1\), \(4!/8=3\) y \(4!/12=2\). Al multiplicarlos obtenemos el valor indicado \(F(2,4)=6\). Esto también ilustra por qué sumar los números de caminos respondería a otra pregunta: cada destino distinto aporta un factor al producto solicitado.
Sea \(p_m(n)\) el número de particiones de \(n\) con a lo sumo \(m\) filas, y sea \(H_h(n)\) el número total de apariciones de la longitud de gancho \(h\) en dichas particiones. Multiplicar la fórmula de las tablas proporciona
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
Necesitamos estas cantidades agregadas, en lugar de enumerar cada partición individual. Definamos
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
Por conjugación de particiones, \([q^n]P_m(q)=p_m(n)\). La notación \([q^s]\) indica extracción de coeficientes; un índice negativo aporta cero. [4]
Representemos una partición mediante sus \(m\) números beta distintos y no negativos \(b_i=\lambda_i+m-i\), interpretados como posiciones ocupadas en una recta de enteros. Su suma es \(|\lambda|+\binom m2\). Los ganchos de longitud \(h\) corresponden exactamente a las posiciones ocupadas \(b\) cuya posición \(b-h\ge0\) está vacía. [3]
Explícitamente, las posiciones vacías no negativas son \(a_j=m+j-1-\lambda'_j\), para \(j\ge1\). Cada casilla \((i,j)\) empareja \(b_i\) con \(a_j<b_i\), y se cumple \(b_i-a_j=h_{i,j}\). Así, esta correspondencia conserva todas las multiplicidades de las longitudes de gancho.
Para \(m,h\) fijos, sea \(A_h(q)\) la suma, sobre todas las configuraciones con peso \(q^{|\lambda|}\), de los posibles movimientos descendentes de una ficha en \(h\) unidades. Sea \(C_h(q)\) el recuento análogo de movimientos ascendentes, y sea \(B_h(q)\) el recuento de posiciones ocupadas entre \(0,\ldots,h-1\). Un movimiento descendente es una operación auxiliar de este argumento de conteo; no tiene por qué ser un único paso de un pingüino.
Invertir cada movimiento descendente da un movimiento ascendente desde una configuración cuya partición tiene tamaño menor en \(h\). Además, para cada configuración, el número de opciones ascendentes menos el de opciones descendentes se simplifica por cancelación telescópica al número de posiciones ocupadas por debajo de \(h\). En consecuencia,
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
Para ver directamente la cancelación, sea \(\eta_a\) igual a 1 en una posición ocupada y a 0 en cualquier otra. La diferencia entre los dos recuentos de movimientos es \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\). Cada configuración contiene un número finito de fichas, de modo que estas sumas están bien definidas.
La correspondencia de ganchos significa exactamente que \(H_h(n)=[q^n]A_h(q)\).
Introduzcamos \(z\) para contar las fichas. La función generatriz de las posiciones ocupadas distintas es
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
La segunda identidad se obtiene al restar la sucesión escalonada \(0,1,\ldots,r-1\) de las posiciones de las fichas ordenadas de forma creciente. Exigir que la posición \(a\) esté ocupada multiplica \(G\) por \(zq^a/(1+zq^a)\). Desarrollemos este factor como \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\), sumemos sobre \(0\le a<h\) y extraigamos \(z^m\). Con [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
el resultado es
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
Sustituyamos en \(A_h\) y utilicemos \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\). Obtenemos así la identidad computable
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
Las expresiones individuales pueden contener potencias negativas, pero su suma finita es la serie generatriz ordinaria de los recuentos de ganchos. Solo es necesario calcular los coeficientes con los índices no negativos que aparecen en la fórmula.
Tomemos \(K=n+\binom m2\), cuyo valor para la entrada solicitada es \(11475\). Todos los índices necesarios son a lo sumo \(K\). Mantenemos un único arreglo de coeficientes para \(P_r\), comenzando con \(P_0=1\). Para \(r=0,\ldots,m-1\), fijamos \(j=m-r\) y construimos los coeficientes \(Q_s\) de \(P_r(q)/(1-q^j)\) en orden creciente:
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
Para cada \(h\), acumulamos la suma con el signo correspondiente de \(Q_{n+d_j-th}\). Después incorporamos el tamaño de parte \(r+1\) mediante la actualización habitual con índices crecientes \(P[s]\leftarrow P[s]+P[s-r-1]\). Tras la última actualización, \(P[n]=p_m(n)\). Los dos arreglos de coeficientes se reutilizan durante todo el cálculo.
El módulo \(M\) es primo, como verifica una prueba por división sucesiva realizada durante la compilación. Todas las bases \(1,\ldots,300\) son distintas de cero módulo \(M\), por lo que el pequeño teorema de Fermat permite reducir cada exponente módulo \(M-1=1234567890\). Por tanto, los arreglos de coeficientes y los recuentos de ganchos se almacenan módulo \(M-1\); este módulo no necesita ser primo. La exponenciación binaria evalúa el numerador y el denominador módulo \(M\), y eleva el denominador a \(M-2\) para invertirlo. La aritmética de enteros sin signo de 64 bits puede representar de forma segura cualquier producto de dos residuos módulo \(M\). [6]
El tiempo de ejecución es \(O(m(n+m^2)+m^2n+n\log M)\), contado en operaciones aritméticas modulares. Las actualizaciones de coeficientes cuestan \(O(mK)\), las sumas de ganchos \(O(m^2n)\) y las potencias modulares \(O(n\log M)\). El espacio auxiliar es \(O(n+m^2)\).
La opción --self-test realiza las siguientes comprobaciones exactas: [7]
Un cálculo separado para el tamaño completo verificó de forma independiente las 300 multiplicidades de las longitudes de gancho y el número de particiones. Comenzó con las particiones sin restricciones y restó aquellas con más de 150 filas. Después de conjugarlas, cada partición excluida tiene una única primera fila de longitud mayor que 150 y una partición restante de tamaño menor que 150. Contar por separado los ganchos de esa partición restante y los de la primera fila proporciona otro cálculo de las mismas cantidades agregadas. Ambos métodos dan \(p_{150}(300)\equiv221703566\pmod{M-1}\), coinciden en cada recuento de ganchos módulo \(M-1\) y producen el mismo resultado final. Esta comparación independiente es una validación adicional, separada de las pruebas incluidas en el programa.
Las referencias siguientes identifican los resultados de base utilizados. La biyección entre marchas y tableaux, la identidad para los recuentos agregados de ganchos y el algoritmo finito de coeficientes se deducen explícitamente arriba.
有 \(m\) 只企鹅，初始位置为 \(1,\ldots,m\)。每一步选择一只企鹅向右移动一个单位，前提是目标位置为空。对于可到达的最终位置向量 \(v\)，令 \(f(v)\) 表示恰好经过 \(n\) 次移动并到达该位置的合法序列数。我们需要将所有可到达终点对应的这些数量相乘，并计算 \(F(150,300)\) 对 \(M=1234567891\) 取模的结果。 [1]
企鹅之间的先后顺序始终不变。将它们的位移记为 \(x_i=v_i-i\)。最终位置互不相同，因此 \(0\le x_1\le\cdots\le x_m\)；将位移顺序反转，便得到一个整数分拆
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
移动一只企鹅，相当于在此分拆的对应行增加一个格子；目标位置为空，当且仅当增加格子后的形状仍然是一个分拆。用移动的序号标记每个新增格子。标号沿各行和各列递增，因此构成一个标准杨表。反过来，按标号顺序读取任意这样的杨表，都能重建唯一的合法行进序列。每个行数不超过 \(m\) 的分拆都可到达。
格子 \((i,j)\) 的钩长，等于其右侧及下方的格子数，再加上它自身：
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
这里，\(\lambda'_j\) 是第 \(j\) 列的高度。因此，由钩长公式可得 \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\)。 [2]
例如，两只企鹅移动四步时，可能得到的形状为 \((4)\)、\((3,1)\) 和 \((2,2)\)。它们的钩长乘积分别为 24、8 和 12，因此路径数为 \(4!/24=1\)、\(4!/8=3\) 和 \(4!/12=2\)。将这些数量相乘，得到题目给出的 \(F(2,4)=6\)。这也说明，对路径数求和会回答另一个问题：每个不同的终点都为所求乘积贡献一个因子。
令 \(p_m(n)\) 表示 \(n\) 的行数不超过 \(m\) 的分拆数，并令 \(H_h(n)\) 表示这些分拆中长度为 \(h\) 的钩的总出现次数。将杨表计数公式相乘，得到
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
我们只需要这些汇总计数，无须逐个枚举分拆。定义
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
通过对分拆取共轭，可得 \([q^n]P_m(q)=p_m(n)\)。记号 \([q^s]\) 表示提取系数；当下标为负时，其贡献为零。 [4]
用分拆对应的 \(m\) 个互不相同的非负贝塔数 \(b_i=\lambda_i+m-i\) 来表示它，并将这些数看作整数线上被占用的位置。它们的总和为 \(|\lambda|+\binom m2\)。长度为 \(h\) 的钩，恰好对应于占用位置 \(b\)，且相应的位置 \(b-h\ge0\) 为空。 [3]
具体来说，非负的空位置为 \(a_j=m+j-1-\lambda'_j\)，其中 \(j\ge1\)。每个格子 \((i,j)\) 将 \(b_i\) 与 \(a_j<b_i\) 配对，并且 \(b_i-a_j=h_{i,j}\)。因此，这一对应保留了每种钩长的出现次数。
固定 \(m,h\)，令 \(A_h(q)\) 统计珠子向下移动 \(h\) 的可行选择数，对所有配置按权重 \(q^{|\lambda|}\) 求和。类似地，令 \(C_h(q)\) 统计向上移动的选择数，并令 \(B_h(q)\) 统计 \(0,\ldots,h-1\) 中被占用的位置数。向下移动只是此计数论证中的辅助操作，不一定对应于企鹅的一次移动。
将每次向下移动反转，就得到一次向上移动，其起始配置对应的分拆大小减少了 \(h\)。此外，对于每个配置，向上移动的选择数减去向下移动的选择数，经逐项相消后等于小于 \(h\) 的占用位置数。因此
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
为了直接看出上述相消，令 \(\eta_a\) 在位置被占用时等于 1，否则等于 0。两种移动选择数之差为 \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\)。每个配置中的珠子数有限，因此这些求和都有明确的定义。
钩与移动的对应关系恰好说明 \(H_h(n)=[q^n]A_h(q)\)。
引入 \(z\) 来记录珠子数。互不相同的占用位置所对应的生成函数为
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
后一个恒等式可由递增的珠子位置减去阶梯序列 \(0,1,\ldots,r-1\) 得到。要求位置 \(a\) 被占用，相当于将 \(G\) 乘以 \(zq^a/(1+zq^a)\)。将该因子展开为 \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\)，对 \(0\le a<h\) 求和，并提取 \(z^m\) 的系数。令 [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
则得到
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
将其代入 \(A_h\)，并使用 \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\)，即可得到可计算的恒等式
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
单个表达式可能包含负幂，但它们的有限和是通常的钩计数生成级数。只需计算公式中所示的非负下标对应的系数。
设 \(K=n+\binom m2\)，对于题目要求的输入，其值为 \(11475\)。所需的所有下标都不超过 \(K\)。维护一个表示 \(P_r\) 的系数数组，从 \(P_0=1\) 开始。对于 \(r=0,\ldots,m-1\)，令 \(j=m-r\)，并按递增顺序计算系数 \(Q_s\)；这些系数来自 \(P_r(q)/(1-q^j)\)：
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
对于每个 \(h\)，累加 \(Q_{n+d_j-th}\) 的带符号和。然后加入大小为 \(r+1\) 的分拆部分，采用通常的递增下标更新 \(P[s]\leftarrow P[s]+P[s-r-1]\)。最后一次更新后，\(P[n]=p_m(n)\)。整个过程中重复使用这两个系数数组。
模数 \(M\) 是素数，这一点由编译期试除检查验证。所有底数 \(1,\ldots,300\) 模 \(M\) 均非零，因此费马小定理允许将每个指数对 \(M-1=1234567890\) 取模。于是，系数数组和钩计数都以模 \(M-1\) 的形式存储；这个模数本身不必是素数。二进制快速幂在模 \(M\) 下计算分子和分母，并将分母提升至 \(M-2\) 次幂以求逆。无符号 64 位算术能够安全容纳任意两个模 \(M\) 的余数之积。 [6]
以模运算次数计，运行时间为 \(O(m(n+m^2)+m^2n+n\log M)\)。系数更新耗时 \(O(mK)\)，钩计数求和耗时 \(O(m^2n)\)，模幂运算耗时 \(O(n\log M)\)。辅助空间为 \(O(n+m^2)\)。
可选参数 --self-test 执行以下精确检查： [7]
另一次独立的完整规模计算核对了全部 300 种钩长的出现次数以及分拆数。该计算从不限制行数的分拆出发，减去行数超过 150 的分拆。取共轭后，每个被排除的分拆都有唯一一行长度超过 150 的首行，而其余部分的大小小于 150。分别统计其余部分中的钩和首行中的钩，便得到对相同汇总量的另一种计算。两种方法都得到 \(p_{150}(300)\equiv221703566\pmod{M-1}\)，所有钩计数在模 \(M-1\) 下均一致，并产生相同的最终结果。这一独立比较是附加验证，与代码自带的自检分开进行。
以下资料说明推导所用的基础结果。企鹅行进与杨表的双射、钩长总计数恒等式及有限系数算法，均已在上文明确推导。
Имеются \(m\) пингвинов в позициях \(1,\ldots,m\). За один ход один пингвин перемещается на единицу вправо, если целевая позиция свободна. Для достижимого вектора конечных позиций \(v\) обозначим через \(f(v)\) число допустимых последовательностей ровно из \(n\) ходов, заканчивающихся в нём. Требуется перемножить эти количества по всем достижимым конечным состояниям и вычислить \(F(150,300)\) по модулю \(M=1234567891\). [1]
Пингвины никогда не меняют свой порядок. Запишем их смещения как \(x_i=v_i-i\). Различие конечных позиций означает \(0\le x_1\le\cdots\le x_m\), поэтому смещения в обратном порядке образуют разбиение
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
Ход пингвина добавляет одну клетку в соответствующую строку этого разбиения; целевая позиция свободна тогда и только тогда, когда увеличенная диаграмма остаётся разбиением. Пометим каждую добавленную клетку номером хода. Метки возрастают вдоль строк и столбцов, образуя стандартную таблицу Юнга. Обратно, чтение любой такой таблицы в порядке меток восстанавливает единственный допустимый марш. Достижимо каждое разбиение с числом строк не более \(m\).
Длина крюка клетки \((i,j)\) равна числу клеток строго справа от неё или ниже неё плюс сама клетка:
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
Здесь \(\lambda'_j\) — высота столбца \(j\). Поэтому формула длин крюков даёт \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\). [2]
Например, для двух пингвинов и четырёх ходов возможны диаграммы \((4)\), \((3,1)\) и \((2,2)\). Произведения длин их крюков равны соответственно 24, 8 и 12, поэтому числа путей равны \(4!/24=1\), \(4!/8=3\) и \(4!/12=2\). Их произведение даёт указанное значение \(F(2,4)=6\). Это также объясняет, почему сложение чисел путей отвечало бы на другой вопрос: каждое отдельное конечное состояние вносит один множитель в требуемое произведение.
Пусть \(p_m(n)\) — число разбиений \(n\) с числом строк не более \(m\), а \(H_h(n)\) — общее число крюков длины \(h\) во всех этих разбиениях. Перемножая формулы для таблиц, получаем
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
Нужны именно эти суммарные количества, без перечисления отдельных разбиений. Определим
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
Сопряжение разбиений даёт \([q^n]P_m(q)=p_m(n)\). Обозначение \([q^s]\) означает извлечение коэффициента; отрицательный индекс даёт нулевой вклад. [4]
Представим разбиение его \(m\) различными неотрицательными бета-числами \(b_i=\lambda_i+m-i\), рассматривая их как занятые позиции на целочисленной прямой. Их сумма равна \(|\lambda|+\binom m2\). Крюки длины \(h\) в точности соответствуют занятым позициям \(b\), для которых позиция \(b-h\ge0\) свободна. [3]
Явно неотрицательные свободные позиции имеют вид \(a_j=m+j-1-\lambda'_j\), где \(j\ge1\). Каждая клетка \((i,j)\) сопоставляет \(b_i\) с \(a_j<b_i\), причём \(b_i-a_j=h_{i,j}\). Таким образом, это соответствие сохраняет количество крюков каждой длины.
Для фиксированных \(m,h\) пусть \(A_h(q)\) подсчитывает возможные перемещения бусины вниз на \(h\), суммируя по всем конфигурациям с весом \(q^{|\lambda|}\). Аналогично пусть \(C_h(q)\) подсчитывает перемещения вверх, а \(B_h(q)\) — занятые позиции среди \(0,\ldots,h-1\). Перемещение вниз является вспомогательной операцией в этом подсчёте; оно не обязано совпадать с одним ходом пингвина.
Обращение каждого перемещения вниз даёт перемещение вверх из конфигурации, размер разбиения которой меньше на \(h\). Кроме того, для каждой конфигурации разность между числами перемещений вверх и вниз телескопически сокращается до числа занятых позиций ниже \(h\). Следовательно,
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
Чтобы увидеть сокращение непосредственно, положим \(\eta_a\) равным 1 для занятой позиции и 0 для свободной. Разность между двумя числами перемещений равна \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\). Каждая конфигурация содержит конечное число бусин, поэтому эти суммы корректно определены.
Соответствие между крюками и перемещениями в точности означает \(H_h(n)=[q^n]A_h(q)\).
Введём \(z\) для учёта числа бусин. Производящая функция для различных занятых позиций имеет вид
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
Последнее тождество получается вычитанием лестницы \(0,1,\ldots,r-1\) из возрастающих позиций бусин. Требование занятости позиции \(a\) означает умножение \(G\) на \(zq^a/(1+zq^a)\). Разложим этот множитель в ряд \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\), просуммируем по \(0\le a<h\) и извлечём коэффициент при \(z^m\). Обозначив [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
получаем
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
Подставим это в \(A_h\) и воспользуемся равенством \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\). Получаем пригодное для вычисления тождество
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
Отдельные выражения могут содержать отрицательные степени, но их конечная сумма является обычным производящим рядом для числа крюков. Вычислять нужно только коэффициенты с указанными неотрицательными индексами.
Положим \(K=n+\binom m2\); для требуемых входных данных это \(11475\). Все нужные индексы не превосходят \(K\). Будем хранить один массив коэффициентов \(P_r\), начиная с \(P_0=1\). Для \(r=0,\ldots,m-1\) положим \(j=m-r\) и вычислим по возрастанию индекса коэффициенты \(Q_s\) функции \(P_r(q)/(1-q^j)\):
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
Для каждого \(h\) накапливаем сумму \(Q_{n+d_j-th}\) с соответствующим знаком. Затем учитываем части размера \(r+1\) обычным обновлением по возрастанию индекса: \(P[s]\leftarrow P[s]+P[s-r-1]\). После последнего обновления \(P[n]=p_m(n)\). На всём протяжении вычисления используются те же два массива коэффициентов.
Модуль \(M\) прост, что проверяется пробным делением во время компиляции. Все основания \(1,\ldots,300\) ненулевые по модулю \(M\), поэтому малая теорема Ферма позволяет сокращать каждый показатель по модулю \(M-1=1234567890\). Следовательно, массивы коэффициентов и количества крюков хранятся по модулю \(M-1\); этот модуль сам не обязан быть простым. Двоичное возведение в степень вычисляет числитель и знаменатель по модулю \(M\), а возведение знаменателя в степень \(M-2\) даёт обратный элемент. Беззнаковая 64-битная арифметика без переполнения вмещает произведение любых двух остатков по модулю \(M\). [6]
Время работы составляет \(O(m(n+m^2)+m^2n+n\log M)\), если считать модульные арифметические операции. Обновления коэффициентов требуют \(O(mK)\), суммы для крюков — \(O(m^2n)\), а модульное возведение в степень — \(O(n\log M)\). Дополнительная память составляет \(O(n+m^2)\).
Необязательный параметр --self-test запускает следующие точные проверки: [7]
Отдельное полноразмерное вычисление независимо проверило все 300 количеств крюков и число разбиений. Оно начиналось с неограниченных разбиений, из которых вычитались разбиения с числом строк более 150. После сопряжения каждое исключённое разбиение имеет единственную первую строку длиной более 150 и хвост размера менее 150. Отдельный подсчёт крюков хвоста и первой строки даёт другой способ вычисления тех же суммарных величин. Оба метода дают \(p_{150}(300)\equiv221703566\pmod{M-1}\), совпадают по каждому количеству крюков по модулю \(M-1\) и приводят к одному итоговому результату. Это независимое сравнение служит дополнительной проверкой и не входит в поставляемые с программой самотесты.
Ниже указаны источники используемых общих результатов. Биекция между маршами и таблицами, тождество для суммарных чисел крюков и конечный алгоритм извлечения коэффициентов явно выведены выше.
لدينا \(m\) من البطاريق في المواضع \(1,\ldots,m\). في كل خطوة يتحرك بطريق واحد وحدة واحدة إلى اليمين، بشرط أن يكون موضع الوصول فارغًا. لكل متجه مواضع نهائية قابل للوصول \(v\)، نعرّف \(f(v)\) بأنه عدد تسلسلات الحركات المسموح بها التي تتكون من \(n\) حركة بالضبط وتنتهي عنده. المطلوب هو ضرب هذه الأعداد لجميع النهايات القابلة للوصول وحساب \(F(150,300)\) بترديد \(M=1234567891\). [1]
لا يتغير ترتيب البطاريق أبدًا. لنكتب إزاحاتها بالشكل \(x_i=v_i-i\). اختلاف المواضع النهائية يقتضي \(0\le x_1\le\cdots\le x_m\)، ولذلك فإن عكس ترتيب الإزاحات يعطي تجزئة
$$\lambda_i=x_{m+1-i},\qquad \lambda_1\ge\cdots\ge\lambda_m\ge0,\qquad |\lambda|=n.$$
تحريك بطريق يضيف خلية واحدة إلى الصف المقابل في هذه التجزئة، ويكون موضع الوصول فارغًا إذا وفقط إذا بقي الشكل الموسّع تجزئة. نضع على كل خلية مضافة رقم الحركة التي أضافتها. تتزايد الأرقام على امتداد الصفوف والأعمدة، فتنتج لوحة يونغ قياسية. وبالعكس، فإن قراءة أي لوحة كهذه بترتيب أرقامها تعيد بناء مسيرة مسموح بها وحيدة. كل تجزئة لا يزيد عدد صفوفها على \(m\) قابلة للوصول.
طول خطاف الخلية \((i,j)\) هو عدد الخلايا الواقعة إلى يمينها في الصف أو أسفلها في العمود، مضافًا إليه الخلية نفسها:
$$h_{i,j}=\lambda_i-j+\lambda'_j-i+1.$$
هنا \(\lambda'_j\) هو ارتفاع العمود \(j\). ولذلك تعطينا صيغة أطوال الخطافات \(f(v)=n!/\prod_{(i,j)\in\lambda}h_{i,j}\). [2]
مثلًا، عند وجود بطريقين وأربع حركات، تكون الأشكال الممكنة هي \((4)\) و\((3,1)\) و\((2,2)\). جداءات أطوال خطافاتها هي 24 و8 و12 على الترتيب، ومن ثم فإن أعداد المسارات هي \(4!/24=1\) و\(4!/8=3\) و\(4!/12=2\). بضربها نحصل على القيمة المعطاة \(F(2,4)=6\). وهذا يوضح أيضًا لماذا يجيب جمع أعداد المسارات عن سؤال مختلف: فكل نهاية متميزة تسهم بعامل واحد في الجداء المطلوب.
لتكن \(p_m(n)\) عدد تجزئات \(n\) التي لا يزيد عدد صفوفها على \(m\)، ولتكن \(H_h(n)\) عدد جميع مرات ظهور طول الخطاف \(h\) في هذه التجزئات. بضرب صيغة عدّ الجداول نحصل على
$$F(m,n)=\frac{(n!)^{p_m(n)}}{\displaystyle\prod_{h=1}^{n}h^{H_h(n)}}.$$
نحتاج إلى هذه الأعداد المجمّعة، دون تعداد التجزئات منفردة. نعرّف
$$P_r(q)=\prod_{i=1}^{r}\frac1{1-q^i},\qquad P_0(q)=1.$$
بأخذ التجزئات المرافقة نحصل على \([q^n]P_m(q)=p_m(n)\). يرمز \([q^s]\) إلى استخراج المعامل؛ ويكون إسهام الفهرس السالب صفرًا. [4]
نمثّل التجزئة بأعداد بيتا وعددها \(m\)، وهي أعداد غير سالبة ومتميزة تُعطى بالعلاقة \(b_i=\lambda_i+m-i\)، ونعدّها مواضع مشغولة على خط الأعداد الصحيحة. مجموعها هو \(|\lambda|+\binom m2\). تقابل الخطافات ذات الطول \(h\) بالضبط المواضع المشغولة \(b\) التي يكون فيها الموضع \(b-h\ge0\) فارغًا. [3]
بصورة صريحة، المواضع الفارغة غير السالبة هي \(a_j=m+j-1-\lambda'_j\)، حيث \(j\ge1\). تربط كل خلية \((i,j)\) بين \(b_i\) و\(a_j<b_i\)، وتتحقق العلاقة \(b_i-a_j=h_{i,j}\). وهكذا يحافظ هذا التقابل على عدد الخطافات من كل طول.
عند تثبيت \(m,h\)، لتكن \(A_h(q)\) دالة تعدّ الحركات الممكنة للخرزات إلى الأسفل بمقدار \(h\)، مع الجمع على جميع الترتيبات بوزن \(q^{|\lambda|}\). ولتعدّ \(C_h(q)\) حركات الاتجاه الأعلى بالطريقة نفسها، ولتعدّ \(B_h(q)\) المواضع المشغولة ضمن \(0,\ldots,h-1\). الحركة إلى الأسفل أداة مساعدة في حجة العدّ هذه، ولا يلزم أن تكون خطوة واحدة لبطريق.
عكس كل حركة إلى الأسفل يعطي حركة إلى الأعلى انطلاقًا من ترتيب يقل حجم تجزئته بمقدار \(h\). كذلك، لكل ترتيب، يؤدي الاختزال المتتابع في الفرق بين عدد خيارات الحركة إلى الأعلى وعدد خيارات الحركة إلى الأسفل إلى عدد المواضع المشغولة الأصغر من \(h\). وبالتالي
$$A_h(q)=q^h C_h(q),\qquad C_h(q)-A_h(q)=B_h(q),\qquad A_h(q)=\frac{q^h}{1-q^h}B_h(q).$$
لرؤية هذا الاختزال مباشرة، لتكن \(\eta_a\) مساوية لـ1 عند الموضع المشغول ولـ0 فيما عدا ذلك. الفرق بين عددي الحركات هو \(\sum_{a\ge0}(\eta_a(1-\eta_{a+h})-(1-\eta_a)\eta_{a+h})=\sum_{a=0}^{h-1}\eta_a\). يحتوي كل ترتيب على عدد منتهٍ من الخرزات، ولذلك فهذه المجاميع معرّفة جيدًا.
يعني تقابل الخطافات على وجه الدقة أن \(H_h(n)=[q^n]A_h(q)\).
ندخل المتغير \(z\) لعدّ الخرزات. الدالة المولّدة للمواضع المشغولة المتميزة هي
$$G(z,q)=\prod_{b\ge0}(1+zq^b),\qquad [z^r]G(z,q)=q^{\binom r2}P_r(q).$$
تنتج المتطابقة الأخيرة بطرح المتتالية الدرجية \(0,1,\ldots,r-1\) من مواضع الخرزات المرتبة تصاعديًا. اشتراط شغل الموضع \(a\) يضرب \(G\) في \(zq^a/(1+zq^a)\). نوسّع هذا العامل بالشكل \(\sum_{j\ge1}(-1)^{j-1}z^jq^{ja}\)، ثم نجمع على \(0\le a<h\) ونستخرج معامل \(z^m\). إذا وضعنا [5]
$$d_j=\binom m2-\binom{m-j}{2}=\frac{j(2m-j-1)}2,$$
فالنتيجة هي
$$B_h(q)=\sum_{j=1}^{m}(-1)^{j-1}q^{-d_j}P_{m-j}(q)\frac{1-q^{jh}}{1-q^j}.$$
نعوّض في \(A_h\) ونستخدم \(q^h(1-q^{jh})/(1-q^h)=\sum_{t=1}^{j}q^{th}\). فنحصل على المتطابقة القابلة للحساب
$$\boxed{H_h(n)=\sum_{j=1}^{m}(-1)^{j-1}\sum_{t=1}^{j}[q^{n+d_j-th}]\frac{P_{m-j}(q)}{1-q^j}.}$$
قد تحتوي التعبيرات المفردة على قوى سالبة، لكن مجموعها المنتهي هو متسلسلة توليد عادية لعدّ الخطافات. يكفي حساب المعاملات ذات الفهارس غير السالبة المعروضة في الصيغة.
نضع \(K=n+\binom m2\)، وقيمته للمدخل المطلوب هي \(11475\). لا يتجاوز أي فهرس مطلوب \(K\). نحتفظ بمصفوفة معاملات واحدة للدالة \(P_r\)، بدءًا من \(P_0=1\). لكل \(r=0,\ldots,m-1\)، نضع \(j=m-r\) ونحسب المعاملات \(Q_s\) للدالة \(P_r(q)/(1-q^j)\) بترتيب تصاعدي:
$$Q_s=[q^s]P_r(q)+Q_{s-j},\qquad Q_u=0\text{ for }u<0.$$
لكل \(h\)، نجمع قيم \(Q_{n+d_j-th}\) مع الإشارة المناسبة. ثم ندخل حجم الجزء \(r+1\) بالتحديث المعتاد ذي الفهارس التصاعدية \(P[s]\leftarrow P[s]+P[s-r-1]\). بعد التحديث الأخير نحصل على \(P[n]=p_m(n)\). نعيد استخدام مصفوفتَي المعاملات طوال الحساب.
المعيار \(M\) عدد أولي، وقد تحقق ذلك باختبار القسمة التجريبية وقت الترجمة. جميع الأساسات \(1,\ldots,300\) غير صفرية بترديد \(M\)، لذا تسمح مبرهنة فيرما الصغرى باختزال كل أس بترديد \(M-1=1234567890\). لذلك تُخزّن مصفوفات المعاملات وأعداد الخطافات بترديد \(M-1\)؛ ولا يلزم أن يكون هذا المعيار نفسه أوليًا. يحسب الرفع الثنائي إلى القوة البسط والمقام بترديد \(M\)، ثم يرفع المقام إلى القوة \(M-2\) لإيجاد معكوسه. تتسع الحسابات باستخدام أعداد صحيحة غير موقّعة من 64 بت بأمان لكل حاصل ضرب لباقيين بترديد \(M\). [6]
زمن التشغيل هو \(O(m(n+m^2)+m^2n+n\log M)\) عند عدّ العمليات الحسابية المعيارية. تكلف تحديثات المعاملات \(O(mK)\)، وتكلف مجاميع الخطافات \(O(m^2n)\)، وتكلف القوى المعيارية \(O(n\log M)\). المساحة الإضافية هي \(O(n+m^2)\).
ينفّذ الخيار الاختياري --self-test الاختبارات الدقيقة التالية: [7]
تحقق حساب مستقل بالحجم الكامل من جميع أعداد الخطافات الثلاثمائة ومن عدد التجزئات. بدأ بالتجزئات غير المقيّدة، ثم طرح التجزئات التي يزيد عدد صفوفها على 150. بعد أخذ المرافق، تمتلك كل تجزئة مستبعدة صفًا أول وحيدًا يزيد طوله على 150، وذيلًا حجمه أقل من 150. يوفّر عدّ خطافات الذيل وخطافات الصف الأول كلٌّ على حدة حسابًا مختلفًا للمجاميع نفسها. تعطي الطريقتان \(p_{150}(300)\equiv221703566\pmod{M-1}\)، وتتفقان في كل عدد من أعداد الخطافات بترديد \(M-1\)، وتنتجان النتيجة النهائية نفسها. تمثّل هذه المقارنة المستقلة تحققًا إضافيًا منفصلًا عن الاختبارات الذاتية المرفقة بالشيفرة.
تحدد المراجع التالية النتائج الأساسية المستخدمة في الاشتقاق. أما التقابل بين مسيرات البطاريق وجداول يونغ، وهوية الأعداد المجمعة للخطافات، وخوارزمية المعاملات المنتهية، فقد اشتُقت صراحةً أعلاه.