poj 3070 矩阵快速幂

Fibonacci

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 12457		Accepted: 8851

Description

In the Fibonacci integer sequence, F₀ = 0, F₁ = 1, and F_n = F_n_{− 1} + F_n_{− 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 F_n.

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

Sample Input

Sample Output

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:

Source

Stanford Local 2006

题意：求斐波那契数列

题解；矩阵快速幂第一题

关键在于矩阵的构造之后就是快速幂了

矩阵的构造 http://www.cnblogs.com/frog112111/archive/2013/05/19/3087648.html

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<stack>
 6 #include<map>
 7 #define mod 10000
 8 using namespace std;
 9 struct matrix
10 {
11     int m[5][5];
12 } ans,exm;
13 
14 struct matrix matrix_mulit(struct matrix aa,struct matrix bb)
15 {
16     struct matrix there;
17     for(int i=0;i<2;i++)
18     {
19         for(int j=0;j<2;j++)
20         {
21             there.m[i][j]=0;
22             for(int k=0;k<2;k++)
23             there.m[i][j]=(there.m[i][j]+aa.m[i][k]*bb.m[k][j]%mod)%mod;
24         }
25     }
26     return there;
27 }
28 int matrix_quick(int gg)
29 {
30      exm.m[0][0]=exm.m[0][1]=exm.m[1][0]=1;
31      exm.m[1][1]=0;
32      ans.m[0][0]=ans.m[1][1]=1;  
33      ans.m[0][1]=ans.m[1][0]= 0;
34      while(gg)
35      {
36          if(gg&1)  
37          {
38              ans=matrix_mulit(ans,exm);        
39          }
40         exm = matrix_mulit(exm, exm);
41         gg >>= 1;
42     }
43      return ans.m[0][0];
44 } 
45 int n; 
46 int main()
47 {
48     while(scanf("%d",&n)!=EOF)
49     {
50         if(n==-1)
51          break;    
52         printf("%d
",matrix_quick(n));
53     }
54     return 0;
55 }