POJ 3070 Fibonacci
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
-1
Sample Output
0
34
626
6875 矩阵快速幂入门题,构造矩阵[fn,fn-1]*[1,1]在自己敲一遍模板就行了。
[0 ,0 ] [1,0]
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long int LL;
using namespace std; int n,mod=; struct Matrix
{
int a[][];
Matrix(){memset(a,,sizeof(a));}
Matrix operator* (const Matrix &p)
{
Matrix res;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
for(int k=;k<;k++)
{
res.a[i][j]+=(a[i][k]*p.a[k][j]%mod);
}
res.a[i][j]%=mod;
}
}
return res;
}
}ans,base; Matrix quick_pow(Matrix base,int k)
{
Matrix res;
for(int i=;i<;i++)
{
res.a[i][i]=;
}
while(k)
{
if(k&) res=res*base;
base=base*base;
k>>=;
}
return res;
} void init_Matrix()
{
ans.a[][]=;
ans.a[][]=;
ans.a[][]=;
ans.a[][]=;
base.a[][]=;
base.a[][]=;
base.a[][]=;
base.a[][]=;
} int main()
{
while(scanf("%d",&n)&&n!=-)
{
init_Matrix();
if(n==) printf("0\n");
else if(n==) printf("1\n");
else
{
ans=ans*quick_pow(base,n-);
printf("%d\n",ans.a[][]);
}
}
return ;
}
最新文章
- Tcpdump命令行 与 GUI Wireshark
- Boost 1.61.0 Library Documentation
- RHEL6.4 postfix+dovecot搭建邮件服务器
- JS总结之二:DOM对象控制HTML
- Java 异常Exception e中e的getMessage()和toString()以及 e.printStackTrace();方法的区别
- 后端分布式系列:分布式存储-HDFS NameNode 设计实现解析
- 寒假作业pta1
- Go语言环境安装&;搭建(Win)
- Gpload安装手册(Linux版本)
- Linux - 快速进入目录的方法
- 【30集iCore3_ADP出厂源代码(ARM部分)讲解视频】30-7底层驱动之滴嗒定时器
- DevExpress使用方法GridControl总结
- 反向路径过滤——reverse path filter
- Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined) D. Artsem and Saunders 数学 构造
- 将 nginx 安装成 windows 的方法
- datetime 模块
- java几个经典的算法题目----------二维矩阵算法
- php中var_dump()函数
- Redis常用类型数据操作
- stm8 全局变量定义 声明