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

Download