[矩阵乘法]斐波那契数列IV
2024-09-03 23:46:57
[
矩
阵
乘
法
]
裴
波
拉
契
数
列
I
V
[矩阵乘法]裴波拉契数列IV
[矩阵乘法]裴波拉契数列IV
Description
求数列f[n]=f[n-2]+f[n-1]+n+1的第N项,其中f[1]=1,f[2]:=1.
Input
n(1<n<231-1)
Output
一个数为裴波拉契数列的第n项mod 9973;
Sample Input
10000
Sample Output
4399
题目解析
对于为什么用矩阵乘法来做,详见博客斐波那契数列II
关于递推式略, 详见博客斐波那契数列III,并请独自尝试通过类比来推递推式。
然后可以构造出一个
4
∗
4
4 * 4
4∗4的矩阵
T
T
T
∣
0
1
0
0
1
1
0
0
0
1
1
0
0
1
1
1
∣
\begin{vmatrix} 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 1\\ \end{vmatrix}
∣∣∣∣∣∣∣∣0100111100110001∣∣∣∣∣∣∣∣
Code
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int nt;
const int MOD = 9973;
struct matrix
{
int n, m;
int t[10][10];
}t1, t2, t3;
matrix operator *(matrix t, matrix r)
{
matrix c;
c.n = t.n, c.m = r.m;
for (int i = 1; i <= c.n; ++ i)
for (int j = 1; j <= c.m; ++ j)
c.t[i][j]=0;
for (int k = 1; k <= t.m; ++ k)
for (int i = 1; i <= t.n; ++ i)
for (int j = 1; j <= r.m; ++ j)
c.t[i][j] = (c.t[i][j] + t.t[i][k] * r.t[k][j] % MOD) % MOD;
return c;
}
void rt (int k)
{
if (k == 1)
{
t2 = t1;
return;
}
rt (k / 2);
t2 = t2 * t2;
if (k & 1) t2 = t2 * t1;
}
int main()
{
scanf ("%d", &nt);
if (nt == 1)
{
printf ("1");
return 0;
}
t3.n = 1;
t1.n = t1.m = t3.m = 4;
t1.t[1][1] = 0, t1.t[1][2] = 1, t1.t[1][3] = 0, t1.t[1][4] = 0;
t1.t[2][1] = 1, t1.t[2][2] = 1, t1.t[2][3] = 0, t1.t[2][4] = 0;
t1.t[3][1] = 0, t1.t[3][2] = 1, t1.t[3][3] = 1, t1.t[3][4] = 0;
t1.t[4][1] = 0, t1.t[4][2] = 1, t1.t[4][3] = 1, t1.t[4][4] = 1;
t3.t[1][1] = t3.t[1][2] = t3.t[1][4] = 1; t3.t[1][3] = 3;
rt (nt - 1);
t3 = t3 * t2;
printf ("%d", t3.t[1][1]);
return 0;
}
最新文章
- Android Studio快捷键每日一练(2)
- RHCE实验环境|rhel7-lab
- ListView 里面嵌套 GridView 遇到的问题及其解决方法。
- spider autohome (1)
- Effective Java 57 Use exceptions only for exceptional conditions
- 《C和指针》读书笔记 第3章-数据
- Java中HashMap的数据结构
- jquery的change 事件
- php引入公用部分html出现了一行空白(原创)
- IIs工作原理
- uva 748 Exponentiation 浮点数乘方运算 高精度水题
- FieldInfo.IsSpecialName Property【转】
- Linux - 有效群组(effective group)与初始群组(initial group),groups,newgrp
- vue启动报错
- TypeScript的概要和简介
- AIX动态增加SWAP空间
- 每天一个小程序—0013题(爬图片+正则表达式 or BeautifulSoup)
- Centos7 安装 erlang rabbitmq
- 004_on-my-zsh漂亮的shell
- 使用 ML Pipeline 构建机器学习工作流
热门文章
- redux &; dispatch &; payload
- learning free programming resources form top university of the world
- 「NGK每日快讯」12.31日NGK第58期官方快讯!
- 010_HTML5
- (十) 数据库查询处理之排序(sorting)
- Dokcer中Mysql的数据导入导出
- IDEA中引用不到HttpServlet的解决方案
- css3自动换行排列
- 一文让你对js的原型与原型链不再害怕、迷惑
- Azure Synapse Analytics Serverless