Project Euler 270

发表于 更新于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

Project Euler 270

题目

Cutting Squares

A square piece of paper with integer dimensions \(N\times 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\times N\) square. For example, \(C(1)=2\) and \(C(2)=30\) (shown below).

What is \(C(30) \bmod 10^8\) ?

解决方案

我们可以看到，由于图形是凸的，不相交的切割会把区域分裂成若干子区域；一旦选定一条切割，它把问题分成两侧，两侧可切方式相互独立，因此总数可乘、可做 DP。

在递归分裂中只会出现三种需要继续计数的标准形状。我们下面都规定：只有来自原正方形边界的那几条边上的整点可以作为切割端点；而由之前切割生成的“内部边”不允许再作为端点。

考虑一个直角三角形，其两条直角边分别是长度为\(i\)与\(j\)的轴对齐边界段（端点整点），斜边是一条内部边（不可作为端点）。这时，令\(T(i,j)\)表示在该三角形内，遵守规则继续切割直到极大时的切割方式数。

由于切割端点只能落在两条直角边上，因此每条切割都连接“这两条边”。不相交约束等价于一种单调配对结构，也就是说我们有如图所示的两种选择：

从而得到递推：

\[ T(i,j)= \left\{ \begin{aligned} &1 && \text{if } i=1 \text{ or } j=1\\ &T(i-1,j)+T(i,j-1) && \text{else} \end{aligned} \right. \]

也就是说，有经典的递推：\(T(i,j)=\dbinom{i+j-2}{i-1}\)。

现在，我们考虑一个凸四边形（直角梯形），其中一条边是长度为\(n\)的“固定外边”（可理解为正方形某条完整边），另外与它相邻的两条外边分别是长度为\(i\)与\(j\)的两段边界线段（均轴对齐），第四条边为内部边（不可作为端点）。令\(Q(i,j)\)表示在该梯形内切到极大的方式数。

在梯形\(Q(i,j)\)中，可作为端点的边共有三条：长度为\(i\)的上段、长度为\(j\)的下段、以及长度为\(n\)的固定边。极大且不交叉意味着：来自上段的切割在固定边上的落点整体偏上，来自下段的整体偏下，因此固定边上存在一个“分界高度”。

把这个分界点在固定边上的位置记为\(b\)，其中\(1\le b\le n-1\)，则会分裂出两个互不影响的三角形子问题：

  • 上侧贡献为\(T(i,b)\)；
  • 下侧贡献为\(T(j,n-b)\)。

对所有\(b\)求和得到“真正发生分界”的贡献；此外还要加入“最靠边的一个单位段不参与切割”的退化累计，对应\(Q(i-1,j)\)与\(Q(i,j-1)\)。于是我们有如下图所示的选择：

因此得到：

\[ Q(i,j)= \left\{ \begin{aligned} &Q(j,i) && \text{if } i>j\\ &T(j,n) && \text{if } i=0\\ &Q(i-1,j)+Q(i,j-1)+\sum_{b=1}^{n-1} T(i,b)T(j,n-b) && \text{else} \end{aligned}\right. \]

现在，考虑一个凸五边形，边界上有三个相邻的直角顶点，并且同样包含一条长度为\(n\)的固定外边；在固定外边的两端附近分别露出长度为\(i\)、\(j\)的两段轴对齐外边；其余一条边为内部边（不可作为端点）。令\(P(i,j)\)表示在该五边形内切到极大的方式数。

由于五边形比梯形多一个拐点，因此沿固定边选分界点时，分裂会出现两类组合：

  • 一侧是三角形、另一侧是梯形：\(T(i,d)\cdot Q(n-d,j)\)；
  • 或反过来：\(Q(i,e)\cdot T(n-e,j)\)。

还存在一个对称特例，使两侧都直接是三角形：\(T(i,n)\cdot T(j,n)\)。

同样需要加入退化累计\(P(i-1,j)\)与\(P(i,j-1)\)，以及当\(i=0\)时退化为梯形\(Q(j,n)\)。于是我们有如下图所示的选择：

因此得到：

\[ P(i,j)= \left\{ \begin{aligned} &P(j,i) && \text{if } i>j\\ &Q(j,n) && \text{if } i=0\\ & P(i-1,j)+P(i,j-1) +\sum_{d=1}^{n-1} T(i,d)Q(n-d,j) +T(i,n)T(j,n) +\sum_{e=1}^{n-1} Q(i,e)T(n-e,j) && \text{else} \end{aligned} \right. \]

最后，我们将各子问题组合得到原问题\(C(n)\)。

把正方形的极大切割分两类：

  • 存在一条切割以原点为端点；
  • 不存在任何切割使用原点。

对应的所有切割方式如下图所示：

最终可写成（对\(n\ge 2\)）：

\[ C(n)=T(n-1,n)T(n,n)+\sum_{i=1}^{n-1} T(n-1,i)Q(n-i,n)+P(n-1,n-1)+\sum_{i=1}^{n-1} Q(n-1,i)T(n-i,n) \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
N = 30
def solve(N):
    if N == 1:
        return 2
    mod = 10 ** 8
    T = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    Q = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    P = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if i == 1 or j == 1:
                T[i][j] = 1
            else:
                T[i][j] = (T[i - 1][j] + T[i][j - 1]) % mod
    for i in range(N + 1):
        for j in range(N + 1):
            if i > j:
                Q[i][j] = Q[j][i]
            elif i == 0:
                Q[i][j] = T[j][N]
            else:
                Q[i][j] = (Q[i - 1][j] + Q[i][j - 1] + sum(T[i][b] * T[j][N - b] for b in range(1, N))) % mod
    for i in range(N + 1):
        for j in range(N + 1):
            if i > j:
                P[i][j] = P[j][i]
            elif i == 0:
                P[i][j] = Q[j][N]
            else:
                P[i][j] = (P[i - 1][j] + P[i][j - 1] + sum(T[i][d] * Q[N - d][j] for d in range(1, N)) + T[i][N] * T[j][
                    N] +sum(Q[i][e] * T[N - e][j] for e in range(1, N))) % mod
    ans = (T[N - 1][N] * T[N][N] + sum(T[N - 1][i] * Q[N - i][N] for i in range(1, N)) + P[N - 1][N - 1] + sum(
        Q[N - 1][i] * T[N - i][N] for i in range(1, N))) % mod
    return ans
print(solve(N))
for n in range(1,8):
    print(solve(n))