https://www.luogu.com.cn/problem/P1349
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p,q,a1,a2,n,m;
struct jz{
int a[5][5];
}x;
jz operator *(jz a,jz b){
jz res={};
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
int sum=0;
for(int k=1;k<=2;k++){
sum+=a.a[i][k]%m*b.a[k][j]%m;
sum%=m;
}
res.a[i][j]=sum%m;
res.a[i][j]%=m;
}
}
return res;
}
jz ksm(jz a,int n){
jz res={};
res.a[1][1]=a2;
res.a[1][2]=a1;
res.a[2][2]=1;
while(n){
if(n%2==1) res=res*a;
a=a*a;
n/=2;
}
return res;
}
signed main(){
memset(&x,0,sizeof(x));
cin>>p>>q>>a1>>a2>>n>>m;
if(n==1) cout<<a1%m;
if(n==2) cout<<a2%m;
if(n<=2) return 0;
x.a[1][1]=p;
x.a[1][2]=q;
x.a[2][1]=1;
x=ksm(x,n-2);
cout<<x.a[1][1]%m;
return 0;
}
\color{red}{WA40}
在线等