Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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

long long base;

struct matrix
{
    long long a[6][6];

    void load(int x)
    {
        x%=base;
        a[0][0]=a[1][2]=a[2][0]=a[2][1]=a[4][5]=1;
        a[3][3]=a[5][4]=base-1;
        a[3][0]=-4LL*x;
        while (a[3][0]<0) a[3][0]+=base;
        a[3][1]=a[3][0];
        a[1][0]=a[1][1]=4LL*x*x%base;
        a[1][3]=a[4][4]=2LL*x%base;
    }

    void multiply(matrix x,matrix y)
    {
        memset(a,0,sizeof(a));
        for (int i=0;i<6;i++)
            for (int j=0;j<6;j++)
                for (int k=0;k<6;k++) a[i][j]=(a[i][j]+x.a[i][k]*y.a[k][j])%base;
    }
};

matrix m[33],u;
long long ans[6];

void multi(long long a[],matrix m)
{
    long long b[6]={0};
    for (int j=0;j<6;j++)
        for (int i=0;i<6;i++)
            b[j]=(b[j]+a[i]*m.a[i][j])%base;
    for (int i=0;i<6;i++) a[i]=b[i];
};

int main()
{
    int test,x,n,i;
    cin >> test;
    while (test--)
    {
        cin >> x >> n >> base;
        if (base==1)
        {
            puts("0"); continue;
        }
        n-=2;
        m[0].load(x);
        for (i=1;1<<i<=n;i++) m[i].multiply(m[i-1],m[i-1]);
        ans[1]=1LL*x*x%base; ans[0]=ans[1]+1;
        ans[3]=ans[4]=x%base; ans[2]=ans[5]=1;
        while (n)
        {
            --i;
            if (1<<i<=n) n-=1<<i,   multi(ans,m[i]);
        }
        cout << ans[0] << endl;
    }
}

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>

const long long base[4][4] = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};

int n, mod;
long long a[4][4];

struct Matrix {
    long long a[4][4];

    Matrix() {
        for(int i = 0; i < 4; ++i)
            for(int j = 0; j < 4; ++j)
                a[i][j] = 0;
    }

    Matrix(const long long a[4][4]) {
        for(int i = 0; i < 4; ++i)
            for(int j = 0; j < 4; ++j)
                this->a[i][j] = a[i][j];
    }

    void operator *= (const Matrix &mat) {
        Matrix res;
        for(int i = 0; i < 4; ++i)
            for(int j = 0; j < 4; ++j)
                for(int k = 0; k < 4; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * mat.a[k][j]) % mod;
        *this = res;
    }

    Matrix operator ^ (const int &n) {
        Matrix res = Matrix(base), now = *this;
        for(int i = n; i != 0; i >>= 1) {
            if(i & 1) res *= now;
            now *= now;
        }
        return res;
    }
};

int main() {
    int tc; scanf("%d", &tc);
    while(tc--) {
        int a2; scanf("%d%d%d", &a2, &n, &mod);
        memset(a, 0, sizeof a);
        a[0][0] = a[1][2] = a[2][0] = a[2][1] = 1;
        a[2][2] = 4LL * a2 * a2 % mod; a[2][3] = 2LL * a2 % mod;
        a[3][2] = -4LL * a2 % mod; a[3][3] = -1;
        Matrix res = Matrix(a) ^ (n-1);
        printf("%lld\n", (((res.a[0][0] + res.a[1][0] + res.a[2][0] * a2 % mod * a2 % mod + res.a[3][0] * a2) % mod) + mod) % mod);
    }
    return 0;
}

Code mẫu của ladpro98

program FBRICK;
uses    math;
const   fi = '';
        fo = '';
type    arr = array[1..6,1..6] of int64;
var     s, c: arr;
        Q:array[1..6] of int64;
        n, m , k, res, kk: int64;
        t, tt, i: longint;
        inp, oup:text;

operator *(a,b: arr) c: arr;
var     i,j,k:longint;
begin
        for i:=1 to 6 do
        for j:=1 to 6 do begin
                C[i,j] := 0;
                for k:=1 to 6 do begin
                        C[i,j] := (C[i,j] + a[i,k]*b[k,j]) mod M;
                end;
                if c[i,j] < 0 then inc(c[i,j], m);
        end;
end;

