Detailed mathematical approach

Problem Summary

Take all lattice points on the boundary of an \(N\times N\) square and list them in cyclic order. These points form a polygon with

$m=4N$

vertices. The problem asks for the number of maximal non-crossing cut systems allowed by the square-cutting rules, with the final result reported modulo \(10^8\).

Mathematical Approach

1. Boundary Points Become a Polygon

The code explicitly builds the boundary in clockwise order:

1. bottom side from \((0,0)\) to \((N,0)\),

2. right side from \((N,1)\) to \((N,N)\),

3. top side from \((N-1,N)\) to \((0,N)\),

4. left side from \((0,N-1)\) to \((0,1)\).

This gives exactly \(4N\) distinct boundary lattice points. Joining consecutive points in that cyclic order produces a simple polygon.

2. Which Chords Are Allowed?

Two vertices may always be connected if they are adjacent on the polygon boundary. Those are just polygon edges.

For non-adjacent vertices, the code uses a geometric rule:

1. if both endpoints lie on the same side of the square and are not adjacent, the chord is forbidden,

2. otherwise the chord is allowed.

So a long segment sliding along one square side is illegal, while a segment connecting different square sides is legal.

3. Why Maximal Non-Crossing Cuts Become Triangulations

Once all legal cuts are viewed as non-crossing chords of the boundary polygon, a maximal family of such chords decomposes the polygon into faces. If any face had more than three sides, one more non-crossing legal chord could still be inserted inside that face, contradicting maximality.

Therefore every maximal non-crossing admissible cut system is exactly a triangulation of the boundary polygon using only allowed diagonals.

This is the key reduction: the original cutting problem becomes a polygon-triangulation count with a forbidden-diagonal mask.

4. Interval DP Recurrence

Let \(dp[i][j]\) be the number of valid triangulations of the chain of vertices

$v_i,v_{i+1},\dots,v_j,$

where indices are taken in the linear order of the opened polygon. If the closing edge \((i,j)\) is forbidden, then

$dp[i][j]=0.$

Otherwise we choose the third vertex \(k\) of the triangle adjacent to edge \((i,j)\). This splits the region into two smaller subpolygons, giving

$dp[i][j]=\sum_{k=i+1}^{j-1} dp[i][k]\;dp[k][j]\pmod{10^8}.$

This is the standard Catalan-style triangulation recurrence, except that forbidden diagonals force many subproblems to be zero.

5. Base Cases

If \(j=i+1\), the chain contains only one polygon edge and no area to triangulate, so

$dp[i][i+1]=1.$

This is the neutral multiplicative base that makes the recurrence work for larger intervals.

6. Small Validation Examples

The program contains four exact checks:

$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$

The case \(N=1\) is especially instructive. The boundary polygon is just a square, and both diagonals connect different square sides, so both are allowed. A square has exactly two triangulations, which explains \(C(1)=2\).

The larger values \(30,604,12168\) verify that the admissibility mask and the interval DP agree with the intended geometry for nontrivial boundary sizes.

7. Why the Threading Is Safe

The DP is filled by interval length. When computing all states with fixed length \(\ell=j-i\), every transition only reads states of smaller lengths. Therefore two states of the same length never depend on one another.

This is why the code can split all intervals of a fixed length across multiple threads without race conditions on the mathematical data dependency graph.

How the Code Works

build_boundary(n) creates the \(4N\) polygon vertices.

same_side(a,b,n) checks whether two vertices lie on the same physical side of the square. Using that, the code fills an allowed matrix for every pair of vertices.

count_triangulations(n, threads) runs the interval DP modulo

$M=10^8.$

It computes short intervals first, then longer ones, and finally returns dp[0][m-1], the number of admissible triangulations of the full polygon.

The command-line interface supports -n N, -t THREADS, and --no-validate.

Complexity Analysis

There are \(O(m^2)\) intervals with \(m=4N\), and each interval tries \(O(m)\) split points, so the runtime is

$O(m^3)=O(N^3).$

The DP table and admissibility matrix each use \(O(m^2)=O(N^2)\) memory.

Further Reading

1. Problem page: https://projecteuler.net/problem=270
2. Polygon triangulation DP: https://en.wikipedia.org/wiki/Polygon_triangulation
3. Catalan recurrence context: https://en.wikipedia.org/wiki/Catalan_number