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<numeric>
using namespace std;

const int MOD = 2012, N = 10;
typedef vector<vector<int> > Matrix; 
int adj[2*N][3], n, s, f, p;

Matrix getMatrix() {
    Matrix res (6*n, vector<int>(6*n, 0));
    for(int i = 0; i < 2*n; ++i)
        for(int j = 0; j < 3; ++j) {
            int prev1 = adj[i][j];
            for(int k = 0; k < 3; ++k) {
                int prev2 = adj[prev1][k];
                if(prev2 != i) res[3*prev1+k][3*i+j] = 1;
            }
        }
    return res;
}

Matrix base() {
    Matrix res(6*n, vector<int>(6*n, 0));
    for(int i = 0; i < 6*n; ++i) res[i][i] = 1;
    return res;
}

Matrix matrixMul(const Matrix &a, const Matrix &b) {
    int m = (int) a.size();
    int n = (int) a.front().size();
    int p = (int) b.front().size();
    Matrix res (m, vector<int>(n, 0));
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < p; ++j)
            for(int k = 0; k < n; ++k)
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD;
    return res;
}

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

void initAdj() {
    for(int i = 0; i < n; ++i) {
        adj[i][0] = (i+1)%n;
        adj[i][1] = (i-1+n)%n;
        adj[i][2] = i+n;
    }
    for(int i = n; i < 2*n; ++i) {
        adj[i][0] = n + (i-1+n)%n;
        adj[i][1] = n + (i+1)%n;
        adj[i][2] = i-n;
    }
}

int main() {
    scanf("%d%d%d", &n, &f, &p); s = 0; --f;
    initAdj();
    Matrix first (1, vector<int>(6*n, 0));
    for(int i = 0; i < 3; ++i) {
        int next = adj[s][i], p = 0;
        while(adj[next][p] != s) ++p;
        first[0][3*next+p] = 1;
    }
    Matrix res = matrixMul(first, matrixPow(getMatrix(), p-1));
    printf("%d\n", accumulate(res.front().begin() + 3*f, res.front().begin() + 3*(f+1), 0) % MOD);
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;

const int N = 21;
const int MOD = 2012;

int n;

void add(int &a, int b) {
  a += b % MOD;
  if (a >= MOD) a -= MOD;
}

typedef vector<int> Array;
typedef vector<Array> Matrix;
#define nRow(a) (int(a.size()))
#define nCol(a) (int(a[0].size()))
#define newMatrix(m, n, v) Matrix(m, Array(n, v))

Matrix operator * (const Matrix &a, const Matrix &b) {
  Matrix c = newMatrix(nRow(a), nCol(b), 0);
  FOR(i, 0, nRow(c)) FOR(j, 0, nCol(c))
  FOR(k, 0, nCol(a)) add(c[i][j], a[i][k] * b[k][j]);
  return c;
}

Matrix unitMatrix(int n) {
  Matrix result = newMatrix(n, n, 0);
  FOR(i, 0, n) result[i][i] = 1;
  return result;
}

Matrix power(Matrix a, int p) {
  Matrix result = unitMatrix(nRow(a));
  while (p > 0) {
    if (p & 1) result = result * a;
    a = a * a;
    p >>= 1;
  }
  return result;
}

#define next(i) ((i + 1) % n)
#define prev(i) ((i + n - 1) % n)

vector<int> adj[N];

void addEdge(vector<int> up, vector<int> down) {
  FOR(i, 0, n) {
    adj[up[i]].push_back(up[prev(i)]);
    adj[up[i]].push_back(up[next(i)]);
    adj[up[i]].push_back(down[i]);
  }
}

Matrix a;

void initialize() {
  vector<int> up, down;
  FOR(i, 0, n) up.push_back(i);
  FOR(i, n, n + n) down.push_back(i);
  addEdge(up, down); addEdge(down, up);
  int nState = (n + n) * 4;
  a = newMatrix(nState, nState, 0);
  #define index(u, i) (u * 4 + i)
  FOR(u, 0, n + n) FOR(i, 0, 4) {
    FOR(j, 0, 3)
    if (i != j) {
      int v = adj[u][j], vi = 0;
      FOR(k, 0, 3)
      if (adj[v][k] == u) {
        vi = k; break;
      }
      a[index(u, i)][index(v, vi)] = 1;
    }
  }
}

int main() {
  int x, p;
  cin >> n >> x >> p;
  --x;
  initialize();
  a = power(a, p);
  int ans = 0;
  FOR(i, 0, 3)
    add(ans, a[index(0, 3)][index(x, i)]);
  cout << ans << endl;
  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;

bool ke[66][66];
int id[66][66];
int ku[66], kv[66];
int n, x, p;

struct Matrix {
    int x[66][66];

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

void refine(int &x, int l, int r) {
    if (x > r) x = l;
    if (x < l) x = r;
}

void init() {
    FOR(i,1,n) {
        int next = i + 1; refine(next, 1, n);
        int prev = i - 1; refine(prev, 1, n);

        ke[i][next] = ke[i][prev] = true;
        ke[i][i+n] = ke[i+n][i] = true;
    }

    FOR(i,n+1,n+n) {
        int next = i + 1; refine(next, n+1, n+n);
        int prev = i - 1; refine(prev, n+1, n+n);

        ke[i][next] = ke[i][prev] = true;
    }

    int nId = 0;
    FOR(i,1,n+n) FOR(j,1,n+n)
    if (ke[i][j]) {
        id[i][j] = ++nId;
        ku[nId] = i;
        kv[nId] = j;
    }
    int cnt = 0;
    FOR(i,1,n+n) FOR(j,1,n+n) if (ke[i][j] && i != j) {
        FOR(k,1,n+n) if (ke[j][k] && k != i) {
            A.x[id[i][j]][id[j][k]] = 1;
            ++cnt;
        }
    }
    FOR(i,1,6*n) I.x[i][i] = 1;
}

Matrix operator * (const Matrix &a, const Matrix &b) {
    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] + a.x[i][k] * b.x[k][j]) % 2012;
    }
    return res;
}

