Problem 270

Problem 270

Cutting Squares

A square piece of paper with integer dimensions N×N is placed with a corner at the origin and two of its sides along the x- and y-axes. Then, we cut it up respecting the following rules:

  • We only make straight cuts between two points lying on different sides of the square, and having integer coordinates.
  • Two cuts cannot cross, but several cuts can meet at the same border point.
  • Proceed until no more legal cuts can be made.

Counting any reflections or rotations as distinct, we call C(N) the number of ways to cut an N×N square. For example, C(1) = 2 and C(2) = 30 (shown below).

What is C(30) mod 108 ?



  • 我们只进行这样的切割:从正方形不同的两条边上选择两个坐标为整数的点,并沿着两点的连线切割。
  • 两次切割不能相交,但多次切割可以经过边上的同一个点。
  • 一直切割下去,直到不存在合法的切割为止。

如果翻转或旋转后相同的切割方法视为不同,我们记切割一个N×N方块的方法数记为C(N)。举例而言,C(1) = 2,而C(2) = 30(如下图所示)。

C(30) mod 108是多少?