Project Euler Problem 412

Solution

Answer: 38788800

Let $a=m-n$.

The shape $L(m,n)$ is the $m\times m$ square with the upper-right $n\times n$ square removed.

If we rotate the diagram by $180^\circ$, the condition

• every entry is smaller than the entry below it and to its left

becomes the standard Young tableau condition

• entries increase to the right and downward.

So $\operatorname{LC}(m,n)$ is exactly the number of standard Young tableaux of the partition

$$\lambda=(\underbrace{m,\dots,m}{a\text{ rows}}, \underbrace{a,\dots,a}{n\text{ rows}}).$$

The total number of cells is

$$|\lambda|=m^2-n^2.$$

Therefore we can use the ordinary hook-length formula:

$$f^\lambda=\frac{(|\lambda|)!}{\prod_{c\in\lambda} h(c)}.$$

---

1. Hook lengths

Split the diagram into three regions.

Let rows and columns start from $1$.

Region A: $1\le i\le a,\ 1\le j\le a$

These cells lie in the upper-left $a\times a$ block.

Their hook lengths are

$$h(i,j)=2m-i-j+1.$$

For fixed $i$,

$$\prod_{j=1}^{a} h(i,j) = \frac{(2m-i)!}{(m+n-i)!}.$$

---

Region B: $1\le i\le a,\ a<j\le m$

These are the top-right rectangular cells.

Their hook lengths are

$$h(i,j)=2m-n-i-j+1.$$

For fixed $i$,

$$\prod_{j=a+1}^{m} h(i,j) = \frac{(m-i)!}{(a-i)!}.$$

---

Region C: $a<i\le m,\ 1\le j\le a$

These are the lower-left cells.

Their hook lengths are again

$$h(i,j)=2m-n-i-j+1.$$

Writing $i=a+k$ ($1\le k\le n$),

$$\prod_{j=1}^{a} h(i,j) = \frac{(m-k)!}{(n-k)!}.$$

---

Combining everything:

$$\boxed{ \operatorname{LC}(m,n) = \frac{(m^2-n^2)!}{ \left( \prod_{i=1}^{a} \frac{(2m-i)!}{(m+n-i)!} \frac{(m-i)!}{(a-i)!} \right) \left( \prod_{k=1}^{n} \frac{(m-k)!}{(n-k)!} \right) } }$$

with $a=m-n$.

---

2. Modular arithmetic trick

We need

$$\operatorname{LC}(10000,5000)\pmod{76543217}.$$

Let

$$p=76543217.$$

It turns out $p$ is prime.

Also,

$$10000^2-5000^2=75,000,000 < p.$$

So every denominator term is invertible modulo $p$.

The only large factorial is

$$75,000,000!.$$

Using Wilson’s theorem:

$$(p-1)! \equiv -1 \pmod p.$$

Hence

$$N! \equiv -\left(\prod_{k=N+1}^{p-1} k\right)^{-1} \pmod p,$$

where

$$N=75,000,000.$$

The tail length is only

$$p-1-N = 1,543,216,$$

which is very manageable.

---

3. Python implementation

MOD = 76543217

m = 10000
n = 5000
a = m - n

# Total number of cells
N = m * m - n * n

# ------------------------------------------------------------
# Compute N! mod MOD using Wilson's theorem
#
# (MOD-1)! = -1 (mod MOD)
#
# Therefore:
# N! = -1 / product(N+1 ... MOD-1)
# ------------------------------------------------------------

tail = 1
for x in range(N + 1, MOD):
    tail = (tail * x) % MOD

num = (-pow(tail, MOD - 2, MOD)) % MOD

# ------------------------------------------------------------
# Precompute factorials up to 2m
# ------------------------------------------------------------

limit = 2 * m

fac = [1] * (limit + 1)
for i in range(1, limit + 1):
    fac[i] = fac[i - 1] * i % MOD

invfac = [1] * (limit + 1)
invfac[limit] = pow(fac[limit], MOD - 2, MOD)

for i in range(limit, 0, -1):
    invfac[i - 1] = invfac[i] * i % MOD

# ------------------------------------------------------------
# Compute hook product denominator
# ------------------------------------------------------------

den = 1

# Region A and Region B
for i in range(1, a + 1):

    # (2m-i)! / (m+n-i)!
    den = den * fac[2 * m - i] % MOD
    den = den * invfac[m + n - i] % MOD

    # (m-i)! / (a-i)!
    den = den * fac[m - i] % MOD
    den = den * invfac[a - i] % MOD

# Region C
for k in range(1, n + 1):

    # (m-k)! / (n-k)!
    den = den * fac[m - k] % MOD
    den = den * invfac[n - k] % MOD

# ------------------------------------------------------------
# Final answer
# ------------------------------------------------------------

answer = num * pow(den, MOD - 2, MOD) % MOD

print(answer)

---

4. Verification on small examples

The program reproduces all given values:

• $\operatorname{LC}(3,0)=42$
• $\operatorname{LC}(5,3)=250250$
• $\operatorname{LC}(6,3)=406029023400$
• $\operatorname{LC}(10,5)\bmod 76543217=61251715$

so the derivation is consistent.

---

5. Final computation

Running the algorithm for $(m,n)=(10000,5000)$ gives

$$\boxed{38788800}.$$

Answer: 38788800