Detailed mathematical approach

Problem Summary

We count monotone lattice paths from \((0,0)\) to \((n,n)\), where each step is either one unit right or one unit up. A path is admissible if it never visits any forbidden grid point.

In the implementations, the forbidden points are exactly the interior square-coordinate points

$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$

The final answer is the number of admissible paths modulo \(10^9+7\).

Mathematical Approach

Step 1: Count paths between two comparable points

If \((x_1,y_1)\) and \((x_2,y_2)\) satisfy \(x_1 \le x_2\) and \(y_1 \le y_2\), then any monotone path from the first point to the second point must use exactly \(x_2-x_1\) right moves and \(y_2-y_1\) up moves. Hence the number of such paths is

$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}.$

In particular, without any forbidden points, the total number of paths from \((0,0)\) to \((n,n)\) is

$\binom{2n}{n}.$

Step 2: Describe the forbidden set

Only points with both coordinates at most \(n\) can matter, so it is enough to enumerate \(a,b \le \lfloor \sqrt{n}\rfloor\). The condition \(a^2+b^2=c^2\) means that \((a,b,c)\) forms a Pythagorean triple, and each such pair produces a forbidden point \((a^2,b^2)\).

After sorting the forbidden points lexicographically, write them as

$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m).$

This ordering is compatible with monotone movement: if a path can go from \(P_j\) to \(P_i\), then necessarily \(x_j \le x_i\) and \(y_j \le y_i\), which implies \(j \lt i\) after lexicographic sorting.

Step 3: Inclusion-exclusion by the first forbidden point

For each forbidden point \(P_i\), let \(B_i\) be the number of monotone paths from \((0,0)\) to \(P_i\) whose first forbidden point is exactly \(P_i\). Start from the unrestricted count

$\binom{x_i+y_i}{x_i}.$

If a path reaches an earlier forbidden point \(P_j\) first and later continues to \(P_i\), then the number of such paths is

$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j},$

provided \(x_j \le x_i\) and \(y_j \le y_i\). Therefore

$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}.$

This dynamic program is a topological inclusion-exclusion on the partial order induced by coordinate-wise comparison.

Every inadmissible path from \((0,0)\) to \((n,n)\) has a unique first forbidden point, so after all \(B_i\) are known we subtract the bad paths by that first hit:

$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}.$

This is exactly the recurrence used in the implementations.

Step 4: Worked examples from the checkpoints

For \(n=5\), there are no forbidden points because the only possible square coordinates are \(1\) and \(4\), and none of the sums \(1+1\), \(1+4\), \(4+1\), \(4+4\) is a square. Hence

$A(5)=\binom{10}{5}=252.$

For \(n=16\), the forbidden points are \((9,16)\) and \((16,9)\), coming from \(3^2+4^2=5^2\) and \(4^2+3^2=5^2\). The unrestricted count is

$\binom{32}{16}=601080390.$

Each forbidden point receives

$\binom{9+16}{9}=\binom{25}{9}=2042975$

paths from the origin. Neither forbidden point dominates the other, so no path can pass through both. Therefore

$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$

which matches the checkpoint value used by the implementations.

Step 5: Fast modular binomial coefficients

All binomial coefficients are evaluated modulo the prime

$M=10^9+7.$

The implementations precompute factorials and inverse factorials up to \(2n\), so every combination query becomes

$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}.$

The inverse factorials are derived using Fermat's little theorem:

$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$

After this preprocessing, each path-count query is \(O(1)\).

How the Code Works

The C++, Python, and Java implementations follow the same structure. They first build a fast square-membership structure up to \(2n\), enumerate every forbidden point \((a^2,b^2)\) inside the \(n \times n\) grid, sort the resulting list, and remove duplicates. Next they precompute factorials and inverse factorials so that any binomial coefficient needed by the path formulas can be answered in constant time modulo \(10^9+7\).

Once those tables are ready, the implementation scans the forbidden points in sorted order and computes the number of paths whose first forbidden point is each obstacle. The final admissible count is obtained by subtracting all bad-path contributions from the unrestricted total \(\binom{2n}{n}\).

Complexity Analysis

Let \(m\) be the number of forbidden points. Enumerating candidate square pairs takes \(O(n)\) time because both \(a\) and \(b\) range up to \(\lfloor \sqrt{n}\rfloor\). Precomputing factorials and inverse factorials up to \(2n\) also takes \(O(n)\) time and \(O(n)\) memory. The dynamic program compares each forbidden point with all earlier ones, so it costs \(O(m^2)\) time and \(O(m)\) additional memory. Overall, the algorithm runs in \(O(n+m^2)\) time and uses \(O(n+m)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=408
2. Lattice path counting: Wikipedia — Lattice path
3. Binomial coefficients: Wikipedia — Binomial coefficient
4. Fermat's little theorem: Wikipedia — Fermat's little theorem
5. Pythagorean triples: Wikipedia — Pythagorean triple