链接：
http://acm.nyist.net/JudgeOnline/problem.php?pid=148
fibonacci数列(二)
时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述 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. 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: . 输入 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. 输出 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). 样例输入 0 9 1000000000 -1 样例输出 0 346875
#include <stdio.h> #include <stdlib.h> #include <string.h> const int mod=10000; long x,y,n; struct mat { int a[2][2]; }; mat mat_mul(const mat &x,const mat &y) { static mat res; memset(res.a,0,sizeof(res.a)); for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) if(x.a[i][k] && y.a[k][j]) res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod; return res; } void mat_fast_pow(long n) { static int i; static mat c,res; c.a[0][0]=c.a[0][1]=c.a[1][0]=1; c.a[1][1]=0; memset(res.a,0,sizeof(res.a)); for(i = 0;i < 2;++i) res.a[i][i]=1; while(n) { if(n&1) res=mat_mul(res,c); c=mat_mul(c,c); n=n>>1; } int yy=res.a[0][0],xx=res.a[0][1]; printf("%d\n", yy); } int main() { while(~scanf("%I64d", &n)) { if(n > 0) mat_fast_pow(n-1); else if(n == 0) printf("0\n"); else break; } return 0; }
