题目链接：P2106 Sam 数 - 洛谷。
本题是经典矩阵乘法优化 DP 题目。
题目描述
小 Z 最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。
Sam 数具有以下特征：相邻两位的数字之差不超过 $2$。
小 Z 还将 Sam 数按位数进行了分类，他将一个 $k$ 位 Sam 数称之为 $k$ 阶 Sam 数。
但不幸的是小 Z 发现他数不清第 $k$ 阶的 Sam 数一共有多少个，这个时候机智的他想到了向你求助。
答案对 $10^9+7$ 取模。
输入格式
输入共一行一个整数 $k$，含义见题面。
输出格式
一行一个整数 $ans$，表示 $k$ 阶的 Sam 数的个数。
答案对 $10^9+7$ 取模。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
对于 $30%$ 的数据，$1\le k\le10^6$。
对于 $60%$ 的数据，$1\le k\le 10^{12}$。
对于 $100%$ 的数据，$1\le k\le10^{18}$。
题解
递推方程
定义 $f(i,j)$ 为第 $i$ 位是 $j$ 时的方案数，显然有 $$ f(i,j) = \sum_{k=j-2}^{j+2}f(i-1,k) $$ 时间复杂度为 $O(n)$，无法通过本题。
矩阵快速幂加速递推
构造矩阵： $$ \mathbf{A} = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\ \end{bmatrix} $$
$$ \mathbf{D} = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\ \end{bmatrix} $$
显然矩阵 $AD^{k-1}$ 的各项之和即为所求。
