Luogu 1349 广义斐波那契数列（递推，矩阵，快速幂）
Description
广义的斐波那契数列是指形如\[A_n=p*a_{n-1}+q*a_{n-2}\]的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。
输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。
Output
输出包含一行一个整数，即an除以m的余数。
1 1 1 1 10 7
Sample Output
6
Http
Luogu:https://www.luogu.org/problem/show?pid=1349
Source
递推，矩阵，快速幂
解决思路
如果熟悉了普通斐波那契数列这道题（如果不知道的话请点击链接，里面还有矩阵的相关知识），那么对于广义的斐波那契数列我们不难想到递推矩阵:\[T=\begin{bmatrix} p & 1 \\ q & 0 \end{bmatrix}\] 所以递推方程就是\[A_i=A_{i-1}*T=\begin{bmatrix} f_{i-1} & f_{i-2}\\ 0 & 0 \end{bmatrix}*\begin{bmatrix} p & 1 \\ q & 0 \end{bmatrix}=\begin{bmatrix} f_i=f_{i-1}*p+f_{i-2}*q & f_{i-1} \\ 0 & 0 \end{bmatrix}\]
代码
#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;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7182441.html
相关资源：JAVA上百实例源码以及开源项目
