#include <bits/stdc++.h>
using namespace std;
#define NMAX 510
#define NMAX2 2510
#define BASE 137
#define mod 1000000009
typedef long long int ll;
typedef unsigned long long int ull;
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;
}
ull MDC(ull a, ull b)
{
if(b == 0)
{
return a;
}
return MDC(b, a % b);
}
int main()
{
BUILD_POT();
ll n, m, k, q, tam, lin, col, pos, i, j;
ull a, b, x, cur, val;
string aux;
unordered_map< ll, ll > freq;
cin >> n >> m >> k;
k = min(k, 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;
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:100:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'ull' {aka 'long long unsigned int'} [-Wsign-compare]
100 | if(marc[i][j] != cur)
| ~~~~~~~~~~~^~~~~~
osmosmjerka.cpp:108:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'ull' {aka 'long long unsigned int'} [-Wsign-compare]
108 | while(marc[lin][col] != cur)
| ~~~~~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
4 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
26 ms |
3136 KB |
Output isn't correct |
| 7 |
Incorrect |
536 ms |
21244 KB |
Output isn't correct |
| 8 |
Execution timed out |
4072 ms |
32036 KB |
Time limit exceeded |
