poj3070来体会矩阵的妙用

题目大意就是求出斐波那契数列第k项的后四位，如果有前导0就不输出0，但最后一个0必须输出

刚开始的时候就想到了一个关于斐波那契数列的数列的一个公式，准备用那个公式求的，但题目已经提示了用矩阵，就没用那个公式

这一题就要注意到矩阵

的右上角或左下角对应的值正好是第n项的值

故可以通过快速幂来求得斐波那契数列的哦n项，由于数据较大，还要记得要不断的对10000取模

矩阵的快速幂我是直接抄的模板，刚开始时不理解，现在懂了，详情直接看代码

poj3070 Fibonacciview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct prog {
    int a[2][2] ;
    void init(){
        a[0][0]=a[1][0]=a[0][1]=1;
        a[1][1]=0;
    }
};

prog matrixmul ( prog a ,prog b )
{
    int i , j , k ;
    prog c ;
    for ( i = 0 ; i < 2; i ++ )
    {
        for ( j = 0 ; j < 2 ; j ++ )
        {
            c.a[i][j]=0;
            for ( k =0 ; k < 2; k ++ )
                c.a[i][j]+=(a.a[i][k]*b.a[k][j]) ;
            c.a[i][j] %= 10000 ;
        }
    }
    return c ;
}
prog mul (prog s , int k )
{
    prog ans ;
    ans.init();
    while ( k >= 1 )
    {
        if ( k & 1 )
            ans = matrixmul ( ans , s ) ;
        k = k >> 1 ;
        s = matrixmul ( s , s ) ;
    }
    return ans ;
}
int main()
{
    int n ;
    while ( cin >> n , ~ n )
    {
        if ( ! n )
        {
            cout<<0<<endl ;
            continue ;
        }
        prog s ;
        s.init ( ) ;
        s = mul ( s , n - 1 ) ;
        cout << s . a [0][1] % 10000 <<endl;
    }

    return 0;
}