#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 503;
const int xx[8] = {0, 1, 0, -1, 1, -1, 1, -1};
const int yy[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int M = 1000000009;
const int P = 31;
bool prime(int x)
{
for (int i = 2; i * i <= x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
int sum(const int& a, const int& b)
{
return (a + b) % M;
}
int dif(const int& a, const int& b)
{
return (a - b + M) % M;
}
int pro(const int& a, const int& b)
{
return (a * 1LL * b) % M;
}
int fast(int x, int n)
{
int ans = 1;
while (n)
{
if (n % 2 == 1)
ans = pro(ans, x);
x = pro(x, x);
n /= 2;
}
return ans;
}
ll gcd(ll x, ll y)
{
if (x == 0)
return y;
return gcd(y % x, x);
}
int n, m, k;
char a[N][N];
int h[30][N][N][8];
void solv()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i)
{
scanf(" %s", a[i]);
}
for (int k = 0; k < 30; ++k)
{
int astt;
int nn, mm;
if (k > 0)
{
astt = fast(P, (1 << (k - 1)));
nn = (1 << (k - 1)) % n;
mm = (1 << (k - 1)) % m;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
for (int u = 0; u < 8; ++u)
{
if (k == 0)
{
h[k][i][j][u] = a[i][j] - 'a' + 1;
continue;
}
int i1 = (i + xx[u] * nn);
int j1 = (j + yy[u] * mm);
if (i1 >= n)
i1 -= n;
else if (i1 < 0)
i1 += n;
if (j1 >= m)
j1 -= m;
else if (j1 < 0)
j1 += m;
h[k][i][j][u] = sum(h[k - 1][i][j][u], pro(h[k - 1][i1][j1][u], astt));
}
}
}
}
ll ham = 0;
ll hay = (n * m * 8) * 1LL * (n * m * 8);
vector<int> v;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
for (int u = 0; u < 8; ++u)
{
int i1 = i;
int j1 = j;
int hh = 0;
int q = 0;
for (int b = 0; b < 30; ++b)
{
if ((k & (1 << b)))
{
hh = sum(hh, pro(fast(P, q), h[b][i][j][u]));
q += (1 << b);
i = (i + xx[u] * (1 << b)) % n;
j = (j + yy[u] * (1 << b)) % m;
i = (i + n) % n;
j = (j + m) % m;
}
}
v.push_back(hh);
i = i1;
j = j1;
}
}
}
sort(all(v));
int q = 1;
for (int i = 1; i < v.size(); ++i)
{
if (v[i] == v[i - 1])
++q;
else
{
ham += q * 1LL * q;
q = 1;
}
}
ham += q * 1LL * q;
ll g = gcd(ham, hay);
ham /= g;
hay /= g;
printf("%lld/%lld\n", ham, hay);
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
//ios_base::sync_with_stdio(false), cin.tie(0);
/*int x = 999999900;
while (!prime(x))
{
++x;
}
printf("%d\n", x);*/
solv();
return 0;
}
//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message
osmosmjerka.cpp: In function 'void solv()':
osmosmjerka.cpp:144:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); ++i)
~~^~~~~~~~~~
osmosmjerka.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", a[i]);
~~~~~^~~~~~~~~~~~~
osmosmjerka.cpp:97:41: warning: 'mm' may be used uninitialized in this function [-Wmaybe-uninitialized]
int j1 = (j + yy[u] * mm);
~~~~~~^~~~
osmosmjerka.cpp:96:41: warning: 'nn' may be used uninitialized in this function [-Wmaybe-uninitialized]
int i1 = (i + xx[u] * nn);
~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 4 |
Correct |
8 ms |
3200 KB |
Output is correct |
| 5 |
Correct |
18 ms |
6912 KB |
Output is correct |
| 6 |
Correct |
79 ms |
20600 KB |
Output is correct |
| 7 |
Correct |
978 ms |
83280 KB |
Output is correct |
| 8 |
Correct |
3773 ms |
245376 KB |
Output is correct |
