首页 > 代码库 > poj 3070 Fibonacci

poj 3070 Fibonacci

矩阵快速幂

1 while(N)2  {3       if(N&1)4           res=res*A;5       n>>=1;6       A=A*A;7  }

 

 1 #include<iostream> 2 using namespace std; 3 #deinfe mod 10000 4 struct matrix 5 { 6     int m[2][2]; 7 }ans,base; 8 matrix multi(matrix a, matrix b) 9 {10     matrix t;11 12     for(int i = 0; i < 2; i++)13     {14         for(int j = 0; j < 2; j++)15         {16             t.m[i][j] = 0;17             for(int pos = 0; pos < 2; pos++)18             {19                 t.m[i][j] = (t.m[i][j] + a.m[i][pos] * a[pos][j]) % mod;20             }21         }22     }23     return t;24 }25 int fast(int n)26 {27 28 }29 30 int main()31 {32     freopen("input.txt","r",stdin);33     int n;34     while(scanf("%d",&n) && n != -1)35     {36         printf("%d\n",fast());37     }38     return 0;39 }