Luogu 1349 广义斐波那契数列（递推，矩阵，快速幂）

Description

广义的斐波那契数列是指形如$$A_n=pa_{n-1}+qa_{n-2}$$的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。

Input

输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。

Output

输出包含一行一个整数，即an除以m的余数。

Sample Input

1 1 1 1 10 7

Sample Output

6

Http

Luogu:https://www.luogu.org/problem/show?pid=1349

Source

递推，矩阵，快速幂

解决思路

如果熟悉了普通斐波那契数列这道题（如果不知道的话请点击链接，里面还有矩阵的相关知识），那么对于广义的斐波那契数列我们不难想到递推矩阵:

所以递推方程就是

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const int inf=2147483647;

ll n,Mod,p,q,A1,A2;

class Matrix//定义矩阵结构体

{

public:

    ll M[2][2];

    Matrix()

    {

        memset(M,0,sizeof(M));

    }

    Matrix(ll Arr[2][2])

    {

        for (int i=0;i<2;i++)

            for (int j=0;j<2;j++)

                M[i][j]=Arr[i][j];

    }

};

Matrix operator * (Matrix A,Matrix B)//重载乘法操作

{

    Matrix Ans;

    for (int i=0;i<2;i++)

        for (int j=0;j<2;j++)

            for (int k=0;k<2;k++)

                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;

    return Ans;

}

int main()

{

    cin>>p>>q>>A1>>A2>>n>>Mod;

    if (n==1)//1和2的情况特殊处理（虽然我也不知道是否有特殊点）

    {

        cout<<A1<<endl;

        return 0;

    }

    if (n==2)

    {

        cout<<A2<<endl;

        return 0;

    }

    n=n-2;

    ll a[2][2]={{A2,A1},{0,0}};//初始矩阵

    ll b[2][2]={{p,1},{q,0}};

    Matrix A(a);

    Matrix B(b);

    while (n!=0)//快速幂

    {

        if (n&1)

            A=A*B;

        B=B*B;

        n=n>>1;

    }

    cout<<A.M[0][0]<<endl;

    return 0;

}