Sam 數（矩陣乘法）

Sam 數

Sam 數是指相鄰的兩位數字相差不超過 2 的數。求長度為 n 的 Sam 數有多少個。輸出對 1000000007 取餘後的結果。 n <= 10^18 。

分析

首先，遞推式很明顯：

用 f(i, j) 表示第 j 位為 i 時總的個數（先不考慮各種特殊情況），則

f(i, j) = f(i-2, j-1) + f(i-1, j-1) + f(i, j-1) + f(i+1, j-1) + f(i+2, j-1)

我們考慮這樣一個矩陣 A ：

[ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]

這個 1*10 矩陣表示當第一位為 i 且一共隻有 1 位時的方案數。

考慮另一個矩陣 B ：