题解 P1962 【斐波那契数列】

· · 题解

正解：矩阵乘法

(请原谅，我对latex还不是很熟悉)

矩阵乘法如何用：

比如说，我们有一个矩阵|a b|

那么，要求下两项，就变成|b a+b|

所以，要乘的矩阵应该是

A=

|0 1|

|1 1|这样一个二阶矩阵。（请自动脑补）

那么，乘的时候就变成

|a b|×A×A×A×A×A（n个A）

重点出场了，怎么样优化

请注意，矩阵乘法满足乘法结合律

所以我们把后面的A先相乘，就变成了快速幂

具体解法见P3390【模板】矩阵快速幂

不多说，见代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int frog=1e9+7;ll n;
struct matrix{ll a[3][3];}A,ans;
void multi(matrix &a,matrix b)
{
    ll c[3][3]={0};
    for(int i=1;i<3;i++)for(int j=1;j<3;j++)for(int k=1;k<3;k++)c[i][j]+=a.a[i][k]*b.a[k][j],c[i][j]%=frog;
    for(int i=1;i<3;i++)for(int j=1;j<3;j++)a.a[i][j]=c[i][j];
}
inline void kasumi()
{
    for(int i=1;i<3;i++)for(int j=1;j<3;j++)ans.a[i][j]=A.a[i][j];n--;
    while(n){if(n%2==1)multi(ans,A);multi(A,A);n/=2;}
}
int main()
{
    scanf("%lld",&n);
    ans.a[1][1]=ans.a[1][2]=1;//初始数据 
    A.a[1][1]=0,A.a[1][2]=A.a[2][1]=A.a[2][2]=1;//构造矩阵 
    kasumi();//矩阵快速幂 
    printf("%lld ",ans.a[1][2]%frog);
}