| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 10440 | Accepted: 7421 |
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:
.
解题思路：
关键是会求解转移矩阵，剩下的就是扔模板了。。
代码：
1 # include<cstdio> 2 # include<iostream> 3 # include<fstream> 4 5 using namespace std; 6 7 # define MOD 10000 8 9 typedef long long LL; 10 11 struct matrix 12 { 13 LL a[2][2]; 14 void init() 15 { 16 a[0][0] = 1; 17 a[0][1] = 1; 18 a[1][0] = 1; 19 a[1][1] = 0; 20 } 21 }; 22 23 int n; 24 25 matrix fun ( matrix aa, matrix bb ) 26 { 27 matrix cc; 28 for ( int i = 0;i < 2;i ++ ) 29 { 30 for ( int j = 0;j < 2;j++ ) 31 { 32 cc.a[i][j] = 0; 33 for ( int k = 0;k < 2;k++ ) 34 { 35 cc.a[i][j]+=(aa.a[i][k]*bb.a[k][j]); 36 } 37 cc.a[i][j]%=MOD; 38 } 39 } 40 41 return cc; 42 } 43 44 45 46 matrix My_power( matrix aa,int k ) 47 { 48 matrix ans; 49 ans.init(); 50 while ( k >= 1 ) 51 { 52 if ( k&1 ) 53 { 54 ans = fun(ans,aa); 55 } 56 k/=2; 57 aa = fun(aa,aa); 58 } 59 60 return ans; 61 62 } 63 64 65 int main(void) 66 { 67 68 int n; 69 while ( scanf("%d",&n)!=EOF ) 70 { 71 if ( n==-1 ) 72 break; 73 if ( n==0 ) 74 { 75 printf("0\n"); 76 continue; 77 } 78 matrix aa; 79 aa.init(); 80 aa = My_power(aa,n-1); 81 printf("%lld\n",aa.a[0][1]%MOD); 82 } 83 84 return 0; 85 }
原文：http://www.cnblogs.com/wikioibai/p/4508981.html