function Pow(p: longint):  arr;
var     t: arr;
begin
        if p = 1 then exit(S);
        t := Pow(p shr 1);
        t := t * t;
        if odd(p) then exit(t * S);
        exit(t);
end;

begin
        assign(inp,fi);reset(inp);
        assign(oup,fo);rewrite(oup);
        readln(inp,t);
        for tt:=1 to t do begin
                readln(inp,kk,n,m);
                k := 2*kk mod m;
                Q[1] := 1; Q[2] := kk*kk mod m; Q[3] := 1;
                Q[4] := kk; Q[5] := kk; Q[6] := 1;
                S[1,1] := 1; S[1,2] := 1; S[2,2] := k*k mod m;
                S[2,3] := 1; S[2,4] := -2*k; S[3,2] := 1;
                S[4,2] := k; S[4,4] := -1; S[5,5] := k;
                S[5,6] := -1; S[6,5] := 1;
                C := Pow(n-1);
                res := 0;
                for i:=1 to 6 do begin
                        res := (res + Q[i] * C[1,i]) mod M;
                        //if res < 0 then inc(res, m);
                end;
                writeln(oup,res);
        end;
        close(oup);
end.

Code mẫu của RR

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define FOR(i,a,b) for(i=(a); i<=(b); i++)
#define REP(i,a) for(i=0; i<(a); i++)
#define ll long long

int base, a, n;

int m[2][16], p[32][16];

int INP,AM;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (feof(stdin)) memset(BUF, 0, sizeof BUF); else fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}

int main() {
//    freopen("tow1.in", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int ntest; GN(ntest);
    int need, i, j, u, v, k, b1, b2, c2, s2, cur, t;
    while (ntest--) {
        GN(a); GN(n); GN(base);
        b1 = 1, b2 = (a * (ll)a) % base;
        c2 = a, s2 = (b1 + b2) % base;
        p[0][0] = p[0][5] = p[0][10] = p[0][15] = 1;

        p[1][1] = 1;
        p[1][4] = 1; p[1][5] = ((4 * (ll) a) % base * a) % base; p[1][6] = base - (4 * (ll) a) % base;
        p[1][9] = (2*a) % base; p[1][10] = (base - 1);
        p[1][12] = 1; p[1][13] = ((4 * (ll) a) % base * a) % base; p[1][14] = base - (4 * (ll) a) % base; p[1][15] = 1;

        need = n-2;
        REP(i,16) m[0][i] = p[0][i];
        cur = 0, t = 0;
        while ((1<<t) < need) t++;
        t++;
        FOR(i,1,t) {
            if (i >= 2) {
                REP(k,16) {
                    p[i][k] = 0;
                    for(u = k - (k&3), v = (k&3); v < 16; u++, v+=4) {
                        p[i][k] += (p[i-1][u] * (ll)p[i-1][v]) % base;
                        if (p[i][k] >= base) p[i][k] -= base;
                    }
                }
            }
            if ((need >> (i-1)) & 1) {
                REP(k,16) {
                    m[1-cur][k] = 0;
                    for(u = k - (k&3), v = (k&3); v < 16; u++, v+=4) {
                        m[1-cur][k] += (m[cur][u] * (ll)p[i][v]) % base;
                        if (m[1-cur][k] >= base) m[1-cur][k] -= base;
                    }
                }
                cur = 1 - cur;
            }
        }
        int res = ((m[cur][12] * (ll) b1
                      + m[cur][13] * (ll) b2) % base
                      + (m[cur][14] * (ll) c2
                      + m[cur][15] * (ll) s2) % base) % base;
        printf("%d\n", (int) res);
    }
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
//#define mod 1000000009
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
const int max_size = 4;
ll mod;

struct Matrix{
    ll x[max_size][max_size];
    Matrix(){};
    Matrix(int d){
        MS(x, 0);
        rep(i, max_size) x[i][i] = d;
    };
    Matrix(ll const a[max_size][max_size]) { for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++) x[i][j] = a[i][j];}
    friend Matrix operator * (const Matrix &a, const Matrix &b){
        Matrix c;
        for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++){
            c.x[i][j] = 0;
            for(int k = 0; k < max_size; k++) c.x[i][j] = (c.x[i][j] + a.x[i][k] * b.x[k][j]) % mod;
        } 
        return c;
    }

    friend Matrix operator ^ (const Matrix &a,const int &k){
        Matrix base;
        rep(i, max_size) rep(j, max_size) base.x[i][j] = a.x[i][j];
        Matrix res = Matrix(1);
        int p = k;
        while (p > 0) {
            if (p & 1) {
                res = res * base;
            }
            p >>= 1;
            base = base * base;
        }
        return res;
    }

    void print(){
        for(int i = 0; i < max_size; i++){
            for(int j = 0; j < max_size; j++) printf("%lld ",x[i][j]);
            printf("\n");
        }
    }
};

