题目描述
广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。
输入输出格式
输入格式：
输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。
输出格式：
输出包含一行一个整数，即an除以m的余数。
输入输出样例
1 1 1 1 10 7
6
说明
数列第10项是55，除以7的余数为6。
Solution：
本题基本算是一道矩阵加速模板了，直接构造一手矩阵：
\begin{bmatrix} a2& a1\end{bmatrix} 以及中间矩阵 \begin{bmatrix} p & 1 \\ q & 0 \end{bmatrix}
代码：
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define mem(p) memset(&p,0,sizeof(p))
using namespace std;
ll pp,q,a1,a2,n,m;
struct mat{ll a[][],r,c;};
il mat mul(mat x,mat y)
{
mat p;
mem(p);
for(int i=;i<x.r;i++)
for(int j=;j<y.c;j++)
for(int k=;k<x.c;k++)
p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%m;
p.r=x.r,p.c=y.c;
return p;
}
il void fast(ll k)
{
mat p,ans;
mem(p),mem(ans);
p.r=p.c=;
p.a[][]=pp,p.a[][]=,p.a[][]=q;
ans.r=,ans.c=;
ans.a[][]=a2,ans.a[][]=a1;
while(k)
{
if(k&)ans=mul(ans,p);
k>>=;
p=mul(p,p);
}
cout<<ans.a[][];
}
int main()
{
ios::sync_with_stdio();
cin>>pp>>q>>a1>>a2>>n>>m;
if(n==)cout<<a1%m;
else if(n==)cout<<a2%m;
else fast(n-);
return ;
}
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define mem(p) memset(&p,0,sizeof(p))
using namespace std;
ll pp,q,a1,a2,n,m;
struct mat{ll a[3][3],r,c;};
il mat mul(mat x,mat y)
{
mat p;
mem(p);
for(int i=0;i<x.r;i++)
for(int j=0;j<y.c;j++)
for(int k=0;k<x.c;k++)
p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%m;
p.r=x.r,p.c=y.c;
return p;
}
il void fast(ll k)
{
mat p,ans;
mem(p),mem(ans);
p.r=p.c=2;
p.a[0][0]=pp,p.a[0][1]=1,p.a[1][0]=q;
ans.r=1,ans.c=2;
ans.a[0][0]=a2,ans.a[0][1]=a1;
while(k)
{
if(k&1)ans=mul(ans,p);
k>>=1;
p=mul(p,p);
}
cout<<ans.a[0][0];
}
int main()
{
ios::sync_with_stdio(0);
cin>>pp>>q>>a1>>a2>>n>>m;
if(n==1)cout<<a1%m;
else if(n==2)cout<<a2%m;
else fast(n-2);
return 0;
}