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

之前一直没敢做矩阵一类的题目

其实还好吧

推荐看一下： http://www.cnblogs.com/SYCstudio/p/7211050.html

但是后面的斐波那契推导不是很懂前面讲的挺好的

后来看到了 http://blog.csdn.net/flyfish1986/article/details/48014523

相当于是一个那个东西的k-1次方而且由于 F(1) = 1 所以直接求k-1次方就可以了

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+9;
typedef long long ll;

class Matrix
{
public:
    ll s[2][2];
    Matrix()
    {
        memset(s,0,sizeof(s));
    }
    Matrix(ll a[2][2])
    {
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                s[i][j] = a[i][j];
    }
};
Matrix operator *(Matrix a,Matrix b)
{
    Matrix ans;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                ans.s[i][j] = (ans.s[i][j] + a.s[i][k]*b.s[k][j]%mod)%mod;
    return ans;
}

void _pow(ll k)
{

    ll a[2][2];
    a[0][0] = 1,a[0][1]=1,a[1][0]=1,a[1][1]=0;//初始化特征矩阵
    Matrix A(a),B(a);
    while (k>0)
    {
        if(k&1) A= A*B;
        B= B*B;
        k>>=1;
    }
    printf("%lld
",A.s[0][0]);//最后结果存储在矩阵第一行第一列上
}


int main ()
{
    ll n;
    scanf("%lld",&n);
    if(n<=2)
    {
        printf("1
");
        return 0;
    }
    n-=2;//这里是因为 本身是矩阵的k-1次幂  但是 本身建立矩阵已经1次了
    // 所以n-=2次
    _pow(n);
}

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

相关推荐