Problem 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 2x3 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 × n grid graph rigid.
E.g. R(2,3) = 19 and R(5,5) = 23679901
Define S(N) as ∑R(i,j) for 1 ≤ i, j ≤ N.
E.g. S(5) = 25021721.
Find S(100), give your answer modulo 1000000033
不可弯折图
图是一系列点和连接点的边的集合，由边连接的两个点称为邻接点。
将图的每个顶点和欧氏空间的一个店相对应，总是可以将图投影到欧氏空间中。
我们称一个图为可弯折图，如果其在欧氏空间中的投影中的一个或多个顶点可以连续地改变位置，使得至少两个非邻接的顶点的距离发生变化，而任意两个邻接的顶点的距离保持不变。
相应地，我们称一个图为不可弯折图，如果其不是可弯折图。
一种不太正式的表述是，如果一个图是不可弯折的，那么当我们将图中的顶点换成铰链，将边换成不可弯折且无弹性的木棒，则图的任意部分都不能独立于其它部分发生移动。
方格图在欧氏空间中的投影是可弯折的，如下面的动画所示：
然而，只要在其中一些方格内加上对角线，就可以将它变成不可弯折图。例如，对于2x3的方格图，一共有19种方法把它变为不可弯折图：
在本题中，更换对角线的方向或是同时加上一个方格内的两条对角线不被认为是一种不同的方法。
记R(m,n)是将m × n方格图变为不可弯折图的方法数。
例如，R(2,3) = 19，以及R(5,5) = 23679901
定义S(N)为∑R(i,j)，其中1 ≤ i, j ≤ N。
例如，S(5) = 25021721。
求S(100)，并将答案模1000000033求余。