Project Euler 434

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

Project Euler 434

题目

Rigid graphs

Recall that a graph is a collection of vertices and edges connecting the vertices, and that two vertices connected by an edge are called adjacent.

Graphs can be embedded in Euclidean space by associating each vertex with a point in the Euclidean space.

A flexible graph is an embedding of a graph where it is possible to move one or more vertices continuously so that the distance between at least two nonadjacent vertices is altered while the distances between each pair of adjacent vertices is kept constant.

A rigid graph is an embedding of a graph which is not flexible.

Informally, a graph is rigid if by replacing the vertices with fully rotating hinges and the edges with rods that are unbending and inelastic, no parts of the graph can be moved independently from the rest of the graph.

The grid graphs embedded in the Euclidean plane are not rigid, as the following animation demonstrates:

However, one can make them rigid by adding diagonal edges to the cells. For example, for the \(2\times3\) grid graph, there are \(19\) ways to make the graph rigid:

Note that for the purposes of this problem, we do not consider changing the orientation of a diagonal edge or adding both diagonal edges to a cell as a different way of making a grid graph rigid.

Let \(R(m,n)\) be the number of ways to make the \(m \times n\) grid graph rigid.

E.g. \(R(2,3) = 19\) and \(R(5,5) = 23679901\)

Define \(S(N)\) as \(\sum R(i,j)\) for \(1 \le i, j \le N\).

E.g. \(S(5) = 25021721\).

Find \(S(100)\), give your answer modulo \(1000000033\)

解决方案

我们把网格看成铰链+刚性杆系统。若不加斜撑，网格会发生剪切。在任意保持边长的连续变形中：同一列带上的纵向边始终保持平行（记为一类方向）；同一行带上的横向边始终保持平行（另一类方向）。因此可把系统抽象成两组方向节点：\(U=\{c_1,\dots,c_m\}\)：\(m\) 个列方向节点；\(V=\{r_1,\dots,r_n\}\)：\(n\) 个行方向节点。

在单元格 \((x,y)\) 加一条对角线，会把该格从可剪切四边形变为不可剪切三角化结构，从而锁定列方向 \(c_x\) 与行方向 \(r_y\) 的夹角。于是每个单元格是否加斜撑，等价于二分图 \(G=(U,V,E)\) 是否加入边 \((c_x,r_y)\)。总共有 \(mn\) 个位置，因此总方案数为 \(2^{mn}\)。

接下来我们证明刚性 \(\Longleftrightarrow\) 二分图\(G\)连通：

  • 必要性：若二分图不连通，设包含某些 \(U',V'\) 的连通分量与其他分量断开。由于没有跨分量的夹角锁定，可让该分量整体相对其他分量发生剪切变化而不破坏已锁定边长，系统仍可动，不刚性。
  • 充分性：若二分图连通，从任意一个方向节点出发，经“列-行-列-…”路径可把所有方向关系传递锁定。最终所有列方向彼此一致，所有行方向彼此一致，且两组夹角全局固定，只剩整体刚体运动（平移/旋转），不存在内部自由度，因此刚性成立。

所以本题完全等价于：\(R(m,n) =\)左右部大小分别为 \(m,n\)的标号二分图中连通图的个数。

考虑左部和右步顶点：\(U=\{u_1,\dots,u_m\}, V=\{v_1,\dots,v_n\}.\)固定顶点 \(u_1\)，考虑任意二分图中包含 \(u_1\) 的连通分量 \(C\)。设 \(C\) 中有左部 \(k\) 个点（\(1\le k\le m\)）；右部 \(l\) 个点（\(0\le l\le n\)）。

那么这\(2^{nm}\)种放边情况可以这样子描述：对固定 \(k,l\)：从其余左部点里选 \(k-1\) 个，那么有\(\dbinom{m-1}{k-1}\)种选法，从右部点里选 \(l\) 个，那么有\(\dbinom{n}{l}\)种选法；那么在这 \(k+l\) 个点上形成连通二分图：\(R(k,l)\)；且剩余点集 \((m-k,n-l)\) 内部边任意选择，也就有\(2^{(m-k)(n-l)}\)种方法。为保证 \(C\) 就是该连通分量，跨越 \(C\) 与外部的边必须不存在，可见这在上述构造中已隐含。于是所有\(2^{nm}\)种放边情况可以如下描述：

\[ 2^{mn} = \sum_{k=1}^{m}\sum_{l=0}^{n} \binom{m-1}{k-1}\binom{n}{l} R(k,l)2^{(m-k)(n-l)}. \]

把 \((k,l)=(m,n)\) 项移到左边，得到递推：

\[ R(m,n) = 2^{mn} \sum_{\substack{1\le k\le m,0\le l\le n\\(k,l)\ne(m,n)}} \binom{m-1}{k-1}\binom{n}{l} R(k,l)2^{(m-k)(n-l)}. \]

递推会用到 \(l=0\) 的状态，因此需定义：\(R(1,0)=1\)：只有一个顶点，连通；\(R(k,0)=0\)（\(k\neq1\)）：多个孤立点，不连通。然后按照\(R(n,m)\)的定义式即可完成计算。

代码

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
38
39
40
41
42
N = 100
MOD=1000000033

def solve(N):
    C = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        C[i][0] = 1
        for j in range(1, i + 1):
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD

    P = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        for j in range(N + 1):
            P[i][j] = pow(2, i * j, MOD)

    R = [[0] * (N + 1) for _ in range(N + 1)]
    R[1][0] = 1

    ans = 0
    for m in range(1, N + 1):
        for n in range(0, N + 1):
            s = 0
            cm = C[m - 1]
            cn = C[n]
            for k in range(1, m + 1):
                a = cm[k - 1]
                Rk = R[k]
                Pk = P[m - k]
                for l in range(0, n + 1):
                    if k == m and l == n:
                        continue
                    rv = Rk[l]
                    if rv:
                        s = (s + a * cn[l] * rv * Pk[n - l]) % MOD
            R[m][n] = (P[m][n] - s) % MOD
            if n >= 1:
                ans = (ans + R[m][n]) % MOD

    return ans

print(solve(N))