PA06ANT - Ant

Tác giả: ladpro98

Ngôn ngữ: C++

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

using namespace std;

int MOD, n, from, to;

void add(long long &a, long long b) {
  a = (a + b) % MOD;
}

//* Matrix Exponentiation

typedef vector<long long> 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;
}

//*

vector<int> adj[8];

#define next(i) ((i + 1) % 4)
#define prev(i) ((i + 3) % 4)

void addEdge(vector<int> Front, vector<int> Back) {
  FOR(i, 0, 4) {
    adj[Front[i]].push_back(Front[prev(i)]);
    adj[Front[i]].push_back(Front[next(i)]);
    adj[Front[i]].push_back(Back[i]);
  }
}

#define index(u, i) ((u) * 4 + i)

Matrix a;

void initialize() {
  vector<int> Front, Back;
  FOR(i, 0, 4) Front.push_back(i);
  FOR(i, 4, 8) Back.push_back(i);
  addEdge(Front, Back);
  addEdge(Back, Front);
  a = newMatrix(8 * 4, 8 * 4, 0);
  FOR(u, 0, 8) FOR(i, 0, 4) {
    //* i = 3 means from nowhere
    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() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("PA06ANT.in", "r", stdin);
  #endif // _LAD_
  initialize();
  char f, t;
  cin >> f >> t >> n >> MOD;
  from = f - 'A'; to = t - 'A';
  a = power(a, n);
  long long ans = 0;
  FOR(i, 0, 3)
    add(ans, a[index(from, 3)][index(to, i)]);
  cout << ans << endl;
  return 0;
}

Download