Fibonacci(模板)【矩阵快速幂】
Fibonacci
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20989 Accepted: 14381 Description
In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is
.
Given an integer n, your goal is to compute the last 4 digits of Fn.
Input
The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.
Output
For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).
Sample Input
0
9
999999999
1000000000
-1Sample Output
0
34
626
6875Hint
As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by
.
Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:
.
思路:
由于输入的n数值特别大,所以如果先打表然后随机访问再输出肯定不行 就用到了矩阵快速幂
(补充)矩阵相乘:
矩阵AB的第i行第j列为 A矩阵第i行与B矩阵第j列对应元素分别相乘再求和
不用字母直接上例子:
已知:(n)=f(n-1)+f(n-2) f(n-1)=f(n-1)+0*f(n-2)
可以构造下面的递推式:
可以化简为:
根据矩阵快速幂就可以 先求常数矩阵的(n-1)次幂 然后输出a[0][0] 即可:
a[0][0]表示的是 f(n) 但要注意考虑当n=0是无法求出 f(-1) 所以要特殊考虑n=0的情况
AC代码:
(通过结构体定义数组方便传参) 感谢@鸡冠花12138
#include<stdio.h>
#include<string.h>
const int mod=1e4;
struct node{
int a[5][5];
};
node mat_mul(node x,node y) //该函数返回值为node型 作用为计算两个矩阵x和y的乘积
{
node res;
memset(res.a,0,sizeof(res.a));
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
res.a[i][j]=0;
for(int k=0;k<2;k++){
res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
}
}
}
return res;
}
node mat_qpow(int n) //返回值仍然是node型 作用是求常数矩阵的n次幂
{
node res,c;
c.a[0][0]=1; c.a[0][1]=1; //c.a表示的是常数矩阵
c.a[1][0]=1; c.a[1][1]=0;
memset(res.a,0,sizeof(res.a));
for(int i=0;i<2;i++){
res.a[i][i]=1;
}
while(n){ //快速幂
if(n%2){
res=mat_mul(res,c);
}
c=mat_mul(c,c);
n/=2;
}
printf("%d\n",res.a[0][0]);
}
int main()
{
int n;
while(~scanf("%d",&n)&&n!=-1){
if(n==0){ //特殊考虑n=0的情况
printf("0\n");
}
else{
mat_qpow(n-1);
}
}
return 0;
}
最新文章
- VS快捷键总结(包括ReSharper)
- S2结业考试的第一次测验
- JS-Math对象
- [MySQL] SQL_ERROR 1032解决办法
- IOS NSInvocation用法简介
- [Excel操作]Microsoft Office Excel 不能访问文件
- open Session In View模式
- json 去空值与缩进
- Windows 下安装 Oracle 12c 教程
- ARM处理器:开放者的逆袭
- VB 读取列表文件名
- BZOJ4482[Jsoi2015]套娃——贪心+set
- 关于使用summernote编辑器提示内容无法汉化临时解决办法
- JustOj 1936: 小明A+B
- How to Change MAC Address on Ubuntu
- unity, 模拟退后台
- Maven 项目管理从未如此通畅
- Android SharedPreferences的应用
- C语言 &#183; 最大最小公倍数
- FlowPortal-BPM——移动手机端配置与IIS发布
热门文章
- hdu6090 菊花图
- 【NLP】老司机带你入门自然语言处理
- c# 优化代码的一些规则——const 和 readonly[二]
- Mysql数值类型,小数点后保留两个零
- [PHP学习教程 - 系统]004.通过ini_set()来设置系统属性(ini_set Method)
- 【图机器学习】cs224w Lecture 15 - 网络演变
- Ondemand和Interactive gonernor工作逻辑简述
- Java实现 蓝桥杯 历届试题 小计算器
- Java实现 蓝桥杯VIP 算法提高 字符串跳步
- Java实现 LeetCode 78 子集