POJ 3070 矩阵快速幂

题目大意：求斐波那契数列数列的第n项的后四位，如果有前导0就不输出0

(斐波那契的另一个公式)

矩阵快速幂求斐波那契数列

 1 #include <cstdio>
 2 #include <cstring>
 3 const int mod=10000;
 4 struct matrix
 5 {
 6     int m[2][2];
 7 };
 8 
 9 matrix mul(matrix a,matrix b)
10 {
11     matrix tmp;
12     memset(tmp.m,0,sizeof(tmp.m));
13     for(int i=0;i<2;i++)
14         for(int j=0;j<2;j++)
15         {
16             for(int k=0;k<2;k++)
17                 tmp.m[i][j]=tmp.m[i][j]+a.m[i][k]*b.m[k][j]%mod;
18             tmp.m[i][j]%=mod;
19         }
20     return tmp;
21 }
22 
23 int cal(int n)
24 {
25     matrix a,b;
26     a.m[0][0]=a.m[1][1]=1;
27     a.m[1][0]=a.m[0][1]=0;
28     b.m[0][0]=b.m[0][1]=b.m[1][0]=1;
29     b.m[1][1]=0;
30     while(n>0)
31     {
32         if(n&1)
33             a=mul(a,b);
34         b=mul(b,b);
35         n>>=1;
36     }
37     return a.m[0][1];
38 }
39 
40 int main()
41 {
42     int n;
43     while(scanf("%d",&n)&&n!=-1)
44     {
45         printf("%d
",cal(n));
46     }
47     return 0;
48 }