Участник:Andriygav/PA06ANT

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
#include <iostream>
using namespace std;
 
int p;
 
struct matrix{
	int x, y;
	long long a[30][30];
};
 
matrix operator * (matrix a, matrix b){
	matrix c {a.x, b.y};
	for(int i = 1; i <= c.x; i++){
		for(int j = 1; j <= c.y; j++){
			c.a[i][j] = 0;
		}
	}
	for(int i = 1; i <= c.x; i++){
		for(int j = 1; j <= c.y; j++){
			for(int k = 1; k <= a.y; k++){
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % p) % p;
			}
		}
	}
	return c;
}
 
matrix power(matrix a, int x){
	if(x == 1){
		return a;
	}
	matrix b = power(a, x/2);
	return x%2 ? b*b*a : b*b;
}
 
 
int adj[9][3] = {
	0,0,0, 2,4,5, 1,3,6,
	2,4,7, 1,3,8, 1,6,8,
	2,5,7, 3,6,8, 4,5,7
};
 
int main() {
	int s, t, k;
	char c1, c2;
	cin >> c1 >> c2;
	s = c1 - 'A' + 1;
	t = c2 - 'A' + 1;
	cin >> k >> p;
 
	int row[9][9];
	pair<int, int>  info[30];
	for(int u = 1; u <= 8; u++){
		for(int i = 0; i <= 2; i++){
			int v = adj[u][i];
			row[0][0]++;
			row[u][v] = row[0][0];
			info[row[0][0]] = {u, v};
		}
	}
 
	long long  F[9][9][3];
	for(int i = 0; i <= 2; i++){
		int v = adj[s][i];
		F[s][v][1] = 1;
	}
 
	if(k == 1){
		cout << F[s][t][1] << endl;
		return 0;
	}
 
	matrix A, B;
	A.x = 24;
	A.y = 1;
	for(int i = 1; i <= A.x; i++){
		A.a[i][1] = F[info[i].first][info[i].second][1];
	}
 
	B.x = B.y = 24;
 
	for(int i = 1; i <= B.x; i++){
		for(int j = 0; j <= 2; j++){
			if(adj[info[i].first][j] != info[i].second){
				B.a[i][row[adj[info[i].first][j]][info[i].first]] = 1;
			}
		}
	}
 
	A = power(B, k-1) * A;
 
	long long ans = 0;
	for(int i = 0; i <= 2; i++){
		ans = (ans + A.a[row[adj[t][i]][t]][1]) % p;
	}
	cout << ans << endl;
 
	return 0;
}