51nod 1242 斐波那契数列的第N项

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1242
 1 #include <cstdio>
 2 typedef long long ll;
 3 const int mod = 1e9+9;
 4 struct Mat
 5 {
 6     ll matrix[2][2];
 7 };
 8 
 9 Mat mul(Mat a,Mat b)
10 {
11     Mat c;
12     for(int i=0;i<2;i++)
13         for(int j=0;j<2;j++)
14         {
15             c.matrix[i][j]=0;
16             for(int k=0;k<2;k++)
17             {
18                 c.matrix[i][j]+=(a.matrix[i][k]*b.matrix[k][j])%mod;
19             }
20             c.matrix[i][j]%=mod;
21         }
22     return c;
23 }
24 Mat mat;
25 Mat solve(ll m)
26 {
27     Mat mt=mat;
28     m--;
29     while(m)
30     {
31         if(m&1)
32         {
33             mt=mul(mat,mt);
34             m--;
35         }
36         mat=mul(mat,mat);
37         m/=2;
38     }
39     return mt;
40 }
41 int main()
42 {
43     //freopen("a.txt","r",stdin);
44     ll n;
45     scanf("%lld",&n);
46     mat.matrix[0][0]=mat.matrix[0][1]=mat.matrix[1][0]=1;
47     mat.matrix[1][1]=0;
48     Mat c=solve(n-1);
49     printf("%lld
",c.matrix[0][0]);
50     return 0;
51 }