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 :