51nod 1242 斐波那契数列的第N项 (用矩阵快速幂加速递推）

1242 斐波那契数列的第N项

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

关注

斐波那契数列的定义如下：

F(0) = 0

F(1) = 1

F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)

给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input

输入1个数n(1 <= n <= 10^18)。

Output

输出F(n) % 1000000009的结果。

Input示例

Output示例

89

矩阵快速幂：需要会矩阵乘法和快速幂算法。
矩阵乘法按照定义去模拟即可。

快速幂算法模板：

typedef long long ll;
ll mod_pow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n)
    {
        if(n&1)
            res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

矩阵乘法模板：

struct matrix
{
    ll m[2][2]; 
};
matrix mul(matrix A,matrix B)
{
    matrix ret;
    for(int i=0;i<2;i++)//枚举行
        for(int j=0;j<2;j++)//枚举列
        {
            ret.m[i][j]=0;
            for(int k=0;k<2;k++)
                ret.m[i][j]+=A.m[i][k]*B.m[k][j]%mod;
        }
    return ret;
}

AC代码：

 1 #include <iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 #define mod 1000000009
 5 struct matrix
 6 {
 7     ll m[2][2];
 8 };
 9 matrix mul(matrix A,matrix B)
10 {
11     matrix ret;
12     for(int i=0;i<2;i++)//枚举行
13         for(int j=0;j<2;j++)//枚举列
14         {
15             ret.m[i][j]=0;
16             for(int k=0;k<2;k++)
17                 ret.m[i][j]+=A.m[i][k]*B.m[k][j]%mod;
18         }
19     return ret;
20 }
21 matrix pow(matrix A,long long n)
22 {
23     matrix ret;
24     ret.m[0][0]=1;
25     ret.m[0][1]=0;
26     ret.m[1][0]=0;
27     ret.m[1][1]=1;
28     while(n)
29     {
30         if(n&1)
31             ret=mul(ret,A);
32         A=mul(A,A);
33         n>>=1;
34     }
35     return ret;
36 }
37 int main()
38 {
39     int n;
40     cin>>n;
41     matrix ans,A;
42     ans.m[0][0]=1;
43     ans.m[0][1]=0;
44     A.m[0][0]=1;
45     A.m[0][1]=1;
46     A.m[1][0]=1;
47     A.m[1][1]=0;
48 
49     ans=mul(ans,pow(A,n-1));
50     cout<<ans.m[0][0]<<endl;
51     return 0;
52 }

View Code