矩阵快速幂优化线性递推-白红宇

矩阵快速幂优化线性递推

阅读量：4544 次

发布时间：2019-06-08

本文共 1759 字，大约阅读时间需要 5 分钟。

我们熟知的斐波那契数列递推公式是：

$f(n)=f(n-1)+f(n-2)$

假设我们需要求斐波那契数列的第n项，当n非常大（如n=1e9)的时候，递推肯定超时。我们不妨设：

$\binom{f_{n}}{f_{n-1}}=\begin{pmatrix}a & b\\ c & d\end{pmatrix}\binom{f_{n-1}}{f_{n-2}}$

将等式右边乘开，得到：

$\binom{af_{n-1}+bf_{n-2}}{cf_{n-1}+df_{n-2}}$

要使其等于等式左边，显然：

$\binom{f_{n}}{f_{n-1}}=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}\binom{f_{n-1}}{f_{n-2}}$

如此递推下去，我们最终能够得到：

$\binom{f_{n}}{f_{n-1}}=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^{n-2}\binom{f_{2}}{f_{1}}$

我们已知$f1=1,f2=1$，这样，我们就可以通过矩阵快速幂来求数列第n项了！像这样，对于所有的线性递推关系，我们都可以使用矩阵快速幂来优化ovo

模版如下(洛谷P3390 矩阵快速幂）：

#include 
     
      #include 
      
       #include 
       
        #define mod 1000000007#define ll long longusing namespace std;struct Matrix{    ll m[101][101];}a,e;ll n,k;Matrix mul(Matrix x,Matrix y){    Matrix c;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            c.m[i][j]=0;        }    }    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            for(int k=1;k<=n;k++)            {                c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;            }        }    }    return c;}Matrix mqpow(Matrix x,ll p){    Matrix ans=e;    while(p!=0)    {        if(p%2)        {            ans=mul(ans,x);        }        x=mul(x,x);        p/=2;    }    return ans;}int main(){    scanf("%lld%lld",&n,&k);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            scanf("%lld",&a.m[i][j]);        }    }    for(int i=1;i<=n;i++)    {        e.m[i][i]=1;    }//初始化    Matrix ans=mqpow(a,k);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            printf("%lld ",ans.m[i][j]%mod);        }        printf("\n");    }    return 0;}