PA06ANT - Ant

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1000000000
#define ooo 1ll << 62
//#define mod 4024
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second

double const PI=4*atan(1);

typedef long long int64;

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int const max_size = 24;
int64 mod;

struct Matrix{
    int64 x[max_size][max_size];
    Matrix(){};
    Matrix(int64 a[max_size][max_size]) { for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++) x[i][j] = a[i][j];}
    friend Matrix operator * (const Matrix &a, const Matrix &b){
        Matrix c;
        for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++){
            c.x[i][j] = 0;
            for(int k = 0; k < max_size; k++) c.x[i][j] = (c.x[i][j] + a.x[i][k] * b.x[k][j]) % mod;
        } 
        return c;
    }
    friend Matrix operator ^ (const Matrix &a, const int &k){
        if(k == 1) return a;
        Matrix c = a ^ (k / 2);
        if(k & 1) return c * c * a;
        else return c * c;
    }
    void print(){
        for(int i = 0; i < max_size; i++){
            for(int j = 0; j < max_size; j++) printf("%lld ",x[i][j]);
            printf("\n");
        }
    }
};

int64  n, x, p; 
vector<pair<int, int> > P;
string s1, s2;

int main(){
    //freopen("input.in","r",stdin); 
    //freopen("output.out","w",stdout);
    
    cin >> s1 >> s2;
    cin >> n >> mod;
    mod *= 2;
    
    for(int i = 1; i <= 4; i++){
        int u = (i + 4 - 2) % 4 + 1;
        P.push_back(make_pair(i, u));
        u = i % 4 + 1;
        P.push_back(make_pair(i, u));
        P.push_back(make_pair(i, i + 4));
    }
    
    for(int i = 4 + 1; i <= 2 * 4; i++){
        int u = (i + 4 - 2) % 4 + 4 + 1;
        P.push_back(make_pair(i, u));
        u = i % 4 + 4 + 1;
        P.push_back(make_pair(i, u));
        P.push_back(make_pair(i, i - 4));        
    }
    
    int64 u[24][24];
    memset(u, 0, sizeof(u));
    for(int i = 0; i < 24; i++) for(int j = 0; j < 24; j++) 
        if(P[i].se == P[j].fi && P[i].fi != P[j].se) u[i][j] = 1;
        
    Matrix I = Matrix(u);
    Matrix A = I ^ n;
    int64 kq = 0;
    for(int i = (s1[0] - 'A') * 3; i < (s1[0] - 'A') * 3 + 3; i++){
        for(int j = (s2[0] - 'A') * 3; j < (s2[0] - 'A') * 3 + 3; j++) kq += A.x[i][j];
    } 
    
    printf("%lld\n",(kq % mod) / 2);
   // getch();
}

Download