PA06ANT - Ant
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#include<numeric>
using namespace std;
typedef long long Long;
typedef vector<vector<Long> > Matrix;
const int adj[8][3] = {{1, 3, 4}, {0, 2, 5}, {1, 3, 6}, {0, 2, 7}, {0, 5, 7}, {1, 4, 6}, {2, 5, 7}, {3, 4, 6}};
int MOD;
Matrix getMatrix() {
Matrix res (24, vector<Long>(24, 0));
for(int i = 0; i < 8; ++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(24, vector<Long>(24, 0));
for(int i = 0; i < 24; ++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<Long>(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 print(const Matrix &v) {
for(int i = 0; i < (int) v.size(); ++i) {
for(int j = 0; j < (int) v[i].size(); ++j)
printf("%lld ", v[i][j]);
printf("\n");
}
}
int main() {
int k; char a, b;
scanf(" %c %c %d %d", &a, &b, &k, &MOD);
int s = a - 'A', f = b - 'A';
Matrix first (1, vector<Long>(24, 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(), k-1));
printf("%lld\n", accumulate(res.front().begin() + 3*f, res.front().begin() + 3*(f+1), 0LL) % MOD);
return 0;
}