Submission #640071

#	Time	Username	Problem	Language	Result	Execution time	Memory
640071		guilhermecpp	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	863 ms	39784 KiB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;

#define NMAX 510
#define NMAX2 250010
#define BASE 137
#define mod 1000000009

typedef long long int ll;

string mat[NMAX];

ll marc[NMAX][NMAX];
	
vector< string > seq;

ll dir_lin[] = {-1, -1, -1, 0, 0, 1, 1, 1};
ll dir_col[] = {-1, 0, 1, -1, 1, -1, 0, 1};

ll pot_base[NMAX2];

void BUILD_POT()
{

	ll i;

	pot_base[0] = 1;

	for(i = 1;i < NMAX2;i++)
	{
	
		pot_base[i] = (BASE * pot_base[i - 1]) % mod;
	
	}
	
	return;

}

ll MDC(ll a, ll b)
{

	if(b == 0)
	{
	
		return a;
	
	}
	
	return MDC(b, a % b);

}

ll MMC(ll a, ll b)
{

	return (a / MDC(a, b)) * b;

}

int main()
{

	BUILD_POT();

	ll n, m, k, q, tam, lin, col, cur, pos, val, a, b, x, i, j;
	
	string aux;
	
	map< ll, ll > freq;
	
	cin >> n >> m >> k;
	
	k = min(k, MMC(n, m));
	
	for(i = 0;i < n;i++)
	{
	
		cin >> mat[i];
	
	}
	
	for(i = 0;i < n;i++)
	{
	
		for(j = 0;j < m;j++)
		{
		
			marc[i][j] = -1;
		
		}
	
	}
	
	for(cur = 0;cur < 8;cur++)
	{
	
		for(i = 0;i < n;i++)
		{
		
			for(j = 0;j < m;j++)
			{
			
				if(marc[i][j] != cur)
				{
				
					aux = "";
				
					lin = i;
					col = j;
				
					while(marc[lin][col] != cur)
					{
					
						marc[lin][col] = cur;
						
						aux.push_back(mat[lin][col]);
					
						lin = (lin + n + dir_lin[cur]) % n;
						col = (col + m + dir_col[cur]) % m;
					
					}
			
					seq.push_back(aux);
					
				}
			
			}
		
		}
		
	}
	
	q = (ll)(seq.size());
	
	a = 0;
	b = 0;
	
	for(i = 0;i < q;i++)
	{
	
		tam = (ll)(seq[i].size());
	
		val = (ll)(seq[i][0] - 'a' + 1);
	
		cur = val;
	
		for(j = 1;j < k;j++)
		{
	
			val = (ll)(seq[i][j % tam] - 'a' + 1);
		
			cur = (BASE * cur + val) % mod;
		
		}
		
		freq[cur]++;
		
		pos = k % tam;
		
		for(j = 1;j < tam;j++)
		{
	
			val = (ll)(seq[i][j - 1] - 'a' + 1);		
		
			cur = (cur + mod - (pot_base[k - 1] * val) % mod) % mod;
	
			val = (ll)(seq[i][pos] - 'a' + 1);
		
			cur = (BASE * cur + val) % mod;
			
			freq[cur]++;
			
			pos = (pos + 1) % tam;
			
		}
	
	}
	
	for(auto atual : freq)
	{
	
		a += atual.second * atual.second;
		b += atual.second;
	
	}
	
	b = b * b;
	
	x = MDC(a, b);
	
	a /= x;
	b /= x;
	
	cout << a << "/" << b << endl;

	return 0;

}

• Subtask 1: 160 / 160