题目传送门

题目

题目描述

广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。
今给定数列的两系数 $p$ 和 $q$，以及数列的最前两项 $a_1$ 和$ a_2$，另给出两个整数 $n$ 和 $m$，试求数列的第 $n$ 项 $a_n \bmod m$。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1 1 1 1 10 7

样例输出 #1

6

提示

数列第 $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$。

题解

要求解广义斐波那契数列，我们需要先从普通斐波那契数列数列讲起

求解斐波那契数列

通常情况下，我们遇到的斐波那契数列是三项递推的形式：

$$F_{i+2}=F_{i+1}+F_{i}$$

当然，你可以递推求解$F_n$，但是如果$n$过大，你就炸了。但是我们可以使用矩阵加速。矩阵是什么？矩阵加速又是什么？详情看这个文章：《矩阵》

设$Fib(n)$表示一个$1\times 2$​的矩阵$\begin{bmatrix} F_{n} & F_{n-1} \end{bmatrix}$，那么我们就需要将它与一个矩阵相乘，得到$Fib(n+1)$，根据矩阵的计算方法，你可以得到这个要乘的矩阵：$\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}$

，你可以计算模拟一下：

$$\begin{aligned}\begin{bmatrix}F_{n+1} & F_{n-1}\end{bmatrix}&=\begin{bmatrix}F_{n} & F_{n-1}\end{bmatrix}\times \begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix} \\& =\begin{bmatrix}F_{n}+F_{n-1} & F_{n}\end{bmatrix}\end{aligned}$$

于是，从$Fib(2)$开始，每次乘上一个相同的矩阵，就可以求解下一个递推项，所以使用矩阵快速幂就能求解$Fib(n)$。

求解广义斐波那契数列

巧妙地转化条件与结论，根据上述规则，我们可以确定下矩阵$\begin{bmatrix}p & 1 \\q & 0\end{bmatrix}$是矩阵快速幂的底数，将上面的公式中的$\begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix}$换成新的式子即可。

代码

代码中$Fib(n)$表示为$\begin{bmatrix}
F_{n-1} & F_{n}
\end{bmatrix}$，与题解内容稍有不同。

Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
ll p,q,A[M],n,m;
struct matrix{
    ll m[101][101],c,r;
    matrix(){
        memset(m,0,sizeof(m));
    }
    void matrix_read(){
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                read(m[i][j]);
        return;
    }
    void matrix_print(){
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                print(m[i][j]);
                space;
            }
            enter;
        }
        return;
    }
}a,ans;
matrix operator *(const matrix &x,const matrix &y){
    matrix c;
    int co=x.c,ro=y.r;
    c.c=co,c.r=ro;
    for(int i=1;i<=ro;i++)
        for(int j=1;j<=co;j++)
            for(int k=1;k<=co;k++)
                c.m[i][j]=(c.m[i][j]+x.m[i][k]*y.m[k][j])%m;
    return c;
}
matrix matrix_pow(matrix x,ll num){
    matrix pow_ans;
    pow_ans.c=pow_ans.r=2;
    memset(pow_ans.m,0,sizeof(pow_ans.m));
    for(int i=1;i<=2;i++)    pow_ans.m[i][i]=1;
    while(num){
        if(num&1)    pow_ans=pow_ans*x;
        x=x*x;
        num>>=1;
    }
    return pow_ans;
}
int main(){
    read(p,q,A[1],A[2],n,m);
    a.m[1][1]=0;
    a.m[1][2]=1;
    a.m[2][1]=q;
    a.m[2][2]=p;
    ans.c=ans.r=a.c=a.r=2;
    ans=matrix_pow(a,n-2);
    print((ans.m[2][1]*A[1]+ans.m[2][2]*A[2])%m);
    return 0;
}