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

Download