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;
}