Problem 312
Cyclic paths on Sierpiński graphs
A Sierpiński graph of order-1 (S1) is an equilateral triangle.
Sn+1 is obtained from Sn by positioning three copies of Sn so that every pair of copies has one common corner.
Let C(n) be the number of cycles that pass exactly once through all the vertices of Sn.
For example, C(3) = 8 because eight such cycles can be drawn on S3, as shown below:
It can also be verified that :
C(1) = C(2) = 1
C(5) = 71328803586048
C(10 000) mod 108 = 37652224
C(10 000) mod 138 = 617720485
Find C(C(C(10 000))) mod 138.
谢尔宾斯基图的回路
1阶谢尔宾斯基图(S1)是一个等边三角形。
将三个Sn摆在一起,使得任意两个Sn都共用一个角,就得到了Sn+1。
记C(n)是经过Sn中所有顶点恰好一次的回路的数目。
例如,C(3) = 8,因为在S3上恰好可以画出8条这样的回路,如下图所示:
同样可以验证:
C(1) = C(2) = 1
C(5) = 71328803586048
C(10 000) mod 108 = 37652224
C(10 000) mod 138 = 617720485
求C(C(C(10 000))) mod 138。