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<iostream>
#include<cstring>
#include<cstdio>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<sstream>
#include<cmath>
using namespace std;

const int BASE = 15625, MAX_LEN = 16;

template<typename T, T MOD> class Mod {
    T n;
    public:
    Mod(const T &n = 0): n(n) {}
    void operator += (const Mod &a) {
        n = (n + a.n) % MOD;
    }
    Mod operator * (const Mod &a) const {
        return n * a.n % MOD;
    }
    Mod operator + (const Mod &a) const {
        return (n + a.n) % MOD;
    }
    T value() const {
        return n;
    }
};

template<class T> class Matrix {
    private:
        vector<vector<T> > a;

    public:
        Matrix(const vector<vector<T> > &a): a(a) {
        }

        Matrix(const int &m, const int &n) {
            a = vector<vector<T> >(m, vector<T>(n, T()));
        }

        Matrix (const int &n) {
            a = vector<vector<T> >(n, vector<T>(n, T()));
            for(int i = 0; i < n; ++i)
                a[i][i] = T(1);
        }

        Matrix operator * (const Matrix &x) const {
            int m = (int) a.size();
            int n = (int) a[0].size();
            int p = (int) x.a[0].size();
            Matrix res (m, p);
            for(int i = 0; i < m; ++i)
                for(int j = 0; j < p; ++j)
                    for(int k = 0; k < n; ++k)
                        res[i][j] += a[i][k] * x.a[k][j];
            return res;
        }

        Matrix operator ^ (long long n) const {
            Matrix res (a.size());
            Matrix a (*this);
            for(; n != 0; n >>= 1) {
                if((n & 1) == 1) res = res * a;
                a = a * a;
            }
            return res;
        }

        vector<T>& operator [] (const int &x) {
            return a[x];
        }
};

const int a[6][6] = {{1, 2, 1, 1, 1, 1},
                    {1, 2, 1, 1, 1, 1},
                    {1, 2, 1, 1, 1, 1},
                    {0, 1, 0, 0, 0, 0},
                    {1, 0, 1, 0, 0, 0},
                    {0, 1, 0, 0, 0, 0}};
const int start[6] = {1, 4, 1, 1, 1, 1};

typedef Mod<long long, 1000000000> Int;

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    if(n == 1) cout << "0\n";
    else if(n == 2) cout << "1\n";
    else {
        vector<vector<Int> > t;
        t.clear();
        for(int i = 0; i < 6; ++i) {
            t.push_back(vector<Int>());
            for(int j = 0; j < 6; ++j)
                t[i].push_back(Int(a[i][j]));
        }
        Matrix<Int> b (t);
        t.assign(1, vector<Int>(start, start+6));
        Matrix<Int> start (t);
        start = start * (b ^ (n-3));
        cout << (start[0][0] + start[0][1] + start[0][2] + (start[0][3] * Int(2))).value() << "\n";
    }
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <utility>
#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 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 III pair<int, II>
#define X first
#define Y second
#define VI vector<int>
#define cnt(i) __builtin_popcount(i)
const int d[] = {-1, 0, 1};
const int MOD = 1000000000;
using namespace std;
vector<III> a[8][3][3];
int n;
int F[6], id[8][3][3];

struct matrix {long long mat[6][6];} base;
matrix operator * (matrix a, matrix b) {
    matrix c;
    FOR(i, 0, 6) FOR(j, 0, 6) {
        c.mat[i][j] = 0;
        FOR(k, 0, 6)
            c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
    }
    return c;
}
matrix POW(matrix a, int p) {
    if (p == 1) return a;
    matrix x = POW(a, p >> 1);
    x = x * x;
    if (p & 1) x = x * a;
    return x;
}

bool valid(int x, int y)
    {return x >= 0 && y >= 0 && x < 3 && y < 3;}
bool ok(int p1, int p2, int n1, int n2)
    {return n1 != n2 && (p1 < p2 ? n1 < n2 : n2 < n1);}
bool adj(int p, int newp)
    {return abs(p - newp) < 2;}
int bit0(int p)
    {FOR(i, 0, 3) if ((p & (1 << i)) == 0) return i;}

void InitMasks() {
    FOR(i, 0, 8) FOR(p1, 0, 3) FOR(p2, p1 + 1, 3) {
        if (cnt(i) == 1 || p1 == p2) continue;
        if ((i & (1 << p1)) && (i & (1 << p2))) {
            FOR(t1, 0, 3) FOR(t2, 0, 3) {
                int newp1 = p1 + d[t1];
                int newp2 = p2 + d[t2];
                if (valid(newp1, newp2) && ok(p1, p2, newp1, newp2)) {
                    int newMask = (1 << newp1) + (1 << newp2);
                    int pos = bit0(i);
                    if (cnt(i) == 2) {
                        if (pos == newp1 || pos == newp2) continue;
                        if (adj(newp1, pos) && adj(pos, bit0(newMask)))
                            a[7][bit0(newMask)][p2].PB(MP(i, MP(p1, p2)));
                        if (adj(newp2, pos) && adj(pos, bit0(newMask)))
                            a[7][p1][bit0(newMask)].PB(MP(i, MP(p1, p2)));
                    }
                    else {
                        a[newMask][newp1][newp2].PB(MP(i, MP(p1, p2)));
                        pos = bit0(newMask);
                        if (adj(pos, newp1)) a[7][pos][newp2].PB(MP(i, MP(p1, p2)));
                        if (adj(pos, newp2)) a[7][newp1][pos].PB(MP(i, MP(p1, p2)));
                    }
                }
            }
        }
    }
}

