sicily Fibonacci 2

矩阵快速幂，1001. Fibonacci 2求斐波那契第n项！毕竟数据量太大！

http://soj.sysu.edu.cn/show_problem.php?pid=1001&cid=1740

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 struct mat {
 7     long long m[2][2];
 8     mat()
 9     {
10         memset(m, 0, sizeof(m));
11     }
12 };
13 
14 int n=2;
15 
16 mat operator * (mat a, mat b)
17 {
18     mat c;
19     for(int i=0; i<n; i++)
20         for(int j=0; j<n; j++)
21             for(int k=0; k<n; k++)
22                 c.m[i][j] += (a.m[i][k] * b.m[k][j]) % 1000000007; //记得模 
23     return c;
24 }
25 
26 void print(mat a)
27 {
28     for(int i=0; i<n; i++)
29     {
30         for(int j=0; j<n; j++)
31             cout << a.m[i][j] << " ";
32         cout << endl;
33     }
34 }
35 
36 int main()
37 {
38     int t;
39     while(cin >> t)
40     {
41         if(t == -1)
42             break;
43         mat a;
44         mat c;
45         c.m[0][0] = 1; c.m[0][1] = 0; c.m[1][0] = 0; c.m[1][1] = 1;
46         a.m[0][0] = 1; a.m[0][1] = 1; a.m[1][0] = 1; a.m[1][1] = 0;
47         int N = t;
48         while(N)
49         {
50             if(N%2) 
51                 c = c * a;
52             a = a * a;
53             N /= 2;
54         }
55         cout << c.m[0][1]%1000000007 << endl;
56     }
57     
58     return 0;
59 }