先写出四行三列的格子，其中定义状态：
0    1    2    3    ...   14    15
X    XX   X    XX         X     XX
X    X    XX   XX         XX    XX
X    X    X    X          XX    XX
X    X    X    X          XX    XX
为k-1的状态。

再定义：
 0     1     2     3     ...   14     15
XX    XXX   XX    XXX         XX     XXX
XX    XX    XXX   XXX         XXX    XXX
XX    XX    XX    XX          XXX    XXX
XX    XX    XX    XX          XXX    XXX
为k的状态，如果令 k的状态下 铺的方式第三列一定要为第二列砖头横向的延伸，例如3：
011
022
00
00
可以看出k-1到k状态的转换，
其中：
k     k-1
0     0 3 9 12 15
1     2 8 14
2     1 13
3     0 12
4     8 11
5     10
6     9
7     8
8     1 4 7
9     0 6
10    5 4
11    4
12    0 3
13    2
14    1
15    0
其中，状态k状态的0 只有状态k-1的 0 3 6 9 12 15 可以得到。
所以得到矩阵：
k-1\k 0  3  6  9 12 15
0     1  1  0  1  1  1
3     1  0  0  0  1  0
6     0  0  0  1  0  0
9     1  0  1  0  0  0
12    1  1  0  0  0  0
15    1  0  0  0  0  0
因为k-1到k的状态为上述矩阵（一步），如果计算从状态0到n的结果（n步），则是矩阵的n次方对应的[0][0]值（模m前结果）。
如果tle了，说明要递归一半一半的乘。Good luck.

• 谢谢~~ 非常感谢 ^_^ (0) arena_zp 2008-07-15 17:01:28
• Re:你的矩阵似乎写反了~~ (1115) ecjtuxsyuan 2008-10-07 12:40:22