20分求助AC#3#11

#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod;
int a[2][3];
int p,q;
int a1,a2;
int base[3][3];
int ans[3][3];
int temp[3][3];
int n;
void jzc(int A[][3],int B[][3],int n){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            temp[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                temp[i][j]=(temp[i][j]+(A[i][k]*B[k][j])%mod)%mod;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            A[i][j]=temp[i][j]%mod;
        }
    }
}
void ksm(int A[][3],int n,int x){
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++){
        ans[i][i]=1;
    }
    while(x){
        if(x&1){
            jzc(ans,A,n);
        }
        x>>=1;
        jzc(A,A,n);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            A[i][j]=ans[i][j]%mod;
        }
    }
}
signed main(){
    cin>>p>>q>>a1>>a2>>n>>mod;
    if(n==1){
        cout<<a1%mod<<endl;
        return 0;
    }
    if(n==2){
        cout<<a2%mod<<endl;
        return 0;
    }
    a[1][1]=a2%mod;
    a[2][1]=a1%mod;
    base[1][1]=p%mod;
    base[1][2]=q%mod;
    base[2][1]=1;
    base[2][2]=0;
    ksm(base,2,n-2);
    jzc(a,base,2);
    cout<<a[1][1]%mod;
    return 0;
}