Fibonacci----poj3070（矩阵快速幂， 模板）

题目链接：http://poj.org/problem?id=3070

.

就是斐波那契的另一种表示方法是矩阵的幂；

所以是矩阵快速幂；矩阵快速幂学习

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<math.h>
using namespace std;
#define N 10

struct node
{
    int a[N][N];
}s,e;

node mul(node p, node q)///求两个矩阵的积；
{
    node tem;
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            tem.a[i][j] = 0;
            for(int k=0; k<2; k++)
                tem.a[i][j] = (tem.a[i][j]+p.a[i][k]*q.a[k][j])%10000;
        }
    }
    return tem;
}
node Pow(node p, int n)
{
    node tem;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            tem.a[i][j] = (i==j);
    while(n)
    {
        if(n&1)///n是奇数；
            tem = mul(tem, p);///让矩阵e和矩阵a相乘；
        n/=2;
        p = mul(p, p);
    }
    return tem;
}

int main()
{
    s.a[0][0] = 1;
    s.a[0][1] = 1;
    s.a[1][0] = 1;
    s.a[1][1] = 0;
    int n;
    while(scanf("%d", &n),n!=-1)
    {
        e = Pow(s, n);
        printf("%d
", e.a[0][1]);
    }
    return 0;
}

对比着想想快速幂；