题目链接:P2106 Sam 数 - 洛谷。
本题是经典矩阵乘法优化 DP 题目。
题目描述
小 Z 最近发现了一种非常有趣的数,他将这种数称之为 Sam 数。
Sam 数具有以下特征:相邻两位的数字之差不超过
小 Z 还将 Sam 数按位数进行了分类,他将一个
但不幸的是小 Z 发现他数不清第
答案对
输入格式
输入共一行一个整数
输出格式
一行一个整数
答案对
输入输出样例 #1
输入 #1
1 |
|
输出 #1
1 |
|
说明/提示
对于
对于
对于
题解
递推方程
定义
时间复杂度为
矩阵快速幂加速递推
构造矩阵:
显然矩阵