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;
}