(矩阵快速幂) Fibonacci -- poj -- 3070
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 11236 | Accepted: 7991 |
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
Hint
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:
.
代码:
#include<stdio.h>
#include<string.h>
#define MOD 10000
struct node
{
int m[][];
}a, b; node cheng(node x, node y)
{
int i, j, k;
node c; for(i=; i<; i++)
for(j=; j<; j++)
{
c.m[i][j] = ;
for(k=; k<; k++)
c.m[i][j] = (c.m[i][j] + x.m[i][k]*y.m[k][j])%MOD;
} return c;
} int Fast_MOD(int n)
{
a.m[][] = a.m[][] = a.m[][] = ;
a.m[][] = ; b.m[][] = b.m[][] = ; /// b 初始化为单位矩阵
b.m[][] = b.m[][] = ; while(n)
{
if(n&) /// n是奇数
b = cheng(b, a);
a = cheng(a, a);
n >>= ;
}
return b.m[][];
} int main()
{
int n;
while(scanf("%d", &n), n!=-)
{
printf("%d\n", Fast_MOD(n));
}
return ;
}
最新文章
- JavaWeb前端基础复习笔记系列 二
- Java反射机制的作用
- webservice可以访问但是不能调用方法
- 理解Java中的接口
- POJ 1422
- Codeforces Round #311 (Div. 2)B. Pasha and Tea 水题
- POCISO-採购创建内部订单(R12.2.3)
- Android平台的事件处理机制和手指滑动例子
- linux find命令强大之处
- php生成雪花图像(不美观请见谅)
- es6 模板字变量和字符串占位符
- Struts的session问题
- UVA1609-Foul Play(构造+递归)
- hive案例
- java的myeclipse,java页面改动默认的javadoc方法
- Laravel返回不重复的某个字段信息列表
- fping命令测试主机存活
- 数据结构与算法JavaScript描述——使用队列
- 2017年--10年java大神告诉你开发最常用的百分之二十的技术有哪些?
- Ini文件格式说明