poj3070 Fibonacci

链接

矩阵经典题目

利用矩阵的快速幂取模快速的求得解

其实它题目已经给的很明显了下面再描述一下过程

f(n） 1 1 f(n)+f(n-1)

f(n-1) 1 0 f(n)

左边乘中间的变成右边的然后可以看出右边的已经变成了 f(n+1) f(n) 那么乘上k次上面那个10矩阵就得到了f(n+k)

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 2
12 #define LL long long
13 #define INF 0xfffffff
14 #define mod 10000
15 const double eps = 1e-8;
16 const double pi = acos(-1.0);
17 const double inf = ~0u>>2;
18 struct Mat
19 {
20     int mat[N][N];
21 };
22 int n;
23 Mat operator * (Mat a,Mat b)
24 {
25     Mat c;
26     memset(c.mat,0,sizeof(c.mat));
27     int i,j,k;
28     for(k =0 ; k < n ; k++)
29     {
30         for(i = 0 ; i < n ;i++)
31         {
32             if(a.mat[i][k]==0) continue;
33             for(j = 0 ;j < n ;j++)
34             {
35                 if(b.mat[k][j]==0) continue;
36                 c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
37             }
38         }
39     }
40     return c;
41 }
42 Mat operator ^(Mat a,int k)
43 {
44     Mat c;
45     int i,j;
46     for(i =0 ; i < n ;i++)
47         for(j = 0; j < n ;j++)
48         c.mat[i][j] = (i==j);
49     for(; k ;k >>= 1)
50     {
51         if(k&1) c = c*a;
52         a = a*a;
53     }
54     return c;
55 }
56 int main()
57 {
58     LL t;
59     n = 2;
60     while(cin>>t)
61     {
62         if(t==-1)
63         break;
64         if(t<=3)
65         {
66             if(t==0)
67             cout<<"0
";
68             continue;
69         }
70         Mat x;
71         x.mat[0][0] = 1,x.mat[0][1] = 1,x.mat[1][0] = 1,x.mat[1][1] = 0;
72         x = x^t;
73         cout<<x.mat[0][1]<<endl;
74     }
75     return 0;
76 }

View Code