Detailed mathematical approach

Problem Summary

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]

Mathematical Approach

1. Legal marches are standard Young tableaux

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.

2. Aggregate hook multiplicities

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]

3. Encode hooks by occupied and empty positions

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)\).

4. Extract a finite coefficient formula

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.

How the Code Works

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]

Complexity and Verification

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]

• The published examples: \(F(2,4)=6\), \(F(3,6)=180000\), and \(F(5,10)\equiv411456133\pmod M\).
• Direct legal-move enumeration for every \(1\le m\le16\) and \(0\le n\le16\), comparing endpoint counts, explicit cell-hook counts, and the product of endpoint path counts.
• The target invariant \(\sum_{h=1}^{300}H_h(300)\equiv300p_{150}(300)\pmod{M-1}\), since each endpoint shape has exactly 300 cells.

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.

Footnotes and References

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.

1. Project Euler 1010 — March of the Penguins. The official statement defines the legal moves, the endpoint product, and the three published checkpoints. These examples test the implementation without disclosing the requested final value.
2. The Hook Graphs of the Symmetric Group. J. S. Frame, G. de B. Robinson and R. M. Thrall, Canadian Journal of Mathematics 6 (1954), 316–324; §2, Theorem 1, equation (2.4). The hook-length formula supplies the number of tableaux of each shape. Section 1 above applies it to legal marches.
3. Combinatorics and Representations of Finite Groups. Jørn B. Olsson, Universität Essen lecture notes, volume 20 (1993), Chapter 1: Partitions, hooks, β-sets. This is the background for encoding a hook by an occupied position and a lower gap. Section 3 above develops the upward/downward counting argument for this problem.
4. The Theory of Partitions — Chapter 1. George E. Andrews, The Theory of Partitions, Chapter 1, especially §§1.2–1.3. Product generating functions and conjugate diagrams explain the coefficients of P_r and the equivalence between a bound on row count and a bound on part size. These are used in Section 2.
5. The Theory of Partitions — Chapter 2. George E. Andrews, The Theory of Partitions, Chapter 2, especially §2.2. Series–product identities provide the q-series background. Section 4 proves the specific staircase identity and expands the occupied-position factor to obtain the finite alternating coefficient sum used by the code.
6. A Computational Introduction to Number Theory and Algebra. Victor Shoup, A Computational Introduction to Number Theory and Algebra, second edition, §§2.7 and 3.4. Fermat's theorem and repeated squaring justify exponent reduction and modular inversion. Here primality is checked separately, and every hook base is nonzero modulo M; M−1 need not be prime.
7. C++ — Euler1010.cpp. The linked immutable C++ revision contains the rolling coefficient arrays, modular arithmetic, and --self-test checks. It is the implementation record for this article. The separate full-size comparison described above is additional validation, not a test packaged in that source file.