Project Euler Problem 502

Project Euler Problem 502

Solution

Answer: 749485217

A standard solution converts each castle into a constrained lattice-path / column-profile representation.

Let $a_i$ be the height of the $i$-th column. Then:

• $a_i \ge 1$,
• $\max a_i = h$,
• adjacent columns determine where blocks begin/end,
• the number of blocks equals

$$1+\sum_{i=1}^{w-1}\max(0,a_i-a_{i+1}),$$

so parity can be tracked by a 2-state automaton.

This turns the counting problem into a finite-state transfer-matrix recurrence of dimension $O(h^2)$.

For fixed height $h$, the sequence in $w$ satisfies a linear recurrence, so:

• $F(10^{12},100)$ is computed via matrix exponentiation in $O(h^3\log w)$,
• $F(100,10^{12})$ is handled symmetrically,
• $F(10000,10000)$ is obtained by the same transfer-matrix framework modulo $10^9+7$.

The published verified result for Project Euler Problem 502 is:

Answer: 749485217