int test;
ll x, k, n, m, a[5], f[5];

int main(){
    //freopen("input.in","r",stdin); 
    //freopen("output.out","w",stdout);
    cin >> test;
    while(test --){
        cin >> x >> n >> mod;
        x %= mod;
        a[1] = 1 % mod; f[1] = a[1];
        a[2] = x ; f[2] = (a[1] * a[1] + a[2] * a[2]) %mod;
        for(int i = 3; i <= 4; i++) {
            a[i] =( 2 * x * a[i - 1] - a[i - 2]) % mod;
            f[i] = (f[i - 1] + a[i] * a[i]) % mod;
        }
        if(n < 5) cout<<f[n]<<endl;

        else {
            k = (4 * x * x - 1) % mod;
            ll u[4][4] = { (k + 1) % mod , 1, 0, 0,
                              mod - ((2 * k) % mod), 0, 1, 0,
                              (k + 1) % mod, 0, 0, 1,
                             mod - 1, 0, 0, 0};
            Matrix A = Matrix(u);
            A = A ^ (n - 4);
            long long kq = 0;
            for(int i = 0; i < 4; i++) kq = (kq + f[4 - i] * A.x[i][0]) % mod;
            cout << kq << endl;
        } 
    }
   // getch();
}

Code mẫu của skyvn97

#include<cstdio>
typedef long long ll;
struct matrix {
    int m,n;
    ll d[10][10];
};
int n;
ll a2;
ll mod;
matrix fst,mul;
matrix multi(const matrix &a,const matrix &b) {
    int i,j,k;
    int x=a.m;
    int y=a.n;
    int z=b.n;
    matrix c;
    c.m=x;c.n=z;
    for (i=0;i<x;i=i+1)
        for (j=0;j<z;j=j+1) {
            c.d[i][j]=0;
            for (k=0;k<y;k=k+1)
                c.d[i][j]=(c.d[i][j]+a.d[i][k]*b.d[k][j])%mod;
        }
    return (c);
}
matrix multiply(const matrix &a,const int &k) {
    if (k==1) return (a);
    matrix r=multiply(a,k/2);
    r=multi(r,r);
    if (k%2==1) r=multi(r,a);
    return (r);
}
void process(void) {
    scanf("%lld",&a2);
    scanf("%d",&n);
    scanf("%lld",&mod);
    if (mod==1) {
        printf("0\n");
        return;
    }
    mul.m=4;
    mul.n=4;
    mul.d[0][0]=1;
    mul.d[0][1]=0;
    mul.d[0][2]=0;
    mul.d[0][3]=0;
    mul.d[1][0]=(4*a2*a2)%mod;
    mul.d[1][1]=(4*a2*a2)%mod;
    mul.d[1][2]=1;
    mul.d[1][3]=(2*a2)%mod;
    mul.d[2][0]=1;
    mul.d[2][1]=1;
    mul.d[2][2]=0;
    mul.d[2][3]=0;
    mul.d[3][0]=(-4*a2)%mod+mod;
    mul.d[3][1]=(-4*a2)%mod+mod;
    mul.d[3][2]=0;
    mul.d[3][3]=mod-1;
    fst.m=1;
    fst.n=4;
    fst.d[0][0]=(1+a2*a2)%mod;
    fst.d[0][1]=(a2*a2)%mod;
    fst.d[0][2]=1;
    fst.d[0][3]=a2%mod;
    if (n>2) fst=multi(fst,multiply(mul,n-2));
    if (fst.d[0][0]<0) fst.d[0][0]+=mod;
    printf("%lld\n",fst.d[0][0]);
}
int main(void) {
    int t,c;
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) process();
    return 0;
}