51Nod 1242 斐波那契数列的第N项——————矩阵快速幂

野性酷女 2022-05-09 10:18 179阅读 0赞

# 1242 斐波那契数列的第N项 #

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

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

F ( 0 ) = 0 F ( 1 ) = 1 F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n > = 2 ) F(0) = 0 \\\\ F(1) = 1\\\\ F(n) = F(n - 1) + F(n - 2)\\qquad (n >= 2) F(0)=0F(1)=1F(n)=F(n−1)\+F(n−2)(n>=2)

( 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , . . . ) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...) (1,1,2,3,5,8,13,21,34,55,89,144,233,377,...)  
给出 n n n，求 F ( n ) F(n) F(n)，由于结果很大，输出 &ThickSpace; F ( n ) % 1000000009 &ThickSpace;&ThickSpace; \\;F(n) \\% 1000000009\\;\\; F(n)%1000000009的结果即可。

**Input**  
输入1个数n(1 <= n <= 10^18)。  
**Output**  
输出 F ( n ) % 1000000009 F(n) \\% 1000000009 F(n)%1000000009的结果。

**Input**示例  
11  
**Output**示例  
89

--------------------

矩阵快速幂模板

矩阵

数学上，一个m×n的矩阵是一个由m行n列元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。

大小相同（行数列数都相同）的矩阵之间可以相互加减，具体是对每个位置上的元素做加减法。矩阵的乘法则较为复杂。两个矩阵可以相乘，当且仅当第一个矩阵的列数等于第二个矩阵的行数。矩阵的乘法满足结合律和分配律，但不满足交换律。

**矩阵乘法**

矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有定义。一般单指矩阵乘积时，指的便是一般矩阵乘积。若A为 m × n \{\\displaystyle m\\times n\} m×n 矩阵，B为 n × p \{\\displaystyle n\\times p\} n×p 矩阵，则他们的乘积 A B &ThickSpace; AB\\; AB(有时记做 A ⋅ B A · B A⋅B）会是一个  m × p \{\\displaystyle m\\times p\} m×p 矩阵。其乘积矩阵的元素如下面式子得出：  
 ( A B ) i j = ∑ r = 1 n a i r b r j = a i 1 b 1 j + a i 2 b 2 j + ⋯ + a i n b n j . \\Large (AB)\_\{ij\}=∑\_\{r=1\}^n a\_\{ir\}b\_\{rj\}=a\_\{i1\}b\_\{1j\}+a\_\{i2\}b\_\{2j\}+⋯+a\_\{in\}b\_\{nj\}. (AB)ij=r=1∑nairbrj=ai1b1j\+ai2b2j\+⋯\+ainbnj.

**线性递推关系与矩阵乘法**

设数列  h n \{h\_n\} hn 满足  k k k 阶常系数线性递推关系：  
 h n = C 1 h n − 1 + C 2 h n − 2 + C 3 h n − 3 + ⋅ ⋅ ⋅ + C k h n − k + b n h\_n = C\_1h\_\{n−1\} + C\_2h\_\{n−2\} + C\_3h\_\{n−3\} +···+ C\_kh\_\{n−k\}+b\_n hn=C1hn−1\+C2hn−2\+C3hn−3\+⋅⋅⋅\+Ckhn−k\+bn  
 b n b\_n bn 可以为常数，也可以是关于n的函数

若  b n b\_n bn为常数，则构造转移矩阵  
 M = ( C 1 C 2 C 3 ⋯ C k − 1 C k b n 1 0 0 ⋯ 0 0 0 0 1 0 ⋯ 0 0 0 0 0 1 ⋯ 0 0 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 0 ⋯ 1 0 0 0 0 0 ⋯ 0 0 1 ) ( k + 1 ) × ( k + 1 ) \\large M=\\begin \{pmatrix\} C\_1 & C\_2 & C\_3 & \\cdots & C\_\{k-1\} & C\_k & b\_n \\\\ 1 & 0 & 0 & \\cdots & 0 & 0 & 0\\\\ 0 & 1 & 0 & \\cdots & 0 & 0 & 0\\\\ 0 & 0 & 1 & \\cdots & 0 & 0 & 0\\\\ \\vdots & \\vdots& \\vdots & \\ddots & \\vdots & \\vdots \\\\ 0 & 0 & 0 & \\cdots & 1 & 0 & 0\\\\ 0 & 0 & 0 & \\cdots & 0 & 0 & 1 \\end\{pmatrix\}\_\{(k+1)×(k+1)\} M=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛C1100⋮00C2010⋮00C3001⋮00⋯⋯⋯⋯⋱⋯⋯Ck−1000⋮10Ck000⋮00bn00001⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞(k\+1)×(k\+1)  
与初始向量  
 X = ( h k − 1 h k − 2 h k − 3 ⋮ h 2 h 1 h 0 1 ) ( k + 1 ) × 1 \\large X=\\begin\{pmatrix\} h\_\{k-1\} \\\\ h\_\{k-2\} \\\\ h\_\{k-3\} \\\\ \\vdots \\\\ h\_\{2\} \\\\ h\_\{1\} \\\\ h\_\{0\} \\\\ 1 \\\\ \\end\{pmatrix\}\_\{(k+1)×1\} X=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛hk−1hk−2hk−3⋮h2h1h01⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞(k\+1)×1  
易见  
 X = ( C 1 C 2 C 3 ⋯ C k − 1 C k b n 1 0 0 ⋯ 0 0 0 0 1 0 ⋯ 0 0 0 0 0 1 ⋯ 0 0 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 0 ⋯ 1 0 0 0 0 0 ⋯ 0 0 1 ) ( h k − 1 h k − 2 h k − 3 ⋮ h 2 h 1 h 0 1 ) = ( h k h k − 1 h k − 2 ⋮ h 3 h 2 h 1 1 ) \\large X=\\begin \{pmatrix\} C\_1 & C\_2 & C\_3 & \\cdots & C\_\{k-1\} & C\_k & b\_n \\\\ 1 & 0 & 0 & \\cdots & 0 & 0 & 0\\\\ 0 & 1 & 0 & \\cdots & 0 & 0 & 0\\\\ 0 & 0 & 1 & \\cdots & 0 & 0 & 0\\\\ \\vdots & \\vdots& \\vdots & \\ddots & \\vdots & \\vdots \\\\ 0 & 0 & 0 & \\cdots & 1 & 0 & 0\\\\ 0 & 0 & 0 & \\cdots & 0 & 0 & 1 \\end\{pmatrix\} \\begin\{pmatrix\} h\_\{k-1\} \\\\ h\_\{k-2\} \\\\ h\_\{k-3\} \\\\ \\vdots \\\\ h\_\{2\} \\\\ h\_\{1\} \\\\ h\_\{0\} \\\\ 1 \\\\ \\end\{pmatrix\} =\\begin\{pmatrix\} h\_\{k\} \\\\ h\_\{k-1\} \\\\ h\_\{k-2\} \\\\ \\vdots \\\\ h\_\{3\} \\\\ h\_\{2\} \\\\ h\_\{1\} \\\\ 1 \\\\ \\end\{pmatrix\} X=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛C1100⋮00C2010⋮00C3001⋮00⋯⋯⋯⋯⋱⋯⋯Ck−1000⋮10Ck000⋮00bn00001⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛hk−1hk−2hk−3⋮h2h1h01⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛hkhk−1hk−2⋮h3h2h11⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞  
事实上我们可以发现，对于任意的  k k k 阶常系数线性递推关系，我们总可以构造一个  k × k k×k k×k 或  ( k + 1 ) × ( k + 1 ) (k+1)×(k+1) (k\+1)×(k\+1) 的转移矩阵  M M M, 对于初始值向量  
 X = ( h k − 1 h k − 2 h k − 3 ⋮ h 2 h 1 h 0 ) k × 1 或 ( h k − 1 h k − 2 h k − 3 ⋮ h 1 h 0 b n ) ( k + 1 ) × 1 \\large X=\\begin\{pmatrix\} h\_\{k-1\} \\\\ h\_\{k-2\} \\\\ h\_\{k-3\} \\\\ \\vdots \\\\ h\_\{2\} \\\\ h\_\{1\} \\\\ h\_\{0\} \\\\ \\end\{pmatrix\}\_\{k×1\}或 \\begin\{pmatrix\} h\_\{k-1\} \\\\ h\_\{k-2\} \\\\ h\_\{k-3\} \\\\ \\vdots \\\\ h\_\{1\} \\\\ h\_\{0\} \\\\ b\_n \\\\ \\end\{pmatrix\}\_\{(k+1)×1\} X=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛hk−1hk−2hk−3⋮h2h1h0⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞k×1或⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛hk−1hk−2hk−3⋮h1h0bn⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞(k\+1)×1  
使得 Y = M n − k + 1 X Y = M^\{n−k+1\}X Y=Mn−k\+1X 第一行第一列的元素恰好为  h n h\_n hn。

--------------------

代码

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    const int INF = 0x3f3f3f3f;
    const int MAX_N = 10;
    const int MOD = 1000000009;
    ll N;//矩阵的大小
    ll b_n=0;//常数
    ll C[MAX_N];//系数
    ll h[MAX_N];//
    struct mat{
        ll m[MAX_N][MAX_N]; };
    
    mat mul(mat a,mat b)//矩阵乘法
    {
        
            mat tmp;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                    {
        
                            tmp.m[i][j]=0;
                            for(int k=1;k<=N;k++)
                                    tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
                    }
            return tmp;
    }
    mat pow_mod(mat a,ll n)
    {
        
            mat res;
            //构造单位矩阵,res相当于快速幂里的 1
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            res.m[i][j] = (i==j);
    
            //矩阵快速幂
            while(n)
            {
        
                    if(n&1) res = mul(res,a);
                    a = mul(a,a);
                    n>>=1;
            }
            return res;
    }
    void init(mat &res,mat &H)//矩阵的初始化
    {
        
            for(int i=1;i<=N;i++)
                    res.m[1][i] = C[i];
            res.m[1][N]=b_n;
            //构造矩阵
            for(int i=2;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            res.m[i][j] = (i==j+1);
    
            res.m[N][N-1] = 0;
            res.m[N][N] = 1;
    
            for(int i=1;i<=N;i++)
            {
        
                    H.m[i][1] = h[N-i];
                    for(int j=2;j<=N;j++)
                            H.m[i][j] = 0;
            }
            H.m[N][1]=1;
    }
    
    void slove(ll k,ll n)
    {
        
            mat res,H;
            init(res,H);
    
            res = pow_mod(res,n-k+1);
            res = mul(res,H);
            ll ans=res.m[1][1];
    
            printf("%lld\n",ans);
    }
    int main()
    {
        
            ll n,k=2;
            C[1]=1;
            C[2]=1;
            N=k+1;
            h[1]=0;
            h[2]=1;
            while(~scanf("%lld",&n))
                    slove(k,n);
            return 0;
    }