P1349 广义斐波那契数列

· · 个人记录

思路分析

既然广义斐波那契，而且数据范围这么大，那么我们使用矩阵快速幂来进行求解。

所以就要推初始矩阵。

设这个矩阵为A，则：

F_{n-1}&F_{n-2} \end{bmatrix}\times A=\begin{bmatrix} F_n&F_{n-1} \end{bmatrix}

易得A是2行2列的，所以：

设

a&b\\ c&d \end{bmatrix}

那么：

F_{n-1}&F_{n-2} \end{bmatrix}\times \begin{bmatrix} a&b\\ c&d \end{bmatrix}=\begin{bmatrix} F_n&F_{n-1} \end{bmatrix}

运用矩阵乘法，得：

F_{n-1}\times a+F_{n-2}\times c&F_{n-1}\times b+F_{n-2}\times d \end{bmatrix}=\begin{bmatrix} F_n&F_{n-1} \end{bmatrix}

所以：

F_{n-1}\times a+F_{n-2}\times c=F_n F_{n-1}\times b+F_{n-2}\times d=F_{n-1}

由题：

F_n=p\times F_{n-1}+q\times F_{n-2}

所以：

a=p c=q

其次很明显：

b=1 d=0

所以终上：

p&1\\ q&0 \end{bmatrix}

接下来确定\begin{bmatrix} F_{n-1}&F_{n-2} \end{bmatrix}的初值

倒回去可以得：

F_2&F_1 \end{bmatrix}\times \begin{bmatrix} a&b\\ c&d \end{bmatrix}=\begin{bmatrix} F_3&F_2 \end{bmatrix}

输入中已经给出a_1 和 a_2，所以这个数组初值为\begin{bmatrix} a_2&a_1 \end{bmatrix}

矩阵都推好了，接下来用矩阵快速幂模板即可。

注意：n不能直接做指数，要用n-2来做；如果n\le2则直接输出a_1 或 a_2

代码如下

#include<bits/stdc++.h>
using namespace std;
long long p,q,a1,a2,n,mod;
struct matrix{long long x[105][105];};
matrix ans,a;
matrix mul(matrix a,matrix b)
{
    matrix c;
    memset(c.x,0,sizeof(c.x));
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int l=1;l<=2;l++)
                c.x[i][j]+=a.x[i][l]*b.x[l][j],c.x[i][j]%=mod;
    return c;
}
int main()
{
    cin>>p>>q>>a1>>a2>>n>>mod;
    if(n==1)
        {cout<<a1%mod;return 0;}
    else if(n==2)
        {cout<<a2%mod;return 0;}
    ans.x[1][1]=a2;ans.x[1][2]=a1;
    a.x[1][1]=p;a.x[1][2]=1;
    a.x[2][1]=q;a.x[2][2]=0;
    n-=2;
    while(n>0)
    {
        if(n&1)  
            ans=mul(ans,a);
        a=mul(a,a);
        n>>=1;
    }
    cout<<ans.x[1][1];
    return 0;
}