P2106 Sam 数

本题是经典矩阵乘法优化 DP 题目。

题目描述

小 Z 最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。

Sam 数具有以下特征：相邻两位的数字之差不超过 $2$ 。

小 Z 还将 Sam 数按位数进行了分类，他将一个 $k$ 位 Sam 数称之为 $k$ 阶 Sam 数。

但不幸的是小 Z 发现他数不清第 $k$ 阶的 Sam 数一共有多少个，这个时候机智的他想到了向你求助。

答案对 $10^{9} + 7$ 取模。

输入共一行一个整数 $k$ ，含义见题面。

一行一个整数 $a n s$ ，表示 $k$ 阶的 Sam 数的个数。

答案对 $10^{9} + 7$ 取模。

对于 $30 %$ 的数据， $1 \leq k \leq 10^{6}$ 。

对于 $60 %$ 的数据， $1 \leq k \leq 10^{12}$ 。

对于 $100 %$ 的数据， $1 \leq k \leq 10^{18}$ 。

定义 $f (i, j)$ 为第 $i$ 位是 $j$ 时的方案数，显然有

f (i, j) = \sum_{k = j - 2}^{j + 2} f (i - 1, k)

时间复杂度为 $O (n)$ ，无法通过本题。

构造矩阵：

A = [\begin{matrix} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}]

D = [\begin{matrix} 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{matrix}]

显然矩阵 $A D^{k - 1}$ 的各项之和即为所求。