HDU 4565 So Easy!

矩阵快速幂

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

long long a,b,n,m;
int R,C;
struct Matrix
{
    long long A[5][5];
    Matrix operator*(Matrix b);
};

Matrix Matrix::operator*(Matrix b)
{
    Matrix c;
    int i,j,k;
    memset(c.A,0,sizeof(c.A));
    for(i=1; i<=R; i++)
        for(j=1; j<=C; j++)
            for(k=1; k<=2; k++)
                c.A[i][j]=(c.A[i][j]+(A[i][k]*b.A[k][j])%m)%m;
    return c;
}

int main()
{
    while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&m))
    {
        Matrix JZ;
        JZ.A[1][1]=(2*a)%m;
        JZ.A[1][2]=(b%m-(a*a)%m+m)%m;
        JZ.A[2][1]=1;
        JZ.A[2][2]=0;
        long long B=n-2;
        Matrix c;
        c.A[1][1]=1;
        c.A[1][2]=0;
        c.A[2][1]=0;
        c.A[2][2]=1;
        R=2,C=2;
        while(B>0)
        {
            if(B%2==1) c=c*JZ,B--;
            else JZ=JZ*JZ,B=B/2;
        }
        R=1,C=2;
        Matrix CS;
        CS.A[1][1]=(((((a*a)%m+b)%m)%m)*2)%m;
        CS.A[2][1]=(2*a)%m;

        if(n==1) printf("%d
",CS.A[2][1]);
        else if(n==2) printf("%d
",CS.A[1][1]);
        else
        {
            CS=c*CS;
            printf("%d
",CS.A[1][1]);
        }
    }
    return 0;
}