void InitMatrix() {
    int dim = 0;
    FOR(i, 0, 8) FOR(p1, 0, 3) FOR(p2, 0, 3)
        if (SZ(a[i][p1][p2])) id[i][p1][p2] = dim++;
    #define con a[i][p1][p2]
    FOR(i, 0, 8) FOR(p1, 0, 3) FOR(p2, 0, 3)
    FOR(j, 0, SZ(con)) base.mat[id[i][p1][p2]][id[con[j].X][con[j].Y.X][con[j].Y.Y]]++;
}

int main() {
    cin >> n;
    if (n == 3) {cout << 8; return 0;}
    InitMasks();
    InitMatrix();
    base = POW(base, n - 3);
    FOR(i, 0, 6) F[i] = 1; F[id[7][0][2]] = 4;
    long long tmp[6]; FOR(i, 0, 6) tmp[i] = 0;
    FOR(i, 0, 6) FOR(j, 0, 6) tmp[i] = (tmp[i] + base.mat[i][j] * F[j]) % MOD;
    long long res = tmp[id[5][0][2]] * 2 + tmp[id[7][0][1]] + tmp[id[7][1][2]] + tmp[id[7][0][2]];
    cout << res % MOD;
    return 0;
}

Code mẫu của RR

//Written by RR
type
  matrix        =       array[1..3,1..3] of int64;
const
  base          =       1000000000;
  one           :       matrix=( (0,0,1) , (0,0,2) , (2,1,4) );

operator * (a,b:matrix) c:matrix;
    var
      i,j,k:longint;
    begin
      fillchar(c,sizeof(c),0);
      for i:=1 to 3 do
      for j:=1 to 3 do
        for k:=1 to 3 do
          c[i,j]:=((a[i,k]*b[k,j]) mod base+c[i,j]) mod base;
    end;
procedure lt(n:longint; var kq:matrix);
    var
      mid:matrix;
    begin
      if n=1 then
        begin
          kq:=one;
          exit;
        end;
      lt(n>>1,mid);
      kq:=mid*mid;
      if n and 1=1 then kq:=kq*one;
    end;

var
  n             :       longint;
  a             :       matrix;

procedure solve;
    var
      t1,t2,t3:int64;
    begin
      lt(n-2,a);
      t1:=a[1,2]*2+a[1,3]*1;
      t3:=a[3,2]*2+a[3,3]*1;
      writeln( (2*t1+t3) mod base);
    end;

begin
  read(n);
  solve;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#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<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111
#define modunlo 1000000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

map<long long,long long> M;

long long xuly(long long n){
      if(M[n]>0) return M[n];
      if(n==3) return M[3] = 192;
      if(n==1) return M[1] = 8;
      if(n==2) return M[2] = 40;
      if(n%2==0){
            long long u = xuly(n/2);
            long long v = xuly(n/2-1);
            return M[n] = (u*u/2+2*v*v)%modunlo;
      }
      else{
            long long u = xuly((n+1)/2);
            long long v = xuly((n+1)/2-1);
            long long r = xuly((n+1)/2-2);
            return M[n] = (u*v/2+2*v*r)%modunlo;
      }
}

int main(){
      long long n;
      scanf("%lld",&n);
      if(n<=1) printf("0");
      else if(n==2) printf("1");
      else printf("%lld",xuly(n-2));
}

Code mẫu của skyvn97

#include<cstdio>
typedef long long ll;
const ll mod=(ll)1e9;
const ll mat[][6]={{1,1,2,1,1,1},
                   {1,1,2,1,1,1},
                   {1,1,2,1,1,1},
                   {0,0,1,0,0,0},
                   {0,0,1,0,0,0},
                   {1,1,0,0,0,0}};
struct matrix {
    int m,n;
    ll d[7][7];
    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;
            }
        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;
matrix fst,mul;
void process(void) {
    scanf("%d",&n);
    if (n==1) {
        printf("0");
        return;
    }
    if (n==2) {
        printf("1");
        return;
    }
    fst.m=1;
    fst.n=6;
    fst.d[0][0]=1;
    fst.d[0][1]=1;
    fst.d[0][2]=4;
    fst.d[0][3]=1;
    fst.d[0][4]=1;
    fst.d[0][5]=1;
    mul.m=6;
    mul.n=6;
    int i,j;
    for (i=0;i<mul.m;i=i+01)
        for (j=0;j<mul.n;j=j+1)
            mul.d[i][j]=mat[i][j];
    if (n>3) fst=fst*(mul^(n-3));
    printf("%lld",(fst.d[0][0]+fst.d[0][1]+fst.d[0][2]+fst.d[0][5]*2)%mod);
}
int main(void) {
    process();
    return 0;
}