PA06ANT - Ant
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
using namespace std;
#define MAX 24
bool b[300][300];
int id[300][300];
int nid;
void edge(int u, int v) {
b[u][v] = b[v][u] = true;
}
char v1, v2;
int k, p;
long long a[MAX][MAX], c[MAX][MAX], d[MAX][MAX];
long long F[1][MAX];
void mul(long long a[][MAX], long long b[][MAX], long long c[][MAX], int n) {
for(int i=0;i<n;++i) {
for(int j=0;j<MAX;++j) {
c[i][j] = 0;
for(int k=0;k<MAX;++k) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % p;
}
}
}
}
void pow(long long a[][MAX], long long b[][MAX], int sm) {
if(sm == 1) {
for(int i=0;i<MAX;++i)
for(int j=0;j<MAX;++j)
b[i][j] = a[i][j];
return;
}
else {
long long tmp[MAX][MAX];
if(sm % 2 == 0) {
pow( a, tmp, sm / 2);
mul( tmp, tmp, b, MAX);
}
else {
pow( a, b, sm / 2);
mul( b, b, tmp, MAX);
mul( tmp, a, b, MAX);
}
}
}
int main() {
cin >> v1 >> v2;
cin >> k >> p;
edge('A','E');edge('A','D');edge('D','H');edge('E','H');edge('D','C');edge('A','B');edge('F','E');edge('G','H');edge('B','C');edge('B','F');edge('C','G');edge('F','G');
for(int i='A';i<='H';++i) for(int j='A';j<='H';++j) {
if(b[i][j]) {
id[i][j] = nid++;
}
}
for(int i='A';i<='H';++i)
for(int j='A';j<='H';++j) if(b[i][j]) {
for(int k='A';k<='H';++k) if(k!=i && b[j][k]) {
a[id[i][j]][id[j][k]] = 1;
}
}
for(int i='A';i<='H';++i)
if(b[v1][i]) {
// cout << v1 << " " << i << endl;
F[0][id[v1][i]] = 1;
}
long long result = 0;
if(k > 1) {
pow( a, c, k - 1);
mul( F, c, d, 1);
for(int i='A';i<='H';++i)
if(b[i][v2])
result = (result + d[0][id[i][v2]]) % p;
}
else {
for(int i='A';i<='H';++i) if(b[i][v2]) {
result = (result + F[0][id[i][v2]]) % p;
}
}
cout << result << endl;
return 0;
}