Polygon Partitions
Time limit2sMemory limit128 MB
Count noncrossing dissections of a regular N-gon into all triangles or all quadrilaterals, modulo 1e9, using Catalan-like combinatorics.
- Level
Medium5 of 10
- Topics
- Combinatorics, Dynamic programming, Math
- Solved
- No attempts yet
Problem
Given a regular N-gon, count two kinds of noncrossing dissections: dissections using only triangles and dissections using only quadrilaterals.
Every added segment must connect two vertices, and no two added segments may cross. Cases that differ only by rotation or reflection are still counted as different.
Input
The first line contains an integer N.
- 3 <= N <= 1,000
Because the answers can be large, output each answer modulo 1,000,000,000.
Output
Print the number of dissections using only triangles on the first line. Print the number of dissections using only quadrilaterals on the second line.