长乐 DAY13

今天是矩阵快速幂和质数约数专场（简称数学专场），第二题没发现规律所以没A，贴代码过了

#include
using namespace std;
long long a,b,c,aa,bb,cc,k[4][4],kk[4][4],n,mod,ans;
int main()
{
    freopen("fib.in","r",stdin);
    freopen("fib.out","w",stdout);
    k[1][1]=k[1][3]=0,k[1][2]=k[2][1]=k[2][2]=k[2][3]=1;
    scanf("%lld%lld%lld%lld",&a,&b,&mod,&n);
    c=2*sqrt(3+a*b);
    k[3][1]=0,k[3][2]=2,k[3][3]=1;
    n--;
    while(n)
    {
        if(n%2==1)
        {
            aa=a*k[1][1]%mod+b*k[1][2]%mod+c*k[1][3]%mod;
            bb=a*k[2][1]%mod+b*k[2][2]%mod+c*k[2][3]%mod;
            cc=a*k[3][1]%mod+b*k[3][2]%mod+c*k[3][3]%mod;
            a=aa,b=bb,c=cc;
        }
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
            {
                kk[i][j]=0;
                for(int t=1;t<=3;t++) kk[i][j]=(kk[i][j]+k[i][t]*k[t][j]%mod)%mod;
            }
        k[1][1]=kk[1][1];
        k[1][2]=kk[1][2];
        k[1][3]=kk[1][3];
        k[2][1]=kk[2][1];
        k[2][2]=kk[2][2];
        k[2][3]=kk[2][3];
        k[3][1]=kk[3][1];
        k[3][2]=kk[3][2];
        k[3][3]=kk[3][3];
        n/=2;
    }
    printf("%lld",b%mod);
    return 0;
}