ProjectEuler 434 Rigid graphs - 拼圖

434. Rigid graphs

http://projecteuler.net/problem=434

在圖論裡，圖的定義為由頂點和邊組成的集合。而其中任兩個點若有邊相連，則稱此
兩點相鄰。

圖可以藉由賦予每個頂點坐標使之內嵌於歐氏空間（即直角坐標空間）。

如果給定一圖，存在一種變換可以在不改變每條邊的長度的情況下改變其中非相鄰的
兩點之間的距離，則我們稱此圖具有彈性結構。

反之，若不存在此一變換，則稱其有剛體結構。

以非正式的說法，若將一剛體圖的頂點換成可以自由旋轉的樞紐，邊換成不可彎曲或
伸縮的桿子，則此圖的任意部分均無法獨立於其他部分自由運動。

二維直角方格圖在二維歐式空間皆不為剛體，如同以下動畫所示：

http://projecteuler.net/project/images/p434_rigid.gif

然而，我們可以藉由添加邊來連接一些格子的對角線使此圖成為剛體。

例如，有19種方法可以讓2 ×3的方格圖成為剛體，如下圖所示：

http://projecteuler.net/project/images/p434_rigid23.png

在此一問題中，我們對一個格子添加不同方向的對角線或是加兩條對角線均視為相同。

令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的餘數。

--