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 happyboy99x

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long Long;
typedef vector<Long> Row;
typedef vector<Row> Matrix;

const Long MOD = 1000000007;

template<class T> int size(const T &a) {
    return (int) a.size();
}

void add(Long &x, const Long &y, const Long &MOD) {
    x = (x + y) % MOD;
}

void mul(Long &x, const Long &y, const Long &MOD) {
    x = x * y % MOD;
}

Matrix matrixMul(const Matrix &a, const Matrix &b, const Long &MOD) {
    const int m = size(a);
    const int n = size(a[0]);
    const int p = size(b[0]);
    Matrix res (m, Row(p, 0));
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < p; ++j)
            for(int k = 0; k < n; ++k)
                add(res[i][j], a[i][k] * b[k][j], MOD);
    return res;
}

Matrix base(const int &n) {
    Matrix res(n, Row(n, 0));
    for(int i = 0; i < n; ++i)
        res[i][i] = 1;
    return res;
}

Matrix getMatrix(const int &n) {
    Matrix res(n, Row(n, 0));
    for(int i = 0; i < n; ++i) res[0][i] = 1;
    for(int i = 1; i < n; ++i) res[i][i-1] = 1;
    return res;
}

Matrix matrixPow(Matrix a, int n, const Long &MOD) {
    Matrix res (base(size(a)));
    for(; n != 0; n >>= 1) {
        if((n & 1) == 1) res = matrixMul(res, a, MOD);
        a = matrixMul(a, a, MOD);
    }
    return res;
}

Long numberPow(Long a, int n, const Long &MOD) {
    Long res = 1;
    for(; n != 0; n >>= 1) {
        if((n & 1) == 1) mul(res, a, MOD);
        mul(a, a, MOD);
    }
    return res;
}

const int K = 50;
int a[K], n, k;

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < k; ++i)
        scanf("%d", &a[i]);
    Matrix expo = matrixMul(Matrix(1, Row(k, 1)), matrixPow(getMatrix(k), n-k-1, MOD-1), MOD-1);
    reverse(expo[0].begin(), expo[0].end());
    Long res = 1;
    for(int i = 0; i < k; ++i)
        mul(res, numberPow(a[i], expo[0][i], MOD), MOD);
    printf("%lld\n", res);
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int P = 1000000007;
const int P1 = P - 1;
const int K = 55;
struct matrix {
    long long mat[K][K];
};

using namespace std;
matrix a;
int n, k, p, res;
int c[K];

matrix MulMat(matrix a, matrix b) {
    matrix c; int i, j, t;
    for(i=1; i<=k; i++)
    for(j=1; j<=k; j++) {
        c.mat[i][j] = 0;
        for(t=1; t<=k; t++)
            c.mat[i][j] = (c.mat[i][j] + a.mat[i][t] * b.mat[t][j]) % P1;
    }
    return c;
}

matrix PowMat(int power) {
    if (power == 1) return a;
    matrix c = PowMat(power >> 1);
    c = MulMat(c, c);
    if (power & 1) c = MulMat(c, a);
    return c;
}

int POW(int x, int p) {
    if (p == 0) return 1;
    long long t = POW(x, p / 2);
    t = t * t % P;
    if (p & 1) t = t * x % P;
    return t;
}

int main()
{
    scanf("%d %d\n", &n, &k);
    int i;
    for(i=1; i<=k; i++) scanf("%d", &c[i]);
    for(i=1; i<=k; i++) a.mat[1][i] = 1;
    for(i=2; i<=k; i++) a.mat[i][i-1] = 1;
    a = PowMat(n - k); res = 1;
    for(i=1; i<=k; i++) {
        p = a.mat[1][i];
        res = (long long)res * POW(c[k-i+1], p) % P;
    }
    cout << res;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>

#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;

const long long MOD = 1000000007LL;

int n, t, a[55];

struct Matrix {
    long long x[55][55];

    Matrix operator * (Matrix a) const {
        Matrix res;
        FOR(i,1,n) FOR(j,1,n) {
            res.x[i][j] = 0;
            FOR(k,1,n) {
                res.x[i][j] = (res.x[i][j] + x[i][k] * a.x[k][j]) % (MOD-1);
            }
        }
        return res;
    }

    void print() {
        FOR(i,1,n) {
            FOR(j,1,n) cout << x[i][j] << ' ';
            cout << endl;
        }
        cout << endl;
    }
} I, A, P;

void init() {
    memset(I.x, 0, sizeof I.x);
    memset(A.x, 0, sizeof A.x);

    FOR(i,1,n) I.x[i][i] = 1;
    FOR(i,1,n-1) A.x[i][i+1] = 1;
    FOR(i,1,n) A.x[n][i] = 1;
}

Matrix lt(int t) {
    P = I;
    REP(i,30) {
        if (t & (1<<i)) {
            P = P * A;
            // P.print();
        }
        A = A * A;
    }
    return P;
}

long long power(long long x, long long k) {
    if (k == 0) return 1 % MOD;
    if (k == 1) return x % MOD;
    long long mid = power(x, k >> 1);
    mid = (mid * mid) % MOD;
    if (k & 1) return mid * x % MOD;
    else return mid;
}

int main() {
    scanf("%d%d", &t, &n);
    FOR(i,1,n) scanf("%d", &a[i]);
    init();
    P = lt(t-n);

    long long res = 1;
    FOR(i,1,n) {
        res = res * power(a[i], P.x[n][i]) % MOD;
    }
    cout << res << endl;
}

Code mẫu của skyvn97

#include<cstdio>
#define MAX   55
typedef long long ll;
const ll mod=1e9+7;
struct matrix {
    int m,n;
    ll d[MAX][MAX];
    matrix(){}  
    matrix operator * (const matrix &a) {
        matrix res;
        int x=m;
        int y=n;
        int z=a.n;
        res.m=x;
        res.n=z;
        int i,j,k;
        for (i=0;i<x;i=i+1)
            for (j=0;j<z;j=j+1) {
                res.d[i][j]=0;
                for (k=0;k<y;k=k+1)
                    res.d[i][j]=(res.d[i][j]+d[i][k]*a.d[k][j])%(mod-1);
            }
        return (res);
    }
    matrix operator ^ (const int &k) {
        if (k==1) return (*this);
        matrix r=(*this)^(k/2);
        r=r*r;
        if (k%2==1) r=r*(*this);
        return (r);
    }
};
int n,k;
ll a[MAX];
ll res;
matrix fst,mul;
ll power(const ll &a,const ll &k) { 
    if (k==0) return (1);
    if (k==1) return (a%mod);
    ll r=power(a,k/2);
    r=(r*r)%mod;
    if (k%2==1) r=(r*a)%mod;
    return (r);
}
void process(void) {
    scanf("%d",&n);
    scanf("%d",&k);     
    int i,j;
    mul.m=k;
    mul.n=k;
    fst.m=1;
    fst.n=k;
    for (i=0;i<k;i=i+1) {
        for (j=0;j<k-1;j=j+1) mul.d[i][j]=0;
        mul.d[i][k-1]=1;
        if (i>0) mul.d[i][i-1]=1;
    }           
    mul=mul^(n-k);  
    res=1;
    for (i=1;i<=k;i=i+1) {
        scanf("%lld",&a[i]);
        for (j=0;j<k;j=j+1) {
            if (j==i-1) fst.d[0][j]=1;
            else fst.d[0][j]=0;
        }           
        fst=fst*mul;
        res=(res*power(a[i],fst.d[0][k-1]))%mod;
    }
    printf("%lld",res);
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    process();
    return 0;
}