#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2260 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2260 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2388 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2516 KB |
Output is correct |
| 6 |
Correct |
42 ms |
5512 KB |
Output is correct |
| 7 |
Correct |
643 ms |
22876 KB |
Output is correct |
| 8 |
Correct |
863 ms |
39784 KB |
Output is correct |