void solve() {
    --p;
    if (p == 0) {
        if (ke[1][x]) puts("1");
        else puts("0");
        return ;
    }
    P = I;
    n = 6*n;
    REP(bit,32) {
        if (p & (1LL<<bit)) {
            P = P * A;
        }
        A = A * A;
    }

    int res = 0;

    FOR(row,1,n) FOR(col,1,n)
    if (kv[col] == x && ku[row] == 1) {
        res = (res + P.x[row][col]) % 2012;
    }

    cout << res << endl;
}

int main() {
    cin >> n >> x >> p;
    init();
    solve();
    return 0;
}

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 1000000000
#define ooo 1ll << 62
#define mod 4024
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second

double const PI=4*atan(1);

typedef long long int64;

using namespace std;

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

int max_size;

struct Matrix{
    int64 x[62][62];
    Matrix(){};
    Matrix(int64 a[62][62]) { 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){
        if(k == 1) return a;
        Matrix c = a ^ (k / 2);
        if(k & 1) return c * c * a;
        else return c * c;
    }
    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");
        }
    }
};

int64  n, x, p; 
vector<pair<int, int> > P;
vector<int> V[11];

int main(){
   // freopen("input.in","r",stdin); 
  //  freopen("output.out","w",stdout);

    int run = 0;
    cin >> n >> x >> p;
    max_size = n * 6;

    for(int i = 1; i <= n; i++){
        int u = (i + n - 2) % n + 1;
        P.push_back(make_pair(i, u));
        u = i % n + 1;
        P.push_back(make_pair(i, u));
        P.push_back(make_pair(i, i + n));
    }

    for(int i = n + 1; i <= 2 * n; i++){
        int u = (i + n - 2) % n + n + 1;
        P.push_back(make_pair(i, u));
        u = i % n + n + 1;
        P.push_back(make_pair(i, u));
        P.push_back(make_pair(i, i - n));        
    }

    int64 u[62][62];
    memset(u, 0, sizeof(u));
    for(int i = 0; i < n * 6; i++) for(int j = 0; j < n * 6; j++) 
        if(P[i].se == P[j].fi && P[i].fi != P[j].se) u[i][j] = 1;
    Matrix I = Matrix(u);
    Matrix A = I ^ p;
    int64 kq = 0;
    for(int i = 0; i < 3; i++){
        for(int j = x * 3 - 3; j < x * 3; j++) kq += A.x[i][j];
    } 

    printf("%lld\n",(kq % mod) / 2);
   // getch();
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   111
#define MOD   2012
using namespace std;
typedef pair<int,int> ii;
struct matrix {
    int m,n;
    int d[MAX][MAX];
    matrix(){}
    matrix operator * (const matrix &a) {
        int i,j,k;
        int x=m;
        int y=n;
        int z=a.n;
        matrix res;
        res.m=x;res.n=z;
        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,f,p;
vector<ii> v;
matrix fst,mul;
void process(void) {
    scanf("%d",&n);
    scanf("%d",&f);
    scanf("%d",&p);
    v.clear();
    int i,j,s;
    for (i=0;i<2*n;i=i+1) {
        v.push_back(ii(i,(i+1+n)%n+n*(i>=n)));
        v.push_back(ii(i,(i-1+n)%n+n*(i>=n)));
        v.push_back(ii(i,(i+n)%(2*n)));
    }   
    mul.m=v.size();
    mul.n=v.size();
    for (i=0;i<v.size();i=i+1)
        for (j=0;j<v.size();j=j+1)
            mul.d[i][j]=((v[j].first==v[i].second) && (v[j].second!=v[i].first));
    fst.m=1;
    fst.n=v.size();
    for (i=0;i<v.size();i=i+1)
        fst.d[0][i]=(v[i].first==0);
    if (p>1) fst=fst*(mul^(p-1));
    s=0;
    for (i=0;i<v.size();i=i+1) s=(s+fst.d[0][i]*(v[i].second==f-1))%MOD;
    printf("%d",s);
}
int main(void) {
    process();
    return 0;
}