Fibonacci
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 16617 | Accepted: 11637 |
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 6875AC代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int MOD = 10000;
struct mut{int at[4][4];
};
int q;
mut d;//两个矩阵相乘
mut mal(mut a, mut b){mut c;memset(c.at, 0, sizeof(c.at));for(int i = 1; i <= q; i++){for(int j = 1; j <= q; j++){for(int k = 1; k <= q; k++){c.at[i][j] += a.at[i][k] * b.at[k][j];if(c.at[i][j] >= MOD) c.at[i][j] %= MOD;}}}return c;
} //求n次幂矩阵
mut expo(mut a, int k){mut e;memset(e.at, 0, sizeof(e.at));for(int i = 1; i <= q; i++) e.at[i][i] = 1;while(k){if(k & 1) e = mal(e, a);a = mal(a, a);k >>= 1;}return e;
}int main(){q = 2;int n;d.at[1][1] = 1;d.at[1][2] = 1;d.at[2][1] = 1;d.at[2][2] = 0;
// mut ans = expo(d, 3);
// for(int i = 1; i <= 2; i++){
// for(int j = 1; j<= 2; j++){
// printf("%d ", ans.at[i][j]);
// }
// printf("\n");
// }while(scanf("%d", &n) != EOF && n != -1){if(n == 0) printf("0\n");else if(n == 1) printf("1\n");else{mut ans = expo(d, n);printf("%d\n", ans.at[1][2]);} }return 0;
}