POJ-3070--Fibonacci （大一版）

POJ-3070--Fibonacci （大一版）

Fibonacci

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, andFn = Fn − 1 + Fn − 2 forn ≥ 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 ofFn.

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 ofFn. If the last four digits ofFn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., printFn mod 10000).

Sample Input

099999999991000000000-1

Sample Output

0346266875

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:

.

矩阵快速幂模板：

第一次写矩阵快速幂的模板，第一次弄清楚了位运算是原理，

分析：

语句     if(k&1)ans=matrixmul(ans,s);         k=k>>1;         s=matrixmul(s,s);  是什么意思呢？    ps：   解析：     if(k&1) :是说k 和 1位运算与“&”的结果，     就是判断它是不是一个奇数，如果最后一位（初始值从最后一位算起）是1 的话    执行语句：ans=matrixmul(ans,s);    将矩阵的乘方存入变量ans中，    然后判断接着从最后一位往前进行，    那么如何继续判断？    语句：k=k>>1;起作用了，表示k 的二进制数往左移位    比如10的二进制：1010，最右边的是0，初始值s=矩阵  往左判断到1是奇数 然后 执行   ans=matrixmul(ans,s);ans=s^2;    接着继续，倒数第三位是0，执行  s=s*s=s^4; 继续：   第一位是1 ，ans=s^2*s^4=s^8; 最后判断k==1,ans=s^8*s^2=s^10;

最后输出的是矩阵最左上方的值。

根据前面的一些思路，现在我们需要构造一个2 x 2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多迭代一次。那么，我们把这个2 x 2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：

开始不懂，请教学姐，最终恍然大悟。

代码：

/***************POJ---3070FibonacciTimes；0ms;***************/#include#include#include#include#include#include#include#include#includeusing namespace std;#define max(a,b) a>b?a:b#define min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};struct Fast_mod{ int a[2][2]; void init() { a[1][1]=a[0][1]=a[1][0]=1; a[0][0]=0; }};Fast_mod matrixmul(Fast_mod a,Fast_mod b){ int i,j,k; Fast_mod c; for(i=0; i<2; i++) { for(j=0; j<2; j++) { c.a[i][j]=0; for(k=0; k<2; k++) c.a[i][j]+=(a.a[i][k]*b.a[k][j]); c.a[i][j]%=10000; } } return c;}Fast_mod mul(Fast_mod s,int k){ Fast_mod ans; ans.init(); while(k>=1) { if(k&1)ans=matrixmul(ans,s); k=k>>1; s=matrixmul(s,s); } return ans;}int main(){ int n; while(scanf("%d",&n),n!=-1) { if(!n) { printf("0\n"); continue; } Fast_mod s;//矩阵初始化 s.init();// s=mul(s,n-1); printf("%d\n",s.a[0][1]%10000); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。