P1349 广义斐波那契数列

广义斐波那契数列#

题目描述#

广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。

今给定数列的两系数 $p$ 和 $q$ ，以及数列的最前两项 $a_1$ 和 $a_2$ ，另给出两个整数 $n$ 和 $m$ ，试求数列的第 $n$ 项 $a_n$ 对 $m$ 取模后的结果。

输入格式#

输入包含一行六个整数， $p,q,a_1,a_2,n,m$ 。

输出格式#

输出包含一行一个整数表示答案。

样例 #1#

样例输入 #1#

1 1 1 1 10 7

样例输出 #1#

提示#

数列第 $10$ 项是 $55$ ， $55 \bmod 7 = 6$ 。

【数据范围】
对于 $100\%$ 的数据， $p,q,a_1,a_2 \in [0,2^{31}-1]$ ， $1\le n,m \le 2^{31}-1$ 。

题目分析#

题目要求的是 $a_n\%m$ 的值。

那么只需要求出第 n 项，再进行取余即可。题面已经提供了递推的公式 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 。暴力做法可以从第 3 项开始，直接一项项进行枚举递推到第 n 项即可。时间复杂度为 $O(n)$ 。但是本题的数据范围较大，直接暴力会超时，需要加速求解第 n 项的过程。

针对递推过程的加速，可以尝试使用矩阵快速幂来进行处理。

设矩阵 A 为: [ $a_{n-2}\ a_{n-1}$ ]。

\begin{bmatrix} a_{n-2} & a_{n-1} \end{bmatrix} \times \begin{bmatrix} b_{1,1} & b_{1,2} \\ b_{2,1} & b_{2,2} \\ \end{bmatrix} = \begin{bmatrix} a_{n-1} & a_{n} \end{bmatrix}

那么意味着

a_{n-2}\times b_{1,1}+a_{n-1}\times b_{2,1}=a_{n-1}\\ a_{n-2}\times b_{1,2}+a_{n-1}\times b_{2,2}=a_n

结合递推式 $a_n=p\times a_{n-1}+q\times a_{n-2}$ , 可推出加速矩阵 B 为

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

可发现，每乘一次矩阵 B，即可向后推一项。那么求第 n 项就成了求 $A\times B^{n-1}$ 的第一列内容，我们可以采用矩阵快速幂在 $O(\log n)$ 的时间复杂度内完成求解。

代码实现#

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,q,a1,a2,n,M;
struct matrix{ll m[5][5];};

matrix operator *(const matrix &a,const matrix &b){
    matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;
    return c;
}
matrix fastPow(matrix a,int n){
    matrix ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=1;i<=2;i++) ans.m[i][i]=1;
    while(n){
        if(n&1) ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}
int main(){
    matrix a,b;
    memset(a.m,0,sizeof(a.m));
    memset(b.m,0,sizeof(b.m));
    cin>>p>>q>>a1>>a2>>n>>M;
    a.m[1][1]=a1;a.m[1][2]=a2;
    b.m[1][1]=0;b.m[1][2]=q;
    b.m[2][1]=1;b.m[2][2]=p;
    matrix c=a*fastPow(b,n-1);
    cout<<c.m[1][1];
    return 0;
}