欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客等级之题N2(8.13场)A 斐波那契(矩阵快速幂)

程序员文章站 2024-03-17 21:30:34
...

传送门

题意:

牛客等级之题N2(8.13场)A 斐波那契(矩阵快速幂)

思路:

斐波那契数列fi=fi1+fi2f_i=f_{i-1}+f_{i-2}
f12+f22+f32+...+fi22+fi12+fi2=fifi+1{f_1}^2+{f_2}^2+{f_3}^2+...+{f_{i-2}}^2+{f_{i-1}}^2+{f_i}^2=f_i*f_{i+1}
牛客等级之题N2(8.13场)A 斐波那契(矩阵快速幂)
用矩阵快速幂求斐波那契的第n项和第n+1项即可

代码:

const int N=2;//矩阵大小
ll quick(ll a,ll b){//快速幂
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans%mod;
}


struct sa
{
    ll m[N][N];
};
sa Mul(sa a,sa b)//矩阵乘法
{
    sa c;
    memset(c.m,0, sizeof(c.m));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
    return c;
}

sa quickjz(sa a,ll n)//矩阵快速幂
{
    sa res;
    memset(res.m,0, sizeof(res.m));
    //res.m[0][0]=1;
    //res.m[1][1]=1;
    for(int i=0;i<N;i++)res.m[i][i]=1;
    while(n)
    {
        if(n&1)
            res=Mul(res,a);
        n/=2;
        a=Mul(a,a);
    }
    return res;
}


int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    sa cnt={1,1,1,0};

    ll n;
    while(cin>>n){
	    sa a=quickjz(cnt,n);
	    ll p=a.m[1][0];
	    a=quickjz(cnt,n+1);
	    p=(p*a.m[1][0])%mod;
	    cout<<p<<endl;
	}
    return 0;
}
相关标签: 矩阵快速幂