EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

P2106 Sam 数

题目链接:P2106 Sam 数 - 洛谷

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

题目描述

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

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

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

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

答案对 109+7 取模。

输入格式

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

输出格式

一行一个整数 ans,表示 k 阶的 Sam 数的个数。

答案对 109+7 取模。

输入输出样例 #1

输入 #1

1
4

输出 #1

1
867

说明/提示

对于 30% 的数据,1k106

对于 60% 的数据,1k1012

对于 100% 的数据,1k1018

题解

递推方程

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

f(i,j)=k=j2j+2f(i1,k)

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

矩阵快速幂加速递推

构造矩阵:

A=[011111111]D=[1110000000111100000011111000000111110000001111100000011111000000111110000001111100000011110000000111]

显然矩阵 ADk1 的各项之和即为所求。