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 <bits/stdc++.h>
using namespace std;

int modulo;

vector<vector<int> > multiply(const vector<vector<int> > &a, const vector<vector<int> > &b) {
    vector<vector<int> > c (a.size(), vector<int>(b[0].size()));
    for (int i = 0; i < (int) a.size(); ++i) {
        for (int j = 0; j < (int) a[0].size(); ++j) {
            for (int k = 0; k < (int) b[0].size(); ++k) {
                c[i][k] = (c[i][k] + a[i][j] * b[j][k]) % modulo;
            }
        }
    }
    return c;
}

vector<vector<int> > unit(int n) {
    vector<vector<int> > a (n, vector<int>(n));
    for (int i = 0; i < n; ++i) a[i][i] = 1;
    return a;
}

vector<vector<int> > power(vector<vector<int> > a, long long n) {
    vector<vector<int> > result = unit(a.size());
    while (n > 0) {
        if (n % 2 != 0) result = multiply(result, a);
        a = multiply(a, a);
        n /= 2;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    long long n; cin >> n >> modulo;
    vector<vector<int> > first (3, vector<int>(1));
    first[2][0] = 1;
    vector<vector<int> > base (3, vector<int>(3));
    base[0][1] = base[1][2] = base[2][0] = base[2][1] = base[2][2] = 1;
    cout << multiply(power(base, n), first)[2][0] << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define FORD(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

using namespace std;

struct matrix { long long a[3][3]; };

int MOD;
long long n;
matrix base;

matrix operator * (matrix a, matrix b) {
  matrix c;
  FOR(i, 0, 3) FOR(j, 0, 3) {
    c.a[i][j] = 0;
    FOR(k, 0, 3)
      c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD;
  }
  return c;
}

matrix power(long long p) {
  if (p == 1) return base;
  matrix x = power(p >> 1);
  x = x * x;
  if (p & 1) return x * base;
  return x;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("DHLOCO.in", "r", stdin);
  #endif // _LAD_
  cin >> n >> MOD;
  base.a[0][0] = base.a[0][1] = base.a[0][2] = base.a[1][0] = base.a[2][1] = 1;
  long long f[4];
  f[1] = 1; f[2] = 2; f[3] = 4;
  if (n <= 3) {
    cout << f[n] % MOD << endl;
  } else {
    matrix M = power(n - 3);
    cout << (f[3] * M.a[0][0] + f[2] * M.a[0][1] + f[1] * M.a[0][2]) % MOD << endl;
  }
  return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
const int sta[]={1,1,2,4};
const int tmp[][3]={{0,0,1},{1,0,1},{0,1,1}};
int mod;
struct Matrix {
    int m,n;
    vector<vector<int> > d;
    Matrix() {
        m=n=0;
        d.clear();
    }
    Matrix(int m,int n) {
        this->m=m;
        this->n=n;
        d.assign(m,vector<int>(n,0));
    }
    Matrix operator * (const Matrix &a) const {
        int x=m;
        int y=n;
        int z=a.n;
        Matrix res(x,z);
        REP(i,x) REP(j,y) REP(k,z) res.d[i][k]=(res.d[i][k]+d[i][j]*a.d[j][k])%mod;
        return (res);
    }
    Matrix operator ^ (long long k) const {
        Matrix res(n,n);
        Matrix mul=*this;
        REP(i,n) REP(j,n) res.d[i][j]=i==j;
        while (k>0) {
            if (k&1) res=res*mul;
            mul=mul*mul;
            k>>=1;
        }
        return (res);
    }
};
void process(void) {
    long long n;
    cin>>n>>mod;
    Matrix fst(1,3),mul(3,3);
    REP(i,3) fst.d[0][i]=sta[i];
    REP(i,3) REP(j,3) mul.d[i][j]=tmp[i][j];
    fst=fst*(mul^n);
    cout<<fst.d[0][0]<<endl;
}
int main(void) {
    ios::sync_with_stdio(true);
    process();
    return 0;
}