L
u
o
g
u
l
i
n
k
Luogu~link
Luogu link
分析:
显然矩乘
普通斐波那契 转移矩阵:
∣
1
,
1
∣
∣
1
,
0
∣
|1,1|\\ |1,0|
∣1,1∣∣1,0∣
那么只需要把系数加上:
∣
p
,
1
∣
∣
q
,
0
∣
|p,1|\\ |q,0|
∣p,1∣∣q,0∣
以及递推矩阵改为
[
a
2
,
a
1
]
[a_2,a_1]
[a2,a1]即可
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,Mod,a1,a2,p,q;
struct Matrix{
ll G[4][4];
}ans,base;
Matrix operator *(Matrix A,Matrix B)
{
Matrix res;
memset(res.G,0,sizeof res.G);
for(int k=1;k<=2;k++)
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
(res.G[i][j]+=(A.G[i][k]%Mod)*(B.G[k][j]%Mod))%=Mod;
return res;
}
void mul(ll k)
{
while(k)
{
if(k&1) ans=ans*base;
base=base*base;
k>>=1;
}
}
int main(){
scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&a1,&a2,&n,&Mod);
ans.G[1][1]=a2; ans.G[1][2]=a1;
base.G[1][1]=p; base.G[1][2]=1;
base.G[2][1]=q;
mul(n-2);
printf("%lld",ans.G[1][1]%Mod);
return 0;
}